LeetCode 刷题笔记：hot100

本人的一些 LeetCode 刷题笔记，欢迎参考。

哈希

哈希表的作用是记录之前出现过的内容，C++ 中对应的数据结构有三种：数组、unordered_set、unordered_map。理想情况下，哈希表的插入/删除/查询的时间复杂度为 $O(1)$。

1. 两数之和

https://leetcode.cn/problems/two-sum/description

力扣第一题，非常经典。基本思路是，扫描一遍数组，记录之前扫过的数以及对应的下标，对每个数 nums[i]，查询是否出现过 target - nums[i]，如果有，则返回两个 对应的下标。

要记录之前扫过的数及其下标，就要使用哈希表来存储，查询效率高。同时，由于要存储对应的下标，因此在 C++ 中采用 unordered_map 数据结构。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;
        for (int i = 0; i < nums.size(); i++) {
            if (seen.find(target - nums[i]) != seen.end()) {
                return {i, seen[target - nums[i]]};
            } else {
                seen[nums[i]] = i;
            }
        }
        return {-1, -1};
    }
};

扫描一遍数组，每次操作 $O(1)$，时间复杂度 $O(n)$。空间复杂度 $O(n)$。

2. 字母异位词分组

https://leetcode.cn/problems/group-anagrams/description/

这题需要将字符串进行分组，分组的标准是：字符串中 26 个字母的出现频次均相同。在扫描所有字符串的过程中，使用一个哈希表存储每一类的字符串。当扫描到一个新的字符串时，检查是否已经有对应的类，如果有则直接加入。

本题的关键在于哈希表的键的设计，这个键需要表征每一组字符串。两个常见的想法是：将排序后的字符串作为键，因为每一类字符串包含的字母相同，排序后形成的字符串一定相同；将出现26个字母的次数作为键。我们这里选择第一种。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> ht;
        for (string &str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            ht[key].emplace_back(str);
        }
        // collect result
        vector<vector<string>> result;
        for (auto &it: ht) {
            result.emplace_back(it.second);
        }
        return result;
    }
};

对于每个字符串，需要对字符串进行排序，设字符串最大长度为 $k$，则时间复杂度为 $O(nk\log k)$。空间复杂度 $O(nk)$。

3. 最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/description

这题同样需要记住数组里出现的元素，方便查找，我们使用哈希表。由于不需要记住其他数值，只需要知道一个数是否出现过，我们使用 unordered_set。对于每个数 x，我们依次往后访问 x+1、x+2、…，查询下一个数是否出现，得到序列长度。

但这样时间复杂度为 $O(n^2)$，因为对序列中每一个数，都统计了序列长度。事实上，我们只需要对第一个数开始的序列统计长度就可以。因此，在访问每个数 x 时，都判断 x-1 是否在数组中，如果确实存在，则不统计从 x 开始的序列长度。这样，确保了时间复杂度为 $O(n)$，即整个数组只被访问常数次。空间复杂度 $O(n)$。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> ht(nums.begin(), nums.end());
        int maxlen = 0;
        for (const int &num: ht) {
            if (ht.find(num - 1) != ht.end()) continue;
            int curlen = 0;
            while (ht.find(num + curlen) != ht.end()) curlen++;
            maxlen = max(maxlen, curlen);
        }
        return maxlen;
    }
};

注意一个点，遍历数组的时候，应该遍历哈希表，而不是遍历初始数组。初始数组可能包含很多重复元素，遍历可能超时。

双指针

4. 移动零

https://leetcode.cn/problems/move-zeroes/description/

本题的关键是原地操作，原地操作的核心是避免覆盖有用数据。

本题使用双指针法。定义一个读指针 read 和一个写指针 write，从左到右移动。当读指针读到非 0 数值时，写到写指针的位置。由于写指针所写的位置都已经被读指针读过，不会存在数据覆盖的问题。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

还有一种方法，就是在读到非 0 数值时，也将两个指针对应的数交换，效果是一样的。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int read = 0, write = 0;
        while (read < nums.size()) {
            if (nums[read] != 0) {
                nums[write++] = nums[read++];
            } else {
                read++;
            }
        }
        while (write < nums.size()) {
            nums[write++] = 0;
        }
    }
};

5. 盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/description/

给定两个边界 i 和 j，储存的水量是 min(height[i], height[j]) * (j - i)。我们想要找到一组 (i, j)，使得这个水量最大。这道题有点类似滑动窗口，它存在一个单调性条件。注意到，当给定 (i, j) 时，如果将高度较高的一边向中间移动，水量一定减小。也就是说，我们对于高度较低一边的当前位置，已经不需要再对另一端遍历中间的所有位置了，因为其水量一定全部小于当前水量，这就避免了 $O(n^2)$ 的暴力搜索。

