Posts

LeetCode 94 https://leetcode.cn/problems/binary-tree-inorder-traversal/description/ 难度：简单 二叉树中序遍历的递归实现。 时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。 空间复杂度：O(n)。空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。 ...

LeetCode 199 https://leetcode.cn/problems/binary-tree-right-side-view/description/ 难度：中等 先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。 时间复杂度：O(n)，其中 n 是二叉树的节点个数。 空间复杂度：O(h)，其中 h 是二叉树的高度。递归需要 O(h) 的栈空间。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 4 https://leetcode.cn/problems/median-of-two-sorted-arrays/description/ 难度：困难 本题难度较大。 灵神题解：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/2950686/tu-jie-xun-xu-jian-jin-cong-shuang-zhi-z-p2gd/ 时间复杂度：O(logmin(m,n))，其中 m 是 a 的长度，n 是 b 的长度。注：这个复杂度比题目所要求的 O(log(m+n)) 更优。 空间复杂度：O(1)。 ...

LeetCode 82 https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/ 难度：中等 本题需要删除链表中所有重复数字的节点，只留下不同的数字。为了删除节点，cur 需要在要被删除的节点前面，因此比较 cur->next 和 cur->next->next 的节点值是否相同，如果相同，通过循环将所有等于这个值的节点都删除。否则，更新 cur 到下一个节点。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 1143 https://leetcode.cn/problems/longest-common-subsequence/description/ 难度：中等 LCS 线性 DP 问题，状态转移方程如下： if (s[i] == t[j]) { f[i + 1][j + 1] = f[i][j] + 1; } else { f[i + 1][j + 1] = max(f[i + 1][j], f[i][j + 1]); } 时间复杂度：O(nm)。 空间复杂度：O(nm)。 ...

LeetCode 19 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/ 难度：中等 前后指针，右节点先走 n 步，然后左右节点同时走。当右节点走到最后一个节点的时候，左节点就在删除节点的前一个节点。为了处理删除第一个节点的情况，设置 dummy 节点。 时间复杂度：O(m)，其中 m 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 142 https://leetcode.cn/problems/linked-list-cycle-ii/description/ 难度：中等 环形链表 II，比环形链表 I 多了需要找到入环节点。 设头节点到入环口需要走 a 步，环长为 c。快慢指针相遇时，慢指针走了 b 步，快指针走了 2b 步。设快指针比慢指针多走了 k 圈，即 2b - b = kc，得 b = kc。 慢指针在入环口开始，在环中走了 b - a = kc - a 步到达相遇点。这说明从相遇点开始，再走 a 步，就恰好到达相遇点。 如果让头节点和慢指针同时走，恰好 a 步后二者必定相遇，且相遇点就在入环口。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 93 https://leetcode.cn/problems/restore-ip-addresses/description/ 难度：中等 子集型回溯题目，本题使用“枚举选哪个”方法。 dfs(i, start) i 表示第几段，start 表示这一段从第几个数字开始。当选够 4 段且所有数字都被使用时添加答案。 如果 s[start] 为 0，这一段只能是 0，dfs(i + 1, start + 1)。 如果不是 0，这一段的数据范围需要在 [1, 255]之间，如果超过 255 就 break。 时间复杂度：\(O(3^N \times m)\)，m 为 s 的长度。 空间复杂度：O(N) ...

LeetCode 124 https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/ 难度：困难 这道题是树形 DP 中的直径 DP。枚举直径拐弯的位置，在每一个拐弯的位置更新答案，将以当前节点为根的链的最大路径和返回给父节点，如果路径和为负数返回 0。 边界条件是空节点的路径和为 0。 需要注意的是，更新答案的是直接的路径和，而返回的是链的路径和。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...

LeetCode 72 https://leetcode.cn/problems/edit-distance/description/ 难度：中等 这是线性 DP 的经典题目，类似 LeetCode 1143 最长公共子序列。 状态转移方程为： //word1[i] == word2[j] f[i + 1][j + 1] = f[i][j]; //word1[i] != word2[j] f[i + 1][j + 1] = min({f[i + 1][j], f[i][j + 1], f[i][j]}) + 1; 在不相等时，三种情况分别对应插入，删除，替换的情况。 此外，还要注意数组的初始化操作。 f[i + 1][0] = i + 1; f[0][j + 1] = j + 1; 时间复杂度：O(nm)，其中 n 为 word1 的长度，m 为 word2 的长度。 空间复杂度：O(nm)。 ...