Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

力扣100热题

发布于：Jun 22, 2025

记录一下算法

二叉树（Morris）

二叉树的中序遍历(√)

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

image-20250622010341916

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]

解法：没啥好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void zhongxu(struct TreeNode* root, int* res, int* returnSize);
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    zhongxu(root, res, returnSize);
    return res;
}
void zhongxu(struct TreeNode* root, int* res, int* returnSize) {
    if (root == NULL) {
        return;
    }
    zhongxu(root->left, res, returnSize);
    res[(*returnSize)++] = root->val;
    zhongxu(root->right, res, returnSize);
}

二叉树的最大深度(√)

给定一个二叉树 root ，返回其最大深度。

解法：没啥好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int deep(struct TreeNode* root);
int maxDepth(struct TreeNode* root) { return deep(root); }
int deep(struct TreeNode* root) {
    if (!root) {
        return 0;
    }
    int l = deep(root->left);
    int r = deep(root->right);
    return (l > r ? l : r) + 1;
}

翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

image-20250622011048170

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

解法：只能用后续遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void reverse(struct TreeNode* root);
struct TreeNode* invertTree(struct TreeNode* root) {
    reverse(root);
    return root;
}

void reverse(struct TreeNode* root) {
    if (!root) {
        return;
    }
    reverse(root->left);
    reverse(root->right);
    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
}

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

image-20250622012210417

解法：利用队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty()) {
            TreeNode* l = q.front();
            q.pop();
            TreeNode* r = q.front();
            q.pop();
            if (!l && !r)
                continue;
            if (l == NULL || r == NULL || l->val != r->val)
                return false;
            q.push(l->left);
            q.push(r->right);
            q.push(l->right);
            q.push(r->left);
        }
        return true;
    }
};

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

image-20250622013044200

1
2
3
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

解法：问题转换为：对于任意一个节点，经过该节点的最长路径 = 左子树深度 + 右子树深度。我们需要遍历所有节点，找到这个最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int max(int a, int b) { return a > b ? a : b; }
int func(struct TreeNode* root, int* res) {
    if (root == NULL) {
        return 0;
    }
    int l = func(root->left, res);
    int r = func(root->right, res);
    *res = max(*res, l + r);
    return max(l, r) + 1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
    int res = 0;
    func(root, &res);
    return res;
}

二叉树的层序遍历(√)

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

解法：没啥好说的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        queue<TreeNode*> q;
        vector<vector<int>> res;
        if (!root)
            return res;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> temp;
            for (int i = 0; i < size; i++) {
                TreeNode* p = q.front();
                q.pop();
                temp.push_back(p->val);
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }
            res.push_back(temp);
        }
        return res;
    }
};

将有序数组转换为二叉搜索树(x)

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

image-20250622014957339

解法：由于输入数组已经有序，选择中间元素作为根节点，左半部分构建左子树，右半部分构建右子树，这样可以保证树的高度平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* addNode(int data) {
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left = NULL;
    root->right = NULL;
    root->val = data;
    return root;
}
struct TreeNode* create(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    int mid = left + (right - left) / 2;
    struct TreeNode* root = addNode(nums[mid]);
    root->left = create(nums, left, mid - 1);
    root->right = create(nums, mid + 1, right);
    return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return create(nums, 0, numsSize - 1);
}

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

解法：用一个前驱节点来保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool func(struct TreeNode* root, struct TreeNode** pre) {
    if (!root) {
        return true;
    }
    bool l = func(root->left, pre);
    if ((*pre) != NULL && (*pre)->val >= root->val) {
        return false;
    }
    (*pre) = root;
    bool r = func(root->right, pre);
    return l && r;
}
bool isValidBST(struct TreeNode* root) {
    struct TreeNode* pre = NULL;

    return func(root, &pre);
}

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

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

image-20250622023329166

1
2
输入：root = [3,1,4,null,2], k = 1
输出：1

