江月迟迟的个人知识库

外观

二刷HOT100笔记 ​

作者:江月迟迟
发表于:2025-10-29
字数统计:2748 字
预计阅读10分钟

1. 两数之和 ​

现在知道数据结构设计的重要性，如果找不出正确推断的方法然后设计一下map的格式：应存下标，取键应用target - nums[i]取，就会在这道题耗时。

49. 字母异位词分组 ​

在这一题中，仍然没有想到具体怎么解决这个问题，哈希表用的方式，一开始想到记录每个字符串的哈希表，然后进行比较，这个时候没有想到时间复杂度为O(n * m * n)，发现时间复杂度还是蛮高的。应该对每一个字符串进行sort之后比较即可。

128. 最长连续序列 ​

错误百出有点，在这里，我使用set去重，然而忘记遍历的使用用set了。这里对事件复杂度有点疑惑，最后写完代码的时候发现，只有起点会进入二层循环，所以总的时间复杂度是O(n)

283. 移动零 ​

这道题使用快慢指针，知道fast指针移动m次（m为非0元素的个数），slow和fast指针的内容交换位置

11. 盛最多水的容器 ​

这一道题知道是双指针解法，直接模拟就行，用贪心的思想发现指针移动方法应该是使得可能的损耗尽可能小，得到的收益尽可能大。

15. 三数之和 ​

这个三数之和想拿哈希做，结果做着做着绕进去了，因为有去重逻辑，都是数组，哈希表去重比较困难。最好的方法应该还是双指针

42. 接雨水 ​

又没做出来，再接再厉。

第二天做了，虽然写了一版单调栈的方法还是没直接想出来逻辑，那里退出之后因为它关注的是最后的一个，所以找到的答案是一行一行的，所以不能用一列一列的想法去加，这就是结合题目具体情况回答。一行一行就需要用一个乘法。不过现在熟悉了一下单调栈的模板，也是蛮好的

3. 无重复字符的最长子串 ​

如果知道这道题用滑动窗口就很简单。滑动窗口也有类似单调栈的化简方法，需要维护一个数据结构满足什么条件，就是让这个数据结构不满足这个条件的时候疯狂弹出一个元素，知道满足这个条件

438. 找到字符串中所有字母异位词 ​

需要识破这是滑动窗口，哈希可以拿来辅助。可以替代哈希的计数结构：map，arr（连续的或者有规则的）

560. 和为 K 的子数组 ​

确立关系，前面的不会影响后面的，所谓和为k的子数组，sum[i...j] = prefix[j] - prefix[i]，故：prefix[j] - prefix[i] === k，就是查找prefixMap.has(prefix[j] - k)是否存在

239. 滑动窗口最大值 ​

单调队列，其实和单调栈的维护差不多，单调栈维护单调递增可以找到下一个更大元素，单调栈维持单调递减可以找到下一个更小元素。单调队列也是，保持队列从队首到队尾单调递减，每次弹出队首（也是索引最小的元素），就是答案

76. 最小覆盖子串 ​

一开始没做出来，第二天发现左边界缩小条件应该是rc === c，然后移动就好了

53. 最大子数组和 ​

过于简单了

56. 合并区间 ​

有一个合不到，就加一个进去合

189. 轮转数组 ​

第一次交容易忘记k大于n的情况，这个时候需要k %= n，使得k比n小

238. 除自身以外数组的乘积 ​

这题把这些数字写出来发现prefix合subfix记录的是什么就行了，是不包括当前数字的前缀和后缀

41. 缺失的第一个正数 ​

这道题用原地哈希，确实想不出来，好难呀

73. 矩阵置零 ​

拿一个标记数组标记之后处理就行，两次for循环

54. 螺旋矩阵 ​

模拟法就行

48. 旋转图像 ​

这个也是模拟，写出表达式就行

240. 搜索二维矩阵 II ​

有序的二维数组搜索一般都是用，Z型搜索。一般都是从右上角开始搜索，一般都是优先向左判定（移动）

160. 相交链表 ​

并不是一定相交，所以指针可以移动到null上，或者我们理解成两个不相交的链表在尾部null上相交

206. 反转链表 ​

头插法

234. 回文链表 ​

用到了找链表中间节点和反转链表，然后head的链表的末尾是没有处理好的，我们确信了mid会弄到双数的n个或者单数的n+1个，就知道后面一定是长的，然后只需要使得mid在while循环退出即可

141. 环形链表 ​

快慢指针一定遇见

142. 环形链表 II ​

假设进环前的路程为 a，环长为 b。设慢指针走了 x 步时，快慢指针相遇，此时快指针走了 2x步。显然 2x-x=nb（快指针比慢指针多走了 n 圈），即 x=nb。也就是说慢指针总共走过的路程是 nb，但这 nb 当中，实际上包含了进环前的一个小 a，因此慢指针在环中只走了 nb-a 步，它还得再往前走 a 步，才是完整的 n 圈。所以，我们让头节点和慢指针同时往前走，当他俩相遇时，就走过了最后这 a 步。

21. 合并两个有序链表 ​

可以双指针迭代或者递归

24. 两两交换链表中的节点 ​

找到迭代表达式就行了，上一次迭代用的是3个，这一回自己写有点懵逼用了4个，但是能做出来就行。

25. K 个一组翻转链表 ​

模拟法硬做，确实很难。里面用了头插法翻转，然后在外面处理K个一组如何处理头尾节点。需要一个p0放在dummyHead来方便连接链表

138. 随机链表的复制 ​

很烧脑子，不太会

76. 最小覆盖子串 ​

又做了一次，现在没问题了，只要判断是滑动窗口类的，都可以套用我的思想。

146. LRU 缓存 ​

