HOT100 一句话题解

2026/04/01@Sean
来源：力扣 HOT100

01. 两数之和

哈希表, 一边查差值, 一边插入

02. 字母异位词分组

哈希表, 键用正序的字符串, 值是字符串数组

03. 最长连续序列

插入哈希表, 从表全部查一遍num, num 有前序 num-1 则放弃, 无前序则计算长度, 更新答案

04. 移动零

i 从头扫描, p记录当前已排好的下一个位置, 最后把 p 之后的填0即可

05. 盛最多水的容器

下标 L,R 从两头开始, 每次计算更新答案, 移动是看 h[L], h[R] 谁低移动谁

06. 三数之和

先排序, 再用下面的两重循环:

1
2
3

for(i=0~n)
    for(j=i+1, k=n-1; j<k; j++)
        while(j<k && nums[i+j+k] > 0)  k--;

注意：jk刚好拼接成一重循环的。
注意：使用 if(i != 0 && nums[i-1] == nums[i]) continue; 去除重复。

07. 接雨水

下标 li, ri 从两头开始, 两头历史最大值 Lmax, Rmax 从0开始。
每次更新 Lmax, Rmax, 哪边 max 更小, 则移动哪边的 i。
A边移动时刚好积累A边的雨水 ans += Amax - h[ai]

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

滑动窗口, 用哈希表记录当前窗口已有字符, 记录当前窗口的开始下标start, 每次字符 c 未存在, 则插入, 更新答案; 若出现 c 已存在, 则从这个窗口开始的那个字符 start 删除, 一直删除到可以插入为止, 插入, 更新答案。

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

固定大小的滑动窗口, 窗口采用计数窗口 P(26, 0), W(26, 0) 方便直接采用 P == W 判断。
挨个移动过去每次判断窗口是否完全一样即可。

10. 和为 K 的子数组

前缀和+计数字典。
每次累计前缀和pre, 采用计数字典记录 TB[pre]++，每次查找 TB[pre-k] 有多少个，加入到ans 即可。

11. 滑动窗口最大值

单调队列, 维护队头到队尾是从大到小。
注意每次先看队头是否已经超出窗口了，需要踢出。
每次的答案就是压入一个队头即可。

12. 最小覆盖子串

滑动窗口, 哈希表计数窗口T,W, 需要写一个 check 判断 W 比 T 大小(false, true)
每次滑入字符 c, 直到 check true了, 开始缩小窗口头 strat, 直到 check false, 继续下一个字符。
每次check true 的时候记得看是否更新答案。

13. 最大子数组和

正的继续走, 非正丢弃或单独走。

14. 合并区间

按照 start 排序, 然后挨个判断新压入是否合并已有尾部。

15. 轮转数组

3次反转即可。注意 k = k % n。

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

两边各求前缀积，最后使用即可。

17. 缺失的第一个正数

插入哈希表, 再从1开始查找即可。

18. 矩阵置零

集合记录需要化0的行列即可。

19. 螺旋矩阵

大模拟, 打标签, 写好 switch case, 记录方向/边界更新。

20. 旋转图像

对角镜像 + 每行逆转（记得带引用原地更新 & ）

21. 搜索二维矩阵 II

在右上角启动, 看大小判断向下还是向左。

22. 相交链表

p1, p2 走完自己走对方, 当 p1 == p2 时出循环, 此时 p1/p2 就是答案

23. 反转链表

记录下 pre, cur 挨个反转即可, 最后 pre 是头

24. 回文链表

没有更优，直接转数组，用指针 p1,p2 在头尾判断是最好的。

25. 环形链表

快慢指针。
当 p1 && p2 时就一直走，每次在里面判断是否相遇 p1 == p2 则是有环了。
注意：在循环里面 p2 若不能走两步了，那就是直接无环！

26. 环形链表 II

快慢指针。
与前面一样。
但是在 p1 == p2 时，p2 拉回头结点, p1,p2都一步一步走，再次相遇时就是入环点。

27. 合并两个有序链表

合并呗。
注意创建一个 dummy, 然后就是谁小先合并谁, 最后记得把多余的直接连上。

28. 两数相加

创建 dummy, 管理好进位 flag，每次计算后 % 和 / 即可。
最后记得看是否还有多余链接上。
最后的最后还记得看是否有多余 flag。

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

p1先走 n 步，p2 再开始走, p1 到头时, p2 就是答案。
注意：实际我们先走 n+1 步, 因为需要用倒n+1 删除倒n。
注意创建 dummy。

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

创建 dummy。记录 pre, cur 两两交换即可。

31. K 个一组翻转链表

与前面类似，用栈存储 i<k && p 入栈。
注意衔接好pre, cur，别断了。

32. 随机链表的复制

哈希表存储映射, 先创建, 再填充 random

33. 排序链表

链表的归并排序。

区间排序 sortSection(L, R) 是排[L,R)，返回头结点。

base 情况：L == NULL 返 NULL。 L->next == R 断L再返L。
取中点mid：快慢指针
分区排序 h1 = [L, mid) 和 h2 = [mid, R)
合并 merge(h1, h2)

合并 merge(h1, h2) 返回头结点。

就是合并两个有序链表。注意dummy, 多余链。

34. 合并 K 个升序链表

