LeetCode 5 https://leetcode.cn/problems/longest-palindromic-substring/description/ 难度：中等 本题是字符串的经典题目，有 3 种做法，分别是动态规划，中心扩展法和马拉车算法。其中前两种做法的时间复杂度为\(O(n^2)\)，马拉车算法的时间复杂度为\(O(n)\)。不过由于马拉车算法较为复杂，在这里使用的是实现较为简单的中心扩展算法。 中心扩展算法就是对于每一个元素，分别讨论子串长度为奇数和偶数的情况，如果子串两端的字符相同，就继续向外扩展。 时间复杂度：\(O(n^2)\)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n−1 个，每个回文中心最多会向外扩展 O(n) 次。 空间复杂度：O(1)。 ...
LeetCode 21 https://leetcode.cn/problems/merge-two-sorted-lists/description/ 难度：简单 每次将 list1 和 list2 中较小值作为下一个节点，最后将剩余节点接在后面。 时间复杂度：O(n+m)，其中 n 为 list 1 的长度，m 为 list 2 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...
本题为手撕快速排序，力扣上类似的题为 LeetCode 912 排序数组。 https://leetcode.cn/problems/sort-an-array/description/ 难度：中等。 需要注意的是，初始化 i = l - 1，j = r + 1，方便在循环开始时直接进行 i++ 和 j–，递归时边界分别是 [l, j] 和 [j + 1, r]。 时间复杂度：O(nlogn) 空间复杂度：O(logn) ...
LeetCode 53 https://leetcode.cn/problems/maximum-subarray/description/ 难度：中等 本题有两种做法，分别是前缀和以及动态规划。 前缀和的做法为维护最小前缀和，答案为当前前缀和减去最小前缀和。 动态规划的转移方程为 \(f[i] = max(f[i-1],0) + nums[i]\)。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...
LeetCode 15 https://leetcode.cn/problems/3sum/description/ 难度：中等 首先，由于输出的顺序不重要，可以先将数组进行排序。然后，枚举第一个数，转化为两数之和 II（LeetCode 142）。为了排除重复答案，如果 i，j，k 与上一个元素相同，需要去重。 时间复杂度：O(\(n^ 2\))，其中 n 为 nums 的长度。排序 O(nlogn)。外层循环枚举第一个数，就变成 167. 两数之和 II - 输入有序数组 了，做法是 O(n) 双指针。所以总的时间复杂度为 O(\(n^ 2\))。 空间复杂度：O(1)。返回值不计入。忽略排序的栈开销。 ...
LeetCode 25 https://leetcode.cn/problems/reverse-nodes-in-k-group/description/ 难度：困难 反转一组节点的代码与 LeetCode 206 类似，每次修改一个节点的 next。 ListNode* nxt = cur->next; cur->next = pre; pre = cur; cur = nxt; 需要注意的是，每次需要保存一组节点的上一个节点 p0，反转结束后，更新 p0 和 p0->next。 ListNode* nxt = p0->next; p0->next->next = cur; p0->next = pre; p0 = nxt; 时间复杂度：O(n)，其中 n 为链表节点个数。 空间复杂度：O(1)，仅用到若干额外变量。 ...
LeetCode 215 https://leetcode.cn/problems/kth-largest-element-in-an-array/description/ 难度：中等 快速选择算法，类似快速排序。 时间复杂度：O(n) 空间复杂度：O(logn) ...
LeetCode 206 https://leetcode.cn/problems/reverse-linked-list/description/ 难度：简单 本题有迭代和递归两种解法，迭代法更易理解，且空间复杂度更优。 ...
LeetCode 146 https://leetcode.cn/problems/lru-cache/description/ 难度：中等 本题是双向链表和哈希表的经典题目。每个节点有 key，value，还有两个指针 prev 和 next 分别指向前一个和下一个节点。 此外，链表中还包含一个 dummy 节点，让每个节点的 prev 和 next 都不为空。 时间复杂度：所有操作均为 O(1)。 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。 ...
LeetCode 0003 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/ 难度：中等 本题为经典的哈希表加滑动窗口的题目，哈希表统计窗口内字符出现次数，如果窗口右端点字符出现次数大于 1，右移左端点，直到无重复字符，最后更新答案。窗口的长度为 right - left + 1。 时间复杂度：O(n)，其中 n 为 s 的长度。注意 left 至多增加 n 次，所以整个二重循环至多循环 O(n) 次。 空间复杂度：O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为 ASCII 字符，所以 ∣Σ∣≤128。 ...