LeetCode 110 https://leetcode.cn/problems/balanced-binary-tree/description/ 难度：简单 这道题对 LeetCode 104 二叉树的最大深度 稍加改造，当求出左右子树的深度时，如果深度差超过 1，则返回 -1，父节点如果接收到 -1，也直接返回 -1，否则返回当前子树的深度。最后判断根节点得到的深度是否为 -1。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...
LeetCode 470 https://leetcode.cn/problems/implement-rand10-using-rand7/description/ 难度：中等 参考题解： https://leetcode.cn/problems/implement-rand10-using-rand7/solutions/167850/cong-zui-ji-chu-de-jiang-qi-ru-he-zuo-dao-jun-yun-/ 假设已知 rand2()可以均匀的生成[1,2]的随机数，现在想均匀的生成[1,4]的随机数，该如何实现？ 答案是 (rand2()-1) × 2 + rand2() 已知 rand_N() 可以等概率的生成[1, N]范围的随机数 那么：(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数 即实现了 rand_XY() 那么如何通过 rand4()来实现 rand2()呢？这个就很简单了，已知 rand4()会均匀产生[1,4]的随机数，通过取余，再加 1 就可以了。 事实上，只要 rand_N()中 N 是 2 的倍数，就都可以用来实现 rand2()，反之，若 N 不是 2 的倍数，则产生的结果不是等概率的。 在本题中，要实现 rand10()，就需要先实现 rand_N()，并且保证 N 大于 10 且是 10 的倍数。这样再通过 rand_N() % 10 + 1 就可以得到[1,10]范围的随机数了。 (rand7()-1) × 7 + rand7() ==> rand49() 拒绝采样：如果某个采样结果不在要求的范围内，则丢弃它。 这样，我们可以得到 [1, 40] 的随机数。对他取余再 +1 得到 rand10()。 时间复杂度：期望时间复杂度为 O(1)，但最坏情况下会达到 O(∞)（一直被拒绝）。 空间复杂度：O(1)。 ...
LeetCode 144 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/ 难度：简单 递归求二叉树的前序遍历。 时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。 空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。 ...
LeetCode 394 https://leetcode.cn/problems/decode-string/description/ 难度：中等 使用双栈法。一个栈存储数字，一个栈存储字符串。当遇到数字时，更新数字，注意数字可能有多位；遇到字母时，加到当前字符串中；遇到 ‘[’ 时，将将当前字符串和数字入栈；遇到 ‘]’ 时，解码，将数字和字符串出栈，将当前字符串重复 k 次加到栈顶字符串后面，将栈顶字符串更新为当前字符串。 时间复杂度：O(S)。 空间复杂度：O(S)。 ...
LeetCode 39 https://leetcode.cn/problems/combination-sum/description/ 难度：中等 子集型回溯，选或不选。 类似完全背包，选的话递归到 dfs(i, left - candidates[i])，不选递归到 dfs(i + 1, left)。 时间复杂度：O(S)，其中 S 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 \(O(n2^n)\) 是一个比较松的上界，即在这份代码中，n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 target−candidates[idx]≥0 进行剪枝，所以实际运行情况是远远小于这个上界的。 空间复杂度：O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层。 ...
LeetCode 104 https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/ 难度：简单 递归求最大深度。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...
LeetCode 34 https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/ 难度：中等 二分查找。 // >= x lower_bound(x) // > x lower_bound(x + 1) // < x lower_bound(x) - 1 // <= x lower_bound(x + 1) - 1 时间复杂度：O(logn)，其中 n 为 nums 的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...
LeetCode 101 https://leetcode.cn/problems/symmetric-tree/description/ 难度：简单 与 LeetCode 100 相同的树 类似，这个比较 p 的左子树和 q 和右子树。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...
LeetCode 155 https://leetcode.cn/problems/min-stack/description/ 难度：中等 栈存储一个 pair，当前值和前缀最小值，初始化存储一个哨兵节点。 stack<pair<int, int>> st; 时间复杂度：所有操作均为 O(1)。 空间复杂度：O(q)。其中 q 是 push 调用的次数。最坏情况下，只有 push 操作，需要 O(q) 的空间保存元素。 ...
LeetCode 129 https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/ 难度：中等 使用参数记录路径之和，当当前节点为叶子节点时更新答案，并处理节点为空的情况。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...