解法：跟踪计数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void func(struct TreeNode* root, int k, int* count, int* res) {
    if (!root)
        return;
    func(root->left, k, count, res);
    (*count)++;
    if (*count == k) {
        *res = root->val;
    }
    func(root->right, k, count, res);
}
int kthSmallest(struct TreeNode* root, int k) {
    int res = 0;
    int count = 0;
    func(root, k, &count, &res);
    return res;
}

二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

1
2
3
输入：root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

image-20250622024416188

image-20250622024419466

解法：就是层序遍历，只取最右边的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<int> res;
        if (!root) {
            return res;
        }
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode* p = q.front();
                q.pop();
                if (i == n - 1) {

                    res.push_back(p->val);
                }
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }
        }
        return res;
    }
};

二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

image-20250622030122349

1
2
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

解法1：反向先序遍历，右→左→中。看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void func(struct TreeNode* root, struct TreeNode** pre) {
    if (!root)
        return;
    func(root->right, pre);
    func(root->left, pre);
    root->right = *pre;
    root->left = NULL;
    *pre = root;
}
void flatten(struct TreeNode* root) {
    struct TreeNode* pre = NULL;
    func(root, &pre);
}

解法2：Morris思想，我们要按前序遍历的顺序重新组织节点：

根 → 左子树 → 右子树

对于每个节点，如果它有左子树，我们需要找到左子树的最右节点

将当前节点的右子树接到左子树最右节点的右边

然后将左子树移到右边，左子树置为null

用图来理解：

image-20250622150123693

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void flatten(struct TreeNode* root) {
    struct TreeNode* p = root;
    while (p) {
        if (p->left != NULL) {
            struct TreeNode* temp = p->left;
            while (temp->right) {
                temp = temp->right;
            }
            temp->right = p->right;
            p->right = p->left;
            p->left = NULL;
        }
        p = p->right;
    }
}

路径总和 III(x)

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

image-20250623010230583

1
2
3
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

解法：

核心思想： 我们可以利用前缀和的性质来快速判断任意一段路径的和。

什么是前缀和？ 在二叉树的路径中，从根节点到当前节点的所有节点值之和，就是当前节点的前缀和。

关键观察： 如果我们知道两个节点的前缀和分别是 prefixSum1 和 prefixSum2，那么这两个节点之间的路径和就是：

1
路径和 = prefixSum2 - prefixSum1

转化问题： 原问题：找路径和等于 targetSum 的路径数量 转化为：找两个节点，使得它们的前缀和之差等于 targetSum

即：prefixSum2 - prefixSum1 = targetSum 也就是：prefixSum1 = prefixSum2 - targetSum

举个例子：

1
2
3
4
5
    10
   /
  5
 /
3
  • 节点10的前缀和：10
  • 节点5的前缀和：10 + 5 = 15
  • 节点3的前缀和：10 + 5 + 3 = 18

如果 targetSum = 8，我们要找前缀和为 18 - 8 = 10 的节点，正好是根节点10！ 所以路径 5 -> 3 的和就是 8。

哈希表存储

Key： 前缀和的值

Value： 该前缀和出现的次数

为什么要记录次数？ 因为可能有多个节点具有相同的前缀和（特别是有负数节点时），每个都对应一条有效路径。

为什么要移除当前节点的前缀和？

因为我们的哈希表只应该存储当前路径上的前缀和，而不是整棵树所有访问过的节点的前缀和。

用例子说明：

1
2
3
4
5
    1
   / \
  2   3
 /
4

假设 targetSum = 3，让我们跟踪遍历过程：

第一条路径：1 -> 2 -> 4

  1. 节点1：currentSum=1，哈希表={0:1, 1:1}
  2. 节点2：currentSum=3，哈希表={0:1, 1:1, 3:1}，找到路径1->2
  3. 节点4：currentSum=7，哈希表={0:1, 1:1, 3:1, 7:1}
  4. 回溯到节点2：移除7，哈希表={0:1, 1:1, 3:1}
  5. 回溯到节点1：移除3，哈希表={0:1, 1:1}

第二条路径：1 -> 3 6. 节点3：currentSum=4，哈希表={0:1, 1:1, 4:1}