小根堆维护。
priority_queue<ListNode*, vector<ListNode*>, delctype(cmp)> H
cmp 直接采用比较头结点的大小即可。
创建 dummy。每次取出一个 p 加入ans，再 p = p->next 压入堆即可。

35. LRU 缓存

新建双向节点 Node (有key/val, 有 pre/nxt)。
LRU表需要头尾节点 head/tail, <key, Node*>映射表TB, 容量大小 cap。
写两个辅助函数 void remove(Node *p) 和 void addHead(Node *p) （注意这两个只管移动不管删除）
后面就是设计就行，注意插入需要看容量TB.size()是否爆了。

36. 二叉树的中序遍历

套模版

void inOrder(TreeNode *root){
    if(!root)  return ;

    inOrder(root->left);
    ans.push_back(root->val);
    inOrder(root->right);
}

37. 二叉树的最大深度

注意计算左右最大深度，再更新自己即可。

int depth(TreeNode* root){
    if(root == NULL)  return 0;

    int l = depth(root->left);
    int r = depth(root->right);
    return 1 + max(l, r);
}

38. 翻转二叉树

翻转子树，反向拼接自己的即可。

TreeNode* invertTree(TreeNode* root) {
    if(root == NULL)  return NULL;

    TreeNode *l = invertTree(root->left);
    TreeNode *r = invertTree(root->right);
    root->left = r;
    root->right = l;
    return root;
}

39. 对称二叉树

写一个函数对比两个子树是否对称。

bool isSym(TreeNode* r1, TreeNode* r2){
    if(!r1 && !r2)  return true;
    else if(!r1 || !r2)  return false;
    else{
        if(r1->val != r2->val)  return false;
        else  return isSym(r1->left, r2->right) && isSym(r1->right, r2->left);
    }
}

40. 二叉树的直径

算深度的过程中更新答案。

int depth(TreeNode *root){
    if(!root)  return 0;

    int l = depth(root->left);
    int r = depth(root->right);
    ans = max(ans, l+r);
    return 1 + max(l, r);
}

41. 二叉树的层序遍历

队列 + 计数。

// 队列模拟+计数
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    queue<TreeNode*> Q;
    if(root)  Q.push(root);
    while(!Q.empty()){
        int sz = Q.size();
        vector<int> path;
        for(int i=0; i<sz; i++){
            TreeNode *t = Q.front();  Q.pop();
            path.push_back(t->val);
            if(t->left)  Q.push(t->left);
            if(t->right)  Q.push(t->right);
        }
        ans.push_back(path);
    }

    return ans;
}

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

写一个构建函数，答案就是 bst(0, n-1, nums)

// 构建 [L, R] 的bst
TreeNode* bst(int L, int R, vector<int>& nums){
    if(L > R)  return NULL;

    int mid = (L + R) / 2;
    TreeNode *l = bst(L, mid-1, nums);
    TreeNode *r = bst(mid+1, R, nums);
    TreeNode *m = new TreeNode(nums[mid], l, r);
    return m;
}

43. 验证二叉搜索树

中序遍历一遍即可。

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

中序遍历，选出第 k 小即可。

45. 二叉树的右视图

层序遍历，每次只压最后一个入ans即可。

46. 二叉树展开为链表

写一个展平函数，答案就是 flat(root, NULL)

// 展平本树，接上next，返回本树头
TreeNode* flat(TreeNode *root, TreeNode *next){
    if(root == NULL)  return next;

    root->right = flat(root->right, next);
    root->right = flat(root->left, root->right);
    root->left = NULL;
    return root;
}

47. 从前序与中序遍历序列构造二叉树 (背！)

背下来。

// 注意中序索引判断即可
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();  if(n == 0)  return NULL;
    stack<TreeNode*> S;
    TreeNode *root = new TreeNode(preorder[0]);
    S.push(root);
    int I = 0;  // 中序标签
    for(int i=1; i<n; i++){
        TreeNode *t = new TreeNode(preorder[i]);
        // 左
        if(inorder[I] != S.top()->val){
            S.top()->left = t;
            S.push(t);
        }
        // 右
        else{
            TreeNode *p = NULL;
            while(!S.empty() && inorder[I] == S.top()->val){
                p = S.top();  S.pop();
                I++;
            }
            p->right = t;
            S.push(t);
        }
    }

    return root;
}

48. 路径总和 III

记录前缀和，若 TB 有当前 pre-targetSum ，则有答案，算上即可。

unordered_map<long long, int> TB;
TB[0] = 1;
// 利用 pre 自动记录和回退
void dfs(TreeNode *root, int targetSum, long long pre){
    if(root == NULL)  return ;
    
    pre += root->val;
    if(TB.find(pre-targetSum) != TB.end())
        ans += TB[pre-targetSum];
    TB[pre]++;
    dfs(root->left, targetSum, pre);
    dfs(root->right, targetSum, pre);
    TB[pre]--;
}

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

法1：准备好所有节点-父节点TB，把A所有父节点压入哈希表，B再依次向上找到有的即可。
法2：性质：假设 ans 是LCA，那么p,q 一定位于 ans 两侧（或者p,q就是ans）
利用这个性质，我们去检测每个树的左右子树是否含有 p/q （至少一个）

