一雌澄、和問題
2020.09.21
No.1 兩數(shù)之和
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù)杯瞻，并返回他們的數(shù)組下標(biāo)镐牺。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是魁莉，數(shù)組中同一個元素不能使用兩遍任柜。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有卒废。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處宙地。
方案一：
/*
* @lc app=leetcode.cn id=1 lang=javascript
*
* [1] 兩數(shù)之和
*/
// @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] 兩數(shù)之和
*/
// @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] 兩數(shù)之和
*/
// @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)
}
};
求兩數(shù)和的常規(guī)思路是逐個相加求和摔认，獲取和是否滿足條件回论，方案一：爆解派哲；方案二：可以利用棧型結(jié)構(gòu)對存取進行優(yōu)化；方案三：構(gòu)造一個hash表對存取進行優(yōu)化
2020.09.22
No.15 三數(shù)之和
給你一個包含 n 個整數(shù)的數(shù)組 nums浑彰，判斷 nums 中是否存在三個元素 a秽梅，b抹蚀，c ，使得 a + b + c = 0 企垦？請你找出所有滿足條件且不重復(fù)的三元組环壤。
注意：答案中不可以包含重復(fù)的三元組。
示例：
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]钞诡，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/3sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有郑现。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處荧降。
方案一：
/*
* @lc app=leetcode.cn id=15 lang=javascript
*
* [15] 三數(shù)之和
*/
// @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;
// 過濾到當(dāng)前項和前一項相同的循環(huán)
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]);
// 跳過中間重復(fù)的元素
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] 三數(shù)之和
*/
// @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到數(shù)組接箫，所以需要判斷只有三次重復(fù)才能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剪返、傳統(tǒng)的轉(zhuǎn)成hash表的形式废累，優(yōu)化效率，是兩數(shù)之和的擴展
2020.09.23
No.16 最接近的三數(shù)字之和
給定一個包括 n 個整數(shù)的數(shù)組 nums 和 一個目標(biāo)值 target脱盲。找出 nums 中的三個整數(shù)邑滨，使得它們的和與 target 最接近。返回這三個數(shù)的和宾毒。假定每組輸入只存在唯一答案驼修。
示例：
輸入：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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有诈铛。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處墨礁。
方案：
/*
* @lc app=leetcode.cn id=16 lang=javascript
*
* [16] 最接近的三數(shù)之和
*/
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];
// 可以收到一個對象數(shù)組里幢竹，后續(xù)進行排序
// 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;
}
};
仍然是快排的延展應(yīng)用，是三數(shù)之和的變形
2020.09.24
No.18 四數(shù)之和
給定一個包含 n 個整數(shù)的數(shù)組 nums 和一個目標(biāo)值 target恩静，判斷 nums 中是否存在四個元素 a焕毫，b蹲坷，c 和 d ，使得 a + b + c + d 的值與 target 相等邑飒？找出所有滿足條件且不重復(fù)的四元組循签。
注意：
答案中不可以包含重復(fù)的四元組。
示例：
給定數(shù)組 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)撒轮，非商業(yè)轉(zhuǎn)載請注明出處乞旦。
方案一：
/*
* @lc app=leetcode.cn id=18 lang=javascript
*
* [18] 四數(shù)之和
*/
// @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++ ) {
// 除去重復(fù)情況
if(i>0 && nums[i-1] == nums[i]) continue;
for(let j = i+1; j< nums.length - 2; j++ ) {
// 除去重復(fù)情況
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] 四數(shù)之和
*/
// @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;
}
三數(shù)之和的加強版，多了一層循環(huán)
2020.09.25
No.39 組合總和
給定一個無重復(fù)元素的數(shù)組 candidates 和一個目標(biāo)數(shù) target 题山，找出 candidates 中所有可以使數(shù)字和為 target 的組合兰粉。
candidates 中的數(shù)字可以無限制重復(fù)被選取。
說明：
所有數(shù)字（包括 target）都是正整數(shù)顶瞳。
解集不能包含重復(fù)的組合玖姑。
示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有浊仆。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)客峭，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @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) {
// 對數(shù)組排序
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深度優(yōu)先遍歷查找，需要在合適位置剪枝囱稽，用數(shù)組來實現(xiàn)樹的結(jié)構(gòu)
2020.09.27
No.40 組合總和-ii
給定一個數(shù)組 candidates 和一個目標(biāo)數(shù) target 郊尝，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的每個數(shù)字在每個組合中只能使用一次战惊。
說明：
所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)流昏。
解集不能包含重復(fù)的組合。
示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有吞获。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)况凉，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @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) {
// 對數(shù)組從小到大排序
candidates.sort((a,b) => a-b);
// 簡化數(shù)組
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去重, 子項要轉(zhuǎn)化成 String
dp[i].add(item + ',' + c)
}
}
}
//最后把Set 轉(zhuǎn)成 Array
return Array.from(dp[target]).map(item => item.slice(1).split(','))
};
思路一和之前比較類似，這里需要有一個先前的位置記錄烤黍，不能重復(fù)遞歸同一元素知市；思路二是利用動態(tài)規(guī)劃
2020.09.28
No.53 最大子序和
給定一個整數(shù)數(shù)組 nums 傻盟，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和嫂丙。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大娘赴，為 6。
進階:
如果你已經(jīng)實現(xiàn)復(fù)雜度為 O(n) 的解法跟啤，嘗試使用更為精妙的分治法求解筝闹。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)腥光，非商業(yè)轉(zhuǎn)載請注明出處关顷。
方案一：
/*
* @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;
};
思路一利用動態(tài)規(guī)劃，關(guān)鍵在于找到遞推公式武福，即循環(huán)不變式议双，本題為f(n)=max{f(n-1)+ai,ai}；思路二是利用分治捉片，把數(shù)組分成兩段平痰，每一段只要最大就是最大，當(dāng)分到最后一個后進行回退伍纫，最后的和就是最大值
2020.09.29
No.64 最小路徑和
給定一個包含非負(fù)整數(shù)的 m x n 網(wǎng)格宗雇，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小莹规。
說明：每次只能向下或者向右移動一步赔蒲。
示例:
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-path-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有良漱。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)舞虱，非商業(yè)轉(zhuǎn)載請注明出處。
方案：
/*
* @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];
};
經(jīng)典動態(tài)規(guī)劃母市，遞推的循環(huán)不變式為 grid[i][j] = min{ grid[i][j-1], grid[i-1][j] }矾兜，邊界的細節(jié)處理需要注意
2020.09.30
No.167 兩數(shù)之和 II - 輸入有序數(shù)組
給定一個已按照升序排列 的有序數(shù)組，找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)患久。
函數(shù)應(yīng)該返回這兩個下標(biāo)值 index1 和 index2椅寺，其中 index1 必須小于 index2。
說明:
返回的下標(biāo)值（index1 和 index2）不是從零開始的蒋失。
你可以假設(shè)每個輸入只對應(yīng)唯一的答案返帕，而且你不可以重復(fù)使用相同的元素。
示例:
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標(biāo)數(shù) 9 高镐。因此 index1 = 1, index2 = 2 溉旋。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有畸冲。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)嫉髓，非商業(yè)轉(zhuǎn)載請注明出處观腊。
方案一：
/*
* @lc app=leetcode.cn id=167 lang=javascript
*
* [167] 兩數(shù)之和 II - 輸入有序數(shù)組
*/
// @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] 兩數(shù)之和 II - 輸入有序數(shù)組
*/
// @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] 兩數(shù)之和 II - 輸入有序數(shù)組
*/
// @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梧油、構(gòu)造一個map數(shù)據(jù)結(jié)構(gòu)；3州邢、二分查找
2020.10.01
No.216 組合總合 III
找出所有相加之和為 n 的 k 個數(shù)的組合儡陨。組合中只允許含有 1 - 9 的正整數(shù)，并且每種組合中不存在重復(fù)的數(shù)字量淌。
說明：
所有數(shù)字都是正整數(shù)骗村。
解集不能包含重復(fù)的組合。
示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有呀枢。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)胚股，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @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裙秋、經(jīng)典回溯算法琅拌，構(gòu)造dfs查詢；2摘刑、騷操作进宝，利用二進制掩碼進行移位枚舉；3枷恕、構(gòu)造一個map數(shù)據(jù)結(jié)構(gòu)
2020.10.04
No.689 三個無重疊子數(shù)組的最大和
給定數(shù)組 nums 由正整數(shù)組成党晋，找到三個互不重疊的子數(shù)組的最大和。
每個子數(shù)組的長度為k徐块，我們要使這3*k個項的和最大化隶校。
返回每個區(qū)間起始索引的列表（索引從 0 開始）。如果有多個結(jié)果蛹锰，返回字典序最小的一個深胳。
示例:
輸入: [1,2,1,2,6,7,5,1], 2
輸出: [0, 3, 5]
解釋: 子數(shù)組 [1, 2], [2, 6], [7, 5] 對應(yīng)的起始索引為 [0, 3, 5]。
我們也可以取 [2, 1], 但是結(jié)果 [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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有敛劝。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處纷宇。
方案一：
/*
* @lc app=leetcode.cn id=689 lang=javascript
*
* [689] 三個無重疊子數(shù)組的最大和
*/
// @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數(shù)組
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);
}
};
// 根據(jù)dp數(shù)組找字典序最小的解
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] 三個無重疊子數(shù)組的最大和
*/
// @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夸盟、動態(tài)規(guī)劃通解，構(gòu)造遞推循環(huán)不變式dp[i][n]=max{dp[i-1][n], dp[i-k][n-1]+sumRange(i-k+1,i)}像捶，其中dp[i][n]的含義是從[0,i]范圍內(nèi)上陕，選擇n個數(shù)得到的最大和桩砰，n個數(shù)的相鄰間隔為k；2释簿、利用分段亚隅，將數(shù)組進行左、中庶溶、右分段后進行移動獲取最大值
2020.10.05
No.1031 兩個非重疊子數(shù)組的最大和
給出非負(fù)整數(shù)數(shù)組 A 煮纵，返回兩個非重疊（連續(xù)）子數(shù)組中元素的最大和，子數(shù)組的長度分別為 L 和 M偏螺。（這里需要澄清的是行疏，長為 L 的子數(shù)組可以出現(xiàn)在長為 M 的子數(shù)組之前或之后。）
從形式上看套像，返回最大的 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
解釋：子數(shù)組的一種選擇中，[9] 長度為 1凉夯，[6,5] 長度為 2货葬。
示例 2：
輸入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
輸出：29
解釋：子數(shù)組的一種選擇中，[3,8,1] 長度為 3劲够，[8,9] 長度為 2震桶。
示例 3：
輸入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
輸出：31
解釋：子數(shù)組的一種選擇中，[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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)人柿，非商業(yè)轉(zhuǎn)載請注明出處柴墩。
方案一：
/*
* @lc app=leetcode.cn id=1031 lang=javascript
*
* [1031] 兩個非重疊子數(shù)組的最大和
*/
// @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的和數(shù)組
mArr = sum(M); // 獲取M的和數(shù)組
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] 兩個非重疊子數(shù)組的最大和
*/
// @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] 兩個非重疊子數(shù)組的最大和
*/
// @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] 兩個非重疊子數(shù)組的最大和
*/
// @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歼指、構(gòu)造雙向鏈表數(shù)據(jù)結(jié)構(gòu)；3甥雕、利用移動窗口進行選擇踩身；4、動態(tài)規(guī)劃社露，遞推逼近 res = max{res, M的最大和值, L的最大和值}
2020.10.16
No.1013 將數(shù)組分成和相等的三個部分
給你一個整數(shù)數(shù)組 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] 就可以將數(shù)組三等分脱拼。
示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)拒炎，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @lc app=leetcode.cn id=1013 lang=javascript
*
* [1013] 將數(shù)組分成和相等的三個部分
*/
// @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] 將數(shù)組分成和相等的三個部分
*/
// @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; // 用于記錄切割點的個數(shù)
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挨务、比較左右指針的位置击你，可以合成一個循環(huán)中，但不太容易擴展谎柄，對于分成更多部分的問題都可以轉(zhuǎn)化為比較指針的位置來返回結(jié)果丁侄；2、記錄分割位點的個數(shù)朝巫，對于分成更多部分的問題可以更好的擴展鸿摇，通過判斷位點個數(shù)來返回結(jié)果
總結(jié)：
- 和問題常見的做法主要是利用map、hash劈猿、棧型等數(shù)據(jù)結(jié)構(gòu)來進行優(yōu)化處理拙吉，其次是利用左右指針的歸約來進行循環(huán)的次數(shù)；
- 對于子問題常見的解法是利用動態(tài)規(guī)劃及回溯剪枝來處理優(yōu)化
二揪荣、位置索引問題
2020.10.09
No.34 在排序數(shù)組中查找元素的第一個和最后一個位置
給定一個按照升序排列的整數(shù)數(shù)組 nums筷黔，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置仗颈。
你的算法時間復(fù)雜度必須是 O(log n) 級別佛舱。
如果數(shù)組中不存在目標(biāo)值，返回 [-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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有请祖。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處脖祈。
方案一：
/*
* @lc app=leetcode.cn id=34 lang=javascript
*
* [34] 在排序數(shù)組中查找元素的第一個和最后一個位置
*/
// @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] 在排序數(shù)組中查找元素的第一個和最后一個位置
*/
// @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] 在排序數(shù)組中查找元素的第一個和最后一個位置
*/
// @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或舞、問題轉(zhuǎn)化荆姆，將位置轉(zhuǎn)為目標(biāo)值與遍歷位置值的差值，利用reduce函數(shù)來對差值進行查找
2020.10.10
No.35 搜索插入位置
給定一個排序數(shù)組和一個目標(biāo)值映凳，在數(shù)組中找到目標(biāo)值胆筒，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置仆救。
你可以假設(shè)數(shù)組中無重復(fù)元素抒和。
示例 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)彤蔽，非商業(yè)轉(zhuǎn)載請注明出處摧莽。
方案一：
/*
* @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、常規(guī)解法：直接遍歷比較顿痪，根據(jù)條件返回位置镊辕，時間復(fù)雜度為O(N)；2蚁袭、二分查找征懈，第一種解法的優(yōu)化，使用二分查找揩悄，將時空復(fù)雜度降為O(logN)卖哎；3、利用js的findIndex以及sort等api進行查找
2020.10.12
No.162 尋找峰值
峰值元素是指其值大于左右相鄰值的元素删性。
給定一個輸入數(shù)組 nums亏娜，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引蹬挺。
數(shù)組可能包含多個峰值照藻，在這種情況下，返回任何一個峰值所在位置即可汗侵。
你可以假設(shè) nums[-1] = nums[n] = -∞幸缕。
示例 1:
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函數(shù)應(yīng)該返回其索引 2晰韵。
示例 2:
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數(shù)可以返回索引 1发乔，其峰值元素為 2；
或者返回索引 5雪猪， 其峰值元素為 6栏尚。
說明:
你的解法應(yīng)該是 O(logN) 時間復(fù)雜度的。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-peak-element
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有只恨。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)译仗，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @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 尋找數(shù)組的中心索引
給定一個整數(shù)類型的數(shù)組 nums笛辟，請編寫一個能夠返回數(shù)組 “中心索引” 的方法。
我們是這樣定義數(shù)組 中心索引 的：數(shù)組中心索引的左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和序苏。
如果數(shù)組不存在中心索引手幢，那么我們應(yīng)該返回 -1。如果數(shù)組有多個中心索引忱详，那么我們應(yīng)該返回最靠近左邊的那一個围来。
示例 1：
輸入：
nums = [1, 7, 3, 6, 5, 6]
輸出：3
解釋：
索引 3 (nums[3] = 6) 的左側(cè)數(shù)之和 (1 + 7 + 3 = 11)，與右側(cè)數(shù)之和 (5 + 6 = 11) 相等匈睁。
同時, 3 也是第一個符合要求的中心索引监透。
示例 2：
輸入：
nums = [1, 2, 3]
輸出：-1
解釋：
數(shù)組中不存在滿足此條件的中心索引。
說明：
nums 的長度范圍為 [0, 10000]软舌。
任何一個 nums[i] 將會是一個范圍在 [-1000, 1000]的整數(shù)才漆。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-pivot-index
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有牛曹。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)佛点，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @lc app=leetcode.cn id=724 lang=javascript
*
* [724] 尋找數(shù)組的中心索引
*/
// @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] 尋找數(shù)組的中心索引
*/
// @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是基于生成器，這里的時間復(fù)雜度是O(N^2)的，效率極差刷袍；2谷丸、對1來說，我們發(fā)現(xiàn) 總和 = 左邊和 + nums[i] + 右邊和 的购城，而當(dāng)左邊和等于右邊和時吕座，總和 - nums[i] = 2*左邊和 的，這時可以不用求出總和瘪板，簡化了中間的一層遍歷吴趴，因而時空復(fù)雜度是O(N)
2020.10.14
No.747 至少是其他數(shù)字兩倍的最大數(shù)
在一個給定的數(shù)組nums中，總是存在一個最大元素 侮攀。
查找數(shù)組中的最大元素是否至少是數(shù)組中每個其他數(shù)字的兩倍锣枝。
如果是，則返回最大元素的索引兰英，否則返回-1撇叁。
示例 1:
輸入: nums = [3, 6, 1, 0]
輸出: 1
解釋: 6是最大的整數(shù), 對于數(shù)組中的其他整數(shù),
6大于數(shù)組中其他元素的兩倍。6的索引是1, 所以我們返回1.
示例 2:
輸入: nums = [1, 2, 3, 4]
輸出: -1
解釋: 4沒有超過3的兩倍大, 所以我們返回 -1.
提示:
nums 的長度范圍在[1, 50].
每個 nums[i] 的整數(shù)范圍在 [0, 100].
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有畦贸。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)税朴，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @lc app=leetcode.cn id=747 lang=javascript
*
* [747] 至少是其他數(shù)字兩倍的最大數(shù)
*/
// @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] 至少是其他數(shù)字兩倍的最大數(shù)
*/
// @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、兩遍循環(huán)正林，第一遍獲取最大泡一，第二遍比較獲取是否滿足條件，時間復(fù)雜度為O(N)+O(N) ~ O(N)觅廓；2鼻忠、一遍循環(huán)，獲取第一大和第二大杈绸，返回結(jié)果只需比較第二大是否滿足條件即可帖蔓，時間復(fù)雜度O(N)
2020.10.15
No.852 山脈數(shù)組的峰頂索引
我們把符合下列屬性的數(shù)組 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]
給定一個確定為山脈的數(shù)組，返回任何滿足 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
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有塑娇。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處劫侧。
方案一：
/*
* @lc app=leetcode.cn id=852 lang=javascript
*
* [852] 山脈數(shù)組的峰頂索引
*/
// @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] 山脈數(shù)組的峰頂索引
*/
// @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] 山脈數(shù)組的峰頂索引
*/
// @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烧栋、一遍循環(huán)写妥，獲取最大值及位置信息；3审姓、利用二分查找珍特，可將時間復(fù)雜度降到O(logN)
總結(jié)：
- 位置索引問題常見的做法主要是利用indexOf、lastIndexOf的api來查找位置魔吐，中間不同的要求可以將目的轉(zhuǎn)換為不同的公式等進行處理扎筒；
- 位置索引問題本質(zhì)是一種查找問題，針對查找問題都可以用到常見的查找算法進行變形酬姆，只是需要考慮時空復(fù)雜度的互斥嗜桌，最常見的查找算法就是二分查找算法
三、路徑問題
2020.10.19
No.62 不同路徑
一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）轴踱。
機器人每次只能向下或者向右移動一步症脂。機器人試圖達到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。
問總共有多少條不同的路徑淫僻？
例如诱篷，上圖是一個7 x 3 的網(wǎng)格。有多少可能的路徑雳灵？
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始棕所，總共有 3 條路徑可以到達右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
提示：
1 <= m, n <= 100
題目數(shù)據(jù)保證答案小于等于 2 * 10 ^ 9
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有悯辙。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)琳省，非商業(yè)轉(zhuǎn)載請注明出處迎吵。
方案一：
/*
* @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) {
// 用矩陣表來記錄所有路徑數(shù)
/**
* 如對于 3 x 2 的矩陣可用如下表示：
* 1 1 1
* 1 2 3
* 無剪枝，將所有信息錄入矩陣表针贬，最后一位數(shù)就是路徑和
*/
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;
}
// 動態(tài)規(guī)劃
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) {
// 階乘函數(shù)
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击费、動態(tài)規(guī)劃：求路徑問題一般都會想到動態(tài)規(guī)劃，利用矩陣表來記錄路徑的和桦他，返回最后一個加和結(jié)果蔫巩，遞歸循環(huán)不變式為 dp[i][j]=dp[i-1][j]+dp[i][j-1] ，這里也可以使用一維數(shù)組直接替換上一層的數(shù)據(jù)快压，但擴展性不好圆仔，僅適用于本體；2蔫劣、排列組合：可以將問題轉(zhuǎn)換為向右為1坪郭，向下為0，每次都有兩種不同結(jié)果的選擇脉幢，進而為在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 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為“Start” ）。
機器人每次只能向下或者向右移動一步鸵隧。機器人試圖達到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）绸罗。
現(xiàn)在考慮網(wǎng)格中有障礙物意推。那么從左上角到右下角將會有多少條不同的路徑豆瘫？
網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。
說明：m 和 n 的值均不超過 100菊值。
示例 1:
輸入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
輸出: 2
解釋:
3x3 網(wǎng)格的正中間有一個障礙物外驱。
從左上角到右下角一共有 2 條不同的路徑：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/unique-paths-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)腻窒，非商業(yè)轉(zhuǎn)載請注明出處昵宇。
方案：
/*
* @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;
// 構(gòu)建二維數(shù)組
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];
}
};
// 動態(tài)規(guī)劃
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];
};
動態(tài)規(guī)劃常見問題，這里的狀態(tài)轉(zhuǎn)移方程需要對obstacleGrid(i,j)的值判斷后進行過濾：當(dāng)obstacleGrid(i,j)為1時儿子，dp[i][j]=0瓦哎；否則，dp[i][j]=dp[i-1][j]+dp[i][j-1]柔逼。邊界條件同樣也需要符合過濾條件蒋譬，不能只是對0或1的填充進行判斷，這一行或這一列填0或1會對下一行或下一列產(chǎn)生影響
2020.10.21
No.120 三角形最小路徑和
給定一個三角形愉适，找出自頂向下的最小路徑和犯助。每一步只能移動到下一行中相鄰的結(jié)點上。
相鄰的結(jié)點 在這里指的是 下標(biāo) 與 上一層結(jié)點下標(biāo) 相同或者等于 上一層結(jié)點下標(biāo) + 1 的兩個結(jié)點维咸。
例如剂买，給定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即惠爽，2 + 3 + 5 + 1 = 11）。
說明：
如果你可以只使用 O(n) 的額外空間（n 為三角形的總行數(shù)）來解決這個問題瞬哼，那么你的算法會很加分婚肆。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/triangle
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)坐慰，非商業(yè)轉(zhuǎn)載請注明出處旬痹。
方案一：
/*
* @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;
// 構(gòu)造動態(tài)規(guī)劃路徑
const dp = new Array(r);
for(let row=0;row<r;row++) dp[row] = new Array(c);
/**
* 狀態(tài)轉(zhuǎn)移方程 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++) {
// 最左側(cè) 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];
}
// 最右側(cè) 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數(shù)組
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 {
// 狀態(tài)轉(zhuǎn)移方程
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
}
return dp[0][0];
};
動態(tài)規(guī)劃經(jīng)典題目，有兩種方案：1讨越、自頂向下：利用 dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j] 的狀態(tài)轉(zhuǎn)移方程两残，注意邊界的處理；2把跨、自底向上：從最底層一層一層向上查找人弓，最底層中的最小值是確定的，因而其走向基本是確定的着逐，最終會歸約到一個數(shù)上
2020.10.22
No.864 獲取所有鑰匙的最短路徑
給定一個二維網(wǎng)格 grid崔赌。 "." 代表一個空房間， "#" 代表一堵墻耸别， "@" 是起點健芭，（"a", "b", ...）代表鑰匙，（"A", "B", ...）代表鎖秀姐。
我們從起點開始出發(fā)慈迈，一次移動是指向四個基本方向之一行走一個單位空間。我們不能在網(wǎng)格外面行走省有，也無法穿過一堵墻痒留。如果途經(jīng)一個鑰匙，我們就把它撿起來蠢沿。除非我們手里有對應(yīng)的鑰匙伸头，否則無法通過鎖。
假設(shè) K 為鑰匙/鎖的個數(shù)舷蟀，且滿足 1 <= K <= 6恤磷，字母表中的前 K 個字母在網(wǎng)格中都有自己對應(yīng)的一個小寫和一個大寫字母。換言之野宜，每個鎖有唯一對應(yīng)的鑰匙扫步，每個鑰匙也有唯一對應(yīng)的鎖。另外速缨，代表鑰匙和鎖的字母互為大小寫并按字母順序排列锌妻。
返回獲取所有鑰匙所需要的移動的最少次數(shù)。如果無法獲取所有鑰匙旬牲，返回 -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'
鑰匙的數(shù)目范圍是 [1, 6]搁吓，每個鑰匙都對應(yīng)一個不同的字母，正好打開一個對應(yīng)的鎖吭历。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-path-to-get-all-keys
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有堕仔。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處晌区。
方案：
/*
* @lc app=leetcode.cn id=864 lang=javascript
*
* [864] 獲取所有鑰匙的最短路徑
*/
// @lc code=start
/**
* @param {string[]} grid
* @return {number}
*/
var shortestPathAllKeys = function(grid) {
// 構(gòu)造一個結(jié)構(gòu)體滿足 {i,j,keybit,step}
/**
* i 橫坐標(biāo) 行坐標(biāo)
* j 縱坐標(biāo) 列坐標(biāo)
* keybit 已經(jīng)拿到的鑰匙信息
* step 起始節(jié)點的最短距離
*/
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') {
// 標(biāo)志判斷位的移位異或比較摩骨，這是ACL的一種常見的方法
KEY_BIT = KEY_BIT | ( 1 << ( grid[r][c].charCodeAt() - LOWER_A ) )
}
}
}
// 構(gòu)造已經(jīng)遍歷節(jié)點結(jié)構(gòu)
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] // 下
];
// 構(gòu)造隊列結(jié)構(gòu) 做緩存用
const queue = [new Step(start[0], start[1], 0 ,0)];
// 循環(huán)隊列進行判斷
while ( queue.length != 0) {
const current = queue.shift();
if(current.keybit == KEY_BIT) {
return current.step;
}
for(let d = 0; d < directions.length; d++) {
// 下一步的坐標(biāo)
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));
// 都已經(jīng)訪問過了
visited[ni][nj][current.keybit] = true;
visited[ni][nj][_keybit] = true;
} else if ( // 是空房間、起始點以及是沒有被訪問過狀態(tài)的鎖
( 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));
// 對這個路徑狀態(tài)置為訪問過了
visited[ni][nj][current.keybit] = true;
}
}
}
}
return -1;
};
Dijkstra最短路徑算法：對路徑是否訪問過進行狀態(tài)校驗朗若，這里利用位運算進行校驗位的判斷恼五，對關(guān)鍵節(jié)點進行不同方向嘗試最后獲取最短路徑
2020.10.23
No.1138 字母板上的路徑
我們從一塊字母板上的位置 (0, 0) 出發(fā)，該坐標(biāo)對應(yīng)的字符為 board[0][0]哭懈。
在本題里灾馒，字母板為board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示遣总。
我們可以按下面的指令規(guī)則行動：
如果方格存在睬罗，'U' 意味著將我們的位置上移一行；
如果方格存在旭斥，'D' 意味著將我們的位置下移一行容达；
如果方格存在，'L' 意味著將我們的位置左移一列垂券；
如果方格存在花盐，'R' 意味著將我們的位置右移一列；
'!' 會把在我們當(dāng)前位置 (r, c) 的字符 board[r][c] 添加到答案中圆米。
（注意卒暂，字母板上只存在有字母的位置啄栓。）
返回指令序列娄帖，用最小的行動次數(shù)讓答案和目標(biāo) target 相同。你可以返回任何達成目標(biāo)的路徑昙楚。
示例 1：
輸入：target = "leet"
輸出："DDR!UURRR!!DDD!"
示例 2：
輸入：target = "code"
輸出："RR!DDRR!UUL!R!"
提示：
1 <= target.length <= 100
target 僅含有小寫英文字母近速。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/alphabet-board-path
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)堪旧，非商業(yè)轉(zhuǎn)載請注明出處削葱。
方案一：
/*
* @lc app=leetcode.cn id=1138 lang=javascript
*
* [1138] 字母板上的路徑
*/
// @lc code=start
/**
* @param {string} target
* @return {string}
*/
var alphabetBoardPath = function(target) {
// 構(gòu)造字母的hash表
let hashTable = {},
stack = 'abcdefghijklmnopqrstuvwxyz'.split('').reverse();
for( let i = 0; i <= 5; i++ ) {
for( let j = 0; j <= 4; j++ ) {
let key = stack.pop();
if( key ) {
hashTable[key] = [i, j];
}
}
};
// 構(gòu)造target的鏈表結(jié)構(gòu)
let list = [[0, 0]];
target.split('').forEach(l => {
list.push(hashTable[l]);
});
console.log(list);
const mapPos = ( pos1, pos2 ) => {
// 解構(gòu)數(shù)組位置
const [ x1, y1 ] = pos1,
[ x2, y2 ] = pos2,
xn = Math.abs(x1 - x2), // 恒坐標(biāo)相差單位的絕對值
yn = Math.abs(y1 - y2); // 縱坐標(biāo)相差單位的絕對值
let r = '';
// 無需兼容z的情況是，只要限制z的方向淳梦，其他的可以隨意析砸，因而只要滿足z的要求就可以了，對于z來說其方向是有先后順序的爆袍，即：z是起點 => 先上后右首繁；z是終點 => 先左后下
if ( x2 - x1 < 0 ) {
r += 'U'.repeat(xn)
};
if ( y2 - y1 > 0 ) {
r += 'R'.repeat(yn)
};
if ( y2 - y1 < 0 ) {
r += 'L'.repeat(yn)
};
if( x2 - x1 > 0 ) {
r += 'D'.repeat(xn)
};
return r + '!';
};
// 遍歷list作郭，獲取相鄰間距的值，返回最終的result
let result = '';
for(let p1=0,p2=1;p2<list.length;p1++,p2++) {
result += mapPos(list[p1], list[p2]);
};
return result;
};
方案二：
/*
* @lc app=leetcode.cn id=1138 lang=javascript
*
* [1138] 字母板上的路徑
*/
// @lc code=start
/**
* @param {string} target
* @return {string}
*/
var alphabetBoardPath = function (target) {
const mapManu = (p1, p2) => {
// 離'a'對比的距離
const LETTER_A = 'a'.charCodeAt();
p1 -= LETTER_A;
p2 -= LETTER_A;
let r = '';
const dy = Math.floor(p1 / 5) - Math.floor(p2 / 5),
dx = p1 % 5 - p2 % 5;
if (dy > 0) r += 'U'.repeat(dy)
if (dx < 0) r += 'R'.repeat(-dx)
if (dx > 0) r += 'L'.repeat(dx)
if (dy < 0) r += 'D'.repeat(-dy)
return r + '!';
};
let res = '',
p1 = 'a'.charCodeAt();
for (let i = 0; i < target.length; i++) {
res += mapManu(p1, target[i].charCodeAt());
p1 = target[i].charCodeAt();
}
return res;
};
主要有兩種解法：1弦疮、構(gòu)建hash表夹攒，對target中的字母進行查找，獲取位置順序坐標(biāo)胁塞，對坐標(biāo)的位置進行映射后輸出答案咏尝，需要注意對最后一行的'z'的處理方向順序；2啸罢、不構(gòu)建hash表编检，利用除法和求余處理target中的每個字母與'a'的距離，輸出最后的答案
總結(jié)：
- 路徑問題主要用到的通解方法是動態(tài)規(guī)劃扰才，需要考慮邊界問題以及對每個題目的狀態(tài)轉(zhuǎn)移方程的歸納蒙谓；
- 對于某些特殊場景的題目，可以考慮排列組合训桶、Dijkstra算法累驮、hash表等數(shù)據(jù)結(jié)構(gòu)與算法的變形引申
四、區(qū)間問題
2020.10.28
No.56 合并區(qū)間
給出一個區(qū)間的集合舵揭，請合并所有重疊的區(qū)間谤专。
示例 1:
輸入: intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例 2:
輸入: intervals = [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。
注意：輸入類型已于2019年4月15日更改午绳。 請重置默認(rèn)代碼定義以獲取新方法簽名置侍。
提示：
intervals[i][0] <= intervals[i][1]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/merge-intervals
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)拦焚，非商業(yè)轉(zhuǎn)載請注明出處蜡坊。
方案一：
/*
* @lc app=leetcode.cn id=56 lang=javascript
*
* [56] 合并區(qū)間
*/
// @lc code=start
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
// 按左邊界升序排列
intervals.sort((a,b) => a[0] - b[0]);
// 獲取滿足要求的子數(shù)組位置
let rIndex = [];
for( let p = 0; p < intervals.length; p++ ) {
if ( isOverlap(intervals[p], intervals[p+1]) ) {
intervals.splice(p+1, 1, mergeOverlap(intervals[p], intervals[p+1]));
} else {
rIndex.push(p)
}
};
// 返回符合要求的區(qū)間
let r = [];
for(let i=0;i<rIndex.length;i++) {
r.push(intervals[rIndex[I]])
}
return r;
// 判斷兩個數(shù)組是否重疊
function isOverlap( arr1, arr2 ) {
if(!arr1 || !arr2) return false;
const [ a1, b1 ] = arr1,
[ a2, b2 ] = arr2;
if( ( a1 <= a2 && a2 <= b1 && b1 <= b2 ) ||
( a1 <= a2 && b2 <= b1 ) ||
( a2 <= a1 && b1 <= b2 ) ||
( a2 <= a1 && a1 <= b2 && b2 <= b1 )
) {
return true;
}
return false;
};
// 重疊兩數(shù)組進行合并
function mergeOverlap(arr1, arr2) {
const a = [...arr1, ...arr2].sort((a,b) => a-b);
return [ a[0], a[ a.length - 1 ] ];
}
};
方案二：
/*
* @lc app=leetcode.cn id=56 lang=javascript
*
* [56] 合并區(qū)間
*/
// @lc code=start
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let res = [];
let idx = -1;
for (let interval of intervals) {
if (idx == -1 || interval[0] > res[idx][1]) {
res.push(interval);
idx++;
} else {
res[idx][1] = Math.max(res[idx][1], interval[1]);
}
}
return res;
};
有兩種解法：1、逐個判斷赎败，記錄位置秕衙，對于重疊區(qū)間會替換到最后一個合并的位置，會改變原數(shù)組僵刮；2据忘、優(yōu)化方案一，對于按區(qū)間左邊界遞增排序的數(shù)組搞糕，只需要判斷后一位的右邊界和前一位的做邊界的大小即可勇吊，對于滿足重疊規(guī)則的右邊界進行取最大值，對于不滿足規(guī)則的只需將區(qū)間存入結(jié)果數(shù)組即可
2020.10.29
No.57 插入?yún)^(qū)間
給出一個無重疊的 窍仰，按照區(qū)間起始端點排序的區(qū)間列表汉规。
在列表中插入一個新的區(qū)間，你需要確保列表中的區(qū)間仍然有序且不重疊（如果有必要的話驹吮，可以合并區(qū)間）针史。
示例 1：
輸入：intervals = [[1,3],[6,9]], newInterval = [2,5]
輸出：[[1,5],[6,9]]
示例 2：
輸入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
輸出：[[1,2],[3,10],[12,16]]
解釋：這是因為新的區(qū)間 [4,8] 與 [3,5],[6,7],[8,10] 重疊膏燕。
注意：輸入類型已在 2019 年 4 月 15 日更改。請重置為默認(rèn)代碼定義以獲取新的方法簽名悟民。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/insert-interval
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有坝辫。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處射亏。
方案一：
/*
* @lc app=leetcode.cn id=57 lang=javascript
*
* [57] 插入?yún)^(qū)間
*/
// @lc code=start
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {
// 如果原數(shù)組為空近忙，直接push新數(shù)組
if(!intervals.length) return [newInterval];
const [ left, right ] = newInterval;
// 設(shè)立左右指針
let p1 = 0,
p2 = intervals.length - 1;
if( getPos(right, intervals[0]) == 'l' ) {
return [ newInterval, ...intervals ]
} else if ( getPos(left, intervals[intervals.length-1]) == 'r' ) {
return [ ...intervals, newInterval ]
}
while( p1 <= p2 ) {
if ( getPos( left, intervals[p1] ) == 'r' ) {
p1++;
} else if ( getPos( right, intervals[p2] ) == 'l' ) {
p2--;
} else {
intervals.splice(p1, p2-p1+1, [Math.min(left, intervals[p1][0]),Math.max(right, intervals[p2][1])]);
break;
}
};
if( p1 > p2 ) intervals.splice(p1,0,newInterval)
return intervals;
function getPos( num, arr ) {
if( num < arr[0] ) {
return 'l';
} else if ( num > arr[1] ) {
return 'r';
} else if ( num >= arr[0] && num <= arr[1] ) {
return 'm';
}
}
};
方案二：
/*
* @lc app=leetcode.cn id=57 lang=javascript
*
* [57] 插入?yún)^(qū)間
*/
// @lc code=start
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {
intervals.push(newInterval);
// 按左邊界升序排列
intervals.sort((a,b) => a[0] - b[0]);
// 獲取滿足要求的子數(shù)組位置
let rIndex = [];
for( let p = 0; p < intervals.length; p++ ) {
if ( isOverlap(intervals[p], intervals[p+1]) ) {
intervals.splice(p+1, 1, mergeOverlap(intervals[p], intervals[p+1]));
} else {
rIndex.push(p)
}
};
// 返回符合要求的區(qū)間
let r = [];
for(let i=0;i<rIndex.length;i++) {
r.push(intervals[rIndex[I]])
}
return r;
// 判斷兩個數(shù)組是否重疊
function isOverlap( arr1, arr2 ) {
if(!arr1 || !arr2) return false;
const [ a1, b1 ] = arr1,
[ a2, b2 ] = arr2;
if( ( a1 <= a2 && a2 <= b1 && b1 <= b2 ) ||
( a1 <= a2 && b2 <= b1 ) ||
( a2 <= a1 && b1 <= b2 ) ||
( a2 <= a1 && a1 <= b2 && b2 <= b1 )
) {
return true;
}
return false;
};
// 重疊兩數(shù)組進行合并
function mergeOverlap(arr1, arr2) {
const a = [...arr1, ...arr2].sort((a,b) => a-b);
return [ a[0], a[ a.length - 1 ] ];
}
};
有兩種方案：1、首尾指針：將新數(shù)組左右邊界和原數(shù)組的每個區(qū)間進行位置比較智润，對在區(qū)間左側(cè)及舍、區(qū)間中、區(qū)間右側(cè)三種情況進行分別處理窟绷，最大限度的使用原數(shù)組進行合并或增加操作锯玛；2、先插入后排序再次合并兼蜈，利用56題的解法攘残，只需要將新數(shù)組插入后按區(qū)間左側(cè)進行升序排列，然后對有重疊的區(qū)間進行合并即可为狸，思路比較容易想到歼郭，但效率不高
2020.10.30
No.228 匯總區(qū)間
給定一個無重復(fù)元素的有序整數(shù)數(shù)組 nums 。
返回 恰好覆蓋數(shù)組中所有數(shù)字 的 最小有序 區(qū)間范圍列表辐棒。也就是說病曾，nums 的每個元素都恰好被某個區(qū)間范圍所覆蓋，并且不存在屬于某個范圍但不屬于 nums 的數(shù)字 x 漾根。
列表中的每個區(qū)間范圍 [a,b] 應(yīng)該按如下格式輸出：
"a->b" 泰涂，如果 a != b
"a" ，如果 a == b
示例 1：
輸入：nums = [0,1,2,4,5,7]
輸出：["0->2","4->5","7"]
解釋：區(qū)間范圍是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2：
輸入：nums = [0,2,3,4,6,8,9]
輸出：["0","2->4","6","8->9"]
解釋：區(qū)間范圍是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
示例 3：
輸入：nums = []
輸出：[]
示例 4：
輸入：nums = [-1]
輸出：["-1"]
示例 5：
輸入：nums = [0]
輸出：["0"]
提示：
0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/summary-ranges
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有辐怕。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)逼蒙，非商業(yè)轉(zhuǎn)載請注明出處。
方案一：
/*
* @lc app=leetcode.cn id=228 lang=javascript
*
* [228] 匯總區(qū)間
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {string[]}
*/
var summaryRanges = function(nums) {
if( nums.length == 0 ) {
return [];
} else if ( nums.length == 1 ) {
return [ nums[0] + '' ]
} else {
let rIndex = [],
r = [],
// 雙指針
p1 = 0,
p2 = 1;
while ( p2 < nums.length ) {
if( nums[p2] - nums[p1] == ( p2 - p1 ) ) {
p2++
} else {
rIndex.push(p2);
p1 = p2;
p2++;
}
}
rIndex.unshift(0);
rIndex.push(nums.length);
// 構(gòu)造r數(shù)組
for(let t1=0,t2=1;t2<rIndex.length;t1++,t2++) {
r.push(nums.slice(rIndex[t1],rIndex[t2]))
}
r = r.map(item => {if(item.length==1){ return item[0] + ''}else{ return item[0] + '->' + item[item.length-1]}});
return r;
}
};
方案二：
/*
* @lc app=leetcode.cn id=228 lang=javascript
*
* [228] 匯總區(qū)間
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {string[]}
*/
var summaryRanges = function(nums) {
const res = [];
nums.push(Infinity);
for (let i = 0, j = 1; j < nums.length; j++) {
if (nums[j] - 1 !== nums[j - 1]) {
res.push(i === j - 1 ? '' + nums[i] : `${nums[i]}->${nums[j - 1]}`);
i = j;
}
}
return res;
};
雙指針移動窗口秘蛇，有兩種寫法：1其做、獲取切割位點，對切割出來的數(shù)組進行格式轉(zhuǎn)換赁还；2、
總結(jié)：
- 區(qū)間問題常見做法主要是通過雙指針判斷區(qū)間的左右位置驹沿，需要注意一些邊界問題的處理艘策；
- 對于某些特殊場景的題目，可以考慮動態(tài)規(guī)劃以及通項公式的總結(jié)歸納
