LeetCode 算法笔记 Part3
本文主要记录了博主的 Leetcode 算法刷题记录,方便以后查询复习。
图论
岛屿数量
LeetCode 原题链接:200. 岛屿数量
深度优先遍历,基本思路为,遇到一个岛就把这个岛给沉没掉,然后统计数加 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* @param {character[][]} grid
* @return {number}
*/
const numIslands = (grid) => {
const m = grid.length,
n = grid[0].length;
const dfs = (i, j) => {
if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] === "0") {
return;
}
grid[i][j] = "0";
dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j + 1);
dfs(i, j - 1);
};
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === "1") {
count++;
dfs(i, j);
}
}
}
return count;
};
腐烂的橘子
LeetCode 原题链接:994. 腐烂的橘子
广度优先遍历,利用循环比较好做,这边需要注意广度优先遍历的一些条件,辅助函数用于推入队列,上下左右扩散的过程还是由循环过程去做。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* @param {number[][]} grid
* @return {number}
*/
const orangesRotting = (grid) => {
const m = grid.length,
n = grid[0].length;
const queue = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) {
queue.push([i, j]);
}
}
}
const step = (i, j, arr) => {
if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] !== 1) {
return;
}
grid[i][j] = 2;
arr.push([i, j]);
};
let count = 0;
while (queue.length) {
const tempArr = [];
while (queue.length) {
const [i, j] = queue.shift();
step(i + 1, j, tempArr);
step(i - 1, j, tempArr);
step(i, j + 1, tempArr);
step(i, j - 1, tempArr);
}
if (tempArr.length) {
count++;
queue.push(...tempArr);
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
return -1;
}
}
}
return count;
};
console.log(orangesRotting([[0, 2]]));
课程表
LeetCode 原题链接:207. 课程表
广度优先遍历,采用图和入度的概念进行求解。
- 构建入度数组,使用哈希表以该课程为键,依赖该课程的数组为值,建立哈希表。
- 将入度为 0 的数组推入队列。
- 迭代,入度为零的课程继续推入队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
const canFinish = (numCourses, prerequisites) => {
const inDegArr = new Array(numCourses).fill(0);
const map = new Map();
for (let i = 0; i < prerequisites.length; i++) {
inDegArr[prerequisites[i][0]]++;
if (map.has(prerequisites[i][1])) {
map.get(prerequisites[i][1]).push(prerequisites[i][0]);
} else {
map.set(prerequisites[i][1], [prerequisites[i][0]]);
}
}
const queue = [];
for (let i = 0; i < inDegArr.length; i++) {
if (inDegArr[i] === 0) {
queue.push(i);
}
}
let count = 0;
while (queue.length) {
const course = queue.shift();
count++;
const depArr = map.get(course);
if (depArr) {
for (const dep of depArr) {
inDegArr[dep]--;
if (inDegArr[dep] === 0) {
queue.push(dep);
}
}
}
}
return count === numCourses;
};
实现 Trie (前缀树)
LeetCode 原题链接:208. 实现 Trie (前缀树)
采用迭代对象来求解,可以考虑使用数组的reduce
方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Trie {
constructor() {
this.children = {};
}
insert(word) {
let node = this.children;
for (const ch of word) {
if (!node[ch]) {
node[ch] = {};
}
node = node[ch];
}
node.isEnd = true;
}
searchPrefix(prefix) {
let node = this.children;
for (const ch of prefix) {
if (!node[ch]) {
return false;
}
node = node[ch];
}
return node;
}
search(word) {
const node = this.searchPrefix(word);
return node !== undefined && node.isEnd !== undefined;
}
startsWith(prefix) {
return this.searchPrefix(prefix);
}
}
回溯
全排列
LeetCode 原题链接:46. 全排列
无他,惟手熟尔。😊
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* @param {number[]} nums
* @return {number[][]}
*/
const permute = (nums) => {
const step = (arr) => {
if (arr.length <= 1) return [arr];
if (arr.length === 2) {
return [
[arr[0], arr[1]],
[arr[1], arr[0]],
];
}
if (arr.length >= 3) {
const res = [];
for (let i = 0; i < arr.length; i++) {
const tempArr = arr.filter((item) => item !== arr[i]);
const tmpRes = step(tempArr);
for (const temp of tmpRes) {
res.push([arr[i]].concat(temp));
}
}
return res;
}
};
return step(nums);
};
/**
* @param {number[]} nums
* @return {number[][]}
*/
const permute0 = (nums) => {
const res = [];
const step = (first) => {
if (first === nums.length) {
res.push([...nums]);
}
for (let i = first; i < nums.length; i++) {
[nums[first], nums[i]] = [nums[i], nums[first]];
step(first + 1);
[nums[first], nums[i]] = [nums[i], nums[first]];
}
};
step(0);
return res;
};
console.log(permute0([1, 2, 3]));
字集
LeetCode 原题链接:78. 字集
可采用幂集算法和深度遍历解决。
对于幂集算法
- 左移
n
位,循环。 - 循环数组的长度次,推入所有的有效数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* @param {number[]} nums
* @return {number[][]}
*/
const subsets = (nums) => {
const res = [];
for (let i = 0; i < 1 << nums.length; i++) {
const temp = [];
for (let j = 0; j < nums.length; j++) {
if (i & (1 << j)) {
temp.push(nums[j]);
}
}
res.push(temp);
}
return res;
};
const subsets = function (nums) {
const temp = [];
const res = [];
const dfs = (cur) => {
if (cur === nums.length) {
res.push([...temp]);
return;
}
temp.push(nums[cur]);
dfs(cur + 1);
temp.pop();
dfs(cur + 1);
};
dfs(0);
return res;
};
电话号码的数字组合
LeetCode 原题链接:17. 电话号码的数字组合
采用回溯算法,从前面回溯到后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @param {string} digits
* @return {string[]}
*/
const letterCombinations = (digits) => {
if (digits.length === 0) {
return [];
}
const map = new Map([
["2", "abc"],
["3", "def"],
["4", "ghi"],
["5", "jkl"],
["6", "mno"],
["7", "pqrs"],
["8", "tuv"],
["9", "wxyz"],
]);
const res = [];
const step = (str, index) => {
if (index === digits.length) {
res.push(str);
return;
}
const charSet = map.get(digits[index]);
for (const char of charSet) {
step(str + char, index + 1);
}
};
step("", 0);
return res;
};
组合总和
LeetCode 原题链接:39. 组合总和
排序candidates
数组,递归回溯,选择当前数字或者不选择当前数字然后跳过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
const combinationSum = (candidates, target) => {
const res = [];
candidates.sort((a, b) => a - b);
const step = (curVal, index, arr) => {
if (index === candidates.length) {
return;
}
if (curVal === 0) {
res.push(arr);
return;
}
if (candidates[index] < curVal) {
step(curVal, index + 1, arr);
}
if (curVal - candidates[index] >= 0) {
step(curVal - candidates[index], index, [...arr, candidates[index]]);
}
};
step(target, 0, []);
return res;
};
括号总和
LeetCode 原题链接:22. 括号生成
采用深度遍历的方式进行求解,左侧括号在小于num
的情况下可以一直推入,右侧括号只有在左侧括号数量大于右侧括号才能推入。非常经典的回溯加剪枝。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number} n
* @return {string[]}
*/
const generateParenthesis = (n) => {
const res = [];
const dfs = (str, left, right) => {
if (left === n && right === n) {
res.push(str);
}
if (left > right) {
dfs(str + ")", left, right + 1);
}
if (left < n) {
dfs(str + "(", left + 1, right);
}
};
dfs("", 0, 0);
return res;
};
单词搜索
LeetCode 原题链接:79. 单词搜索
谨慎使用fill
方法,主要利用深度遍历与标记数组。通过每个数组都尝试遍历。注意空数组不会被Map
等方法遍历,需要先fill
值再遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
const exist = (board, word) => {
const rowLen = board.length;
const colLen = board[0].length;
const visited = new Array(rowLen)
.fill(0)
.map(() => new Array(colLen).fill(false));
const dfs = (i, j, k) => {
if (k === word.length) {
return true;
}
if (i < 0 || i > rowLen - 1 || j < 0 || j > colLen - 1 || visited[i][j]) {
return;
}
if (board[i][j] === word[k]) {
visited[i][j] = true;
const flag =
dfs(i - 1, j, k + 1) ||
dfs(i + 1, j, k + 1) ||
dfs(i, j - 1, k + 1) ||
dfs(i, j + 1, k + 1);
visited[i][j] = false;
return flag;
}
};
for (let i = 0; i < rowLen; i++) {
for (let j = 0; j < colLen; j++) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
};
分割回文串
LeetCode 原题链接: 131. 分割回文串
深度遍历加上动态规划。我能说我其实是背下来的吗?🤧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @param {string} s
* @return {string[][]}
*/
const partition = (s) => {
const n = s.length,
ans = [],
res = [];
const f = new Array(n).fill(0).map(() => new Array(n).fill(true));
for (let i = n - 1; i >= 0; i--) {
for (let j = i + 1; j < n; j++) {
f[i][j] = s[i] === s[j] && f[i + 1][j - 1];
}
}
const step = (i) => {
if (i === n) {
res.push([...ans]);
return;
}
for (let j = i; j < n; j++) {
if (f[i][j]) {
ans.push(s.slice(i, j + 1));
step(j + 1);
ans.pop();
}
}
};
step(0);
return res;
};
N 皇后
LeetCode 原题链接:51. N 皇后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* @param {number} n
* @return {string[][]}
*/
const solveNQueens = (n) => {
const ans = [];
const col = new Array(n).fill(0);
const onPath = new Array(n).fill(false);
const diag1 = new Array(n * 2 - 1).fill(false);
const diag2 = new Array(n * 2 - 1).fill(false);
const dfs = (r) => {
if (r === n) {
ans.push(col.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - 1 - c)));
return;
}
for (let c = 0; c < n; c++) {
if (!onPath[c] && !diag1[r + c] && !diag2[r - c]) {
col[r] = c;
onPath[c] = diag1[r + c] = diag2[r - c] = true;
dfs(r + 1);
onPath[c] = diag1[r + c] = diag2[r - c] = false; // 恢复现场
}
}
};
dfs(0);
return ans;
};
/**
* @param {number} n
* @return {string[][]}
*/
const solveNQueens = (n) => {
const arr = new Array(n);
const res = [];
const judge = (row) => {
for (let i = 0; i < row; i++) {
if (arr[i] === arr[row] || row - i === Math.abs(arr[row] - arr[i]))
return false;
}
return true;
};
const step = (count) => {
if (count === n) {
const temp = [];
for (const item of arr) {
const strArr = new Array(n).fill(".");
strArr[item] = "Q";
temp.push(strArr.join(""));
}
res.push(temp);
return;
}
for (let i = 0; i < n; i++) {
arr[count] = i;
if (judge(count)) {
step(count + 1);
}
}
};
step(0);
return res;
};
console.log(solveNQueens(4));
二分查找
搜索插入位置
LeetCode 原题链接:35. 搜索插入位置
二分查找的变式,稍作修改,注意ans
的初始值需要设置为num.length
来处理越界情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const searchInsert = (nums, target) => {
let low = 0,
high = nums.length - 1,
ans = nums.length;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (target <= nums[mid]) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
};
搜索二维矩阵
LeetCode 原题链接:74. 搜索二维矩阵
依旧是二分查找的变式,查找到大于当前数字的一行,然后对当前这一行进行二分查找。另外这里例子是Z
字型查找的一个特例,也可使用Z
字型查找的方式,更简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
const searchMatrix = (matrix, target) => {
const binarySearchRow = () => {
let low = 0,
high = matrix.length - 1,
ans = 0;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (target < matrix[mid][0]) {
high = mid - 1;
} else if (target >= matrix[mid][0]) {
ans = mid;
low = mid + 1;
}
}
return ans;
};
const binarySearchCol = (index) => {
let low = 0,
high = matrix[0].length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (target < matrix[index][mid]) {
high = mid - 1;
} else if (target > matrix[index][mid]) {
low = mid + 1;
} else {
return true;
}
}
return false;
};
const index = binarySearchRow();
return binarySearchCol(index);
};
在排序数组中查找元素的第一个和最后一个位置
LeetCode 原题链接:34. 在排序数组中查找元素的第一个和最后一个位置
二分查找的变式,注意如何查找到第一次出现的元素与最后一次出现的元素,这边采取循环的方式更好写一些。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const searchRange = (nums, target) => {
const binarySearch = (low, high, flag) => {
if (low > high) {
return -1;
}
const mid = Math.floor((low + high) / 2);
if (target > nums[mid]) {
return binarySearch(mid + 1, high, flag);
} else if (target < nums[mid]) {
return binarySearch(low, mid - 1, flag);
} else {
if (flag) {
if (mid === 0 || nums[mid - 1] < nums[mid]) {
return mid;
} else {
return binarySearch(low, mid - 1, flag);
}
} else {
if (mid === nums.length - 1 || nums[mid] < nums[mid + 1]) {
return mid;
} else {
return binarySearch(mid + 1, high, flag);
}
}
}
};
const left = binarySearch(0, nums.length - 1, true);
const right = binarySearch(0, nums.length - 1, false);
return [left, right];
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const searchRange = (nums, target) => {
const binarySearch = (flag) => {
let low = 0,
high = nums.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (target > nums[mid]) {
low = mid + 1;
} else if (target < nums[mid]) {
high = mid - 1;
} else {
if (flag) {
if (mid !== 0 && nums[mid - 1] === nums[mid]) {
high = mid - 1;
} else {
return mid;
}
} else {
if (mid !== nums.length - 1 && nums[mid] === nums[mid + 1]) {
low = mid + 1;
} else {
return mid;
}
}
}
}
return -1;
};
return [binarySearch(true), binarySearch(false)];
};
搜索旋转排序数组
LeetCode 原题链接:33. 搜索旋转排序数组
来详细讲解一下这道题目的思路
考虑mid
在前区间与后区间的两种情况
- 在前区间:只有满足
target >= nums[0] && target < nums[mid]
的情况才有high = mid - 1
其他情况都是low = mid + 1
。 - 在后区间:只有满足
target > nums[mid] && target <= nums[n - 1]
才有low = mid + 1
其他情况都是high = mid - 1
。 - 注意前区间必须是满足
>=
以确定边缘情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const search = (nums, target) => {
const n = nums.length;
if (n === 0) return -1;
if (n === 1) return nums[0] === target ? 0 : -1;
let low = 0,
high = n - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (target === nums[mid]) return mid;
if (nums[mid] >= nums[0]) {
if (target >= nums[0] && target < nums[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[n - 1]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
};
寻找旋转排序数组中的最小值
LeetCode 原题链接:153. 寻找旋转排序数组中的最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {number[]} nums
* @return {number}
*/
const findMin = (nums) => {
const n = nums.length;
if (n <= 1) return nums[0];
if (nums[0] <= nums[n - 1]) return nums[0];
let low = 0,
high = n - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (nums[mid] < nums[mid - 1]) {
return nums[mid];
}
if (nums[mid] >= nums[0]) {
low = mid + 1;
}
if (nums[mid] < nums[n - 1]) {
high = mid - 1;
}
}
};
console.log(findMin([2, 1]));
寻找两个正序数组的中位数
LeetCode 原题链接:4. 寻找两个正序数组的中位数
技巧性较强的题目,菜就多练。🦀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
const findMedianSortedArrays = (nums1, nums2) => {
const getKthEl = (nums1, nums2, k) => {
let index1 = 0,
index2 = 0;
while (true) {
if (index1 === nums1.length) {
return nums2[index2 + k - 1];
}
if (index2 === nums2.length) {
return nums1[index1 + k - 1];
}
if (k === 1) {
return Math.min(nums1[index1], nums2[index2]);
}
const half = Math.floor(k / 2);
const newIndex1 = Math.min(index1 + half, nums1.length) - 1;
const newIndex2 = Math.min(index2 + half, nums2.length) - 1;
if (nums1[newIndex1] <= nums2[newIndex2]) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
} else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
};
const totalLength = nums1.length + nums2.length;
if (totalLength % 2 === 1) {
const midIndex = Math.floor(totalLength / 2);
return getKthEl(nums1, nums2, midIndex + 1);
} else {
const midIndex = totalLength / 2;
return (
(getKthEl(nums1, nums2, midIndex) +
getKthEl(nums1, nums2, midIndex + 1)) /
2
);
}
};
栈
有效括号
LeetCode 原题链接:20. 有效括号
非常经典的题目,细心点就可以做出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {string} s
* @return {boolean}
*/
const isValid = (s) => {
const stack = [];
const map = new Map([
["(", ")"],
["{", "}"],
["[", "]"],
]);
for (const char of s) {
if (stack.length && map.get(stack[stack.length - 1]) === char) {
stack.pop();
continue;
}
stack.push(char);
}
return stack.length ? false : true;
};
最小栈
LeetCode 原题链接:155. 最小栈
采用辅助栈进行求解,注意考虑栈为空的边缘情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MinStack {
constructor() {
this.arr = [];
this.MinStack = [];
}
push(el) {
this.arr.push(el);
if (
!this.MinStack.length ||
el <= this.MinStack[this.MinStack.length - 1]
) {
this.MinStack.push(el);
}
}
pop() {
const el = this.arr.pop();
if (
this.MinStack.length &&
el === this.MinStack[this.MinStack.length - 1]
) {
this.MinStack.pop();
}
return el;
}
top() {
return this.arr[this.arr.length - 1];
}
getMin() {
return this.MinStack[this.MinStack.length - 1];
}
}
字符串解码
LeetCode 原题链接:394. 字符串解码
可采用正则表达式的解法与数字栈与字符栈的解法来计算,类似逆波兰表达式的计算。注意对多位数字的置零处理,和字符串栈的转换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const decodeString = (s) => {
while (s.includes("[")) {
// 正则匹配每一组编码,其中n为数字,s为字符
s = s.replace(/(\d+)\[([a-z]+)\]/g, (_, n, s) => s.repeat(n));
}
return s;
};
const decodeString = (s) => {
let numStack = []; // 存倍数的栈
let strStack = []; // 存 待拼接的str 的栈
let num = 0; // 倍数的“搬运工”
let result = ""; // 字符串的“搬运工”
for (const char of s) {
// 逐字符扫描
if (!isNaN(char)) {
// 遇到数字
num = num * 10 + Number(char); // 算出倍数
} else if (char == "[") {
// 遇到 [
strStack.push(result); // result串入栈
result = ""; // 入栈后清零
numStack.push(num); // 倍数num进入栈等待
num = 0; // 入栈后清零
} else if (char == "]") {
// 遇到 ],两个栈的栈顶出栈
let repeatTimes = numStack.pop(); // 获取拷贝次数
result = strStack.pop() + result.repeat(repeatTimes); // 构建子串
} else {
result += char; // 遇到字母,追加给result串
}
}
return result;
};
每日温度
LeetCode 原题链接:739. 每日温度
注意栈中存储的是数组的下标,单调栈一般是遇到大的元素开始做相关的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} temperatures
* @return {number[]}
*/
const dailyTemperatures = (temperatures) => {
const stack = [];
const arr = new Array(temperatures.length).fill(0);
for (let i = 0; i < temperatures.length; i++) {
while (
stack.length &&
temperatures[i] > temperatures[stack[stack.length - 1]]
) {
const j = stack.pop();
arr[j] = i - j;
}
stack.push(i);
}
return arr;
};
堆
数组中的第 K 个最大元素
LeetCode 原题链接:215. 数组中的第 K 个最大元素
存在快排和堆两种排序算法,熟能生巧,注意快排的边界判断,菜就多练。🦀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
const findKthLargest = (nums, k) => {
const quickSelect = (l, r) => {
if (l === r) {
return nums[nums.length - k];
}
let i = l - 1,
j = r + 1;
const x = nums[l];
while (i < j) {
do {
i++;
} while (nums[i] < x);
do {
j--;
} while (nums[j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
if (nums.length - k <= j) {
return quickSelect(l, j);
} else {
return quickSelect(j + 1, r);
}
};
return quickSelect(0, nums.length - 1);
};
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
const findKthLargest = (nums, k) => {
const buildMaxHeap = (heapSize) => {
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
maxHeapify(i, heapSize);
}
};
const maxHeapify = (i, heapSize) => {
const l = i * 2 + 1;
const r = i * 2 + 2;
let largest = i;
if (l < heapSize && nums[l] > nums[largest]) {
largest = l;
}
if (r < heapSize && nums[r] > nums[largest]) {
largest = r;
}
if (i !== largest) {
swap(i, largest);
maxHeapify(largest, heapSize);
}
};
const swap = (i, j) => {
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
};
let heapSize = nums.length;
buildMaxHeap(heapSize);
for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
swap(0, i);
heapSize--;
maxHeapify(0, heapSize);
}
return nums[0];
};
贪心
买卖股票的最佳时机
LeetCode 原题链接:121. 买卖股票的最佳时机
贪心算法,每次都找到前一个的最优条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} prices
* @return {number}
*/
const maxProfit = (prices) => {
let maxIn = 0,
minPrice = prices[0];
for (let i = 1; i < prices.length; i++) {
if (minPrice < prices[i]) {
maxIn = Math.max(maxIn, prices[i] - minPrice);
} else {
minPrice = prices[i];
}
}
return maxIn;
};
跳跃游戏
LeetCode 原题链接:55. 跳跃游戏
贪心算法,每次在符合条件情况下更新最长的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} nums
* @return {boolean}
*/
const canJump = (nums) => {
let head = nums[0];
for (let i = 1; i < nums.length; i++) {
if (i <= head) {
head = Math.max(head, i + nums[i]);
}
if (head >= nums.length - 1) {
return true;
}
}
return head >= nums.length - 1;
};
动态规划
爬楼梯
LeetCode 原题链接:70. 爬楼梯
经典问题,甚至让我觉得有点像斐波那契数列。🤔
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number} n
* @return {number}
*/
const climbStairs = (n) => {
let pre = 1,
cur = 1;
for (let i = 1; i < n; i++) {
const temp = pre + cur;
pre = cur;
cur = temp;
}
return cur;
};
打家劫舍
LeetCode 原题链接:70. 爬楼梯
常规的动态规划题目,注意状态转移方程的书写,注意初始条件的设置,并不影响整体的判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @param {number[]} nums
* @return {number}
*/
const rob = (nums) => {
if (!nums || nums.length === 0) {
return 0;
}
if (nums.length === 1) {
return nums[0];
}
let first = nums[0],
second = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
const temp = second;
second = Math.max(second, first + nums[i]);
first = temp;
}
return second;
};
/**
* @param {number[]} nums
* @return {boolean}
*/
const rob = (nums) => {
if (!nums || nums.length === 0) {
return 0;
}
if (nums.length === 1) {
return nums[0];
}
const sumArr = new Array(nums.length);
sumArr[0] = nums[0];
sumArr[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
sumArr[i] = Math.max(sumArr[i - 1], sumArr[i - 2] + nums[i]);
}
return sumArr[sumArr.length - 1];
};
单词拆分
LeetCode 原题链接:139. 单词拆分
这边还是有些技巧,首先dp
数组的长度为n + 1
并且第一项为true
,然后状态转移方程如下,值得仔细理解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
const wordBreak = (s, wordDict) => {
const set = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i < s.length + 1; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && set.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[dp.length - 1];
};
最长递增子序列
LeetCode 原题链接:300. 最长递增子序列
维护一个dp
数组,数组中的每个值为当前索引的最长子序列长度,然后动态规划求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} nums
* @return {number}
*/
const lengthOfLIS = (nums) => {
const dp = new Array(nums.length).fill(1);
let maxLen = 1;
for (let i = 1; i < nums.length; i++) {
let max = 1;
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
max = Math.max(max, dp[j] + 1);
}
}
dp[i] = max;
maxLen = Math.max(maxLen, max);
}
return maxLen;
};
多维动态规划
不同路径
LeetCode 原题链接:62. 不同路径
二维动态规划,也可直接使用一维数组来模仿,重点在于当前节点的次数只会来源于左上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
const uniquePaths = (m, n) => {
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
f[i][0] = 1;
}
for (let j = 0; j < n; j++) {
f[0][j] = 1;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
};
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
const uniquePaths = (m, n) => {
const newArr = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
newArr[j] += newArr[j - 1];
}
}
return newArr[n - 1];
};
最小路径和
LeetCode 原题链接:64. 最小路径和
相同的动态规划思路,左边和上面哪个更小取哪个,注意需要初始化边缘的行与列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[][]} grid
* @return {number}
*/
const minPathSum = (grid) => {
const rowLen = grid.length,
colLen = grid[0].length;
for (let i = 1; i < colLen; i++) {
grid[0][i] += grid[0][i - 1];
}
for (let i = 1; i < rowLen; i++) {
grid[i][0] += grid[i - 1][0];
}
for (let i = 1; i < rowLen; i++) {
for (let j = 1; j < colLen; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[rowLen - 1][colLen - 1];
};
最长回文子串
LeetCode 原题链接:5. 最长回文子串
中心扩散法直接秒,经典无需多言。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome = (s) => {
if (s.length <= 1) {
return s;
}
let res = "";
const helper = (m, n) => {
while (m >= 0 && n < s.length && s[m] === s[n]) {
m--;
n++;
}
const temp = s.slice(m + 1, n);
if (temp.length > res.length) {
res = temp;
}
};
for (let i = 0; i < s.length; i++) {
helper(i, i);
helper(i, i + 1);
}
return res;
};
技巧
多数元素
LeetCode 原题链接:169. 多数元素
哈希表求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} nums
* @return {number}
*/
const majorityElement = (nums) => {
if (nums.length <= 1) return nums;
const map = new Map();
for (const num of nums) {
if (map.has(num)) {
const count = map.get(num);
if (count === Math.floor(nums.length / 2)) {
return num;
}
map.set(num, count + 1);
} else {
map.set(num, 1);
}
}
};
下一个排列
LeetCode 原题链接:31. 下一个排列
从右往左找到较小的一个数,然后找到较大的一个数然后需要尽量靠右,交换后然后反转。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
const nextPermutation = (nums) => {
const swap = (i, j) => {
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
};
const reverse = (l, r) => {
while (l < r) {
swap(l++, r--);
}
};
let i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
let j = nums.length - 1;
while (j > i && nums[j] <= nums[i]) {
j--;
}
swap(i, j);
}
reverse(i + 1, nums.length - 1);
};