bool check(TreeNode *root, TreeNode *p, TreeNode *q){
    if(root == NULL)  return false;

    bool sf = root->val == p->val || root->val == q->val;
    if(sf){
        ans = root;
        return true;
    }

    bool lc = check(root->left, p, q);
    bool rc = check(root->right, p, q);
    if(lc && rc){
        ans = root;
        return true;
    }

    return sf || lc || rc;
}

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

仍然是 dfs 遍历过程中更新答案即可

int dfs(TreeNode *root){
    if(root == NULL)  return 0;
    
    int s = root->val;
    int l = dfs(root->left);
    int r = dfs(root->right);
    ans = max({ans, s, s+l, s+r, s+l+r});

    return max({s, s+l, s+r});
}

51. 岛屿数量

遍历每个没有看过的岛点。
每个岛点连带看四周情况。
注意写好防越界 check。

class Solution {
private:
    int R, C;

public:
    // 深度优先遍历每个岛屿即可
    int numIslands(vector<vector<char>>& grid) {
        R = grid.size(), C = grid[0].size();
        int ans = 0;
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                if(grid[i][j] == '1')
                    traversal(grid, i, j), ans++;
        return ans;
    }
    // 遍历这个岛
    void traversal(vector<vector<char>> &grid, int i, int j){
        // base
        if(!check(i, j))  return ;
        
        if(grid[i][j] == '0')  return ;
        if(grid[i][j] == '1'){
            grid[i][j] = '2';
            traversal(grid, i-1, j);
            traversal(grid, i+1, j);
            traversal(grid, i, j-1);
            traversal(grid, i, j+1);
        }
    }
    // base 边界
    bool check(int i, int j){
        return 0 <= i && i < R && 0 <= j && j < C;
    }

};

52. 腐烂的橘子

每轮是全局判断感染；
打好感染标记，方便后续感染；
统计好每轮新增感染，用来判断是否还要感染。
统计好全部感染数量，用来判断是否能全腐烂。

class Solution {
private:
    int R, C;
    int One = 0, Two = 0;

public:
    int orangesRotting(vector<vector<int>>& grid) {
        R = grid.size(), C = grid[0].size();
        // 先看全部橘子情况
        look(grid);
        if(One == 0)  return 0;     // 不用感染已经全部腐烂
        
        // 开始感染
        int epoch = 2;
        int epCnt = Two;    // 本轮新增感染
        int alCnt = Two;    // 目前总感染数量
        while(epCnt){
            epCnt = epRotting(grid, epoch);
            alCnt += epCnt;
            epoch++;
        }

        return alCnt == (One+Two) ? epoch-3: -1;
    }
    // 统计橘子情况
    void look(vector<vector<int>> &grid){
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                if(grid[i][j] == 1)  One++;
                else if(grid[i][j] == 2)  Two++;
    }
    // 本次轮到 epoch 全局感染一次, 返回新增腐烂数量
    int epRotting(vector<vector<int>>& grid, int epoch){
        int newCnt = 0;
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                if(grid[i][j] == epoch)
                    newCnt += rot4(grid, i, j, epoch+1);
        return newCnt;
    }
    // 当前橘子感染四周，返回成功感染数量
    int rot4(vector<vector<int>>& grid, int i, int j, int epoch){
        int cnt = 0;
        if(check(i-1, j, grid))  cnt++, grid[i-1][j] = epoch;
        if(check(i+1, j, grid))  cnt++, grid[i+1][j] = epoch;
        if(check(i, j-1, grid))  cnt++, grid[i][j-1] = epoch;
        if(check(i, j+1, grid))  cnt++, grid[i][j+1] = epoch;
        return cnt;
    }
    // 不越界，且是可感染的橘子
    bool check(int i, int j, vector<vector<int>>& grid){
        if(0 <= i && i< R && 0 <= j && j < C)
            return grid[i][j] == 1;
        else
            return false;
    }
};

53. 课程表

记录好修读情况，深度优先修读。

class Solution {
private:
    vector<int> State;              // 记载所有课程修读情况
    vector<vector<int>> preCourse;  // 记载所有课程的前置课程
    bool ans = true;

public:
    // 标记: 0 未修读, 1 正在修读, 2 修读完毕
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        State.resize(numCourses, 0);
        preCourse.resize(numCourses);
        for(auto pre: prerequisites)  preCourse[pre[0]].push_back(pre[1]);
        // 现在开始修读所有课程
        for(int i=0; i<numCourses; i++){
            dfs(i);
            if(ans == false)  return false;
        }
        return true;
    }
    // 深度优先修读本门课程
    bool dfs(int t){
        if(State[t] == 0){
            State[t] = 1;
            for(int pre: preCourse[t]){
                if(dfs(pre))  continue;
                else  return false;
            }
            State[t] = 2;
            return true;
        }
        else if(State[t] == 1){
            ans = false;
            return false;
        }
        else  return true;
    }
};

54. 实现 Trie (前缀树)

很巧妙的一个结构设计，直接背下来。
利用 vector 索引下标对应字符, 每次直接进入下一节点, this 为开头本节点。

class Trie {
private:
    vector<Trie*> next;
    bool end;

public:
    Trie() {
        next.resize(26, NULL);
        end = false;
    }
    
