代码随想录

我目前是参考代码随想录的题单来做题的，因为还有学业上的 task，可能有点三天打鱼两天晒网（逃

数组

刚开始都是些比较基础的练习，没啥特别值得记下来的我就不多写了。

704. 二分查找

27. 移除元素

这题我有点偷懒，用了std::vector的容器迭代器和erase()方法，代码如下。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        for (auto it = nums.begin(); it != nums.end();) {
            if ((*it) == val) nums.erase(it);
            else ++it;
        }
        return nums.size();
    }
};

值得一提的是，调用erase()的时候，会改变容器迭代器，所以不需要使指针向前移动一位。这个我是从大二上学期 SEP 某次 Debug Lab 中所设置的一个小 trick 中知道的。

这题的另一种做法是双指针法，慢指针指向新数列的尾部，快指针遍历整个数列，最后返回慢指针的位置即可。

977. 有序数组的平方

还是偷懒了，遍历之后直接调用了std::sort()。

209. 长度最小的子数组

我对滑动窗口的熟悉程度挺低的，正好重温一下它的经典题目。

59. 螺旋矩阵 II

链表

这里的链表定义中的头结点都用来存放元素了，这让我觉得操作起来特别麻烦，我个人的习惯是头结点不放元素。在做链表题时，我尝试了直接操作和定义一个虚拟的头结点，感觉还是后者用起来更方便。

203. 移除链表元素

707. 设计链表

206. 反转链表

大一上学期的程设课有写过反转链表的算法，当时我采取的方法是遍历后一个个转过来，最后在把头指针指向原来的最后一个元素。后来听同学说他们老师讲的一种方法是遍历时不断地把下一个插到头部，不过我当时并没有再去写一次，这次正好写写这个方法试试。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return head;
        ListNode *p = head;
        while (p->next) {
            ListNode *q = p->next;
            p->next = q->next;
            q->next = head;
            head = q;
        }
        return head;
    }
};

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

我的做法是单独操作了头部的两个节点。

19. 删除链表的倒数第 N 个结点

也是程设课上学到的快慢指针法，定义一个的虚拟的头结点操作起来要方便得多。

160. 相交链表

142. 环形链表 II

这两题都是看了解答才学会的方法qwq

哈希表

242. 有效的字母异位词

这题用了哈希表的思想。初始化一个长度为26的全零数组，遍历s中的每个字母，在对应位置上+1。然后遍历t，在对应位置上-1。最后查找整个数组有没有非零项即可。

349. 两个数组的交集

又是没有用过的数据结构，这题使用了std::unordered_set，它是基于哈希表实现的。与之相关的还有std::set和std::multiset，这二者是基于红黑树实现的，区别在于后者存储的数据可重复。此外，std::unordered_set是无序的，而std::set和std::multiset是有序的。

202. 快乐数

把一个数的各个数位平方后求和得到一个新数，一直这么做下去，如果最终得到1，那么这个数就是快乐数，否则会陷入无限循环。给定一个数，要判断它是不是一个快乐数，可以把每次操作后得到的新数都放入一个哈希表中，一旦出现了重复的数字，就说明它不是一个快乐数。

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> appeared;
        while (!appeared.contains(n)) {
            appeared.insert(n);
            int sum = 0;
            while (n) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            if (sum == 1) return true;
            n = sum;
        }
        return false;
    }
};

1. 两数之和

用哈希表std::unordered_map存储已经访问过的数组元素及其下标，提高插入和查询的效率。

454. 四数相加 II

遍历前两个数组，用std::unordered_map存储前两个数组中每种和出现的次数，用一个变量存储符合条件的个数，遍历后两个数组，判断哈希表里是否有后两个数组中每种和的相反数，有的话就在变量上加上它的次数

383. 赎金信

和有效的字母异位词类似。

15. 三数之和

这题使用双指针法比哈希法更加高效，代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
 
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) --right;
                else if (nums[i] + nums[left] + nums[right] < 0) ++left;
                else {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums [left + 1]) ++left;
                    while (left < right && nums[right] == nums[right - 1]) --right;
                    ++left;
                    --right;
                }
            }
        }
        return ans;
    }
};

