LeetCode Hot 100（JS版）

之前的笔记中，有更新过力扣的题目，但都是按类型更新的（做了代码随想录分类的题目），这次是根据LeetCode热题100去做，会有重复题目

哈希

1. 两数之和

思路

将每一项及对应的index存入map中，使用map.get获取它对应的另一个加数的index

var twoSum = function(nums, target) { let numMap = new Map(); let resArr = []; for(let i = 0; i < nums.length; i++) { if(numMap.has(target - nums[i])) { resArr.push(i, numMap.get(target - nums[i])); return resArr; } numMap.set(nums[i], i); } };

49. 字母异位词分组

思路

互为字母异位词的两个字符串包含的字母相同，对两个字符串分别进行排序之后得到的字符串一定是相同的，将排序之后的字符串作为哈希表的键，再使用map.get获取即可

var groupAnagrams = function(strs) { let wordList = []; let letterMap = new Map(); for(let i = 0; i < strs.length; i++) { let newStr = Array.from(strs[i]).sort().toString(); if(letterMap.get(newStr)) { wordList = letterMap.get(newStr) // 先拿到之前存储的值 } else { wordList = []; // 创建一个新的字母组合数组 } wordList.push(strs[i]); letterMap.set(newStr, wordList); } return Array.from(letterMap.values()); };

128. 最长连续序列

思路

如果当前元素是否和下一个元素相等，跳过当前元素。

比较当前元素是否和下一个元素连续，如果不连续就重新开始判断。（判断的截止条件）

var longestConsecutive = function(nums) { let sortArr = nums.sort((a, b) => a - b); let numMap = new Map(); let numArr = [], max = 0; for(let i = 0; i < nums.length; i++) { if(nums[i] == nums[i+1]) continue; // 当前元素和下一个元素相当，就不进行比较，直接跳过 numArr.push(nums[i]); numMap.set(numArr, numArr.length); // 当前这一位和下一位不连续，重新开始判断 if(nums[i] + 1 !== nums[i+1]) numArr = []; } for(let [key, value] of numMap.entries()) { if(value >= max) max = value; } return max; };

双指针

283. 移动零

他们都会用到一个交换元素的方法

var swapNumber = function(nums, left, right) { let temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; return nums; }

思路一：交换位置

遍历数组，将当前不是0的数字与0交换位置，将0都换到后面去，以两个示例来说：

[0, 1, 0, 3, 12]

[1, 0, 2, 0, 3, 0]

var moveZeroes = function(nums) { let left = 0, right = 0; for(let i = 0; i < nums.length; i++) { if(nums[i] !== 0) { right = i; swapNumber(nums, left, right); left++; } } };

思路二：非0元素偏移

遇到几个0，就说明下一个非0元素需要向左偏移几位。将当前的非0元素，与第一位0元素交换位置。

var moveZeroes = function(nums) { let offset = 0; for(let i = 0; i < nums.length; i++) { if(nums[i] == 0) { offset++; // 遇到0就增加一个偏移量，让非0元素向左偏移 } if(nums[i] !== 0) { // 当前非0元素与第一个0元素交换位置 swapNumber(nums, i, i-offset); } } };

11. 盛最多水的容器

思路

根据题目中给出的图来看，我们要求的就是某个区间组成的面积最大值，并且两条线的高度要取较小的那条（因为取大的那条边，水会溢出来） ，左指针从0开始，右指针从末尾开始。

一开始我是使用嵌套for循环写的，会超时！！

因为我想把每个区间的面积都求出来，再去取最大值，这样不是很优雅。

var maxArea = function(height) { let max = 0, curWeight = 0; for(let left = 0; left < height.length; left++) { for(let right = height.length - 1; right > 0; right--) { curWeight = Math.min(height[left], height[right]) * (right - left); if(curWeight > max) max = curWeight; } } return max; };

因此，我们应该思考一个优化点，就是如果index本身就很小的那个元素（比右边小），我们要跳过这一位，也就是left++，同理right--，这样就会大大减少比较和计算的次数。

var maxArea = function(height) { let max = 0, curWeight = 0; let left = 0, right = height.length - 1; while(left < right) { curWeight = Math.min(height[left], height[right]) * (right - left); if(curWeight > max) max = curWeight; if(height[left] < height[right]) left++; else right--; } return max; };

子串

560. 和为 K 的子数组

前置题目—加深前缀和的理解

303. 区域和检索 - 数组不可变

这道题是因为我在写560的时候一直不理解在定义前缀和数组的时候，为什么要在第一位定义一个0。这是因为在做right-left这个运算的时候，在left为0时会出现越界的情况，因此要在前面补充一位。

思路

遍历数组，将当前元素 加上 前面所有元素之和 存入前缀和数组中，在计算每对range的时候，只需要用right这一位（因为数组第一位补充了一个0，这里应该是right+1）减去左边界之前得到的那个元素和即可，即可得到range中各个元素的和。描述的太绕，画个图：

let resArr = []; var NumArray = function(nums) { let len = nums.length; resArr = new Array(len + 1).fill(0); let curSum = 0; for(let i = 0; i < nums.length; i++) { curSum += nums[i]; resArr[i+1] = curSum; } }; NumArray.prototype.sumRange = function(left, right) { return resArr[right+1] - resArr[left]; };

思路1：双重循环

我最初的想法就是前一个元素和后一个元素相加和为k即可就count++，但测试用例nums=[1, -1, 0]，k=0没有通过。我输出的结果是2，期望结果是3。这时候才发现，所谓的连续，只要各个加起来是k，1-1+0也是0，所以期望结果为3的情况应该是：1）[1, -1] 2）[0] 3）[1, -1, 0]

所以我构思了一个方法：用i去遍历数组中的每一项，用j去遍历i后面的项，定义一个变量来存储当前的元素和去和k实时比较。如果当前和加上nums[i+j]==k就count++；否则就继续用j遍历后面的元素，这里要注意不仅要保证j<nums.length，还要保证j+i<nums.length。

var subarraySum = function(nums, k) { let count = 0; let curSum = 0; if(nums.length == 1 && nums[0] !== k) return 0; for(let i = 0; i < nums.length; ++i) { curSum = nums[i]; if(curSum == k) count++; for(let j = 1; j < nums.length && j + i < nums.length; ++j) { curSum += nums[i+j]; if(curSum == k) count++; } } return count; };

但是这种方式的耗时会很长，不是很优雅的解法。所以可以使用map来降低复杂度。

思路2：Map

从第一个元素开始，逐个加上后面的元素。只需要遍历一次即可得到当前元素与之前元素之和的总和。在遍历的过程中，就不仅要看前缀和的区间，还需要看其他的小区间，我们得到k的方法就是用大区间（0~right的前缀和）减去小区间（left~right的前缀和(left>=0&&left<=right)），进行位置互换就是用大区间减去k得到小区间（curSum-k），去查找是否在map中已经存在有这个小区间，如果存在count在当前次数基础上增加。

var subarraySum = function(nums, k) { let count = 0; let countMap = new Map(); let curSum = 0; countMap.set(0, 1); for(let i = 0; i < nums.length; i++) { curSum += nums[i]; if(countMap.has(curSum - k)) { count += countMap.get(curSum - k); } if(countMap.has(curSum)) countMap.set(curSum, countMap.get(curSum) + 1); else countMap.set(curSum, 1); } return count; };

普通数组

​​​​​​53. 最大子数组和

思路

遍历数组中的item，依次相加，只要出现负数就清0重新相加；如果当前的和大于max，就更新最大值

var maxSubArray = function(nums) { let max = -Infinity, sum = 0; for(let i = 0; i < nums.length; i++) { sum += nums[i]; if(sum > max) max = sum; if(sum < 0) sum = 0; } return max; };

347. 前 K 个高频元素

思路

这里使用 Map，遍历数组中的 item，将当前的数字及它的出现次数 set 到 Map 中，如果这个数字已经存在于 Map 中，就 .get(num) 并 +1；如果是第一次出现这个数字就 0+1。因为 Map 是个键值对集合，此题是要根据出现次数大小排序，因此根据 Map 中的value（key 就是数字）从大到小进行排序，最后截取前k个即可

var topKFrequent = function(nums, k) { const numsMap = new Map(); for(const num of nums) { numsMap.set(num, (numsMap.get(num) || 0) + 1); } const sorted = [...numsMap].sort((a, b) => b[1] - a[1]); const res = sorted.slice(0, k).map(([num]) => num); return res; };

二叉树

前置题目—二叉树操作

112. 路径总和

思路

二叉树的题目大部分都使用递归。如果当前节点存在，就与当前路径和相加，直到叶子节点；

如果某一路径的和不等于目标值，会回退至上一节点的右节点继续相加

var hasPathSum = function(root, targetSum) { return checkNode(root, targetSum, 0); }; const checkNode = (root, target, curSum) => { if(root == null) return false; curSum += root.val; if (root.left !== null || root.right !== null) { return checkNode(root.left, target, curSum) || checkNode(root.right, target, curSum) } return curSum == target; }

前置题目—二叉树指向问题

116. 填充每个节点的下一个右侧节点指针

思路

左子节点的 next 指向右子节点，右子节点的 next 指向下一个兄弟节点的左子节点，每个节点都默认为null，因此无需赋值，只需要将左右子树连接即可

var connect = function(root) { if (!root) return null; if (root.left) { root.left.next = root.right; if (root.next) { root.right.next = root.next.left; } } connect(root.left); connect(root.right); return root; };

图论

997. 找到小镇的法官

思路

这里我是用图论，法官的出度为0（不信任任何人），入度为 n-1（除了自己的所有人）。

定义一个 长度为 n+1 的数组，因为 trust 数组中的第一个人是1而不是0。

以 trust = [[1,3],[2,3]] 为例，trustCount 就是 [0, 0, 0, 0]

以 [a, b] 形式去遍历 trust 就可以遍历到每一个人，如果这个人被信任，那么这个人的入度增加（trustCount[b]++）；如果这个人信任别人，那么这个人的出度增加（trustCount[a]--）。

最终只要找 trustCount 数组中与 n-1 相等的那个 item 即可。

var findJudge = function(n, trust) { if(n === 1 && trust.length === 0) return 1; const trustCount = new Array(n + 1).fill(0); for(let [a, b] of trust) { trustCount[a]--; trustCount[b]++; } for(let i = 1; i <= n; i++) { if(trustCount[i] == n - 1) return i; } return -1; };

技巧

31. 下一个排列

前置题目—便于理解全排列

46. 全排列

思路

将每个元素依次放入结果数组中，得到不同的排序方式，每放入一个元素时就要将这个元素标记为已使用，防止重复放置这个元素。这里是使用回溯的方式，push完一个元素就要再进行下一个元素的设置，直到元素都被放置完成。此时就将数组中的元素pop（想象成栈，将顶部元素拿出），再次进行下一次的循环。

resArr.push(Array.from(path));这里需要重新定义一个数组放入resArr中，否则在path.pop()的时候会影响到push传入的结果。

var permute = function(nums) { let resArr = [], path = []; backTracking(nums, nums.length, []); return resArr; function backTracking(nums, len, used) { if(path.length === len) { // 说明此时已经都排列完了 resArr.push(Array.from(path)); return; } for(let i = 0; i < len; i++) { if(used[i]) continue; path.push(nums[i]); used[i] = true; backTracking(nums, len, used); path.pop(); used[i] = false; } } };

思路

var nextPermutation = function(nums) { let i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i >= 0) { let j = nums.length - 1; while (nums[j] <= nums[i]) { j--; } [nums[i], nums[j]] = [nums[j], nums[i]]; } let left = i + 1, right = nums.length - 1; while (left < right) { [nums[left], nums[right]] = [nums[right], nums[left]]; left++; right--; } return nums; };

75. 颜色分类

思路

这里我一开始是想使用双指针去做，但是感觉越想越复杂，突然发现上面经常用到次数统计，这也是一个突破口，也就是说我去记录每个元素出现的次数，然后将对应颜色根据次数的大小填充到这个数组中即可。

var sortColors = function(nums) { let red = 0, white = 0, blue = 0; for(let i = 0; i < nums.length; i++) { switch(nums[i]) { case 0: red++; break; case 1: white++; break; case 2: blue++; break; } } nums.fill(0, 0, red).fill(1, red, red + white).fill(2, red + white); };

136. 只出现一次的数字

思路

此题要求实现线性时间复杂度，且只使用常量额外空间。也就是说时间复杂度是O(n)，空间复杂度O(1)。我在没有考虑空间复杂度的情况下，想到的是使用Map，将每个元素及其出现的次数存储，再判断哪个元素的出现次数是1。

var singleNumber = function(nums) { let numMap = new Map(); for(let i = 0; i < nums.length; i++) { if(numMap.has(nums[i])) numMap.set(nums[i], numMap.get(nums[i])+1) else numMap.set(nums[i], 1) } for (let [key, value] of numMap.entries()) { if (value === 1) return key; } };

但为了满足空间复杂度为O(1)，这里就不能定义Map了，只能在当前数组上进行操作。了解到使用异或这种方式。 异或运算中，两个相同数字异或为 0 ，即对于任意整数 a 有 a⊕a=0 。将 nums 中所有元素执行异或，就可以得到出现一次的元素。

var singleNumber = function(nums) { let temp = 0; for(let i = 0; i < nums.length; i++) { temp ^= nums[i]; } return temp; };

169. 多数元素

思路

将每个元素及其出现次数存入Map中，并且在存入之前判断当前次数是否已经大于nums.length/2，如果大于就直接返回，否则就存入。

var majorityElement = function(nums) { let numMap = new Map(); let temp = 0; for(let i = 0; i < nums.length; i++) { if(numMap.has(nums[i])) { temp = numMap.get(nums[i])+1; if(temp > nums.length / 2) return nums[i]; numMap.set(nums[i], temp); } else numMap.set(nums[i], 1) } return nums[0]; };

287. 寻找重复数

思路

只需要将元素存储起来，再去查找是否已经存在，存在就返回。这里一开始我用map，但是用map就需要存value，也是要消耗性能，所以这里改用set

var findDuplicate = function(nums) { let numMap = new Set(); for(let i = 0; i < nums.length; ++i) { if(numMap.has(nums[i])) { return nums[i]; } numMap.add(nums[i]); } return 0; };