前端 | 前端常见算法题(数组篇).png
一、和问题
2020.09.21
No.1 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=1 lang=javascript
*
* [1] 两数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let p1 = 0;
while(p1<nums.length) {
let p2 = nums.length - 1;
while(p2>0) {
if(nums[p1] + nums[p2] == target && p1 != p2) {
return [p1,p2];
}
p2--;
}
p1++;
}
};
方案二：
/*
* @lc app=leetcode.cn id=1 lang=javascript
*
* [1] 两数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let i = nums.length;
while(i > 1) {
let last = nums.pop();
if (nums.indexOf(target - last) > -1) {
return [nums.indexOf(target - last), nums.length]
}
I--
}
};
方案三：
/*
* @lc app=leetcode.cn id=1 lang=javascript
*
* [1] 两数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map()
for (let i = 0; i < nums.length; i ++) {
const otherIndex = map.get(target - nums[I])
if (otherIndex !== undefined) return [otherIndex, I]
map.set(nums[i], i)
}
};
求两数和的常规思路是逐个相加求和，获取和是否满足条件，方案一：爆解；方案二：可以利用栈型结构对存取进行优化；方案三：构造一个hash表对存取进行优化
2020.09.22
No.15 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=15 lang=javascript
*
* [15] 三数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let r = [];
// 从小到大排序
nums.sort((a,b) => a-b);
if(nums[0] > 0 || nums[nums.length-1] < 0 || nums.length < 3) {
return [];
} else {
for(let i=0;i<nums.length;i++) {
let pos = nums[I],
left = i + 1,
right = nums.length - 1;
// 过滤到当前项和前一项相同的循环
if(pos == nums[i-1] && i>0) continue;
while(left < right) {
let a = nums[left],
b = nums[right];
if(pos + a + b == 0) {
r.push([pos,a,b]);
// 跳过中间重复的元素
while(left < right && nums[left]==a) left++;
while(left < right && nums[right]==b) right--;
} else if(pos + a + b < 0) {
left++;
} else {
right--;
}
}
}
return r;
}
};
方案二：
/*
* @lc app=leetcode.cn id=15 lang=javascript
*
* [15] 三数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let arr = []
if(nums == null || nums.length < 3) return arr;
nums.sort((a, b) => a - b)
for(var i =0; i<nums.length-2; i++){
const hashMap = new Map()
if(nums[i] > 0) break;
// 去重处理
if(i > 0 && nums[i] == nums[i-1]) continue
for(var j =i+1; j<nums.length; j++){
const dif = -(nums[i]+nums[j])
// 去重处理
// 因为hashMap是首次记录第二次才会push到数组，所以需要判断只有三次重复才能continue
if(j>i+2 && nums[j]==nums[j-1] && nums[j]==nums[j-2])
continue
if(hashMap.has(dif)){
arr.push([nums[i],nums[hashMap.get(dif)],nums[j]])
hashMap.delete(dif)
}
hashMap.set(nums[j],j)
}
}
return arr
};
本题有两种思路：1、借鉴快排思路，固定pivot，利用左右指针遍历；2、传统的转成hash表的形式，优化效率，是两数之和的扩展
2020.09.23
No.16 最接近的三数字之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=16 lang=javascript
*
* [16] 最接近的三数之和
*/
const { lexicographicSortSchema } = require("graphql");
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
// 从小到大排序
nums.sort((a,b) => a-b);
if(nums.length>=3) {
let pivot = 0,
sum = 0,
// r = [],
r = nums[0] + nums[1] + nums[2];
for(;pivot<nums.length-2;pivot++) {
let left = pivot + 1,
right = nums.length - 1;
while(left < right) {
sum = nums[pivot] + nums[left] + nums[right];
// 可以收到一个对象数组里，后续进行排序
// r.push({
// value: sum,
// gap: Math.abs(sum-target)
// })
if(Math.abs(sum-target)<Math.abs(r-target)) r = sum;
if(sum == target){
return sum;
} else if (sum < target) {
left++;
} else if (sum > target) {
right--;
}
}
}
// return r.sort((a,b) => a.gap-b.gap)[0].value;
return r;
}
};
仍然是快排的延展应用，是三数之和的变形
2020.09.24
No.18 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=18 lang=javascript
*
* [18] 四数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
// 排序
nums.sort((a,b) => a-b);
let r = [];
for(let i = 0; i < nums.length-3;i++ ) {
// 除去重复情况
if(i>0 && nums[i-1] == nums[i]) continue;
for(let j = i+1; j< nums.length - 2; j++ ) {
// 除去重复情况
if(j>i+1 && nums[j-1] == nums[j]) continue;
let left = j + 1,
right = nums.length - 1;
while(left < right) {
let a = nums[left],
b = nums[right];
if (a+b+nums[i]+nums[j] < target) {
left++;
} else if (a+b+nums[i]+nums[j] > target) {
right--;
} else {
r.push([ nums[i], nums[j], nums[left], nums[right] ]);
while(left < right && nums[left] == a) {
left++
};
while(left < right && nums[right] == b) {
right--;
};
}
};
}
}
return r;
};
方案二：
/*
* @lc app=leetcode.cn id=18 lang=javascript
*
* [18] 四数之和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
let len = nums.length;
if (len < 4) return [];
let ans = [];
for (let i = 0; i < len - 2; i++) {
for (let j = i + 1; j < len - 1; j++) {
let map = {};
for (let x = j + 1; x < len; x++) {
let key = target - nums[i] - nums[j] - nums[x];
if (map[nums[x]]) {
let temp = [nums[x], ...map[nums[x]]].sort((a, b) => a - b)
if (removeDup(ans, temp)) {
ans.push(temp);
}
} else {
map[key] = [nums[i], nums[j], nums[x]]
}
}
}
}
return ans;
}
三数之和的加强版，多了一层循环
2020.09.25
No.39 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=39 lang=javascript
*
* [39] 组合总和
*/
// @lc code=start
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
// 对数组排序
candidates.sort((a,b) => a-b);
// 简化无效元素
candidates.splice(targetIdx(candidates,target));
let r = [];
// 递归
function targetDfs(temp ,sum) {
// 剪枝
if(sum > target) {
return;
} else if (sum == target) {
r.push(temp.concat())
}
for(let i= 0;i<candidates.length;i++) {
// 最后一位锚点
const p = temp[temp.length-1] || 0;
// 如果比最后一位小则仍在这一层树中遍历，如果比最后一位大，则需要向下一层查找，知道终止回溯
if(candidates[i] >= p) {
temp.push(candidates[I]);
targetDfs(temp, sum + candidates[I]);
temp.pop()
}
}r
}
targetDfs([],0);
return r;
function targetIdx(candidates, target) {
let index = 0;
for(let i=0;i<candidates.length;i++) {
if(candidates[i] > target) {
return I;
} else {
index = I;
}
}
return index + 1;
}
};
思路比较一致，回溯，dfs深度优先遍历查找，需要在合适位置剪枝，用数组来实现树的结构
2020.09.27
No.40 组合总和-ii
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=40 lang=javascript
*
* [40] 组合总和 II
*/
// @lc code=start
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
// 对数组从小到大排序
candidates.sort((a,b) => a-b);
// 简化数组
candidates.splice(targetIdx(candidates, target));
console.log(candidates);
let r = [];
function targetDfs(start,temp,sum) {
if(sum > target) {
return;
} else if(sum == target) {
r.push(temp.concat());
}
for(let i = start;i<candidates.length;i++) {
if(candidates[i] == candidates[i-1] && i-1>=start) continue;
temp.push(candidates[I]);
targetDfs(i+1,temp,sum+candidates[I]);
temp.pop();
}
};
targetDfs(0, [], 0);
return r;
function targetIdx(candidates, target) {
let index = 0;
for(let i=0; i< candidates.length; i++) {
if(candidates[i] > target) {
return I;
} else {
index = I;
}
}
return index+1;
}
};
方案二：
/*
* @lc app=leetcode.cn id=40 lang=javascript
*
* [40] 组合总和 II
*/
// @lc code=start
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function (candidates, target) {
var dp = []
//先排序解决顺序问题 例 （1，2）（2，1）
candidates.sort((a, b) => a - b)
for (let i = 0; i <= target; i++) {
dp[i] = new Set()
}
dp[0].add('')
for (let c of candidates) {
for (let i = target; i >= c; i--) {
for (item of dp[i - c]) {
//使用Set去重, 子项要转化成 String
dp[i].add(item + ',' + c)
}
}
}
//最后把Set 转成 Array
return Array.from(dp[target]).map(item => item.slice(1).split(','))
};
思路一和之前比较类似，这里需要有一个先前的位置记录，不能重复递归同一元素；思路二是利用动态规划
2020.09.28
No.53 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=53 lang=javascript
*
* [53] 最大子序和
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let max = nums[0],
cache = 0;
for(let i=0; i< nums.length; i++) {
cache = Math.max(cache+nums[i],nums[I]);
max = Math.max(cache,max);
}
return max;
};
方案二：
/*
* @lc app=leetcode.cn id=53 lang=javascript
*
* [53] 最大子序和
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
function Status(l, r, m, i) {
this.lSum = l;
this.rSum = r;
this.mSum = m;
this.iSum = I;
}
const pushUp = (l, r) => {
const iSum = l.iSum + r.iSum;
const lSum = Math.max(l.lSum, l.iSum + r.lSum);
const rSum = Math.max(r.rSum, r.iSum + l.rSum);
const mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
return new Status(lSum, rSum, mSum, iSum);
}
const getInfo = (a, l, r) => {
if (l === r) {
return new Status(a[l], a[l], a[l], a[l]);
}
const m = (l + r) >> 1;
const lSub = getInfo(a, l, m);
const rSub = getInfo(a, m + 1, r);
return pushUp(lSub, rSub);
}
var maxSubArray = function(nums) {
return getInfo(nums, 0, nums.length - 1).mSum;
};
思路一利用动态规划，关键在于找到递推公式，即循环不变式，本题为f(n)=max{f(n-1)+ai,ai}；思路二是利用分治，把数组分成两段，每一段只要最大就是最大，当分到最后一个后进行回退，最后的和就是最大值
2020.09.29
No.64 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=64 lang=javascript
*
* [64] 最小路径和
*/
// @lc code=start
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (i == 0 && j == 0) {
// 入口不做处理
grid[i][j] = grid[i][j];
} else if (i == 0 && j > 0) {
// 第一行元素
grid[i][j] += grid[i][j - 1];
} else if (i > 0 && j === 0) {
// 第一列元素
grid[i][j] += grid[i - 1][j];
} else {
// 递推公式 grid[i][j] = min{grid[i][j-1], grid[i-1][j]}
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
}
return grid[grid.length - 1][grid[0].length - 1];
};
经典动态规划，递推的循环不变式为 grid[i][j] = min{ grid[i][j-1], grid[i-1][j] }，边界的细节处理需要注意
2020.09.30
No.167 两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=167 lang=javascript
*
* [167] 两数之和 II - 输入有序数组
*/
// @lc code=start
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let p1 = 0,
p2 = numbers.length -1;
while(p1<p2) {
if(numbers[p1]+numbers[p2]<target) {
p1++;
} else if(numbers[p1]+numbers[p2]>target) {
p2--;
} else {
return [p1+1,p2+1]
}
}
};
方案二：
/*
* @lc app=leetcode.cn id=167 lang=javascript
*
* [167] 两数之和 II - 输入有序数组
*/
// @lc code=start
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let map = {}
for(let i = 0; i < numbers.length; i ++) {
const dim = target - numbers[I]
if(map[dim] === undefined) {
map[numbers[i]] = I
}else {
return [map[dim] + 1,i + 1]
}
}
};
方案三：
/*
* @lc app=leetcode.cn id=167 lang=javascript
*
* [167] 两数之和 II - 输入有序数组
*/
// @lc code=start
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function (numbers, target) {
let len = numbers.length,
left = 0,
right = len - 1,
mid = 0
for (let i = 0; i < len; ++i) {
left = i + 1
while (left <= right) {
mid = parseInt((right - left) / 2) + left
if (numbers[mid] == target - numbers[i]) {
return [i + 1, mid + 1]
} else if (numbers[mid] > target - numbers[i]) {
right = mid - 1
} else {
left = mid + 1
}
}
}
return [-1, -1]
}
三种解法：1、双指针向中间聚拢；2、构造一个map数据结构；3、二分查找
2020.10.01
No.216 组合总合 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=216 lang=javascript
*
* [216] 组合总和 III
*/
// @lc code=start
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
let r = [];
function sumDfs(start, temp, sum) {
if(temp.length == k) {
if(sum == n) {
r.push(temp.concat());
};
return;
}
for(let i=start;i<=9;i++) {
temp.push(i);
sumDfs(i+1,temp,sum+i);
temp.pop();
}
};
sumDfs(1, [], 0);
return r;
};
方案二：
/*
* @lc app=leetcode.cn id=216 lang=javascript
*
* [216] 组合总和 III
*/
// @lc code=start
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
let temp = [];
const ans = [];
const check = (mask, k, n) => {
temp = [];
for (let i = 0; i < 9; ++i) {
if ((1 << i) & mask) {
temp.push(i + 1);
}
}
return temp.length === k && temp.reduce((previous, value) => previous + value, 0) === n;
}
for (let mask = 0; mask < (1 << 9); ++mask) {
if (check(mask, k, n)) {
ans.push(temp);
}
}
return ans;
};
方案三：
/*
* @lc app=leetcode.cn id=216 lang=javascript
*
* [216] 组合总和 III
*/
// @lc code=start
/**
* @param {number} k
* @param {number} n
* @return {number[][]}
*/
var combinationSum3 = function(k, n) {
let number = [[]];
let a = []
let numbers = [1,2,3,4,5,6,7,8,9];
for(let i = 0; i < 9; i++){
let turn = number.map(v => [...v,numbers[I]])
// console.log(turn)
number = number.concat(turn);
}
for(let i = 0; i < number.length; i++){
if(number[i].length != k){
continue;
}else{
if(sum(number[i])!==n){
continue;
}else{
a.push(number[I])
}
}
}
return a;
};
function sum(arr){
let sum = 0;
for(let i = 0; i < arr.length; i++){
sum+=arr[i];
}
return sum;
}
三种解法：1、经典回溯算法，构造dfs查询；2、骚操作，利用二进制掩码进行移位枚举；3、构造一个map数据结构
2020.10.04
No.689 三个无重叠子数组的最大和
给定数组 nums 由正整数组成，找到三个互不重叠的子数组的最大和。
每个子数组的长度为k，我们要使这3*k个项的和最大化。
返回每个区间起始索引的列表（索引从 0 开始）。如果有多个结果，返回字典序最小的一个。
示例:
输入: [1,2,1,2,6,7,5,1], 2
输出: [0, 3, 5]
解释: 子数组 [1, 2], [2, 6], [7, 5] 对应的起始索引为 [0, 3, 5]。
我们也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
注意:
nums.length的范围在[1, 20000]之间。
nums[i]的范围在[1, 65535]之间。
k的范围在[1, floor(nums.length / 3)]之间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-sum-of-3-non-overlapping-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=689 lang=javascript
*
* [689] 三个无重叠子数组的最大和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSumOfThreeSubarrays = function(nums, k) {
const dp = new Array(nums.length).fill(0).map( _ => new Array(4).fill(0) );
// 计算前缀和
const prefixSums=[nums[0]];
for(let i=1;i<nums.length;i++) {
prefixSums[i] = prefixSums[i-1] + nums[I];
}
// 填充dp数组
for(let n=1;n<=3;n++) {
for(let i=k*n-1;i<nums.length;i++) {
const prev1 = i-1 >= 0 ? dp[i-1][n] : 0;
const prevK = i-k >= 0 ? dp[i-k][n-1] : 0;
const tailSum = i-k >= 0 ? prefixSums[i] - prefixSums[i-k] : prefixSums[I];
dp[i][n] = Math.max(prev1, prevK + tailSum);
}
};
// 根据dp数组找字典序最小的解
const result = [];
let n = 3;
let current = dp.length-1;
while(result.length < 3) {
const v = dp[current][n];
let i = current;
while( i-1 >= 0 && dp[i-1][n] == v) {
I--;
}
current = i - k + 1;
result.push(current);
current--;
n--;
}
return result.reverse();
};
方案二：
/*
* @lc app=leetcode.cn id=689 lang=javascript
*
* [689] 三个无重叠子数组的最大和
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSumOfThreeSubarrays = function(nums, k) {
let n = nums.length
let l = n - k + 1
let sums = Array(l).fill(0)
let s = nums.slice(0,k).reduce((x,y) => x+y)
sums[0] = s
for (let i=1;i<l;i++){
s = s + nums[i-1+k] - nums[i-1]
sums[i] = s
}
let j,m
let mid = new Map()
for (let i=k-1;i<l;i++){
mid.set(i,0)
}
for (let i=k;i<l;i++){
j = mid.get(i-1)
if (sums[i-k] > sums[j]){
j = i-k
}
mid.set(i,j)
}
let right = new Map()
for (let i=2*k-1;i<l;i++){
right.set(i,k)
}
let res = [0,k,2*k]
for (let r=2*k;r<l;r++){
m = right.get(r-1)
if (sums[r-k]+sums[mid.get(r-k)] > sums[m]+sums[mid.get(m)]){
m = r-k
}
right.set(r,m)
if (sums[r]+sums[m]+sums[mid.get(m)] > sums[res[0]]+sums[res[1]]+sums[res[2]]){
res = [mid.get(m),m,r]
}
}
return res
};
两种解法：1、动态规划通解，构造递推循环不变式dp[i][n]=max{dp[i-1][n], dp[i-k][n-1]+sumRange(i-k+1,i)}，其中dp[i][n]的含义是从[0,i]范围内，选择n个数得到的最大和，n个数的相邻间隔为k；2、利用分段，将数组进行左、中、右分段后进行移动获取最大值
2020.10.05
No.1031 两个非重叠子数组的最大和
给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）
从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一：
0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
0 <= j < j + M - 1 < i < i + L - 1 < A.length.
示例 1：
输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
示例 2：
输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
示例 3：
输入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
提示：
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-sum-of-two-non-overlapping-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=1031 lang=javascript
*
* [1031] 两个非重叠子数组的最大和
*/
// @lc code=start
/**
* @param {number[]} A
* @param {number} L
* @param {number} M
* @return {number}
*/
var maxSumTwoNoOverlap = function(A, L, M) {
let max = -Infinity,
lArr = sum(L), // 获取L的和数组
mArr = sum(M); // 获取M的和数组
for(let i=0;i<lArr.length;i++) {
for(let j=0;j<mArr.length;j++) {
if( j > i+L-1 || i> j+M-1 ) {
max = Math.max(max, lArr[i]+mArr[j]);
}
}
}
return max;
function sum(n) {
let s = [];
for(let i=0;i+n<=A.length;i++) {
s.push(A.slice(i,i+n).reduce((prev,curr)=>prev+curr))
}
return s;
}
};
方案二：
/*
* @lc app=leetcode.cn id=1031 lang=javascript
*
* [1031] 两个非重叠子数组的最大和
*/
// @lc code=start
/**
* @param {number[]} A
* @param {number} L
* @param {number} M
* @return {number}
*/
var ListNode = function (val, start, end) {
this.val = val;
this.start = start;
this.end = end;
this.prev = null;
this.next = null;
}
var List = function () {
this.head = null;
this.tail = null;
}
var maxSumTwoNoOverlap = function(A, L, M) {
let l = [], m = [];
let lList = new List();
for (let i = 0; i <= A.length-L; i++) {
let sum = 0;
for (let j = 0; j < L; j++) {
sum+= A[i+j];
}
let node = new ListNode(sum, i, i+L-1);
addToList(lList,node);
}
let mList = new List();
for (let i = 0; i <= A.length-M; i++) {
let sum = 0;
for (let j = 0; j < M; j++) {
sum+= A[i+j];
}
let node = new ListNode(sum, i, i+M-1);
addToList(mList, node);
}
let mPtr = mList.head;
let lPtr = lList.head;
let max = 0;
mPtr = mList.head;
while (mPtr) {
while (lPtr) {
if (Math.max(mPtr.start, lPtr.start) <= Math.min(mPtr.end, lPtr.end)) {
lPtr = lPtr.next;
} else {
max = Math.max(max, mPtr.val+ lPtr.val);
lPtr = lPtr.next;
}
}
mPtr = mPtr.next;
lPtr= lList.head;
}
return max;
};
function addToList(list, node) {
if (!list.head) {
list.head= node;
list.tail = node;
} else {
if (list.head.val <= node.val) {
list.head.prev = node;
node.next = list.head;
list.head = node;
} else if (list.tail.val >= node.val) {
list.tail.next = node;
node.prev = list.tail;
list.tail = node;
} else {
let ptr = list.head;
while(ptr && ptr.val > node.val) {
ptr= ptr.next;
}
if (!ptr) {
list.tail = node;
list.head.next = list.tail;
node.prev = list.tail;
}
else {
let prev = ptr.prev;
prev.next = node;
node.prev = prev;
node.next = ptr;
ptr.prev = node;
}
}
}
}
方案三：
/*
* @lc app=leetcode.cn id=1031 lang=javascript
*
* [1031] 两个非重叠子数组的最大和
*/
// @lc code=start
/**
* @param {number[]} A
* @param {number} L
* @param {number} M
* @return {number}
*/
var maxSumTwoNoOverlap = function(A, L, M) {
return Math.max(traverse(L,M), traverse(M,L));
function traverse(a, b) {
let res = 0;
for (let i = 0; i <= A.length-a-b; i++) {
let sum = A.slice(i,i+a+b).reduce((acc,cur) => acc+cur);
let l = i+a, r = l+b;
res = Math.max(res, sum);
while (r < A.length) {
sum = sum-A[l]+A[r];
res = Math.max(res, sum)
l++, r++;
}
}
return res;
}
};
方案四：
/*
* @lc app=leetcode.cn id=1031 lang=javascript
*
* [1031] 两个非重叠子数组的最大和
*/
// @lc code=start
/**
* @param {number[]} A
* @param {number} L
* @param {number} M
* @return {number}
*/
var maxSumTwoNoOverlap = function(A, L, M) {
let len = A.length;
for(let i = 1; i < len; i++) {
A[i] += A[i - 1];
}
let LMax = A[L - 1], MMax = A[M-1];
let res = A[M + L - 1];
for(let i = M + L ; i< len ; i++) {
// update LMax to i - M;
LMax = Math.max(LMax, A[i - M ] - A[i - M - L]);
MMax = Math.max(MMax, A[i - L ] - A[i - M - L]);
res = Math.max(res,
LMax + A[i] - A[i - M],
MMax + A[i] - A[i - L]
)
}
return res;
};
三种解法：1、获取前M、L的所有前缀和，对和进行筛选加和，获取最大值；2、构造双向链表数据结构；3、利用移动窗口进行选择；4、动态规划，递推逼近 res = max{res, M的最大和值, L的最大和值}
2020.10.16
No.1013 将数组分成和相等的三个部分
给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
形式上，如果可以找出索引 i+1 < j 且满足 A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1] 就可以将数组三等分。
示例 1：
输入：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
示例 2：
输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false
示例 3：
输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
提示：
3 <= A.length <= 50000
-10^4 <= A[i] <= 10^4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=1013 lang=javascript
*
* [1013] 将数组分成和相等的三个部分
*/
// @lc code=start
/**
* @param {number[]} A
* @return {boolean}
*/
var canThreePartsEqualSum = function(A) {
const sum = A.reduce((prev, memo) => prev + memo);
if( sum % 3 != 0 ) {
return false;
} else {
const s = sum / 3;
// 左右指针
let p1 = 0,
l = 0,
p2 = A.length - 1,
r = 0;
while( p1 < A.length ) {
l += A[p1];
if(l != s) {
p1++;
} else {
break;
}
}
while( p2 > 0 ) {
r += A[p2];
if(r != s) {
p2--;
} else {
break;
}
}
if( p1 + 1 < p2 ) {
return true;
} else {
return false;
}
}
};
方案二：
/*
* @lc app=leetcode.cn id=1013 lang=javascript
*
* [1013] 将数组分成和相等的三个部分
*/
// @lc code=start
/**
* @param {number[]} A
* @return {boolean}
*/
var canThreePartsEqualSum = function(A) {
const sum = A.reduce((prev, memo) => prev+memo);
if(sum % 3 != 0) {
return false;
} else {
const s = sum / 3;
let temp = 0, // 用于记录前i项的和
n = 0; // 用于记录切割点的个数
for(let i=0; i< A.length; i++) {
temp += A[I];
if(temp == s) {
n++;
temp = 0;
};
if(n == 3) return true;
};
return false;
}
};
两种解法：1、比较左右指针的位置，可以合成一个循环中，但不太容易扩展，对于分成更多部分的问题都可以转化为比较指针的位置来返回结果；2、记录分割位点的个数，对于分成更多部分的问题可以更好的扩展，通过判断位点个数来返回结果
总结：
- 和问题常见的做法主要是利用map、hash、栈型等数据结构来进行优化处理，其次是利用左右指针的归约来进行循环的次数；
- 对于子问题常见的解法是利用动态规划及回溯剪枝来处理优化
二、位置索引问题
2020.10.09
No.34 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=34 lang=javascript
*
* [34] 在排序数组中查找元素的第一个和最后一个位置
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
let p1 = 0,
p2 = nums.length - 1;
// 二分查找
while(p1 <= p2) {
let mid = Math.floor((p1 + p2) / 2);
if( target < nums[mid] ) {
p2 = mid - 1;
} else if( target > nums[mid] ) {
p1 = mid + 1;
} else {
p1 = mid;
p2 = mid;
break;
}
};
// 判断
if( p1 > p2 ) {
return [-1,-1];
} else {
// 从中心向两边推，推到最远的两个target的位置
while(nums[p1-1] == target) p1--;
while(nums[p2+1] == target) p2++;
return [p1,p2];
}
};
方案二：
/*
* @lc app=leetcode.cn id=34 lang=javascript
*
* [34] 在排序数组中查找元素的第一个和最后一个位置
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
// console.log(nums.indexOf(target),nums.lastIndexOf(target))
return [nums.indexOf(target),nums.lastIndexOf(target)]
};
方案三：
/*
* @lc app=leetcode.cn id=34 lang=javascript
*
* [34] 在排序数组中查找元素的第一个和最后一个位置
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function(nums, target) {
return nums.map(n => n - target).reduce((p, n, i) => {
if (n === 0) {
if (p[0] === -1) {
p[0] = I
p[1] = I
}
p[1] = I
}
return p
}, [-1, -1])
};
有三种解法：1、二分查找：收到中间后向两边扩展到最远位置即为首末位查找位置；2、利用indexOf和lastIndexOf的api；3、问题转化，将位置转为目标值与遍历位置值的差值，利用reduce函数来对差值进行查找
2020.10.10
No.35 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=35 lang=javascript
*
* [35] 搜索插入位置
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
for(let i=0; i<nums.length; i++) {
if(nums[i] == target) {
return I;
} else {
if(nums[i] < target && nums[i+1] > target) {
return I+1;
};
if(nums[nums.length - 1] < target) return nums.length;
if(nums[0] > target) return 0;
}
}
};
方案二：
/*
* @lc app=leetcode.cn id=35 lang=javascript
*
* [35] 搜索插入位置
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
const n = nums.length;
let left = 0, right = n - 1, ans = n;
while (left <= right) {
let mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
};
方案三：
/*
* @lc app=leetcode.cn id=35 lang=javascript
*
* [35] 搜索插入位置
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
return nums.concat(Infinity).findIndex(n => n >= target);
};
有三种解法：1、常规解法：直接遍历比较，根据条件返回位置，时间复杂度为O(N)；2、二分查找，第一种解法的优化，使用二分查找，将时空复杂度降为O(logN)；3、利用js的findIndex以及sort等api进行查找
2020.10.12
No.162 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。
示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
说明:
你的解法应该是 O(logN) 时间复杂度的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=162 lang=javascript
*
* [162] 寻找峰值
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
let p1 = 0,
p2 = nums.length - 1;
// 二分查找
while( p1 < p2 ) {
let mid = Math.floor( (p1 + p2) / 2 );
if( nums[mid] > nums[mid+1] ) {
p2 = mid;
} else {
p1 = mid + 1;
}
};
return p2;
};
方案二：
/*
* @lc app=leetcode.cn id=162 lang=javascript
*
* [162] 寻找峰值
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
return nums.indexOf(Math.max(...nums));
};
有两种解法：1、二分查找，看到要求O(logN)，就要考虑二分查找；2、利用indexOf和Math.max的api
2020.10.13
No.724 寻找数组的中心索引
给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
示例 1：
输入：
nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，与右侧数之和 (5 + 6 = 11) 相等。
同时, 3 也是第一个符合要求的中心索引。
示例 2：
输入：
nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心索引。
说明：
nums 的长度范围为 [0, 10000]。
任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-pivot-index
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=724 lang=javascript
*
* [724] 寻找数组的中心索引
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
// 为空直接返回-1
if(nums.length == 0) return -1;
// 第一个
if(aSum(nums.slice(1)) == 0) return 0;
// 中间
for(let i=1;i<= nums.length-2;i++) {
if(aSum(nums.slice(0,i)) == aSum(nums.slice(i+1))) return I
};
// 最后一个
if(aSum(nums.slice(0,nums.length-1)) == 0) return nums.length - 1;
return -1;
function aSum(arr) {
return arr.reduce((prev, memo) => prev + memo, 0);
}
};
方案二：
/*
* @lc app=leetcode.cn id=724 lang=javascript
*
* [724] 寻找数组的中心索引
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
let sum = nums.reduce((prev, memo) => prev+memo,0),
leftsum = 0;
for(let i=0;i<nums.length;i++) {
if(sum - nums[i] == 2* leftsum) {
return I;
} else {
leftsum += nums[I];
}
}
return -1;
};
有两种方案：1、利用reduce的api分别求出左边和以及右边和，然后进行比较，这里需要对首尾进行一下处理，由于reduce是基于生成器，这里的时间复杂度是O(N^2)的，效率极差；2、对1来说，我们发现 总和 = 左边和 + nums[i] + 右边和 的，而当左边和等于右边和时，总和 - nums[i] = 2*左边和 的，这时可以不用求出总和，简化了中间的一层遍历，因而时空复杂度是O(N)
2020.10.14
No.747 至少是其他数字两倍的最大数
在一个给定的数组nums中，总是存在一个最大元素 。
查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
如果是，则返回最大元素的索引，否则返回-1。
示例 1:
输入: nums = [3, 6, 1, 0]
输出: 1
解释: 6是最大的整数, 对于数组中的其他整数,
6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.
示例 2:
输入: nums = [1, 2, 3, 4]
输出: -1
解释: 4没有超过3的两倍大, 所以我们返回 -1.
提示:
nums 的长度范围在[1, 50].
每个 nums[i] 的整数范围在 [0, 100].
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=747 lang=javascript
*
* [747] 至少是其他数字两倍的最大数
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var dominantIndex = function(nums) {
let max = -Infinity, pos = 0;
for(let i=0; i< nums.length; i++) {
if( nums[i] > max) {
max = nums[I];
pos = I;
}
}
for(let i=0; i< nums.length; i++) {
if( i != pos && ( 2*nums[i] ) > max) return -1;
}
return pos;
};
方案二：
/*
* @lc app=leetcode.cn id=747 lang=javascript
*
* [747] 至少是其他数字两倍的最大数
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number}
*/
var dominantIndex = function(nums) {
let max = 0, max2 = 0, pos = 0;
for(let i = 0; i< nums.length; i++) {
if(nums[i] > max) {
max2 = max;
max = nums[I];
pos = I
} else if (nums[i] > max2) {
max2 = nums[I];
}
};
if(2*max2 > max) return -1;
return pos;
};
有两种方案：1、两遍循环，第一遍获取最大，第二遍比较获取是否满足条件，时间复杂度为O(N)+O(N) ~ O(N)；2、一遍循环，获取第一大和第二大，返回结果只需比较第二大是否满足条件即可，时间复杂度O(N)
2020.10.15
No.852 山脉数组的峰顶索引
我们把符合下列属性的数组 A 称作山脉：
A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。
示例 1：
输入：[0,1,0]
输出：1
示例 2：
输入：[0,2,1,0]
输出：1
提示：
3 <= A.length <= 10000
0 <= A[i] <= 10^6
A 是如上定义的山脉
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=852 lang=javascript
*
* [852] 山脉数组的峰顶索引
*/
// @lc code=start
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function(arr) {
return arr.indexOf(Math.max(...arr));
};
方案二：
/*
* @lc app=leetcode.cn id=852 lang=javascript
*
* [852] 山脉数组的峰顶索引
*/
// @lc code=start
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function(arr) {
let max = -Infinity, pos = 0;
for(let i=0; i<arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
pos = I;
}
};
return pos;
};
方案三：
/*
* @lc app=leetcode.cn id=852 lang=javascript
*
* [852] 山脉数组的峰顶索引
*/
// @lc code=start
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function(arr) {
let l = 0, r = arr.length - 1;
// 二分查找
while( l < r ) {
let m = Math.floor( ( l + r ) / 2 );
if( arr[m] < arr[m+1] ) {
l = m + 1;
} else {
r = m;
}
};
return l;
};
有三种方案：1、使用indexOf以及Math.max的api；2、一遍循环，获取最大值及位置信息；3、利用二分查找，可将时间复杂度降到O(logN)
总结：
- 位置索引问题常见的做法主要是利用indexOf、lastIndexOf的api来查找位置，中间不同的要求可以将目的转换为不同的公式等进行处理；
- 位置索引问题本质是一种查找问题，针对查找问题都可以用到常见的查找算法进行变形，只是需要考虑时空复杂度的互斥，最常见的查找算法就是二分查找算法
三、路径问题
2020.10.19
No.62 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=62 lang=javascript
*
* [62] 不同路径
*/
// @lc code=start
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
// 用矩阵表来记录所有路径数
/**
* 如对于 3 x 2 的矩阵可用如下表示：
* 1 1 1
* 1 2 3
* 无剪枝，将所有信息录入矩阵表，最后一位数就是路径和
*/
let dp = new Array(n);
// 对于第一行所有算元素和第一列所有元素置为1
for(let row=0;row<n;row++) {
dp[row] = new Array(m);
dp[row][0] = 1;
}
for(let col=0;col<m;col++) {
dp[0][col] = 1;
}
// 动态规划
for(let i=1;i<n;i++) {
for(let j=1;j<m;j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[n-1][m-1];
};
方案二：
/*
* @lc app=leetcode.cn id=62 lang=javascript
*
* [62] 不同路径
*/
// @lc code=start
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
// 阶乘函数
const fac = (n) => {
if(n<=1) return 1;
return fac(n-1)*n;
}
return fac(n-1+m-1) / ( fac(m-1) * fac(n-1) );
};
有两种解法：1、动态规划：求路径问题一般都会想到动态规划，利用矩阵表来记录路径的和，返回最后一个加和结果，递归循环不变式为 dp[i][j]=dp[i-1][j]+dp[i][j-1] ，这里也可以使用一维数组直接替换上一层的数据，但扩展性不好，仅适用于本体；2、排列组合：可以将问题转换为向右为1，向下为0，每次都有两种不同结果的选择，进而为在m-1+n-1个选择中选择1或0的排列组合，即Cm-1+n-1n-1=Cm-1+n-1m-1
2020.10.20
No.63 不同路径-ii
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=63 lang=javascript
*
* [63] 不同路径 II
*/
// @lc code=start
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
var uniquePathsWithObstacles = function(obstacleGrid) {
const r = obstacleGrid.length,
c = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1 || obstacleGrid[r-1][c-1] == 1) return 0;
// 构建二维数组
let dp = new Array(r);
for(let row=0;row<r;row++) dp[row] = new Array(c);
dp[0][0] = 1;
// 第一列元素
for(let row=1;row<r;row++) {
if(obstacleGrid[row][0] == 1) {
dp[row][0] = 0;
} else if(obstacleGrid[row][0] == 0) {
dp[row][0] = dp[row-1][0];
}
};
// 第一行元素
for(let col=1;col<c;col++) {
if(obstacleGrid[0][col] == 1) {
dp[0][col] = 0;
} else if(obstacleGrid[0][col] == 0) {
dp[0][col] = dp[0][col-1];
}
};
// 动态规划
for(let i=1;i<r;i++) {
for(let j=1;j<c;j++) {
if(obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
} else if(obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
};
return dp[r-1][c-1];
};
动态规划常见问题，这里的状态转移方程需要对obstacleGrid(i,j)的值判断后进行过滤：当obstacleGrid(i,j)为1时，dp[i][j]=0；否则，dp[i][j]=dp[i-1][j]+dp[i][j-1]。边界条件同样也需要符合过滤条件，不能只是对0或1的填充进行判断，这一行或这一列填0或1会对下一行或下一列产生影响
2020.10.21
No.120 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：
/*
* @lc app=leetcode.cn id=120 lang=javascript
*
* [120] 三角形最小路径和
*/
// @lc code=start
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
const r = triangle.length,
c = triangle[0].length;
// 构造动态规划路径
const dp = new Array(r);
for(let row=0;row<r;row++) dp[row] = new Array(c);
/**
* 状态转移方程 dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]
*/
// 边界条件处理
dp[0][0] = triangle[0][0];
for(let i=1;i<r;i++) {
// 最左侧 dp[i][0] = dp[i-1][0] + triangle[i][0]
dp[i][0] = dp[i-1][0] + triangle[i][0];
for(let j=1;j<i;j++) {
dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j];
}
// 最右侧 dp[i][i] = dp[i-1][i-1] + triangle[i][I]
dp[i][i] = dp[i-1][i-1] + triangle[i][I];
}
return Math.min(...dp[r-1]);
};
方案二：
/*
* @lc app=leetcode.cn id=120 lang=javascript
*
* [120] 三角形最小路径和
*/
// @lc code=start
/**
* @param {number[][]} triangle
* @return {number}
*/
const minimumTotal = (triangle) => {
const height = triangle.length;
const width = triangle[0].length;
// 初始化dp数组
const dp = new Array(height);
for (let i = 0; i < height; i++) {
dp[i] = new Array(width);
}
for (let i = height - 1; i >= 0; i--) {
for (let j = triangle[i].length - 1; j >= 0; j--) {
if (i == height - 1) {
// base case
dp[i][j] = triangle[i][j];
} else {
// 状态转移方程
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
}
return dp[0][0];
};
动态规划经典题目，有两种方案：1、自顶向下：利用 dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j] 的状态转移方程，注意边界的处理；2、自底向上：从最底层一层一层向上查找，最底层中的最小值是确定的，因而其走向基本是确定的，最终会归约到一个数上
2020.10.22
No.864 获取所有钥匙的最短路径
给定一个二维网格 grid。 "." 代表一个空房间， "#" 代表一堵墙， "@" 是起点，（"a", "b", ...）代表钥匙，（"A", "B", ...）代表锁。
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 K 为钥匙/锁的个数，且满足 1 <= K <= 6，字母表中的前 K 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
示例 1：
输入：["@.a.#","###.#","b.A.B"]
输出：8
示例 2：
输入：["@..aA","..B#.","....b"]
输出：6
提示：
1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'
钥匙的数目范围是 [1, 6]，每个钥匙都对应一个不同的字母，正好打开一个对应的锁。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-to-get-all-keys
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方案：
/*
* @lc app=leetcode.cn id=864 lang=javascript
*
* [864] 获取所有钥匙的最短路径
*/
// @lc code=start
/**
* @param {string[]} grid
* @return {number}
*/
var shortestPathAllKeys = function(grid) {
// 构造一个结构体满足 {i,j,keybit,step}
/**
* i 横坐标 行坐标
* j 纵坐标 列坐标
* keybit 已经拿到的钥匙信息
* step 起始节点的最短距离
*/
function Step(i,j,keybit,step) {
this.i = I;
this.j = j;
this.keybit = keybit;
this.step = step;
};
const ROW = grid.length,
COL = grid[0].length,
LOWER_A = 'a'.charCodeAt(), // 97
UPPER_A = 'A'.charCodeAt(); // 68
let KEY_BIT = 0;
// 获取所有钥匙信息
let start = null;
for(let r = 0; r < ROW; r++) {
for(let c = 0; c < COL; c++) {
if(grid[r][c] == '@') {
// 起始位置
start = [r,c];
} else if (grid[r][c] >= 'a' && grid[r][c] <= 'f') {
// 标志判断位的移位异或比较，这是ACL的一种常见的方法
KEY_BIT = KEY_BIT | ( 1 << ( grid[r][c].charCodeAt() - LOWER_A ) )
}
}
}
// 构造已经遍历节点结构
const visited = new Array(ROW);
for(let i = 0; i < ROW; i++) {
visited[i] = new Array(COL);
for( let j = 0; j < COL; j++) {
visited[i][j] = {}
}
};
visited[start[0]][start[1]][0] = true;
// 移动方向
const directions = [
[-1, 0], // 左
[1, 0], // 右
[0, 1], // 上
[0, -1] // 下
];
// 构造队列结构 做缓存用
const queue = [new Step(start[0], start[1], 0 ,0)];
// 循环队列进行判断
while ( queue.length != 0) {
const current = queue.shift();
if(current.keybit == KEY_BIT) {
return current.step;
}
for(let d = 0; d < directions.length; d++) {
// 下一步的坐标
const ni = current.i + directions[d][0],
nj = current.j + directions[d][1];
// 对四个方向进行不同的判断
if( ( ni >= 0 && ni < ROW ) && ( nj >= 0 && nj < COL ) && !visited[ni][nj][current.keybit] ) {
// 是钥匙
if( grid[ni][nj] >= 'a' && grid[ni][nj] <= 'f' ) {
const _keybit = current.keybit | ( 1 << (grid[ni][nj].charCodeAt() - LOWER_A) );
queue.push(new Step(ni, nj, _keybit, current.step+1));
// 都已经访问过了
visited[ni][nj][current.keybit] = true;
visited[ni][nj][_keybit] = true;
} else if ( // 是空房间、起始点以及是没有被访问过状态的锁
( grid[ni][nj] == '.' ) ||
( grid[ni][nj] == '@' ) ||
( grid[ni][nj] >= 'A' && grid[ni][nj] <= 'F' && ( current.keybit & ( 1 << (grid[ni][nj].charCodeAt() - UPPER_A) ) ) )
) {
queue.push(new Step(ni, nj, current.keybit, current.step+1));
// 对这个路径状态置为访问过了
visited[ni][nj][current.keybit] = true;
}
}
}
}
return -1;
};
Dijkstra最短路径算法：对路径是否访问过进行状态校验，这里利用位运算进行校验位的判断，对关键节点进行不同方向尝试最后获取最短路径
2020.10.23
No.1138 字母板上的路径
我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。
在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。
image
网友评论