LeetCode 14 https://leetcode.cn/problems/longest-common-prefix/description/ 难度：简单 从左到右遍历 strs 的每一列。 设当前遍历到第 j 列，从上到下遍历这一列的字母。 设当前遍历到第 i 行，即 strs[i][j]。如果 j 等于 strs[i] 的长度，或者 strs[i][j] != strs[0][j]，说明这一列的字母缺失或者不全一样，那么最长公共前缀的长度等于 j，返回 strs[0] 的长为 j 的前缀。 如果没有中途返回，说明所有字符串都有一个等于 strs[0] 的前缀，那么最长公共前缀就是 strs[0]。 时间复杂度：O(nm)，其中 n 为 strs 的长度，m 为 strs 中最短字符串的长度。 空间复杂度：O(1)。返回值不计入。 ...
LeetCode 234 https://leetcode.cn/problems/palindrome-linked-list/description/ 难度：简单 本题需要用到两个知识点，寻找链表的中间节点和反转链表。 首先找到链表的中间节点，然后反转链表的后半段。最后，同时遍历这两段链表，判断值是否相等。 时间复杂度：O(n)，其中 n 是链表的长度（节点个数）。 空间复杂度：O(1)。 ...
LeetCode 98 https://leetcode.cn/problems/validate-binary-search-tree/description/ 难度：中等 使用中序遍历验证二叉搜索树，比较当前节点与上一个节点的值的大小。需要注意的是，为了处理节点值为 INT_MIN 的情况，pre 需要初始化为 LLONG_MIN。 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉搜索树退化成一条链（注意题目没有保证它是平衡树），因此递归需要 O(n) 的栈空间。 ...
LeetCode 240 https://leetcode.cn/problems/search-a-2d-matrix-ii/description/ 难度：中等 排除法。比较剩余矩阵右上角的元素 matrix[i][j] 和 target。如果更小，说明这一行所有元素都小于 target，i++。如果更大，说明这一列所有元素都大于 target，j–。直到找到 target 或矩阵为空。 时间复杂度：O(m+n)，其中 m 和 n 分别为 matrix 的行数和列数。 空间复杂度：O(1)。 ...
LeetCode 128 https://leetcode.cn/problems/longest-consecutive-sequence/description/ 难度：中等 对于 nums 中的元素 x，以 x 为起点，不断查找下一个数 x+1,x+2,⋯ 是否在 nums 中，并统计序列的长度。 为了做到 O(n) 的时间复杂度，需要两个关键优化： 把 nums 中的数都放入一个哈希集合中，这样可以 O(1) 判断数字是否在 nums 中。 如果 x−1 在哈希集合中，则不以 x 为起点。为什么？因为以 x−1 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长！这样可以避免大量重复计算。比如 nums=[3,2,4,5]，从 3 开始，我们可以找到 3,4,5 这个连续序列；而从 2 开始，我们可以找到 2,3,4,5 这个连续序列，一定比从 3 开始的序列更长。 ⚠ 注意：遍历元素的时候，要遍历哈希集合，而不是 nums！如果 nums=[1,1,1,…,1,2,3,4,5,…]（前一半都是 1），遍历 nums 的做法会导致每个 1 都跑一个 O(n) 的循环，总的循环次数是 \(O(n^2)\)，会超时。 时间复杂度：O(n)，其中 n 是 nums 的长度。在二重循环中，每个元素至多遍历两次：在外层循环中遍历一次，在内层循环中遍历一次。所以二重循环的时间复杂度是 O(n) 的。比如 nums=[1,2,3,4]，其中 2,3,4 不会进入内层循环，只有 1 会进入内层循环。 空间复杂度：O(n)。 ...
LeetCode 122 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/ 难度：中等 买卖股票类题目一般都是状态机 DP。f[i][0] 不持有股票，f[i][1] 持有股票。答案是 f[n][0]。初始化 f[0][0] = 0，f[0][1] = INT_MIN。 注意二维的 DP 数组，vector<int[2]> f(n + 1) 会比 vector<vector> 更快，如果数组长度固定，尽量使用 array 而不是 vector。 时间复杂度：O(n)，其中 n 为 prices 的长度。 空间复杂度：O(n)。 ...
LeetCode 221 https://leetcode.cn/problems/maximal-square/description/ 难度：中等 二维 DP，状态转移方程如下，并在计算 f 数组的时候维护正方形边长的最大值。 f[i + 1][j + 1] = min({f[i + 1][j], f[i][j + 1], f[i][j]}) + 1; 时间复杂度：O(mn)，其中 m 和 n 是矩阵的行数和列数。需要遍历原始矩阵中的每个元素计算 dp 的值。 空间复杂度：O(mn)，其中 m 和 n 是矩阵的行数和列数。创建了一个和原始矩阵大小相同的矩阵 dp。由于状态转移方程中的 dp(i,j) 由其上方、左方和左上方的三个相邻位置的 dp 值决定，因此可以使用两个一维数组进行状态转移，空间复杂度优化至 O(n)。 ...
LeetCode 543 https://leetcode.cn/problems/diameter-of-binary-tree/description/ 难度：简单 树形 DP 中的直径 DP。 链：从子树中的叶子节点到当前节点的路径。把最长链的长度，作为 dfs 的返回值。根据这一定义，空节点的链长是 −1，叶子节点的链长是 0。 直径：等价于由两条（或者一条）链拼成的路径。我们枚举每个 node，假设直径在这里「拐弯」，也就是计算由左右两条从下面的叶子节点到 node 的链的节点值之和，去更新答案的最大值。 直径可能在下面的某个节点拐弯，不一定经过树根 root。 dfs 返回的是链的长度，不是直径的长度。如果返回直径，那么上面与其他的链继续拼接，得到的就不是直径了。 dfs 返回的是当前子树的最大链长（也可以理解为子树的高度），不包含当前节点和其父节点的这条边。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...
LeetCode 48 https://leetcode.cn/problems/rotate-image/description/ 难度：中等 怎样 O(1)旋转矩阵？ 答案是先将矩阵转置，再将矩阵的每行翻转。 时间复杂度：\(O(n^2)\)，其中 n 是 matrix 的行数和列数。 空间复杂度：O(1)。 ...
LeetCode 64 https://leetcode.cn/problems/minimum-path-sum/description/ 难度：中等 网格图 DP 题目。f 数组初始化为 INF，f[0][1] = 0。 f[i + 1][j + 1] = min(f[i + 1][j], f[i][j + 1]) + grid[i][j]; 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。 ...