需要注意的是其中去重的方式，如果遍历时该元素和上一个元素相同，说明这种情况已经被处理过了，直接跳过。

18. 四数之和

和三数之和的做法类似，但是要多嵌套一层循环，时间复杂度也会提高一个数量级。以及由于目标和不再是0而是 target，判断跳过的标准也需要做出一点点小修改。

类似地， $k$ 数之和都可以采取这样的做法，时间复杂度为 $O(n^{k - 2})$ 。

字符串

344. 反转字符串

双指针法，从头尾向中间遍历，逐个交换。

541. 反转字符串 II

151. 反转字符串中的单词

我的做法是遍历整个字符串，把每个单词起始和终止索引都存起来，然后再倒着把它们拼在一起，代码如下：

class Solution {
public:
    string reverseWords(string s) {
        vector<pair<int, int>> tmp;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] != ' ') {
                int j = i;
                while (j < s.length() && s[j] != ' ') ++j;
                tmp.push_back({i, j});
                i = j;
            }
        }
 
        string res = "";
        for (auto it = tmp.rbegin(); it != tmp.rend(); ++it)
            res += s.substr(it->first, it->second - it->first) + " ";
        if(res != "") res.erase(res.end() - 1);
        return res;
    }
};

28. 找出字符串中第一个匹配项的下标

采用经典的 KMP 算法，当然我是现学的。

首先是next数组的计算，以i作为后缀指针，j作为前缀指针，如果当前前后缀指向不同，则前缀一直回退到和后缀相同的为止，否则就向前移动一位指针。

接着就是在文本串中匹配模式串，以i作为文本串指针，j作为模式串指针，如果指向不同，则把模式串指针回退到相同的为止，否则同样向前移动一位指针，当j指向模式串的最后一位时，说明找到了匹配的子串。

class Solution {
public:
    vector<int> buildNext(const string &needle) {
        int j = -1;
        vector<int> next(needle.length());
        next[0] = j;
        for (int i = 1; i < next.size(); ++i) {
            while (j != -1 && needle[j + 1] != needle[i]) j = next[j];
            if (needle[j + 1] == needle[i]) ++j;
            next[i] = j;
        }
        return next;
    }
 
    int strStr(string haystack, string needle) {
        if (needle.length() == 0) return 0;
 
        vector<int> next = buildNext(needle);
        int j = -1;
        for (int i = 0; i < haystack.length(); ++i) {
            while (j != -1 && needle[j + 1] != haystack[i]) j = next[j];
            if (needle[j + 1] == haystack[i]) ++j;
            if (j == needle.length() - 1) return i - j;
        }
        return -1;
    }
};

459. 重复的子字符串

把字符串和它本身拼接在一起再去掉首尾的两个字符得到一个新字符串，如果原字符串是新字符串的子串，则原字符串可以由它的一个子串重复多次构成。

这题还可以用 KMP 算法解决：

设字符串s的长度为n，计算得s的next[n]数组；
如果next[n - 1] != -1，说明有公共前后缀；
此时再判断n - next[n - 1] + 1（即循环周期的长度）是否能整除n即可。

栈与队列

232. 用栈实现队列

225. 用队列实现栈

这两题感觉挺简单的，就偷懒没写了，原理都是用两个已有的数据结构来处理待实现的数据结构。

20. 有效的括号

栈的经典应用，遇到一个左括号就进栈，遇到一个右括号就判断栈顶是否与之匹配，如此遍历完后再判断栈是否为空。

1047. 删除字符串中的所有相邻重复项

逐一判断字符串中的所有字符，如果与栈顶的字符不同（或栈为空）则进栈，否则使栈顶字符出栈。最后再把栈中字符逐一拼到一个空字符串的头部。

150. 逆波兰表达式求值

大一数据结构课上讲过，当有数字时进栈，当有运算符时取出栈顶的两个数字计算后把结果压栈，最后返回栈中剩下的最后一个数即可。

