之前的笔记中有更新过力扣的题目但都是按类型更新的做了代码随想录分类的题目这次是根据LeetCode热题100去做会有重复题目哈希1. 两数之和思路将每一项及对应的index存入map中使用map.get获取它对应的另一个加数的indexvar 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[i1]) continue; // 当前元素和下一个元素相当就不进行比较直接跳过 numArr.push(nums[i]); numMap.set(numArr, numArr.length); // 当前这一位和下一位不连续重新开始判断 if(nums[i] 1 ! nums[i1]) 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这里应该是right1减去左边界之前得到的那个元素和即可即可得到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[i1] curSum; } }; NumArray.prototype.sumRange function(left, right) { return resArr[right1] - resArr[left]; };思路1双重循环我最初的想法就是前一个元素和后一个元素相加和为k即可就count但测试用例nums[1, -1, 0]k0没有通过。我输出的结果是2期望结果是3。这时候才发现所谓的连续只要各个加起来是k1-10也是0所以期望结果为3的情况应该是1[1, -1] 2[0] 3[1, -1, 0]所以我构思了一个方法用i去遍历数组中的每一项用j去遍历i后面的项定义一个变量来存储当前的元素和去和k实时比较。如果当前和加上nums[ij]k就count否则就继续用j遍历后面的元素这里要注意不仅要保证jnums.length还要保证jinums.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[ij]; if(curSum k) count; } } return count; };但是这种方式的耗时会很长不是很优雅的解法。所以可以使用map来降低复杂度。思路2Map从第一个元素开始逐个加上后面的元素。只需要遍历一次即可得到当前元素与之前元素之和的总和。在遍历的过程中就不仅要看前缀和的区间还需要看其他的小区间我们得到k的方法就是用大区间0~right的前缀和减去小区间left~right的前缀和(left0leftright)进行位置互换就是用大区间减去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如果是第一次出现这个数字就 01。因为 Map 是个键值对集合此题是要根据出现次数大小排序因此根据 Map 中的valuekey 就是数字从大到小进行排序最后截取前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除了自己的所有人。定义一个 长度为 n1 的数组因为 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⊕a0 。将 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也是要消耗性能所以这里改用setvar 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; };