    void insert(string word) {
        Trie *p = this;
        for(char c: word){
            int i = c-'a';
            if(p->next[i] != NULL)
                p = p->next[i];
            else
                p->next[i] = new Trie(), p = p->next[i];
        }
        p->end = true;
    }
    
    bool search(string word) {
        Trie *p = this;
        for(char c: word){
            int i = c-'a';
            if(p->next[i] != NULL)
                p = p->next[i];
            else
                return false;
        }
        return p->end;
    }
    
    bool startsWith(string prefix) {
        Trie *p = this;
        for(char c: prefix){
            int i = c-'a';
            if(p->next[i] != NULL)
                p = p->next[i];
            else
                return false;
        }
        return true;
    }
};

55. 全排列

排序树标准三件套 ans/path/used。

class Solution {
private:
    // 排列树标准三件套
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> used;

public:
    // 标准 排列树遍历回溯
    vector<vector<int>> permute(vector<int>& nums) {
        int n = nums.size();
        used.resize(n, false);
        backtrace(nums);
        return ans;
    }
    // 回溯
    void backtrace(vector<int>& nums){
        if(path.size() == nums.size()){
            ans.push_back(path);
            return ;
        }

        for(int i=0; i<nums.size(); i++){
            if(!used[i]){
                path.push_back(nums[i]);  used[i] = true;
                backtrace(nums);
                path.pop_back();  used[i] = false;
            }
        }
    }
};

56. 子集

子集树两件套 ans/path。

class Solution {
private:
    // 子集树两件套，每个节点都收结果
    vector<vector<int>> ans;
    vector<int> path;

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrace(nums, 0);
        return ans;
    }
    // 子集树遍历回溯, 本次收集k及k之后的
    void backtrace(vector<int> &nums, int k){
        ans.push_back(path);
        for(int i=k; i<nums.size(); i++){
            path.push_back(nums[i]);
            backtrace(nums, i+1);
            path.pop_back();
        }
    }
};

57. 电话号码的字母组合

类似，看代码吧。

class Solution {
private:
    unordered_map<char, string> TB = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"},
    };
    vector<string> ans;
    string path;
public:
    vector<string> letterCombinations(string digits) {
        backtrace(digits, 0);
        return ans;
    }
    // 回溯, 本次选 k 开始组合
    void backtrace(string& digits, int k){
        if(k == digits.size()){
            ans.push_back(path);
            return;
        }
        for(char c: TB[digits[k]]){
            path.push_back(c);
            backtrace(digits, k+1);
            path.pop_back();
        }
    }

};

58. 组合总和

三件套 ans/path/状态记录pathSum.
注意这里可以重复选。

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> path;
    int pathSum = 0;
    int tarSum;

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        tarSum = target;
        backtrace(candidates, 0);
        return ans;
    }
    // 子集树遍历回溯, 本次选 k 数字
    void backtrace(vector<int>& candidates, int k){
        if(k == candidates.size())  return ;
        if(pathSum == tarSum){
            ans.push_back(path);
            return ;
        }
        
        if(pathSum < tarSum){
            path.push_back(candidates[k]);  pathSum += candidates[k];
            backtrace(candidates, k);   // 可以重复选
            path.pop_back();  pathSum -= candidates[k];
        }
        
        backtrace(candidates, k+1); // 现在才开始选下一个
    }
};

59. 括号生成

写一个函数，答案就是调用 backtrace(n, n)。

// 回溯遍历解空间树, 当前还有 l 个左括号，r个右括号需要添加
void backtrace(int l, int r){
    // base
    if(l > r)  return ;     // 这种情况无法正确了
    if(l == 0 && r == 0){
        ans.push_back(path);
        return ;
    }

    if(l){
        path.push_back('(');
        backtrace(l-1, r);
        path.pop_back();
    }
    if(r){
        path.push_back(')');
        backtrace(l, r-1);
        path.pop_back();
    }
}

60. 单词搜索

从每个位置探四周。

class Solution {
private:
    int M, N;
    vector<vector<bool>> used;
    bool ans = false;


public:
    bool exist(vector<vector<char>>& board, string word) {
        M = board.size(), N = board[0].size();
        used.resize(M, vector<bool>(N, false));
        // 从每个位置开始
        for(int i=0; i<M; i++)
            for(int j=0; j<N; j++){
                visit4(board, word, 0, i, j);
                if(ans)  return true;
            }

        return false;
    }
    // 探索四周, 当前在 ci, cj, 需要匹配 word[k]
    void visit4(vector<vector<char>>& board, string &word, int k, int ci, int cj){
        // base
        if(k == word.size())  return ;

        if(word[k] == board[ci][cj]){
            if(k == word.size()-1){
                ans = true;
                return ;
            }
            used[ci][cj] = true;
            if(check(ci-1, cj))  visit4(board, word, k+1, ci-1, cj);
            if(check(ci+1, cj))  visit4(board, word, k+1, ci+1, cj);
            if(check(ci, cj-1))  visit4(board, word, k+1, ci, cj-1);
            if(check(ci, cj+1))  visit4(board, word, k+1, ci, cj+1);
            used[ci][cj] = false;
        }
        else  return;
    }
    // 防越界，未使用可访问
    bool check(int i, int j){
        if(0 <= i && i< M && 0 <= j && j < N)  return !used[i][j];
        else  return false;
    }

};

61. 分割回文串

