LeetCode 8 https://leetcode.cn/problems/string-to-integer-atoi/description/ 难度：中等 本题是一道比较麻烦的模拟。 跳过前导空格。 检查符号。 读入数字。需要注意检查溢出。32 位 int 的范围是 [-2147483648, 2147483647]。无论是正数还是负数，只要绝对值大于 2147483647，我们就返回 INT_MAX/INT_MIN。对于正数是已经溢出，对于负数则正好是 INT_MIN。判断方式是 ans > INT_MAX / 10 || (ans == INT_MAX / 10 && s[i] > ‘7’)。 时间复杂度：O(n)。 空间复杂度：O(1)。 ...
LeetCode 2 https://leetcode.cn/problems/add-two-numbers/description/ 难度：中等 递归处理两个链表相加。 时间复杂度：O(n)，其中 n 为 l1 长度和 l2 长度的最大值。 空间复杂度：O(n)。递归需要 O(n) 的栈空间。 ...
LeetCode 69 http://leetcode.cn/problems/sqrtx/description/ 难度：简单 本题是找满足 i * i <= x 的最大 i。i 越小越满足要求，i 越大越不满足要求，答案具有单调性，可以二分答案。 本题是“求最大”类型的题目，与“求最小”类型不同。左边是满足要求的，染成蓝色，右边是不满足要求的，染成红色。满足条件时更新 left = mid，最后也返回 left。 时间复杂度：O(logx)。 空间复杂度：O(1)。 ...
LeetCode 239 https://leetcode.cn/problems/sliding-window-maximum/description/ 难度：困难 这道题是单调队列。单调队列是一个双端队列，类似单调栈，但需要把超过窗口的元素移除。队首元素就是窗口内的最大值。 右边入（元素进入队尾，同时维护队列单调性） 左边出（元素离开队首） 记录/维护答案（根据队首） 时间复杂度：O(n)，其中 n 为 nums 的长度。由于每个下标至多入队出队各一次，所以二重循环的循环次数是 O(n) 的。 空间复杂度：O(min(k,U))，其中 U 是 nums 中的不同元素个数（本题至多为 20001）。双端队列至多有 k 个元素，同时又没有重复元素，所以也至多有 U 个元素，所以空间复杂度为 O(min(k,U))。返回值的空间不计入。 ...
LeetCode 31 https://leetcode.cn/problems/next-permutation/description/ 难度：中等 从右向左，找第一个小于右侧相邻数字的数 x 找 x 右边最小的大于 x 的数 y，交换 x 和 y 反转 y 右边的数，把右边的数变成最小的排列 时间复杂度：O(n)，其中 n 是 nums 的长度。最坏情况下需要遍历整个 nums 数组。 空间复杂度：O(1)。 ...
LeetCode 148 https://leetcode.cn/problems/sort-list/description/ 难度：中等 本题使用归并排序。 找到链表的中间结点 head 2 的前一个节点，并断开 head2 与其前一个节点的连接。这样我们就把原链表均分成了两段更短的链表。 分治，递归调用 sortList，分别排序 head（只有前一半）和 head2。 排序后，我们得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点。 时间复杂度：O(nlogn)，其中 n 是链表长度。递归式 T(n)=2T(n/2)+O(n)，由主定理可得时间复杂度为 O(nlogn)。 空间复杂度：O(logn)。递归需要 O(logn) 的栈开销。 ...
LeetCode 22 https://leetcode.cn/problems/generate-parentheses/description/ 难度：中等 选或不选。选就是左括号，不选就是右括号。左右括号的数量需要有约束，open 是左括号的数量。open < n 限制左括号至多填 n 个，i - open < open 限制右括号至多填 open 个。 时间复杂度：分析回溯问题的时间复杂度，有一个通用公式：路径长度 × 搜索树的叶子数。对于本题，它等于 O(n⋅C(2n,n))。但由于左右括号的约束，实际上没有这么多叶子，根据 Catalan 数，实际的时间复杂度为 O(C(2n,n))。 空间复杂度：O(n)。返回值的空间不计入。 ...
LeetCode 232 https://leetcode.cn/problems/implement-queue-using-stacks/description/ 难度：简单 用两个栈，输入栈和输出栈来模拟队列。push 时将输入压进输入栈。pop 时，如果输出栈为空，将输出栈的元素全部压入输出栈，这时输出栈的顺序就是输入的顺序。返回输出栈栈顶元素。 时间复杂度：push 和 empty 为 O(1)，pop 和 peek 为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)。 空间复杂度：O(n)。其中 n 是操作总数。对于有 n 次 push 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)。 ...
LeetCode 704 https://leetcode.cn/problems/binary-search/description/ 难度：简单 红蓝染色法，开区间二分。满足条件 nums[mid] >= target 更新 right = mid。更新什么什么就是答案，本题 right 就是答案。 时间复杂度：O(logn)，其中 n 为 nums 的长度。 空间复杂度：O(1)。 ...
LeetCode 165 https://leetcode.cn/problems/compare-version-numbers/description/ 难度：中等 使用两个指针，遍历两个字符串，直到找到’.’，将每一段的版本号转换为整数，比较两个整数是否相等。整数初始化为 0，以处理这一段版本号缺失的情况。 时间复杂度：O(n+m)，其中 m 是字符串 version1 的长度，n 是字符串 version2 的长度。 空间复杂度：O(1)，我们只需要常数的空间保存若干变量。 ...