如果不回溯会怎样？ 当处理节点3时，哈希表仍然是{0:1, 1:1, 3:1, 7:1}，这样就会错误地认为节点2和节点4还在当前路径上，可能产生错误的路径计算。

回溯的本质： 确保哈希表始终只包含从根节点到当前节点这条路径上的前缀和，保证计算的正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int func(TreeNode* root, int targetSum, long long cur,
             unordered_map<long long, int>& map) {
        if (!root)
            return 0;
        cur = cur + root->val;
        int count = map[cur - targetSum];//不能用targetSum-cur，只有cur - targetSum才是下面的-上面的
        map[cur]++;
        count = count + func(root->left, targetSum, cur, map);
        count = count + func(root->right, targetSum, cur, map);
        map[cur]--;
        return count;
    }
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> map;
        map[0] = 1;
        return func(root, targetSum, 0, map);
    }
};

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

image-20250623011158191

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

解法：

  • 如果root为空，直接返回
  • 如果root=p或者q，返回root。
  • 如果在左右子树都找到了p或者q。说明当前节点就是祖先
  • 如果左边找到了p右边没找到q，说明q在左下
  • 如果在右边找到了p左边没找到q，说明q在右下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* func(struct TreeNode* root, struct TreeNode* p,
                      struct TreeNode* q) {
    if (!root)
        return NULL;
    if (root == p || root == q)
        return root;
    struct TreeNode* left = func(root->left, p, q);
    struct TreeNode* right = func(root->right, p, q);
    if (left != NULL && right != NULL)
        return root;
    if (left != NULL)
        return left;
    return right;
}
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p,
                                      struct TreeNode* q) {
    return func(root, p, q);
}

二叉树中的最大路径和(背)

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

image-20250623013547805

1
2
3
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

解法：

对于每个节点，我们需要考虑两种情况：

  1. 经过该节点的最大路径和（该节点作为路径的”转折点”）
  2. 以该节点为端点向上延伸的最大路径和（该节点作为路径的一端，可以向上连接到父节点）

这两个概念完全不同：

  • 第一种情况：路径在该节点”拐弯”，左右子树都可能被包含
  • 第二种情况：路径在该节点”向上延伸”，只能选择左子树或右子树其中之一

递归函数返回： 以node为端点向上延伸的最大路径和，同时在递归过程中更新全局最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 递归函数返回的当前节点向上延伸的最大路径和
int Max(int a, int b) { return a > b ? a : b; }
int func(struct TreeNode* root, int* max) {
    if (!root)
        return 0;
    int left = Max(0, func(root->left, max));
    int right = Max(0, func(root->right, max));
    int nowPath = root->val + left + right;
    *max = Max(*max, nowPath);
    return root->val + Max(left, right);
}
int maxPathSum(struct TreeNode* root) {
    int max = -0xffffff;
    func(root, &max);
    return max;
}

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

image-20250623022307212

1
2
3
前序：[1,2,4,5,3,6]

中序：[4,2,5,1,3,6]

栈操作的详细过程：

初始状态：

1
2
栈：[]
inorderIndex = 0  // 指向中序的4

步骤1：处理节点1

1
2
3
4
TreeNode node1 = new TreeNode(1);
stack.push(node1);  
// 栈：[1]
// inorderIndex = 0，指向4

步骤2：处理节点2

1
2
3
4
5
6
7
8
TreeNode node2 = new TreeNode(2);
TreeNode parent = stack.peek();  // parent = 1

// 关键判断：1 != inorder[0](即4)
// 说明还在左子树，所以2是1的左子节点
parent.left = node2;
stack.push(node2);
// 栈：[1, 2]，inorderIndex = 0

步骤3：处理节点4

1
2
3
4
5
6
7
8
TreeNode node4 = new TreeNode(4);
TreeNode parent = stack.peek();  // parent = 2

// 关键判断：2 != inorder[0](即4)
// 说明还在左子树，所以4是2的左子节点
parent.left = node4;
stack.push(node4);
// 栈：[1, 2, 4]，inorderIndex = 0

步骤4：处理节点5