map在js中是有序的，可以利用这个特性，写出利用hashmap设计的LRU缓存，这就不需要维护双向链表或者最小堆

3066. 超过阈值的最少操作数 II ​

需要维护一个单调递增的数组，也就是小顶堆

101. 对称二叉树 ​

传入a.left，b.right即可

114. Flatten Binary Tree to Linked List ​

用变形的Morris遍历，所谓Morris遍历就是不使用额外指针空间，进行的遍历

105. Construct Binary Tree from Preorder and Inorder Traversal ​

这一题，知道中序遍历是比较有序的就可以做出来，用递归传入分割的数组

437. Path Sum III ​

这个想要用回溯做，然后一座发现不对劲，需要去重，而且去重逻辑用回溯这种局部的方法非常麻烦，比如说某节点不能记录多次，但是多个一样的节点可以被记录，就造成了困扰。所以应该用前缀和+回溯，最后用回溯处理多个一样的节点可以被记录的问题

236. Lowest Common Ancestor of a Binary Tree ​

最近公共祖先，就是利用后序遍历

200. Number of Islands ​

更改原数组，记录遍历后，以保证不会重复遍历

高手题解：二维数组遍历

https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-

695. Max Area of Island ​

和上一题一样，就是记录答案的逻辑有变化

827. Making A Large Island ​

两次遍历：第一次计算每个岛屿的面积。第二次：要连接两个不同的岛屿，就是找一个海水格子的附近有若干个不同的岛屿，将他们加起来：area = 岛A + 岛B + 岛C + 岛D + 1（加1是因为海水变成岛屿了）。 那么第二次：1.如果发现没有海水格子，那么输入的整个grid都是岛屿，直接返回。2.如果有海水格子，那么可以考虑使用上面的记录方法。岛需要判断是不是岛（grid[i+1][j] !== 0），岛需要判断是否相同：我首先使用一个area数组来记录不同的岛屿的索引和大小，然后再遍历的时候，使用一个set记录记录的岛的索引名字是否重复，达到记录不同岛屿的效果

463. Island Perimeter ​

还可以优化一下return的逻辑

994. Rotting Oranges ​

秒了宝宝

207. Course Schedule ​

第一次做，不太熟悉。这个就是要判断有没有环

208. Implement Trie (Prefix Tree) ​

So hard，QWQ

22. Generate Parentheses ​

嘿嘿，会做了。剪枝就好啦

79. Word Search ​

Easy

131. Palindrome Partitioning ​

这个就是几个函数的事情，分割的方法

3095. Shortest Subarray With OR at Least K I ​

我们总结滑动窗口题型的时候，会发现left弹出的操作那里，需要进行一次逆操作：比如加法的逆运算是减法，乘法的逆运算是除法，统计字符的数量（HashMap）需要把对应字符的数量相反操作。然而，或运算是没有逆运算的，所以我们使用一个数组记录窗口里出现的数字，然后重新运算（当然使用nums.slice也可以）

当数据量更大的时候n方没法过

这道题出的非常好； 一眼 sliding window, 但是 left 右移无法直接相减，本质上是因为 OR 不像加减乘除 没有逆运算 但是十进制转化为二进制数组 bits 表示之后，OR 的逆运算在 bits 中的表示就是减去每一位上面的1 -> 变成了有逆运算的加减

152. Maximum Product Subarray ​

状态转移的过程中，不能预知有多少个负号，未来还有多少个负号，未来的负号的数量能不能与当前的接上而成为子数组。所以需要用另一个Fmin状态转移，这个数组用来记录当前出现的最小值。对于Fmax，如果一个数字是正数，那么Fmax[i] = Fmax[i-1] * nums[i]，如果一个数字是负数，如果这是连续的第偶数个数字，那么Fmax[i] = Fmin[i-1] * nums[i]，如果这是连续的第奇数个数字那么Fmax[i] = nums[i]（因为往往Fmax记录正数，前面的和蛮大的，所以要截断一下）。所以Fmax = Math.max(Fmax[i-1] * nums[i], Fmin[i-1] * nums[i], nums[i])

139. Word Break ​

方法一：dp：dp[i]表示s的前i个字符，能不能满足题目要求：被分割，然后用一个双重循环遍历即可，复杂度是n方的，对于每一个判断如果dp[j]满足true，并且j -> i的字符串也是在那里中的，那么可以dp[i]就是true。这个非常精妙，就是运用了上一个的状态，每次添加一个字符串。

方法二：回溯。就是就是暴力分割。leetcode是否出现在leet, code中，就是判断leetcode\eetcode\etcode\tcode\code\ode\de\e是否出现在leet, code中，显然，这是从索引0开始的一次回溯，还有的回溯可能是：其他的，他们有可能从同一个索引开始出发，如果一个索引已经开始回溯过（并且没有答案），那么这个索引不需要再次回溯

62. Unique Paths ​

嘿嘿

64. Minimum Path Sum ​

哈哈

5. Longest Palindromic Substring ​

只会暴力，而且暴力效率还不高。。。

1143. Longest Common Subsequence ​

这个比之前的写得好，更新到那个题解中

js
var longestCommonSubsequence = function(text1, text2) {
    const dp = Array(text1.length+1).fill().map(() => Array(text2.length+1).fill(0))
    // dp[i][j] 代表t1的前i个和t2的前j个，的LCS问题
    for(let i = 1; i <= text1.length; i++) {
        for(let j = 1; j <= text2.length; j++) {
            if(text2[j-1] === text1[i-1]) {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[text1.length][text2.length]
};

72. Edit Distance ​

分析增和删的逻辑：互为逆操作，改的逻辑：先删后增。然后就回发现他们有状态转移方程饿了