239. 滑动窗口最大值

单调队列的经典题目，用std::deque作为单调队列的底层容器，入队时，从队尾移除所有破坏单调性的元素；出队时，判断队首元素是否符合条件。遍历整个数组，每次都取出队首元素即是符合条件的一组滑动窗口最大值。

class Solution {
public:
    struct MonotonicQueue {
        deque<int> queue;
    
        void push(int value) {
            while (!queue.empty() && queue.back() < value)
                queue.pop_back();
            queue.push_back(value);
        }
 
        void pop(int value) {
            if (!queue.empty() && queue.front() == value)
                queue.pop_front();
        }
 
        int top() { return queue.front(); }
    } monotonic_queue;
 
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
 
        for (int i = 0; i < k; ++i)
            monotonic_queue.push(nums[i]);
        res.push_back(monotonic_queue.top());
        
        for (int i = 0; i < nums.size() - k; ++i) {
            monotonic_queue.pop(nums[i]);
            monotonic_queue.push(nums[i + k]);
            res.push_back(monotonic_queue.top());
        }
 
        return res;
    }
};

347. 前 K 个高频元素

先用一个std::unordered_map存放每个元素出现的次数，再维护一个大小为k的小顶堆，小顶堆内最后剩下的就是待查的元素集合了。

std::priority_queue在 LSM-tree 里已经写过好几次了，属于是比较熟悉的部分。

二叉树

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

这三题都用了两种做法，一种是普通的递归，另一种是迭代。

三种遍历方式的迭代又有些不同，最简单的是前序遍历。中序遍历则需要先在循环中访问到最左边的节点。后序遍历类似于前序遍历，最后需要把结果做个反转。

102. 二叉树的层序遍历

用一个队列存放每层的节点，处理每一层时都把当次取出的节点的左右子节点入队。

107. 二叉树的层序遍历 II

把上一题的结果做个反转即可，或者用一个链表存，每次在头部插入。

199. 二叉树的右视图

637. 二叉树的层平均值

这两题和层序遍历的做法都类似，右视图只需要每层都拿队尾元素。

429. N 叉树的层序遍历

515. 在每个树行中找最大值

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

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

每一层的最右侧节点需要单独处理。

104. 二叉树的最大深度

111. 二叉树的最小深度

这两题都可以用递归或者层序遍历的方式解决。值得注意的一点是，用求最小深度时，只有左右孩子都为空时才能算是叶子结点（一棵完整的子树）。

226. 翻转二叉树

递归交换每个节点的左右子节点。

101. 对称二叉树

还是用递归的方法，代码如下：

class Solution {
public:
    bool isSym(TreeNode* left, TreeNode* right) {
        if (!left && !right) return true;
        if (left && !right) return false;
        if (!left && right) return false;
        return left->val == right->val && isSym(left->left, right->right) && isSym(left->right, right->left);
    }
    
    bool isSymmetric(TreeNode* root) {
        return root ? isSym(root->left, root->right) : true;
    }
};

222. 完全二叉树的节点个数

110. 平衡二叉树

都是递归。

257. 二叉树的所有路径

采用递归的方式，我的做法是把遍历到的节点值加入到传入的字符串末尾，然后判断当前节点是否是叶子结点，如果是，就把这个字符串存入（以引用方式传入的）数组中。

404. 左叶子之和

深度优先遍历，传入一个是否为左子结点的标记，代码如下：

class Solution {
public:
    void dfs(TreeNode* node, bool is_left, int &sum) {
        if (!node) return;
 
        if (is_left && !node->left && !node->right) {
            sum += node->val;
            return;
        }
 
        dfs(node->left, true, sum);
        dfs(node->right, false, sum);
    }
 
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        dfs(root, false, sum);
        return sum;
    }
};

513. 找树左下角的值

前一阵子从期末周一直忙到小学期结束，已经整整一个多月没写 LeetCode 了，最近准备复健一下，发现好多东西都忘了。