1
2
3
4
5
TreeNode node5 = new TreeNode(5);
TreeNode parent = stack.peek();  // parent = 4

// 关键判断：4 == inorder[0](即4) ！！！
// 这是第一次相等！说明什么？

相等意味着： 栈顶节点4就是中序遍历当前要访问的节点！

这时我们需要”回退”：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 开始弹栈，找到应该挂右子树的节点
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
    parent = stack.pop();      // parent变成4，然后弹出4
    inorderIndex++;            // inorderIndex变成1，指向2
}

// 继续判断：栈顶现在是2，inorder[1]也是2，继续相等
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
    parent = stack.pop();      // parent变成2，然后弹出2  
    inorderIndex++;            // inorderIndex变成2，指向5
}

// 现在栈顶是1，inorder[2]是5，不相等了，退出循环
// parent = 2，所以5是2的右子节点
parent.right = node5;
stack.push(node5);
// 栈：[1, 5]，inorderIndex = 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        stack<TreeNode*> stack;
        TreeNode* root = new TreeNode(preorder[0]);

        int inorderIndex = 0;
        stack.push(root);
        for (int i = 1; i < preorder.size(); i++) {
            TreeNode* par = stack.top();
            TreeNode* newnode = new TreeNode(preorder[i]);
            if (par->val != inorder[inorderIndex]) {
                par->left = newnode;
                stack.push(newnode);
            } else {
                while (!stack.empty() &&
                       stack.top()->val == inorder[inorderIndex]) {
                    par = stack.top();
                    stack.pop();
                    inorderIndex++;
                }
                par->right = newnode;
                stack.push(newnode);
            }
        }
        return root;
    }
};

图论

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解法：遍历整个图，当遇到1时，岛屿+1，同时递归遍历他的上下左右，将1变成0代表已经遍历过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1) {
            return;
        }
        if (grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
    }

}

腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

image-20250624172211335

1
2
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

解法：先遍历grid的，求出新鲜橘子的数量，并把腐烂的橘子放在队列里。从队列里取出烂橘子，判断烂橘子的4个方向是否是新鲜的，如果是新鲜的，记录当前新鲜+1，并将其变为腐烂橘子2，并把腐烂橘子加在队列里，同时记录这一层为isFulan=true;这一层结束后，如果isFulan=true，就把结果分钟+1，重置isFulan=false进入下一层。最后如果当前新鲜橘子的数量=开始计算出的新鲜橘子数量，说明新鲜橘子全部被腐烂，返回分钟数，反之返回-1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int freshcount = 0;
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    freshcount++;
                } else if (grid[i][j] == 2) {
                    q.add(new int[] { i, j });
                }
            }
        }
        boolean isFulan = false;
        int curcount = 0;
        int minuts = 0;
        int arr[][] = new int[][] {
                { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }
        };
        while (!q.isEmpty()) {
            int num = q.size();
            for (int i = 0; i < num; i++) {
                int cur[] = q.poll();
                for (int dir[] : arr) {
                    int newI = dir[0] + cur[0];
                    int newJ = dir[1] + cur[1];
                    if (newI < 0 || newI > m - 1 || newJ < 0 || newJ > n - 1) {
                        continue;
                    }
                    if (grid[newI][newJ] == 1) {
                        curcount++;
                        grid[newI][newJ] = 2;
                        q.add(new int[] { newI, newJ });
                        isFulan = true;
                    }
                }
            }
            if (isFulan == true) {
                minuts++;
                isFulan = false;
            }
        }
        return curcount == freshcount ? minuts : -1;
    }
}

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

解法：就是一个拓扑排序的过程，先构建邻接表和度数组。将度为0的节点入队，遍历队列，去出对应的邻接表，并且记录当前节点已经遍历，修改表里的节点的度-1，如果减过后度=0，则加在队列里。如果遍历的次数等于numCourses说明所有元素都已经遍历，是一个完整的拓扑排序，反之就有环。

实现 Trie (前缀树)(背)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

