LeetCode 103 https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/ 难度：中等 这道题类似 LeetCode 102，只是需要判断当前层的奇偶性，如果是偶数，需要把当前层的结果翻转后再加入答案。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此数组中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。 ...
LeetCode 236 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 难度：中等 二叉树题目。如果当前节点为空，或者为 p，或者为 q，直接返回当前节点。 如果左右子树都找到 p 或 q，返回当前节点。 如果左子树找到 p 和 q，返回左子树的结果。 如果右子树找到 p 和 q，返回右子树的结果。 如果左右子树都没找到，返回空节点。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树是一条链，因此递归需要 O(n) 的栈空间。 ...
LeetCode 121 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/ 难度：简单 贪心题目，枚举第 i 天之前价格的最小值，作为买入价格。 时间复杂度：O(n)，其中 n 为 prices 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...
LeetCode 20 https://leetcode.cn/problems/valid-parentheses/description/ 难度：中等 本题是栈的应用。如果是左括号就入栈，如果是右括号，如果栈顶元素与其匹配，则出栈，否则返回 false。最后返回栈是否为空。 时间复杂度：O(n)，其中 n 是 s 的长度。 空间复杂度：O(n)。 ...
LeetCode 88 https://leetcode.cn/problems/merge-sorted-array/description/ 难度：简单 本题最简单的思路是使用额外的空间存储，最后复制回 nums1。那么有没有什么方案可以避免额外空间？答案是使用逆向双指针算法。从最后一个元素开始，将结果赋值到 nums1。这样可以避免 nums1 中元素被覆盖的问题。 时间复杂度：O(m+n)。 空间复杂度：O(1)。仅用到若干额外变量。 ...
LeetCode 46 https://leetcode.cn/problems/permutations/description/ 难度：中等 这是一道回溯法的题目，本题适用于“枚举选哪个”方法。 时间复杂度：O(n⋅n!)，其中 n 为 nums 的长度。搜索树中的节点个数低于 3⋅n!。实际上，精确值为 ⌊e⋅n!⌋，其中 e=2.718⋯ 为自然常数。有 O(n!) 个叶节点，每个叶节点花费 O(n) 的时间复制 path 数组，因此时间复杂度为 O(n⋅n!)。 空间复杂度：O(n)。返回值的空间不计入。 ...
LeetCode 200 https://leetcode.cn/problems/number-of-islands/description/ 难度：中等 本题是一道图论 DFS 的题目。初始图中的陆地为 1，水为 0。当我们遍历陆地的时候，将遍历过的陆地改为 2，以防止重复访问。 遍历整张图，如果发现 grid[i][j] == 1，说明这是一块没被访问过的岛屿，dfs(i, j)，岛屿数量加一。 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。 ...
LeetCode 33 https://leetcode.cn/problems/search-in-rotated-sorted-array/description/ 难度：中等 本题是二分查找的应用，使用红蓝染色法。如果 mid 就是 target 或者在 target 右侧，染为蓝色，如果在 target 左侧，染为红色。 如果数组被旋转了，那么分为左右两段，左边一段的元素大于最后一个元素。 对于节点 i 被染为蓝色分为以下情况： 如果 nums[i] > end，也就是 i 在左边这段。那么需要 target 也在左边这段，并且在他左边。 如果 nums[i] <= end，也就是 i 在右边这段。那么需要 target 要么在左边这段，要么在右边这段但是在他左边。 由于最后一个元素一定在 target 右边，初始就为蓝色，因此二分区间为 [0, n - 2]。 时间复杂度：O(logn)，其中 n 为 nums 的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...
LeetCode 1 https://leetcode.cn/problems/two-sum/description/ 难度：简单 LeetCode 第一题，哈希表的应用。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(n)。哈希表需要 O(n) 的空间。 ...
LeetCode 102 https://leetcode.cn/problems/binary-tree-level-order-traversal/description/ 难度：中等 这道题是 BFS 的经典题目。本题使用两个数组 cur 和 nxt 来实现 BFS。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。满二叉树（每一层都填满）最后一层有大约 n/2 个节点，因此数组中最多有 O(n) 个元素，所以空间复杂度是 O(n) 的。 ...