先预处理回文串是否的情况dp[i][j]
再回溯法收集答案。

class Solution {
private:
    vector<vector<string>> ans;
    vector<string> path;
    vector<vector<bool>> dp;    // dp[i][j] 表示 s[i:j] 是否为回文串

public:
    // 先预处理，再回溯
    vector<vector<string>> partition(string s) {
        int n = s.size();
        // 回文串判断预处理
        dp.resize(n, vector<bool>(n, true));    // 初始为true,尤其 i>=j要为true
        for(int i=n-1; i>=0; i--)
            for(int j=i+1; j<=n-1; j++)
                dp[i][j] = s[i]==s[j] && dp[i+1][j-1];
        // 回溯法收集答案
        backtrace(s, 0);
        return ans;
    }
    // 回溯, 现在开始分 k 及k之后的即可
    void backtrace(string &s, int k){
        if(k == s.size()){
            ans.push_back(path);
            return ;
        }

        for(int i=k; i<s.size(); i++){
            if(dp[k][i]){
                path.push_back(s.substr(k, i-k+1));
                backtrace(s, i+1);
                path.pop_back();
            }
        }
    }
};

62. N 皇后

写好 check 是不能同行同列，以及斜线是斜率为1/-1。

class Solution {
private:
    // 两件套收集结果
    vector<vector<string>> ans;
    vector<string> path;
    vector<vector<int>> pos;    // 记录已有的全部坐标
    int N;

public:
    // 解空间树回溯遍历即可
    vector<vector<string>> solveNQueens(int n) {
        N = n;
        backtrace(0);
        return ans;
    }
    // 回溯, 下面开始放置第 k 行的皇后
    void backtrace(int k){
        // base
        if(k == N){
            ans.push_back(path);
            return ;
        }
        // 放置 k
        for(int i=0; i<N; i++){
            if(check(k, i)){
                string ts(N, '.');  ts[i] = 'Q';
                path.push_back(ts);  pos.push_back({k, i});
                backtrace(k+1);
                path.pop_back();  pos.pop_back();
            }
        }
    }
    // i, j是否可放
    bool check(int i, int j){
        // 浏览已放置的皇后满足不攻击
        for(auto p: pos){
            int x = p[0], y = p[1];
            if(x == i || y == j || x-i == y-j || x-i == j-y)
                return false;
        }
        return true;
    }
};

63. 搜索插入位置

标准二分查找

// 二分查找 [l, r]
int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int l = 0, r = n-1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(nums[mid] < target)
            l = mid+1;
        else if(nums[mid] > target)
            r = mid-1;
        else
            return mid;
    }

    return l;
}

64. 搜索二维矩阵

利用行mid/n 和列mid%n 整体二分查找即可。

// 整体二分 [l, r]
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int l = 0, r = m*n-1;
    while(l <= r){
        int mid = (l+r)/2;
        if(target > matrix[mid/n][mid%n])
            l = mid+1;
        else if(target < matrix[mid/n][mid%n])
            r = mid-1;
        else
            return true;
    }
    return false;
}

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

二分控制。nums[mid] >= target 都采用 r = mid-1 逼近左边去。再从左边往右找右边界。

// 二分控制
vector<int> searchRange(vector<int>& nums, int target) {
    int n = nums.size();
    if(n == 0)  return {-1, -1};

    int l = 0, r = n-1;
    while(l <= r){
        int mid = (l+r)/2;
        if(nums[mid] >= target)
            r = mid-1;
        else
            l = mid+1;
    }
    if(l<n && nums[l] == target){
        r = l;
        while(r+1 < n && nums[r+1]==target)  r++;
        return {l, r};
    }
    else  return {-1, -1};
}

66. 搜索旋转排序数组

[4,5,6,7,0,1,2]

一定先单独判断 mid 是否 target
再看哪边有序
不同边采用不同判断和 mid 移动

// 仍然可以利用一半信息进行二分
int search(vector<int>& nums, int target) {
    int n = nums.size();
    int l = 0, r = n-1;
    while(l <= r){
        int mid = (l+r)/2;
        // 一定先单独判断
        if(nums[mid] == target)  return mid;
        // 判断有序在哪边
        if(nums[l] <= nums[mid]){    // 说明左边有序
            if(nums[l] <= target && target < nums[mid]) // mid 不会是 target 要是就不会进内层了
                r = mid;
            else
                l = mid+1;
        }
        else{   // 说明右边有序
            if(nums[mid] < target && target <= nums[r])
                l = mid;
            else
                r = mid-1;
        }
    }

    return -1;
}

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

判断最小的在哪边即可。
注意变动 mid 不同。

// 判断最小在那边即可
int findMin(vector<int>& nums) {
    int n = nums.size();
    int minNum = nums[0];
    int l = 0, r = n-1;
    while(l <= r){
        int mid = (l+r)/2;
        minNum = min(minNum, nums[mid]);
        if(nums[mid] < nums[r])     // 右边有序，最小在左边
            r = mid;
        else                        // 右边混序，最小在混边
            l = mid+1;
    }

    return minNum;
}

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