用层序遍历的思路，更新result为每一层第一个节点的值即可。

HOT 100

面字节后端前准备一周极限速通 HOT 100

49. 字母异位词分组

用一个std::unordered_map<string, vector<string>>来存储同组的词，用排序后的字符串作为 key。

128. 最长连续序列

用一个哈希表来存放所有数字，遍历哈希表的每个元素，如果某个元素的前一个元素在哈希表中，则跳过，否则找到从该元素起始的最长序列。

283. 移动零

快慢指针，快指针每读到一个非零数，就填充到慢指针的位置上。

11. 盛最多水的容器

左右指针，每次都把高度低的那个指针往中间移动，更新最大面积。

42. 接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) res += leftMax - height[left++];
            else res += rightMax - height[right--];
        }
        return res;
    }
};

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

滑动窗口，维护一个哈希表，如果即将加入的下一个字符在哈希表中，就把窗口左边一直缩减到不重复的位置。

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

滑动窗口，维护一个长度为 26 的数组，每个位置用来存放当前窗口内各个字母的数量，每滑动一个位置就进行一次比较。

560. 和为 K 的子数组

用一个std::unordered_map<int, int>来存所有出现过的前缀和的次数，遍历得到所有前缀和的同时，判断某个已出现过的前缀和是否符合条件，若是则叠加上对应的次数。

76. 最小覆盖子串

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> map;
        for (char c : t) ++map[c];
 
        int cnt = map.size();
        int left = 0, right = 0;
        int start = -1, end = -1, len = INT_MAX;
        while (right < s.length()) {
            if (cnt != 0 && map.contains(s[right]))
                if (--map[s[right]] == 0)
                    --cnt;
 
            while (cnt == 0) {
                if (len > right - left + 1) {
                    end = right;
                    start = left;
                    len = end - start + 1;
                }
 
                if (map.contains(s[left]))
                    if (++map[s[left]] > 0)
                        ++cnt;
 
                ++left;
            }
 
            ++right;
        }
 
        return end == -1 ? "" : s.substr(start, len);
    }
};

146. LRU 缓存

哈希表 + 双向链表，用哈希表以 $O(1)$ 的时间定位到节点，每次查找 / 插入后把节点移到表头。

53. 最大子数组和

动态规划，状态转移方程为 $f(i) = \max\{f(i - 1) + nums[i], nums[i]\}$ 。

56. 合并区间

先按区间左端点排序，然后逐个判断是能合并的区间还是另起的区间。

189. 轮转数组

先反转整个数组，然后分别反转数组的前 $k \mod size$ 个数和后面的数。

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

由于不允许用除法，用两个数组分别保存每个位置上的数字所有左边数字的乘积和所有右边数字的乘积。

41. 缺失的第一个正数

如果nums[i]在区间 $[1, n]$ 内，那么它理应处于nums[nums[i] - 1]的位置上，遍历一次数组，把所有数字都交换到它理应处在的位置上。完成该操作后，再遍历一次数组，找到第一个满足nums[i] != i + 1的数即为所求。

73. 矩阵置零

54. 螺旋矩阵

48. 旋转图像

240. 搜索二维矩阵 II

234. 回文链表

141. 环形链表

21. 合并两个有序链表

2. 两数相加

25. K 个一组翻转链表

70. 爬楼梯

118. 杨辉三角

198. 打家劫舍

279. 完全平方数

动态规划，创建一个长度为 $n + 1$ 的数组dp。dp[i]表示和为 $i$ 的完全平方数的最少数量。对于每个 $i$ ，遍历所有满足 $j^2 \le i$ 的 $j$ ，找到最小的dp[i - j * j]再加一即为dp[i]。

322. 零钱兑换

136. 只出现一次的数字

由于 异或运算 满足以下三条性质：

任何数和 0 的做异或仍为自己；
任何数和自己做异或结果为 0；
交换律和结合律。

因此，可以对数组中全部的数做异或，即得唯一剩下的数。