解法：直接背；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Trie {
    private Trie children[];
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public Trie searchPrefix(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    public boolean search(String word) {
        return searchPrefix(word) != null && searchPrefix(word).isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

技巧

出现一次的数字I

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]

输出：1

解法1：无需多言

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res=0;
        for(int i:nums){
            res=res^i;
        }
        return res;
    }
}

解法2：无需多言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int singleNumber(int[] nums) {
        int res=0;
        for(int i=0;i<32;i++){
            int count=0;
            for(int j=0;j<nums.length;j++){
                if( ((nums[j]>>i)&1)==1 ){
                    count++;
                }
            }
            if(count%2==1){
                res=res|(1<<i);
            }
            
        }
        return res;
    }
}

只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

1
2
输入：nums = [2,2,3,2]
输出：3

示例 2：

1
2
输入：nums = [0,1,0,1,0,1,99]
输出：99

解法1：相减法，先用set去重，假设每一个元素都出现3次，那么他们的乘积减去原数组x3=只出现一次的数字x2。代码无需多言。

解法2：位运算是通解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 == 1) {
                res = res | (1 << i);
            }

        }
        return res;
    }
}

只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

1
2
3
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

1
2
输入：nums = [-1,0]
输出：[-1,0]

解法：核心是异或完之后的结果是两个不同的数的异或结果。用n & (-n)得到最右边的1，用来作为区分位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] singleNumber(int[] nums) {
        int huo = 0;
        for (int i : nums) {
            huo = huo ^ i;
        }
        int res[] = new int[2];
        int split = huo & (-huo);
        for (int i : nums) {
            if ((i & split) != 0) {
                res[0] = res[0] ^ i;
            } else {
                res[1] = res[1] ^ i;
            }
        }
        return res;
    }
}

多数元素(Boyer-Moore 投票算法x)

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1
2
输入：nums = [3,2,3]
输出：3

示例 2：

1
2
输入：nums = [2,2,1,1,1,2,2]
输出：2

解法1：长度为n的数组，多数元素的个数一定≥n/2+1,所以多数元素的二进制位个数/(n/2+1)一定=1，少数元素的二进制位个数/(n/2+1)一定=0；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length / 2 + 1;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1) == 1) {
                    count++;
                }
                if (count / n != 0) {
                    res = res | (1 << i);
                }
            }
        }
        return res;
    }
}

颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地** 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]

解法1：单指针法，既然有三种颜色，我们可以分两步来处理：

  1. 第一次遍历：把所有的 0 移到数组前面
  2. 第二次遍历：把所有的 1 移到 0 的后面

这样剩下的 2 自然就在数组末尾了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public void sortColors(int[] nums) {

        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                swap(nums, index++, i);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                swap(nums, index++, i);
            }
        }
    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }
}

解法2：双指针法，（荷兰国旗问题）我们用三个指针来维护数组的不同区域，通过交换元素来完成排序：

  • left：指向下一个 0 应该放置的位置
  • right：指向下一个 2 应该放置的位置
  • current：当前正在处理的元素

当 current 指针遇到不同数字时，我们有不同的处理方式：

情况1：nums[current] == 0（红色）

  • 操作：将 nums[current] 与 nums[left] 交换
  • 移动指针：left++，current++
  • 原因：0应该放在左边区域，交换后left位置就是正确的0

情况2：nums[current] == 1（白色）

  • 操作：什么都不做
  • 移动指针：只有 current++
  • 原因：1本来就应该在中间，当前位置就对了

情况3：nums[current] == 2（蓝色）

  • 操作：将 nums[current] 与 nums[right] 交换
  • 移动指针：right--，current不动
  • 原因：2应该放在右边，但交换过来的元素还没检查过，所以current不能前进
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public void sortColors(int[] nums) {
        int left=0;
        int right=nums.length-1;
        int cur=0;
        while(cur<=right){
            if(nums[cur]==0){
                swap(nums,left,cur);
                left++;
                cur++;
            }else if(nums[cur]==1){
                cur++;
            }else{
                swap(nums,cur,right);
                right--;
            }
        }
    }
    public void swap(int nums[],int i,int j){
        int temp=nums[j];
        nums[j]=nums[i];
        nums[i]=temp;
    }
}