获取第 k 小的数字，每次除去前 k/2 的数字。

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size() + nums2.size();
    if(n%2 == 1)
        return getKth(nums1, nums2, n/2+1, 0, 0) * 1.0;
    else
        return (getKth(nums1, nums2, n/2, 0, 0) + getKth(nums1, nums2, n/2+1, 0, 0)) / 2.0;
}
// 获取第 k 小的数字（在 nums1[idx1:..], nums2[idx2:..] 中
int getKth(vector<int>& nums1, vector<int>& nums2, int k, int idx1, int idx2){
    // base
    if(idx1 == nums1.size())  return nums2[idx2+k-1];
    if(idx2 == nums2.size())  return nums1[idx1+k-1];
    if(k == 1)  return min(nums1[idx1], nums2[idx2]);

    // 处理:去除前 halfK 个
    int halfK = min({k/2, int(nums1.size()-idx1), int(nums2.size()-idx2)});
    if(nums1[idx1+halfK-1] < nums2[idx2+halfK-1])
        return getKth(nums1, nums2, k-halfK, idx1+halfK, idx2);
    else
        return getKth(nums1, nums2, k-halfK, idx1, idx2+halfK);
}

69. 有效的括号

栈+备一个表写好小中大括号的键值对（刚好右-左）

左括号：入栈
右括号：消栈顶，不对应则 false
最终出来看栈empty则 true

70. 最小栈

用两个栈。
额外存储一个对应的最小值的栈（最初压入INT_MAX）

71. 字符串解码

容易出错，请注意虽然同时都是栈压入，
但strSrk 压入的是上次字符串，numStr 压入的是当前串即将会被复制的次数。
管理好 [和]即可。

// 栈记录
string decodeString(string s) {
    stack<string> strStk;
    stack<int> numStk;
    string curS = "";
    int curN = 0;
    for(char c: s){
        if(c == '['){
            // 保护现场
            numStk.push(curN);
            strStk.push(curS);
            // 设置新现场
            curN = 0, curS = "";
        }
        else if(c == ']'){
            // 内部完毕，回退上次现场
            string tmp = curS;
            int repeat = numStk.top();  numStk.pop();
            for(int i=1; i<repeat; i++)  curS += tmp;
            curS = strStk.top() + curS;  strStk.pop();
        }
        else if('0' <= c && c <= '9'){
            curN = curN*10 + (c-'0');
        }
        else{
            curS += c;
        }
    }

    return curS;
}

72. 每日温度

单调栈，退栈时是找到答案，没有退栈的说明没有更高温度。

// 单调栈, 保持递减，退栈时记录答案
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ans(n, 0);
    stack<int> S;   // 为了好返回答案，我们记录下标
    S.push(0);      // 压入第一天温度
    for(int i=1; i<n; i++){
        if(temperatures[i] <= temperatures[S.top()])
            S.push(i);
        else{
            while(!S.empty() && temperatures[i] > temperatures[S.top()]){
                ans[S.top()] = i - S.top();  S.pop();
            }
            S.push(i);
        }
    }

    return ans;
}

73. 柱状图中最大的矩形

预计算，固定当前高度 h[i] 时，最远左下标和最远右下标在哪
预计算通过单调栈实现，维持递增，每个 h 入栈时就记录答案。

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    vector<int> L(n), R(n);

    // L
    stack<int> S;           // 存下标，因为需要知道位置
    for(int i=0; i<n; i++){
        while(!S.empty() && heights[i] <= heights[S.top()])  S.pop();   // 等于也要走，尽量扩大范围
        L[i] = S.empty() ? 0 : S.top()+1;
        S.push(i);
    }
    // R
    while(!S.empty())  S.pop();
    for(int i=n-1; i>=0; i--){
        while(!S.empty() && heights[i] <= heights[S.top()])  S.pop();
        R[i] = S.empty() ? n-1 : S.top()-1;
        S.push(i);
    }
    
    // 计算
    int ans = 0;
    for(int i=0; i<n; i++){
        int area = heights[i] * (R[i] - L[i] + 1);
        ans = max(ans, area);
    }

    return ans;
}

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

使用最大堆，全压入，再pop出K个，选第K个即可

75. 前 K 个高频元素

先统计，再用最大堆。
可以选用 pair<int, int>
可以直接push {kv.first, kv.second}
cmp 按照 second 排序。
取值只用 first 即可。

76. 数据流的中位数

维护两个相同大小（或Ha大一个）的堆，维护堆顶保持 Ha < Hb
大根堆 priority_queue<int, vector<int>, less<int>> Ha;
小根堆 priority_queue<int, vector<int>, greater<int>> Hb;
写两个函数：

找中位数：看Ha和Hb是否相等，相等返回两个堆顶平均值；Ha大1，返回Ha堆顶。
插入数字：先通过看中位数判断数字压入Ha/Hb，压入后看两边堆是否需要调整（调整就push pop 堆顶即可）

77. 买卖股票的最佳时机

一直更新目前看到的历史最低价 preLow, 每次使用当前价cur-preLow 看看是否需要更新答案。

for(int i=0; i<n; i++){
    preLow = min(preLow, prices[i]);
    ans = max(ans, prices[i]-preLow);
}

78. 跳跃游戏

维护当前最远可达，慢慢向前走，走到当前最远可达再决策。

bool canJump(vector<int>& nums) {
    int n = nums.size();
    int hand = 0;
    int cur = 0;
    int next = 0;
    while(cur < n && cur <= hand){
        next = max(next, cur + nums[cur]);
        if(cur == hand)  hand = next;
        cur++;
    }
    return next >= n-1;
}

