资源力扣Hot100
Breezli力扣Hot100
1.两数之和
for
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| var twoSum = function(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const now = nums[i];
const oth = target - now;
if (map.has(oth)) {
return [map.get(oth), i];
}
map.set(now, i);
}
};
|
forEach
1
| >forEach((element, index, array) => { })
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| var twoSum = function(nums, target) {
const map = new Map();
let res;
nums.forEach((now, i) => {
const oth = target - now;
if (map.has(oth)) {
res = [map.get(oth), i];
}
map.set(now, i);
});
if (res) { return result; }
};
|
3.无重复字符最长字串
const map = new Set()
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| var lengthOfLongestSubstring = function(s) {
let ans = 0
let l = 0
const map = new Set()
for(let r=0; r<s.length; r++){
let c=s[r]
while(map.has(c)){
map.delete(s[l])
l++
}
map.add(c)
if(ans<r-l+1){
ans=r-l+1
}
}
return ans
};
|
17.电话号码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| var letterCombinations = function(digits) {
if (digits.length == 0) return [];
const res = [];
const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
const dfs = (now, i) => {
if (i > digits.length - 1) {
res.push(now);
return;
}
const strs = map[digits[i]];
for (const str of strs) {
dfs(now + str, i + 1);
}
};
dfs('', 0);
return res;
};
|
20.括号栈
入栈右括号
([)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var isValid = function(s) {
if (s.length % 2) {
return false;
}
const map = {'(': ')', '[': ']', '{': '}'};
const strs = [];
for (const str of s) {
if (map[str]) {
strs.push(map[str]);
} else if (strs.length === 0 || strs.pop() !== str) {
return false;
}
}
return strs.length === 0;
};
|
22.括号生成
dfs (填入括号数，左括号数)
注意填入右括号的判断逻辑
join() 将一个数组的所有元素 连接成一个字符串
1
2
3
4
5
6
7
8
9
10
| const array = ["A", "B", "C"];
console.log(array.join());
console.log(array.join(""));
console.log(array.join("-"));
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| var generateParenthesis = function(n) {
const res = []
const max = 2*n
const path = Array(max)
const dfs = ((sum,l)=>{
if(sum===max){
res.push(path.join(""))
return
}
if(l<n){
path[sum]='('
dfs(sum+1,l+1)
}
if(sum-l<l){
path[sum]=')'
dfs(sum+1,l)
}
})
dfs(0,0)
return res
}
|
46.全排列
array.slice (start, end)
若省略则为 0-end
JavaScript 中数组是引用类型
.slics 是一个 浅拷贝 操作
创建一个新的数组副本，并将这个副本加入到结果
本题如果写 res.push(path)：是将 path 的引用（而不是副本）push 到 res 中
初始状态：path = [], res = []。
第一次递归：
第二次递归：
选择 2，更新 path = [1, 2]。
当前路径长度等于数组长度，执行
- 此时，
res = [[1, 2]]，但 res[0] 是对 path 的引用。
回溯：
- 撤销选择
2，更新 path = [1]。
- 撤销选择
1，更新 path = []。
最终状态：
path = []，而 res 中存储的是对 path 的引用。- 因此，
res = [[], []]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| const permute = (nums) => {
const res = [];
const isused = {};
const dfs = (path) => {
if (path.length == nums.length) {
res.push(path.slice());
return;
}
for (const num of nums) {
if (isused[num]) continue;
path.push(num);
isused[num] = true;
dfs(path);
path.pop();
isused[num] = false;
}
}
dfs([]);
return res;
};
|
70.爬楼梯
1
2
3
4
5
| var climbStairs = function(n) {
const sqrt_5 = Math.sqrt(5);
const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
return Math.round(fib_n / sqrt_5);
};
|
78.子集
遍历树
dfs里的两种状态
不选 / 选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| var subsets = function(nums) {
const n = nums.length;
const ans = []
const path = []
function dfs(i) {
if (i === n) {
ans.push(path.slice());
return;
}
dfs(i + 1);
path.push(nums[i]);
dfs(i + 1);
path.pop();
}
dfs(0);
return ans;
};
|
94.二叉树中序遍历
先递归左子树，再访问根节点，接着递归右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var inorderTraversal = function (root) {
const ans = [];
const dfs = root => {
if (!root) {
return;
}
dfs(root.left);
ans.push(root.val);
dfs(root.right);
};
dfs(root);
return ans;
};
|
101.对称二叉树
1
2
3
4
5
6
7
8
9
| var isSymmetric = function(root) {
function isSameTree(p, q) {
if (p === null || q === null) {
return p === q;
}
return p.val === q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);
}
return isSameTree(root.left, root.right);
};
|
104.二叉树最大深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var maxDepth = function(root) {
let ans = 0;
const dfs = ((root,deep) => {
if (deep>ans)ans=deep
if (!root) {
return;
}
dfs(root.left,deep+1);
dfs(root.right,deep+1);
});
dfs(root, 0);
return ans;
};
|
136.只出现一次的数
异或 ^
a⊕0 = a
a⊕a = 0
满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
1
2
3
4
5
6
7
| var singleNumber = function(nums) {
let ans = 0
nums.forEach((num) => {
ans ^= num
})
return ans
};
|
148.排序链表（?）
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
|
function middleNode(head) {
let pre = head, slow = head, fast = head;
while (fast && fast.next) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
return slow;
}
function mergeTwoLists(list1, list2) {
const dummy = new ListNode();
let cur = dummy;
while (list1 && list2) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 ?? list2;
return dummy.next;
}
var sortList = function(head) {
if (head === null || head.next === null) {
return head;
}
let head2 = middleNode(head);
head = sortList(head);
head2 = sortList(head2);
return mergeTwoLists(head, head2);
};
|
153.旋转排序最小值
160.相交链表
初始化两个指针 p=headA, q=headB。不断循环，直到 p=q。
每次循环，p 和 q 各向后走一步。
如果 p 不是空节点，那么更新 p 为 p.next，否则更新 p 为 headB；
如果 q 不是空节点，那么更新 q 为 q.next，否则更新 q 为 headA。
循环结束时，如果两条链表相交，那么此时 p 和 q 都在相交的起始节点处，返回 p；
如果两条链表不相交，那么 p 和 q 都走到空节点，所以也可以返回 p，即空节点。
1
2
3
4
5
6
7
8
| var getIntersectionNode = function(headA, headB) {
let p = headA, q = headB;
while (p !== q) {
p = p ? p.next : headB;
q = q ? q.next : headA;
}
return p;
};
|
226.翻转二叉树
1
2
3
4
5
6
7
8
9
10
| var invertTree = function(root) {
if (root === null) {
return null;
}
const left = invertTree(root.left);
const right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
};
|
283.移动零
快慢双指针
解构赋值交换变量值 [a, b] = [b, a];
快指针位非0 => 交换
1
2
3
4
5
6
7
8
9
| var moveZeroes = function(nums) {
let i0 = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
[nums[i], nums[i0]] = [nums[i0], nums[i]];
i0++;
}
}
};
|
543.二叉树直径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| var diameterOfBinaryTree = function(root) {
let ans = 1;
function depth(rootNode) {
if (!rootNode) {
return 0;
}
let L = depth(rootNode.left);
let R = depth(rootNode.right);
ans = Math.max(ans, L + R + 1);
return Math.max(L, R) + 1;
}
depth(root);
return ans - 1;
};
|