下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

  • 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须** 原地 **修改，只允许使用额外常数空间。

示例 1：

1
2
输入：nums = [1,2,7,4,3,1]
输出：[1,3,1,2,4,7]

示例 2：

1
2
输入：nums = [3,2,1]
输出：[1,2,3]

解法：

  1. **从右往左找”峰值”**：找到第一个 nums[i] < nums[i+1] 的位置
  2. 如果找不到：说明数组完全降序，没有更大排列
  3. 如果找到了：在右边找到比 nums[i] 大的最小数字来替换
  4. 替换后颠倒后面：让右边部分尽可能小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public void nextPermutation(int[] nums) {
        //[1,2,7,4,3,1]
        int i = nums.length - 2;
        while (i >= 0 && nums[i] > nums[i + 1]) {
            i--;
        }
        if (i == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        int j = nums.length - 1;
        while (nums[i] >= nums[j]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1, nums.length - 1);

    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    }

    public void reverse(int nums[], int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

1
2
输入：nums = [1,3,4,2,2]
输出：2

示例 2：

1
2
输入：nums = [3,1,3,4,2]
输出：3

解法1：

对于长度为n的数组，其数字都在 [1, n-1] 范围内，也就是说至少有一个元素是重复的，假设n=5，

理想情况下的数组是：

[1,2,3,4]

实际重复的情况下是：

[1,2,2,3,4];

对于每一个数的二进制位的和， 假设如果理想情况下的第0位的和！=实际情况下第0位的和，说明这重复元素的这一位=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int findDuplicate(int[] nums) {

        int n = nums.length;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int actualCount = 0;
            int idealCount = 0;
            for (int j = 0; j < n; j++) {
                if ((nums[j] >> i & 1) == 1) {
                    actualCount++;
                }
            }
            for (int j = 1; j < n; j++) {
                if ((j >> i & 1) == 1) {
                    idealCount++;
                }
            }
            if (actualCount > idealCount) {
                res = res | (1 << i);
            }
        }
        return res;
    }
}

解法2：将将数组看作一个隐式的链表，数组索引看作节点，数组值看作指向下一个节点的指针，转化为寻找链表的入环口，参考链表题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        int head = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) {
                while (slow != head) {
                    slow = nums[slow];
                    head = nums[head];
                }
                return slow;
            }
        }

    }
}

二分查找

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

解法：注意是left<=right,循环结束后，left指向第一个≥target的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return left;
    }
}

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

image-20250629011928369

1
2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

解法：讲二维数组展开变成一维数组，然后用二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
    /**
        2x4 3=11
        0x4 2=2
        1x4 1=5
        11/n  11%n
        
        
         */
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int i = mid / n;
            int j = mid % n;
            if (matrix[i][j] < target) {
                left = mid + 1;
            } else if (matrix[i][j] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;
        
    }
}

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

​ 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

解法1：二分找到后不返回，继续找:

找第一个时有两种情况，当前mid不是第一个，则需要继续往左找。如果是第一个，往左找永远找不到。

找第二个时有两种情况，当前mid不是最后一个，则需要继续往右找。如果是最后一个，往右永远找不到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[2];
        res[0] = findFirst(nums, target);
        res[1] = findLast(nums, target);
        return res;
    }

    public int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                res = mid;
                //找到了会有两种情况：
                //1、mid不是第一个，则需要继续往左找
                //2、mid是第一个，左找一定找不到
                right = mid - 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    public int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                res = mid;
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}

解法2：利用小数：

1
输入：nums = [5,7,7,8,8,10], target = 8，查找8-0.5和8+0.5

因为这两个数永远不会找到，所以找7.5后，left会落到第一个大于7.5的位置，也就是第一个8。

找8.5后，left会落到第一个大于8.5的位置，也就是10，那么right=left-1就落在了最后一个8.