79. 跳跃游戏 II

同理，不过在决策时多记录信息。

int jump(vector<int>& nums) {
    int n = nums.size();
    int i = 0, hand = 0, maxIdx = 0;
    int dump = 0;
    while(i < n-1 && i <= hand){
        if(i+nums[i] > maxIdx+nums[maxIdx])
            maxIdx = i;
        if(i == hand){
            hand = maxIdx+nums[maxIdx];
            dump++;
        }
        i++;
    }

    return dump;
}

80. 划分字母区间

首先预计算每个字母最远所在位置
再按窗口计算字符串最远囊括位置

vector<int> partitionLabels(string s) {
    int n = s.size();
    // 预计算
    vector<int> alpha(26, -1);
    for(int i=0; i<n; i++)  alpha[s[i] - 'a'] = i;
    // 窗口囊括
    vector<int> ans;
    int i = 0, win = alpha[s[0] - 'a'], start = 0;
    
    while(i <= win){
        win = max(win, alpha[s[i] - 'a']);

        if(i == win){
            ans.push_back(win - start + 1);
            if(i+1 < n)  start = i + 1, win = alpha[s[start] - 'a'];
        }
        i++;
    }

    return ans;
}

81. 爬楼梯

int pre = 1, cur = 2;
for(int i=3; i<=n; i++){
    int t = cur + pre;
    pre = cur;
    cur = t;
}

82. 杨辉三角

两边是1，中间用上方两侧的数字相加即可。

vector<vector<int>> ans(numRows);
for(int i=0; i<numRows; i++){
    ans[i].resize(i+1);
    ans[i][0] = 1, ans[i][i] = 1;
    for(int j=1; j<i; j++)
        ans[i][j] = ans[i-1][j-1] + ans[i-1][j];
}

83. 打家劫舍

动态规划：dp[i] 表示前 i 家可偷得最大金额。
状态转移：dp[i] = max(dp[i-1], dp[i-2]+nums[i])
答案：dp[n-1]

84. 完全平方数

动态规划：dp[i] 表示数字 i 的最少所需完全平方数。
初始化：每个数字必有 dp[i] = i(全1)
需要判断j为从1 到 j*j<=i, 进行状态转移判断。
状态转移：dp[i] = min(dp[i], 1 + dp[i-j*j])
答案：dp[n]

85. 零钱兑换

dp[i] 表示构成 i 元所需最少硬币数量（初始化为 amount+1 刚好）
初始化 dp[coin] = 1
状态转移：dp[i] = min(dp[i], 1+dp[i-coin])
答案：dp[amount] == amount+1 ? -1 : dp[amount]

86. 单词拆分

字典改为哈希表存储。
dp[i] 表示 s[:i] 是否可以被拼接出来
初始化 dp[0] = true 其余全 false。
状态转移：dp[i] = dp[j] + s[j:i] 在 dict
注意每个dp 只要要 true 就够了，不用全判断。（双重循环）
答案 dp[n]

87. 最长递增子序列

在向后找递增的，尽可能保证增长最缓慢
是否加入递增? 是: 加入; 否 : 看是否要替换来达到递增缓慢
dp[i] 表示以 nums[i] 结尾时, 可以达到的最大长度
注意并不一定越往后接越好，可能后面的dp是更小的，因此二重循环不可避免。

vector<int> dp(n, 1);   // dp[i] 表示以 nums[i] 结尾时, 可以达到的最大长度
int ans = 1;
for(int i=1; i<n; i++){
    // 寻找自己最佳可以接在谁后面
    for(int j=0; j<i; j++){
        if(nums[j] < nums[i])
            dp[i] = max(dp[i], dp[j]+1);
    }
    ans = max(ans, dp[i]);
}

88. 乘积最大子数组

有负数，同时记录最大值最小值
更新时，要么接上，要么单独

int preMin = nums[0];
int preMax = nums[0];
int ans = nums[0];
for(int i=1; i<n; i++){
    int a = preMin * nums[i];
    int b = preMax * nums[i];
    preMax = max({a, b, nums[i]});
    preMin = min({a, b, nums[i]});
    ans = max(ans, preMax);
}

89. 分割等和子集

那就是能否选出元素和为一半大小
dp[i][j] 表示前 i 个数字能否合成数字 j
初始化 dp[i][0] = true
初始化 dp[i][nums[i-1]] = true
状态转移：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
以上都要注意判断是否越界，不越界的才加入 dp。
答案：dp[n][target]

90. 最长有效括号

合法二条件：

左右括号一样多
扫描过程中始终保持左 >= 右

int ans = 0;
// 从左向右扫描
int l = 0, r = 0;
for(char c: s){
    if(c == '(')  l++;
    if(c == ')')  r++;
    if(l == r)  ans = max(ans, l+r);
    if(l < r)  l = r = 0;
}
// 从右向左扫描(注意反着来)
l = 0, r = 0;
for(int i=n-1; i>=0; i--){
    char c = s[i];
    if(c == '(')  l++;
    if(c == ')')  r++;
    if(l == r)  ans = max(ans, l+r);
    if(l > r)  l = r = 0;
}

91. 不同路径