139. 单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        for (auto word : wordDict) dict.insert(word);
 
        int len = s.length();
        vector<bool> dp(len + 1);
        dp[0] = true;
        for (int i = 1; i <= len; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.contains(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
 
        return dp[len];
    }
};

300. 最长递增子序列

152. 乘积最大子数组

动态规划，遍历的同时要存储当前乘积的最小值，因为最小值有可能乘以某个负数后变成最大值。

138. 随机链表的复制

用一个哈希表储存每个节点对应的新节点的创建情况，遍历时若遇到还未创建的节点，则立即创建，最后回溯。

class Solution {
public:
    unordered_map<Node *, Node *> link_list;
 
    Node* copyRandomList(Node* head) {
        if (head == NULL) return NULL;
 
        if (!link_list.count(head)) {
            Node *node = new Node(head->val);
            link_list[head] = node;
            node->next = copyRandomList(head->next);
            node->random = copyRandomList(head->random);
        }
 
        return link_list[head];
    }
};

23. 合并 K 个升序链表

用一个小顶堆来存放每个链表的头结点，当堆顶被弹出时，将堆顶的下一个元素压入堆中，直到所有链表的所有节点都被处理完。

543. 二叉树的直径

递归遍历每个节点的深度，同时计算该节点左右子树高度和并更新res。

416. 分割等和子集

让 DeepSeek 给了一个解法：

计算总和：先算出数组中所有数字的总和 S。如果 S 是奇数，直接返回 false。
设定目标：如果 S 是偶数，设目标值 target = S / 2。
初始化 dp 数组：创建一个长度为 target + 1 的布尔数组 dp，初始时只有 dp[0] 为 true，其他都是 false。这表示一开始只能拼出和 0。
遍历每个数字：对于数组中的每个数字 num，我们从 target 开始向下遍历到 num（包括 num），更新 dp 数组：
- 对于每个位置 j，如果 j - num 这个和可以被拼出来（即 dp[j - num] 为 true），那么加上当前数字 num，就可以拼出和 j，所以设置 dp[j] = true。
- 为什么从后往前遍历？这是为了避免重复使用同一个数字。如果从前往后遍历，一个数字可能会被多次使用，但这里每个数字只能用一次。
检查结果：最后，如果 dp[target] 为 true，说明可以拼出目标值，返回 true；否则返回 false。
以 nums = [1, 5, 11, 5] 为例：
- 总和 S = 22，是偶数，target = 11。
- 初始化 dp = [true, false, false, ..., false]（长度 12，索引 0 到 11）。
- 处理数字 1：
  - 从 j=11 到 1，更新 dp：dp[1] 变为 true（因为 dp[0] 为 true）。
- 处理数字 5：
  - 从 j=11 到 5，更新 dp：dp[5] 变为 true（因为 dp[0] 为 true），dp[6] 变为 true（因为 dp[1] 为 true）。
- 处理数字 11：
  - 从 j=11 到 11，更新 dp：dp[11] 变为 true（因为 dp[0] 为 true）。
- 现在 dp[11] 为 true，所以返回 true。

代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;
        
        int sum = 0;
        for (const auto &num : nums) sum += num;
        if (sum % 2) return false;
        
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (const auto &num : nums) {
            for (int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
 
        return dp[target];
    }
};

32. 最长有效括号

动态规划，用一个std::vector<int> dp(s.length())存储字符串s中每个位置对应的最长有效括号子串的长度，最后返回数组中最大数即可。如果s[i] == '('，那么dp[i]一定是 0；如果s[i] == ')'，状态转移方程如下：

如果s[i - 1] == '('，那么dp[i] = dp[i - 2] + 2；
如果s[i - 1] == ')'，那么只有在s[i - dp[i - 1] - 1] == '('时，dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2。

每日一题

1930. 长度为 3 的不同回文子序列

对于 26 个字母，均从左右开始遍历找到首个，然后判断它们之间有几个不同的字母，累加到答案上。

我的 LeetCode 解题记录

代码随想录

数组

链表

哈希表

字符串

栈与队列

二叉树

HOT 100

每日一题