但是要注意边界条件，这里还没有搞懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[2];
        res[0] = findFirst(nums, target);
        res[1] = findLast(nums, target);
        return res;
    }

    public int findFirst(int[] nums, int target) {
        double newTarget = target - 0.5;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < newTarget) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (left < nums.length && nums[left] != target) {
            return -1;
        }
        return left < nums.length ? left : -1;
    }

    public int findLast(int[] nums, int target) {
        double newTarget = target + 0.5;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < newTarget) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (left - 1 >= 0 && nums[left - 1] != target) {
            return -1;
        }
        return left - 1 >= 0 ? left - 1 : -1;
    }
}

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

解法：旋转数组有一个重要性质：一定有一半是完全有序的，如果left的值<=mid值，说明左边有序，反之右边有序，在有序的部分进行二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
                //左半部分有序
                if (target >= nums[left] && target <= nums[mid]) {//如果target在left和mid之间，进行二分
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                //右半部分有序
                if (target >= nums[mid] && target <= nums[right]) {//如果target在mid和right之间，进行二分
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;

    }
}

寻找旋转排序数组中的最小值(背)

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
2
3
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

1
2
3
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

解法：

如果左端 < 右端，说明数组没有旋转，整个数组有序

如果mid位置的值比right位置的值大，说明中间有断点，最小值在断点右边。

如果mid位置的值 ≤ right位置的值，说明从mid到right是有序的，最小值可能就是mid。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        if (nums[left] < nums[right]) {
            return nums[0];
        }
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

寻找两个正序数组的中位数(背)

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //11
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0;
        int right = m;//注意！
        while (left <= right) {
            int i = (left + right) / 2;//A左边的个数
            int j = (m + n + 1) / 2 - i;//B左边的个数
            int ALeftMax = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int ARightMin = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int BLeftMax = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int BRightMin = (j == n ? Integer.MAX_VALUE : nums2[j]);
            if (ALeftMax <= BRightMin && BLeftMax <= ARightMin) {
                if ((m + n) % 2 == 1) {
                    return Math.max(ALeftMax, BLeftMax);
                } else {
                    return (Math.max(ALeftMax, BLeftMax) + Math.min(ARightMin, BRightMin)) / 2.0;
                }
            } else if (ALeftMax > BRightMin) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        return -1;
    }
}

栈

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”

输出：true

示例 2：

输入：s = “()[]{}”

输出：true

示例 3：

输入：s = “(]”

输出：false

示例 4：

输入：s = “([])”

输出：true

解法：很恶心的题，判断条件多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char str[] = s.toCharArray();

        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
                stack.push(str[i]);
            } else {
                if (!stack.isEmpty()) {
                    if (stack.peek() == '(' && str[i] == ')'
                            || stack.peek() == '[' && str[i] == ']'
                            || stack.peek() == '{' && str[i] == '}') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }

            }
        }
        if (!stack.isEmpty()) {
            return false;
        }
        return true;
    }
}

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

1
2
3
4
5
6
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解法：维护两个栈，一个主栈，一个最小栈。

push：只要当最小栈为空或者添加的元素<=栈顶元素时，最小栈才push；注意是<=,因为有重复元素。

pop：只要当主栈pop的值与最小栈的栈顶值一样时，才pop；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || minStack.peek() >= val) {
            minStack.push(val);
        }
    }

    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

1
2
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

1
2
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

1
2
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

1
2
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

解法：用两个栈，一个栈用来记录数字，一个栈用来记录上一个字符串。

  1. 初始化：数字栈、字符串栈、当前数字、当前字符串

  2. 遍历字符串，分情况处理：

    • 遇到数字字符：累积构建多位数字（如”23”要构建成数字23）

    • 遇到左括号 [

      ：

      • 说明要开始处理一个新的编码块
      • 把当前的数字和字符串”暂存”到栈中
      • 清空当前数字和字符串，准备处理括号内的内容

    • 遇到右括号 ]

      ：

      • 说明当前编码块处理完毕
      • 从栈中取出之前保存的重复次数和字符串
      • 将当前字符串重复指定次数
      • 与之前的字符串拼接，作为新的当前字符串

    • 遇到普通字母：直接添加到当前字符串中

  3. 返回最终的当前字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public String decodeString(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<String> strStack = new Stack<>();
        int curNum = 0;
        String curStr = "";
        char str[] = s.toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (Character.isDigit(str[i])) {
                curNum = curNum * 10 + str[i] - '0';
            } else if (str[i] == '[') {
                numStack.push(curNum);
                strStack.push(curStr);
                curNum = 0;
                curStr = "";
            } else if (str[i] == ']') {
                int repeats = numStack.pop();
                String preStr = strStack.pop();
                String temp = "";
                for (int j = 0; j < repeats; j++) {
                    temp = temp + curStr;
                }
                curStr = preStr + temp;
            } else {
                curStr = curStr + str[i];
            }
        }
        return curStr;
    }
}

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