法1：动态规划 dp[i][j] 表示走到 i,j 有多少种方法。
被动更新dp[i+1][j] += dp[i][j], dp[i][j+1] += dp[i][j]。
注意防越界。
答案 dp[m-1][n-1]
法2：数学，共移动 m-1 + n-1 次, 选出 m-1 次移动为下移动即可, 即C(m+n-2, m-1)

int uniquePaths(int m, int n) {
    long long ans = 1;
    for(int i=1, j=n; i<=m-1; i++, j++)
        ans  = ans * j / i;
    return ans;
}
// 从小开始乘
// 1    1+n-1
// m-1  m+n-2
// m    m+n-1

92. 最小路径和

dp[i][j] 表示到 i,j 所需的最小数字
被动更新。

vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
dp[0][0] = grid[0][0];
for(int i=0; i<m; i++)
    for(int j=0; j<n; j++){
        if(i+1 < m)  dp[i+1][j] = min(dp[i+1][j], dp[i][j]+grid[i+1][j]);
        if(j+1 < n)  dp[i][j+1] = min(dp[i][j+1], dp[i][j]+grid[i][j+1]);
    }
return dp[m-1][n-1];

93. 最长回文子串

dp[i][j] 表示 s[i:j] 是否为回文串。

int ansL = 0, ansLen = 1;
vector<vector<bool>> dp(n, vector<bool>(n, true));
for(int i=n-1; i>=0; i--)
    for(int j=i+1; j<n; j++){
        dp[i][j] = s[i] == s[j] && dp[i+1][j-1];
        if(dp[i][j] && j-i+1 > ansLen)
            ansL = i, ansLen = j-i+1;
    }

return s.substr(ansL, ansLen);

94. 最长公共子序列

dp[i][j] 表示 s1[:i], s2[:j] 的最长公共子序列长度（不要求以 i, j 字符结尾）
注用0表示空串。
初始化全0。

vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
for(int i=1; i<=n1; i++){
    for(int j=1; j<=n2; j++){
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        if(text1[i-1] == text2[j-1])
            dp[i][j] = max(dp[i][j], 1+dp[i-1][j-1]);
    }
}

答案 dp[n1][n2]

95. 编辑距离

dp[i][j] 表示 w[:i] 和 w[:j] 的转换最少操作数
初始化全 INT_MAX
初始化 dp[i][0] = i, dp[0][j] = j
状态转移：用 1+dp[i-1][j], 1+dp[i][j-1], 1+dp[i-1][j-1]
若有 w[i] == w[j] 再加入 dp[i-1][j-1]

int n1 = word1.size(), n2 = word2.size();
// dp[i][j] 表示 w[:i] 和 w[:j] 的转换最少操作数
vector<vector<int>> dp(n1+1, vector<int>(n2+1, INT_MAX));
for(int j=0; j<=n2; j++)  dp[0][j] = j;
for(int i=0; i<=n1; i++)  dp[i][0] = i;

for(int i=1; i<=n1; i++){
    for(int j=1; j<=n2; j++){
        dp[i][j] = min({dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1});
        if(word1[i-1] == word2[j-1])
            dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
    }
}

答案 dp[n1][n2]

96. 只出现一次的数字

全部求异或

1
2
3

// 哈希表肯定可以做，但是这里更巧妙的是位运算求异或
int ans = 0;
for(int num: nums)  ans ^= num;

97. 多数元素

这里众数过半，可以看做正负粒子，可以慢慢消耗

int cnt = 0, ans;
for(int num: nums){
    if(cnt == 0)
        ans = num, cnt++;
    else
        if(num == ans)  cnt++;
        else  cnt--;
}

98. 颜色分类

别想那么多，还是太复杂，简简单单先看0，再看1，反正都是O(n)

int p = 0;
for(int i=0; i<n; i++)
    if(nums[i] == 0)  swap(nums[p], nums[i]), p++;
for(int i=p; i<n; i++)
    if(nums[i] == 1)  swap(nums[p], nums[i]), p++;

99. 下一个排列

7 6 5 9 3 8 4 2 1
4 3
4 1 2 3 8

从后面找，找到第一个相邻升序的 a<x（若没有则已经最大字典序，直接全员反转结束）
从 a 右边找到满足比a大的最小数字b（倒着找到第一个满足大于a的就是最小的）
把 b 换过来, a 过去
重排a右边（不含a），从小到大排（直接反转即可）

int n = nums.size();
// 1. ai
int ai = -1;
for(int i=n-2; i>=0 && ai == -1; i--)
    if(nums[i] < nums[i+1])  ai = i;
if(ai == -1){
    reverse(nums.begin(), nums.end());
    return ;
}
// 2. bi
int bi = -1;
for(int i=n-1; i>ai && bi == -1; i--)
    if(nums[i] > nums[ai])  bi = i;
// 3. 交换
swap(nums[ai], nums[bi]);
// 4. 重排后续
reverse(nums.begin()+ai+1, nums.end());

100. 寻找重复数

模拟链表找入环点

// 第一次相遇
int slow = 0, fast = 0;
do{
    slow = nums[slow];
    fast = nums[nums[fast]];
}while(slow != fast);
// 入环点
fast = 0;
while(slow != fast){
    slow = nums[slow];
    fast = nums[fast];
}

return fast;