综上所述，我们的思路是，将指针初始化在头尾，逐渐向中间移动，记录整个过程中的最大水量。每次的移动方法是，移动高度较低的那一边。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int maxWater = 0, curWater;
        while (i < j) {
            curWater = min(height[i], height[j]) * (j - i);
            maxWater = max(maxWater, curWater);
            if (height[i] < height[j]) i++;
            else j--;
        }
        return maxWater;
    }
};

6. 三数之和

https://leetcode.cn/problems/3sum/description/

本题的关键是去重。由于返回值不需要包含下标，我们可以首先对数组进行排序，这样更方便去重。

基本思路是：固定三元组中最小的数 nums[i]，将问题转化为在一个数组中找到所有和为 -nums[i] 的二元组，这一步通过双指针实现即可。具体来说，两个指针分别指向 i 右侧数组的首尾，逐渐向中间移动，在过程中收集所有和为 -nums[i] 的去重二元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int i = 0, j, k, target, curSum;
        vector<vector<int>> result;
        while (i < nums.size()) {
            target = -nums[i];
            j = i + 1; k = nums.size() - 1;
            while (j < k) {
                curSum = nums[j] + nums[k];
                if (curSum < target) j++;
                else if (curSum > target) k--;
                else {
                    result.push_back({nums[i], nums[j], nums[k]});
                    while (j < k && nums[j + 1] == nums[j]) j++;
                    while (j < k && nums[k - 1] == nums[k]) k--;
                    j++; k--;
                }
            }
            while (i < nums.size() - 1 && nums[i + 1] == nums[i]) i++;
            i++;
        }
        return result;
    }
};

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$（排序）。

7. 接雨水

https://leetcode.cn/problems/trapping-rain-water/description

这道题的思路没有那么直接，我们需要考虑这个雨水的体积究竟如何计算。观察可以发现，从左到右遍历柱子，当出现一个高度为 x 的柱子时，它能决定和左侧每一根“它们之间没有高度超过 x 的柱子”的柱子之间的水量，而这个水量由左侧柱子以及它们之间柱子的最大高度决定。

我们需要维护一个单调栈，存储数组下标，从栈底到栈口，对应的柱子高度单调减小。当扫描到一个新的柱子 k 时，如果栈顶的柱子 j 高度不超过 height[k]，将其弹出并将该高度作为水池的底，假设此时栈顶为 i，那么此时形成水池的高度是 min(height[i], height[k]) - height[j]，宽度是 k - i - 1，如此依次弹出所有高度不超过 height[k] 的柱子，接着将这个新的柱子 j 压入栈中。被弹出的这些柱子已经无法和 k 右侧的柱子一起接住雨水，因为它们被 k 阻挡。

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int result = 0, i, j;
        for (int k = 0; k < height.size(); k++) {
            while (!st.empty() && height[k] >= height[st.top()]) {
                j = st.top(); st.pop();
                if (!st.empty()) {
                    i = st.top();
                    result += (min(height[i], height[k]) - height[j]) * (k - i - 1);
                }
            }
            st.push(k);
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。这道题也有动态规划和双指针的做法。

滑动窗口

8. 无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

这道题采用滑动窗口的思路，依次向右扩展窗口，如果发现读入的数已经在字符串中出现过，则缩小左侧窗口，直到该字符不重复，记录过程中窗口的最大值，即为答案。可以使用 unordered_set 哈希表来记录当前字符串中有哪些元素。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> seen;
        int result = 0, i = 0;
        for (int j = 0; j < s.length(); j++) {
            if (seen.find(s[j]) != seen.end()) {
                while (s[i] != s[j]) seen.erase(s[i++]);
                i++;
            } else {
                seen.insert(s[j]);
            }
            result = max(result, j - i + 1);
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(|\Sigma|)$，其中 $|\Sigma|$ 表示字符集的大小。

9. 找到字符串中所有字母异位词

https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

这道题思路比较直接，因为窗口的大小是固定的，就是 p 的长度。我们只要一格格移动这个窗口，维护好这个窗口中有哪些字母出现（即每个字母出现多少次），是否和 p 中出现的字母完全一致就可以了。可以采取存储差值的方法，当所有差值全为 0 的时候，表明窗口中包含的字符和 p 完全一致。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.length() < p.length()) return {};
        int diff[26];
        vector<int> result;
        int non_zero = 0, tmp, j;
        for (int i = 0; i < p.length(); i++) {
            tmp = ++diff[p[i] - 'a'];
            if (tmp == 1) non_zero++;
            else if (tmp == 0) non_zero--;
            tmp = --diff[s[i] - 'a'];
            if (tmp == -1) non_zero++;
            else if (tmp == 0) non_zero--;
        }
        for (int i = 0; i + p.length() <= s.length(); i++) {
            j = i + p.length() - 1;
            if (i != 0) {
                tmp = --diff[s[j] - 'a'];
                if (tmp == -1) non_zero++;
                else if (tmp == 0) non_zero--;
                tmp = ++diff[s[i - 1] - 'a'];
                if (tmp == 1) non_zero++;
                else if (tmp == 0) non_zero--;
            }
            if (non_zero == 0) result.push_back(i);
        }
        return result;
    }
};