解法：使用一个栈来记录还没有找到下一个更高温度的日期索引。栈中存储的是温度数组的下标，并且栈底到栈顶对应的温度是单调递减的。

算法思路：

  1. 初始化：创建一个栈用来存储数组索引，创建结果数组 res

  2. 遍历温度数组

    ：对于每个位置 

    1
    i

    ：

    • 栈不为空且当前温度大于栈顶索引对应的温度

      ：说明为栈顶的日期找到了下一个更高温度

      • 弹出栈顶索引 index
      • 计算天数差：res[index] = i - index
      • 重复此过程直到栈为空或当前温度不大于栈顶温度

    • 将当前索引压入栈：等待后续找到更高温度

  3. 返回结果：栈中剩余的索引对应的位置在 res 中保持默认值 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int res[] = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int index = stack.pop();
                res[index] = i - index;
            }
            stack.push(i);
        }
        return res;
    }
}

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

解法1：快速排序思想：

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, k, 0, nums.length - 1);
    }

    public int quickSort(int[] nums, int k, int left, int right) {
        int n = nums.length;
        int part = partition(nums, left, right);
        if (part < n - k) {
            return quickSort(nums, k, part + 1, right);
        } else if (part > n - k) {
            return quickSort(nums, k, left, part - 1);
        } else {
            return nums[part];
        }

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public int partition(int[] nums, int left, int right) {
        Random rand = new Random();
        int randomIndex = left + rand.nextInt(right - left + 1);
        swap(nums, left, randomIndex);
        int temp = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= temp)
                right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= temp)
                left++;
            nums[right] = nums[left];
        }
        nums[left] = temp;
        return left;
    }

}

解法二：小根堆

1
2
3
4
5
6
7
8
9
10
public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int num : nums) {
            q.add(num);
            if (q.size() > k) {
                q.poll();
            }
        }
        return q.peek();
    }

解法3：堆排序思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int findKthLargest(int[] nums, int k) {
        build(nums);
        int n = nums.length - 1;
        for (int i = n; i >= n - k + 2; i--) {//循环的次数
            swap(nums, 0, i);//第一个元素和最后一个元素交换
            adjust(nums, 0, i - 1);//交换后数组长度-1，调整前面的。
        }
        return nums[0];
    }

    public void build(int[] nums) {
        int n = nums.length - 1;
        for (int i = n / 2; i >= 0; i--) {
            adjust(nums, i, n);
        }
    }

    public void swap(int nums[], int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void adjust(int[] nums, int k, int n) {

        for (int i = k * 2 + 1; i <= n; i = i * 2 + 1) {//注意i <= n
            if (i < n && nums[i] < nums[i + 1]) {//注意i < n
                i++;
            }
            if (nums[i] > nums[k]) {
                int temp = nums[i];
                nums[i] = nums[k];
                nums[k] = temp;
                k = i;
            }
        }
    }

}

解法4：桶排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        //0 1 2 3 4 5
        //1 2 2 1 2 1
        int bucketLen = max - min + 1;
        int bucket[] = new int[bucketLen];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            bucket[nums[i] - min]++;
        }
        int count = 0;
        for (int j = bucketLen - 1; j >= 0; j--) {
            count = count + bucket[j];
            if (count >= k) {
                return j + min;

            }
        }
        return -1;
    }

}

更新于：Jul 2, 2025

评论