时间复杂度 $O(n + m)$，空间复杂度 $O(|\Sigma|)$。

子串

10. 和为 K 的子数组

11. 滑动窗口最大值

12. 最小覆盖子串

普通数组

13. 最大子数组和

14. 合并区间

15. 轮转数组

16. 除了自身以外数组的乘积

17. 缺失的第一个正数

矩阵

18. 矩阵置零

19. 螺旋矩阵

20. 旋转图像

21. 搜索二维矩阵 II

链表

22. 相交链表

23. 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

反转链表是链表的经典题目，采用双指针法，pre 和 cur 指针分别指向前一个和后一个节点，基本过程如下。

tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;

完整代码如下。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

24. 回文链表

25. 环形链表

26. 环形链表 II

27. 合并两个有序链表

28. 两数相加

29. 删除链表的倒数第 N 个结点

30. 两两交换链表中的节点

31. K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

这道题是反转链表的进阶版，主体还是反转链表，不涉及额外的算法，但是加上了链表之间的连接操作，即每一组反转结束后，要将上一组的尾节点 pre_tail 的 next 指针指向这次的头节点。又由于每组的尾节点是反转前的头节点，所以每一组反转前的头节点用 pre_cur 进行保存。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *pre = nullptr, *cur = head, *pnr = head;
        ListNode *pre_tail = nullptr, *pre_cur = nullptr, *result = nullptr;
        while (pnr) {
            for (int i = 0; i < k; i++) {
                if (pnr) pnr = pnr->next;
                else {
                    pre_tail->next = cur;
                    return result;
                }
            }
            pre_cur = cur;
            pre = nullptr;
            while (cur != pnr) {
                ListNode *tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }
            if (pre_tail) pre_tail->next = pre;
            else result = pre;
            pre_tail = pre_cur;
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

32. 随机链表的复制

33. 排序链表

34. 合并 K 个升序链表

35. LRU 缓存

https://leetcode.cn/problems/lru-cache/description/

为了实现根据 key 的 $O(1)$ 查找，我们需要使用哈希表。为了实现 LRU 的排队策略，在 $O(1)$ 时间内从队列中选一个元素排到队尾，我们需要使用链表。但是注意三件事情：

• 为了快速找到节点来完成队列调整，我们在哈希表中应当存放的值是节点指针，而不是 value；
• 单向链表的节点删除需要 $O(n)$ 时间，因为我们需要找到前一个节点，因此我们需要使用双向链表；
• 为了在逐出节点时同时删去哈希表中的项，在每个节点中我们还需要存放 key 值。

我们将队尾设在双向链表的头部，队头设在双向链表的尾部。

struct DLinkedNode {
    int key, value;
    DLinkedNode* pre;
    DLinkedNode* next;

    DLinkedNode() : key(0), value(0), pre(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value) : key(_key), value(_value), pre(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int cap;

public:
    LRUCache(int capacity) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->pre = head;
        cap = capacity;
        size = 0;
    }
    
    int get(int key) {
        auto find_res = cache.find(key);
        if (find_res == cache.end()) return -1;
        DLinkedNode* cur = find_res->second;
        // remove node
        cur->pre->next = cur->next;
        cur->next->pre = cur->pre;
        // add to head
        cur->pre = head; cur->next = head->next;
        head->next->pre = cur;
        head->next = cur;
        return cur->value;
    }
    
    void put(int key, int value) {
        auto find_res = cache.find(key);
        if (find_res != cache.end()) {
            DLinkedNode* cur = find_res->second;
            // remove node
            cur->pre->next = cur->next;
            cur->next->pre = cur->pre;
            // add to head
            cur->pre = head; cur->next = head->next;
            head->next->pre = cur;
            head->next = cur;
            cur->value = value;
            return;
        }
        if (size == cap) {
            DLinkedNode* out = tail->pre;
            // remove from tail
            out->pre->next = tail;
            tail->pre = out->pre;
            cache.erase(out->key);
            delete out;
            size--;
        }
        size++;
        DLinkedNode* cur = new DLinkedNode(key, value);
        cache.emplace(key, cur);
        // add to head
        cur->pre = head; cur->next = head->next;
        head->next->pre = cur;
        head->next = cur;
    }
};

时间复杂度对于 put 和 get 都是 $O(1)$，空间复杂度 $O(\text{capacity})$。

二叉树

36. 二叉树的中序遍历

37. 二叉树的最大深度

38. 翻转二叉树

39. 对称二叉树

40. 二叉树的直径

41. 二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

二叉树的层序遍历，属于基本算法，使用一个队列维护要处理的节点。本题需要分开收集每一层的节点，可以用一个 bdth 变量记录每一层的节点数量。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> result;
        if (root) q.push(root);
        while (!q.empty()) {
            int bdth = q.size();
            vector<int> nodes;
            while (bdth--) {
                TreeNode *cur = q.front(); q.pop();
                nodes.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            result.push_back(nodes);
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

42. 将有序数组转换为二叉搜索树

43. 验证二叉搜索树

44. 二叉搜索树中第 K 小的元素

45. 二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/description/

本题是基于二叉树的层序遍历的，每一层输出最右侧节点即可，也就是队列中最后弹出的节点。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> q;
        if (root) q.push(root);
        while (!q.empty()) {
            int bdth = q.size();
            while (bdth--) {
                TreeNode *cur = q.front(); q.pop();
                if (bdth == 0) result.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

46. 二叉树展开为链表

47. 从前序与中序遍历序列构造二叉树

48. 路径总和 III

49. 二叉树的最近公共祖先

50. 二叉树中的最大路径和

图论

51. 岛屿数量

https://leetcode.cn/problems/number-of-islands/description/

基础图论题，求连通分量数，用 BFS 或者 DFS 都可以。

class Solution {
public:
    int dirs[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

    bool inGrid(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    void bfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int m, int n, int x, int y) {
        queue<pair<int, int>> q;
        q.emplace(x, y); visited[x][y] = true;
        while (!q.empty()) {
            int i = q.front().first, j = q.front().second; q.pop();
            for (int dir = 0; dir < 4; dir++) {
                int newx = i + dirs[dir][0], newy = j + dirs[dir][1];
                if (inGrid(newx, newy, m, n) && grid[newx][newy] == '1' && !visited[newx][newy]) {
                    q.emplace(newx, newy);
                    visited[newx][newy] = true;
                }
            }
        }
        return;
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                bfs(grid, visited, m, n, i, j);
                result++;
            }
        }
        return result;
    }
};

这里使用 BFS，时间复杂度 $O(mn)$，空间复杂度 $O(\min(m, n))$。

52. 腐烂的橘子

53. 课程表

54. 实现 Trie (前缀树)

回溯

55. 全排列

56. 子集

57. 电话号码的字母组合

58. 组合总和

59. 括号生成

60. 单词搜索

61. 分割回文串

62. N 皇后

二分查找

63. 搜索插入位置

64. 搜索二维矩阵

65. 在排序数组中查找元素的第一个和最后一个位置

66. 搜索旋转排序数组

https://leetcode.cn/problems/search-in-rotated-sorted-array/description/

这道题的时间要求是 $O(\log n)$，表明要使用类似二分查找的算法。每次从中间 mid 处将数组分为两半，至少有一个是顺序区间（可以通过左右端点值判断）。通过对比端点数值和 target 的大小，可以确定 target 在哪一半，这样就可以继续二分查找，直到进入顺序区间，采用二分法即可。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid])  {
                if (target >= nums[left] && target < nums[mid]) right = mid - 1;
                else left = mid + 1; 
            } else {
                if (target > nums[mid] && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
};

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

67. 寻找旋转排序数组中的最小值

68. 寻找两个正序数组的中位数

栈

69. 有效的括号

70. 最小栈

71. 字符串解码

72. 每日温度

73. 柱状图中最大的矩形

堆

74. 数组中的第 K 个最大元素

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/

这道题有两种经典的做法。首先是快速选择算法。选择一个枢轴 pivot，将数组划分为小于 pivot 和大于 pivot 的两个，然后根据 k 的位置选择其中一边，递归操作，直到找到第 k 大的元素。为了让算法性能更好，我们每次随机选择枢轴。划分的具体方法是：使用双指针，一个从左向右扫描，一个从右向左扫描，分别找到第一个左侧大于 pivot 的数和右侧小于 pivot 的数，然后交换，直到两个指针相遇。

class Solution {
public:
    int partition(vector<int> &nums, int left, int right) {
        int idx = left + rand() % (right - left + 1);
        swap(nums[left], nums[idx]);
        int pivot = nums[left];
        int i = left + 1, j = right;
        while (i <= j) {
            while (i <= j && nums[i] < pivot) i++;
            while (i <= j && nums[j] > pivot) j--;
            if (i <= j) swap(nums[i++], nums[j--]);
        }
        swap(nums[left], nums[j]);
        return j;
    }

    int quickSelect(vector<int>& nums, int left, int right, int target) {
        if (left == right) return nums[target];
        int pivot = partition(nums, left, right);
        if (pivot == target) return nums[pivot];
        else if (pivot < target) return quickSelect(nums, pivot + 1, right, target);
        else return quickSelect(nums, left, pivot - 1, target);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quickSelect(nums, 0, n - 1, n - k);
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(\log n)$（递归用栈）。

第二种方法是用堆来做。我们建立一个大小为 k 的小根堆，堆顶元素即为第 k 大的元素。

class Solution {
public:
    void buildHeap(vector<int> &heap, int len) {
        for (int i = len / 2; i > 0; i--) {
            heapAjust(heap, i, len);
        }
    }

    void heapAjust(vector<int> &heap, int i, int len) {
        heap[0] = heap[i];
        for (int j = 2 * i; j <= len; j *= 2) {
            if (j < len && heap[j] > heap[j + 1]) j++;
            if (heap[0] <= heap[j]) break;
            heap[i] = heap[j];
            i = j;
        } 
        heap[i] = heap[0];
    }

    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap(k + 1, 0);
        for (int i = 1; i <= k; i++) heap[i] = nums[i - 1];
        buildHeap(heap, k);
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > heap[1]) heap[1] = nums[i];
            heapAjust(heap, 1, k);
        }
        return heap[1];
    }
};

时间复杂度 $O(n \log k)$，空间复杂度 $O(k)$。

75. 前 K 个高频元素

76. 数据流的中位数

贪心算法

77. 买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

这题比较直观，采用贪心的思路，在最低点买入，最高点卖出。我们只要维护一个过去的最低价格，以及当前能获得的最大利润即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = prices[0], profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            profit = max(profit, prices[i] - low);
            low = min(low, prices[i]);
        }
        return profit;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

78. 跳跃游戏

79. 跳跃游戏 II

80. 划分字母区间

动态规划

81. 爬楼梯

82. 杨辉三角

83. 打家劫舍

84. 完全平方数

85. 零钱兑换

86. 单词拆分

87. 最长递增子序列

88. 乘积最大子数组

89. 分割等和子集

90. 最长有效括号

多维动态规划

91. 不同路径

92. 最小路径和

93. 最长回文子串

94. 最长公共子序列

95. 编辑距离

技巧

96. 只出现一次的数字

97. 多数元素

https://leetcode.cn/problems/majority-element/description/

这道题比较巧妙的做法是使用摩尔投票法。这个方法基于一个观察：从数组中任意删去两个不同的数，剩下数组的多数元素不变。

因此，我们可以直接选当前的数字作为候选，维护一个计数器，每次出现相等的数字就加 1，出现不同的数字就减 1。如果计数器变为 0，表明前面的元素已经全部抵消，后面数组的多数元素就是整个数组的多数元素，所以只要再次选中当前元素作为候选就可以。最后留下来的候选元素一定就是多数元素，因为它在最后一段中是多数元素，也就在整个数组中是多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate, vote = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (vote == 0) candidate = nums[i];
            if (nums[i] == candidate) vote++;
            else vote--;
        }
        return candidate;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

98. 颜色分类

99. 下一个排列

https://leetcode.cn/problems/next-permutation/description/

观察可以发现，求解下一个排列的思路是：从右向左扫描数组，找到第一个下降的数 x，在它右边序列中找出大于 x 的最小的数 y，将这两个数交换位置，再把这一段有序数组反转，就能得到下一个排列。这个思路类似计数的原理。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i;
        for (i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) break;
        }
        if (i >= 0) {
            int left = i + 1, right = nums.size() - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] > nums[i]) left = mid + 1;
                else right = mid - 1;
            }
            swap(nums[i], nums[right]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

100. 寻找重复数