Posted Updated algorithm

矩阵处理算法题目集合

leetcode48 旋转图像

思路

  • 1/4 矩阵旋转

leetcode289 生命游戏

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律： 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活； 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡； 如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

题解

leecode 题解

使用二进制的第二位存储修改后的状态。

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 gameOfLife(vector<vector<int>>& board) {
        int dx[] = {-1,  0,  1, -1, 1, -1, 0, 1};
        int dy[] = {-1, -1, -1,  0, 0,  1, 1, 1};

        for(int i = 0; i < board.size(); i++) {
            for(int j = 0 ; j < board[0].size(); j++) {
                int sum = 0;
                for(int k = 0; k < 8; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) {
                        sum += (board[nx][ny]&1); // 只累加最低位
                    }
                }
                if(board[i][j] == 1) {
                    if(sum == 2 || sum == 3) {
                        board[i][j] |= 2;  // 使用第二个bit标记是否存活
                    }
                } else {
                    if(sum == 3) {
                        board[i][j] |= 2; // 使用第二个bit标记是否存活
                    }
                }
            }
        }
        for(int i = 0; i < board.size(); i++) {
            for(int j = 0; j < board[i].size(); j++) {
                board[i][j] >>= 1; //右移一位，用第二bit覆盖第一个bit。
            }
        }
    }
};

矩阵哈希

leetcode36 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

题解

分别从行、列和九宫格统计数字出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isValidSudoku(vector<vector<char>>& board) {

    vector<vector<bool>> row(9, vector<bool>(9, false));
    vector<vector<bool>> col(9, vector<bool>(9, false));
    vector<vector<bool>> box(9, vector<bool>(9, false));

    for (int i = 0; i < 9; i ++) {
        for (int j = 0; j < 9; j ++) {
            if (board[i][j] == '.') continue;
            int b = i / 3 * 3 + j / 3;
            int no = board[i][j] - '0' - 1;
            if (row[i][no] || col[j][no] || box[b][no]) return false;
            row[i][no] = true;
            col[j][no] = true;
            box[b][no] = true;
        }
    }

    return true;
}

leetcode240 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

利用特性缩小检索范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int a = 0, b = 0;
    int i = m - 1, j = n - 1;
    while (i >= 0 && j >= 0) {
        if (matrix[i][j] < target) return false;
        while (b < n - 1 && matrix[i][b] < target) {
            b ++;
        }
        if (matrix[i][b] == target) return true;
        i --;
        while (a < m - 1 && matrix[a][j] < target) {
            a ++;
        }
        if (matrix[a][j] == target) return true;
        j --;
    }
    return false;
}

转换为二叉搜索树

参考题解

Posted Updated algorithm

数学推理算法题目集合

2024 360 秋招提前批 最大曼哈顿距离

给定一个包含若干个点的集合，求其中任意两点之间的最大/最小曼哈顿距离。

题解

由上述式子可得：

整理合并可得：

所以，问题转换为比较点和点的横纵坐标和与差。 在遍历各个点的时候分别计算横纵坐标的和与差，且分别排序。 将最大值减去最小值得到两种情况下的最大曼哈顿距离，然后再从中选择最大的曼哈顿距离作为最终答案。

1
2
3
4
5
6
7
8
9
vector<int> d1;
vector<int> d2;
for (int i = 0; i < points.size(); i ++)
    d1.push_back(points[i][0] - points[i][1])
    d2.push_back(points[i][0] + points[i][1])
sort(d1.begin(), d1.end())
sort(d2.begin(), d2.end())

cout << max(d1[d1.size() - 1] - d1[0], d2[d2.size() - 1] - d2[0]))

相似题型

1014. 最佳观光组合

leetcode172 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。 提示 

1
2
3
4
5
6
7
8
9
10
11
int trailingZeroes(int n) {
    int times = 0;
    for (int i = 5; i <= n; i += 5) {
        int count = i;
        while (count && count % 5 == 0) {
            times ++;
            count /= 5;
        }
    }
    return times;
}

leetcode201 数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

题解

相邻两个数相与，末尾的 0 将会被消除，通过移位找公共前缀得到区间相与结果

1
2
3
4
5
6
7
8
9
10
int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    // 找到公共前缀
    while (left < right) {
        left >>= 1;
        right >>= 1;
        ++shift;
    }
    return left << shift;
}

leetcode1823 找出游戏的获胜者

思路

leetcode29 两数相除

思路

  • 特殊情况处理
  • 除数左移位，与被除数比较

leetcode238 除自身以外数组的乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

题解

正反向前缀积，使用中间变量记录累积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret(nums.size());
        int mul = nums[0];
        ret[0] = 1;
        for (int i = 1; i < nums.size(); i ++) {
            ret[i] = mul;
            mul *= nums[i];
        }
        mul = nums[nums.size() - 1];
        for (int i = nums.size() - 2; i >= 0; i --) {
            ret[i] *= mul;
            mul *= nums[i];
        }
        return ret;
    }
};

leetcode69 x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

题解

官方题解

乘方拆解

leetcode50 Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，）。

题解

将拆解为

其中，式子可转换为

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
double myPow(double x, int n) {
    // 特殊情况
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n == -1) return 1 / x;

    bool flag = n < 0;
    long nn = n;
    if (flag) nn = -1 * nn;

    double temp = x;
    double res = 1;

    // 将 n 次累乘拆解为 logn 次
    while (nn > 1) {

        long times = 2;
        temp = x;

        while (true) {
            temp *= temp;
            if (times * 2 <= nn) times *= 2;
            else break;
        }

        nn -= times;
        res *= temp;

    }

    for (long i = 0; i < nn; i ++) res *= x;

    return flag ? 1 / res : res;
}

二进制位计数

leetcode137 只出现一次的数字 II

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

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

题解

统计每个二进制位 1 的出现次数，若只出现一次的数在该为为 0，那么统计次数应为 3 的倍数，否则有余数

1
2
3
4
5
6
7
8
9
10
11
int singleNumber(vector<int>& nums) {
    int ret = 0;
    for (int i = 0; i < 32; i ++) {
        int count = 0;
        for (auto n : nums) {
            count += n >> i & 1;
        }
        if (count % 3) ret += 1 << i;
    }
    return ret;
}

另一种方法通过状态机的思想，用一个两位二进制数统计当前二进制位的状态，00 -> 01 -> 10 -> 00

1
2
3
4
5
6
7
8
9
10
11
12
13
int singleNumber(vector<int>& nums) {
    // n1 表示二进制的低位
    // n2 表示二进制的高位
    int n1 = 0, n2 = 0;
    for (auto n : nums) {
        // 若高位 n2 为 0，则低位 n1 只与当前值 n 有关；否则计数已满 3，低位直接置 0
        n1 = ~n2 & n1 ^ n;
        // 若低位 n1 为 0，则高位 n2 只与当前值 n 有关，若 n 为 1，则表示要进位，否则表示计数已满；若低位为 1，那么高位只能为 0
        n2 = ~n1 & n2 ^ n;
    }
    // 若计数满 3，低位应为 0，若计数除以 3 余 1，则低位应为 1，所以返回低位
    return n1;
}

leetcode169 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

排序后中值必包含多数元素

1
2
3
4
int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
}

摩尔投票法

参考题解推荐了这种方法，思考方向为若与当前假设的众数相同，则投赞成票 1，否则投否认票-1，当得票为 0 时，则继续进行假设，多数元素将获得更多投票将投票值稳定为正；另外，从代码上理解，多数元素总有更多数量的连续元素

1
2
3
4
5
6
7
8
int majorityElement(vector<int>& nums) {
    int x = 0, votes = 0;
    for (int num : nums){
        if (votes == 0) x = num;
        votes += num == x ? 1 : -1;
    }
    return x;
}

集合类题目

leetcode2306 公司命名

Posted Updated algorithm

动态规划算法题目集合

0/1 背包

准备多种大小的背包，当物品体积小于背包时，可尝试比较当前已放置物品价值，与当前物品价值和更小体积背包放置物品价值之和，取更大值

leetcode416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (auto n : nums) sum += n;
    // 若累加值为奇数，则不可能存在这样的两个子集
    if (sum % 2 != 0) return false;
    sum >>= 1;
    int n = nums.size();
    // 判断大小为sum的背包，是否能恰好装入价值为sum的物品
    // 其中，各个物品的体积和价值均为nums[i]
    vector<int> maxPack(sum + 1);
    for (auto n : nums) {
        if (n > sum) return false;
        for (int i = sum; i >= n; i --) {
            maxPack[i] = max(maxPack[i], maxPack[i - n] + n);
        }
    }
    return maxPack[sum] == sum;
}

一维动态规划

leetcode139 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool wordBreak(string s, vector<string>& wordDict) {
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 1, len = s.size(); i <= len; i ++) {
        bool flag = false;
        for (string word : wordDict) {
            if (i < word.size()) continue;
            int start = i - word.size();
            if (dp[start] && s.substr(start, word.size()) == word) {
                flag = true;
                break;
            }
        }
        dp[i] = flag;
    }
    return dp[s.size()];
}

牛客 2021360 春招编程题(第一批) 火星人的宝藏

X 星人发现了一个藏宝图，在藏宝图中标注了 N 个宝库的位置。这 N 个宝库连成了一条直线，每个宝库都有若干枚金币。 X 星人决定乘坐热气球去收集金币，热气球每次最多只能飞行 M 千米（假设热气球在飞行过程中并不会发生故障）此外，由于设计上的缺陷，热气球最多只能启动 K 次。 X 星人带着热气球来到了第 1 个宝库（达到第 1 个宝库时热气球尚未启动），收集完第 1 个宝库的金币后将启动热气球前往下一个宝库。如果他决定收集某一个宝库的金币，必须停下热气球，收集完之后再重新启动热气球。当然，X 星人每到一个宝库是一定会拿走这个宝库所有金币的。 已知每一个宝库距离第 1 个宝库的距离（单位：千米）和宝库的金币数量。 请问 X 星人最多可以收集到多少枚金币？

输入描述： 单组输入。

第 1 行输入三个正整数 N、M 和 K，分别表示宝库的数量、热气球每次最多能够飞行的距离（千米）和热气球最多可以启动的次数，三个正整数均不超过 100，相邻两个正整数之间用空格隔开。

接下来 N 行每行包含两个整数，分别表示第 1 个宝库到某一个宝库的距离（千米）和这个宝库的金币枚数。（因为初始位置为第 1 个宝库，因此第 1 个宝库所对应行的第 1 个值为 0。）

输入保证所有的宝库按照到第 1 个宝库的距离从近到远排列，初始位置为第 1 个宝库。

输出描述： 输出一个正整数，表示最多可以收集的金币数。

示例 1 输入例子： 5 10 2 0 5 8 6 10 8 18 12 22 15 输出例子： 25 例子说明： X 星人启动热气球两次，分别收集第 1 个、第 3 个和第 4 个宝库的金币，一共可以得到的金币总数为 5+8+12=25 枚。

题解

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
50
51
52
53
54
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M, K;
    while (cin >> N >> M >> K) { // 注意 while 处理多个 case
        vector<vector<int>> ship(N, vector<int>(2, 0));
        vector<vector<int>> dp(N, vector<int>(K + 1, 0));
        int k, v;
        for (int i = 0; i < N; i ++) {
            cin >> k >> v;
            ship[i][0] = k;
            ship[i][1] = v;
            if (i > 0 && k <= M) {
                dp[i][1] = max(dp[i - 1][1], v);
            }
        }
        if (N - 1 <= K) {
            long long ret = 0;
            for (int i = 1; i < N; i ++) {
                if (ship[i][0] - ship[i - 1][0] > M) break;
                ret += ship[i][1];
                // cout << ret << endl;
            }
            cout << ret + ship[0][1];
            return 0;
        }
        for (int k = 2; k <= K; k ++) {
            for (int n = k; n < N; n ++) {
                int nn = n - 1;
                int maxV = 0;
                while (nn >= k - 1) {
                    if (dp[nn][k - 1] == 0) {
                        nn --;
                        continue;
                    }
                    if (ship[n][0] - ship[nn][0] > M) break;
                    maxV = max(maxV, dp[nn][k - 1] + ship[n][1]);
                    nn --;
                }
                dp[n][k] = maxV;
                // if (k == K) cout << "n: " << n << " k: " << k << " dp:" << dp[n][k] << endl;
            }
        }
        int ret = 0;
        for (int i = K; i < N; i ++) {
            ret = max(ret, dp[i][K]);
        }
        cout << ret + ship[0][1];
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

leetcode221 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

1
dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1])

leetcode873 最长的斐波那契子序列的长度

思路

  • 状态定义

    其中表示以位置 i 和 j 结尾的子序列

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 lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        if (n < 3) return 0;
        if (n == 3) {
            if (arr[0] + arr[1] == arr[2]) return 3;
            return 0;
        }
        int maxLen = 0;
        vector<vector<int>> m(n, vector<int>(n, 0));
        unordered_map<int, int> diff;
        for (int i = 1; i < n - 1; i ++) {
            diff[arr[i - 1]] = i - 1;
            for (int j = i + 1; j < n; j ++) {
                int interval = arr[j] - arr[i];
                if (diff.count(interval)) {
                    m[i][j] = m[diff[interval]][i] + 1;
                    maxLen = max(maxLen, m[i][j]);
                }
            }
        }
        return maxLen > 0 ? maxLen + 2 : 0;
    }
};

最大子数组和

leetcode918 环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。 环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

思路

通常对于环形数组的最大子数组和有两种情形，一种是不需要首尾相连的子数组，另一种则是需要连接开头的子数组 对于子数组 1，其求解方式与传统求解方法一样； 对于子数组 2，可以通过逆向思维求解，由于子数组 2 为最大子数组，所以数组的和减去子数组 2 的和，得到的是最小子数组 3，子数组 3 的首位是不相连的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int maxSubarraySumCircular(vector<int>& nums) {
    int maxSum = nums[0], minSum = nums[0];
    int preMaxSum = nums[0], preMinSum = nums[0];
    int sum = nums[0];
    for (int i = 1, len = nums.size(); i < len; i ++) {
        // 对比局部最大与当前值
        preMaxSum = max(preMaxSum + nums[i], nums[i]);
        // 对比最大值与局部最大
        maxSum = max(preMaxSum, maxSum);
        // 对比局部最小与当前值
        preMinSum = min(preMinSum + nums[i], nums[i]);
        // 对比最小值与局部最小
        minSum = min(preMinSum, minSum);
        // 数组累加和
        sum += nums[i];
    }
    // 若此时最大值为负值，即所有值为负值，则不存在两个子数组
    if (maxSum < 0) return maxSum;
    // 对比两个子数组
    return max(maxSum, sum - minSum);
}

逆向动态规划

leetcode174. 地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。 为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。 返回确保骑士能够拯救到公主所需的最低初始健康点数。 注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

思路

对于任意位置，其起始健康点数取决于后续经过的房间，所以尝试使用逆向 DP 解题 对比理解，若问题为到达终点的最大健康点数，对于任意位置，其最大健康点数只与已经经过的房间有关，可以使用正向 DP 解题 根据观察发现，当后续房间值为非负值时，对起始健康点数无影响；而当后续房间值为负值时，起始健康点数应为负值的相反数。由此可得到状态转移方程为： 其中，操作用于获得所需健康点数更小的后续房间值，操作则将正值置，保留负值 为了实现原地算法，将所需健康点数累加到当前位置，若累加后值为正，则代表加上当前房间值后，后续的路径勇士都有足够的健康点数，否则代表需要更大的健康点数 另外，由于勇士只有在健康点数为时才能存活，所以对于负值为的房间，需要保证起始健康点数为

时间复杂度: 空间复杂度: 

1
2
3
4
5
6
7
8
9
10
11
12
int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    for (int i = m - 1; i >= 0; i --) {
        int j = (i == m - 1) ? n - 2 : n - 1;
        for (; j >= 0; j --) {
            int right = (j + 1 == n) ? dungeon[i + 1][j] : dungeon[i][j + 1];
            int bottom = (i + 1 == m) ? dungeon[i][j + 1] : dungeon[i + 1][j];
            dungeon[i][j] += min(max(right, bottom), 0);
        }
    }
    return dungeon[0][0] > 0 ? 1 : (- 1 * dungeon[0][0]) + 1;
}

leetcode213 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

分类讨论动态规划

可考虑两种可能的情况，一种为小偷偷了第一家，最后一家就不能偷；第二种情况为小偷没有偷第一家

Posted Updated algorithm

排序辅助算法题目集合

leetcode274 H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

题解

1
2
3
4
5
6
7
8
9
10
int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int h = 0, i = citations.size() - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }

给定数组求组合

leetcode39 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路

题目要求得到所有组合，而不是值。所以考虑通过递归和回溯的方式得到不用的组合 组成元素和数量相同的两个组合为同一种组合，所以在递归的时候需要传递当前的候选值范围 由于有目标值的要求，可以通过排序剪枝不可能的组合

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
class Solution {
private:
    vector<vector<int>> ret;
public:

    void getSum(vector<int>& candidates, int target, int start, int sum, vector<int>& host) {
        // 若满足条件则记录
        if (sum == target) {
            ret.push_back(host);
            return;
        }
        // 从取值起始点遍历候选值
        for (int i = start, num = candidates.size(); i < num; i ++) {
            // 如果加上最小值都超过目标条件，那么可以直接结束遍历
            if (sum + candidates[i] > target) break;
            // 加入当前值到组合中
            host.push_back(candidates[i]);
            // 通过罗列自身及之后的候选值构建满足条件的组合
            getSum(candidates, target, i, sum + candidates[i], host);
            // 回溯组合
            host.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> v;
        getSum(candidates, target, 0, 0, v);
        return ret;
    }
};
Posted Updated algorithm

贪心算法题目集合

leetcode452 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [, ] 表示水平直径在 和 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 , 且满足 ≤ x ≤ ，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。 给你一个数组 points ，返回引爆所有气球所必须射出的 最小弓箭数 。

题解

排序，记录最小右边界（箭所能移动的最远方向），若不在射程范围内，记录新的右边界，否则更新最小右边界

Posted Updated algorithm

树算法题目集合

leetcode199 二叉树的右视图

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

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

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

题解

root->left->val < root->val < root->right->val

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
int kthSmallest(TreeNode* root, int k) {
    int count = 0;
    stack<TreeNode*> treeStack;
    treeStack.push(root);
    while (treeStack.size() > 0) {
        TreeNode* base = treeStack.top();
        if (base->left == nullptr) {
            count ++;
            treeStack.pop();
            if (count == k) {
                return base->val;
            }
            if (base->right != nullptr) {
                treeStack.push(base->right);
                continue;
            }
        }
        else {
            treeStack.push(base->left);
            base->left = nullptr;
            continue;
        }
    }
    return 0;
}

leetcode148 排序链表

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表

题解

归并排序链表，递归分治，子链表按序合并

树和算式

Leetcode 题解

各种表达式没有本质区别，他们其实是同一个语法树，只是遍历方式不同而得到的不同式子；是一个事物的一体多面，只不过是从不同角度观察罢了。

中缀表达式是其对应的语法树的中序遍历； 后缀表达式是其对应的语法树的后序遍历； 前缀表达式是其对应的语法树的前序遍历；

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

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

题解

前序遍历提供根节点，中序遍历提供子树结构

Leetcode 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++)
            dic[inorder[i]] = i;
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector<int> preorder;
    unordered_map<int, int> dic;
    TreeNode* recur(int root, int left, int right) {
        if (left > right) return nullptr;                        // 递归终止
        TreeNode* node = new TreeNode(preorder[root]);          // 建立根节点
        int i = dic[preorder[root]];                            // 划分根节点、左子树、右子树
        node->left = recur(root + 1, left, i - 1);              // 开启左子树递归
        node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                            // 回溯返回根节点
    }
};

leetcode94 树的中序遍历

中序遍历

使用栈数据结构控制遍历节点顺序，类比递归调用的栈

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
/**
 * 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> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr) return ret;
        stack<TreeNode*> tree;
        tree.push(root);
        while (! tree.empty()) {
            TreeNode* top = tree.top();
            if (top->left != nullptr) {
                tree.push(top->left);
                top->left = nullptr;
                continue;
            }
            ret.push_back(top->val);
            tree.pop();
            if (top->right != nullptr) {
                tree.push(top->right);
            }
        }
        return ret;
    }
};

通过递归重复根节点操作

leetcode124 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

思路

共有两种路径，一种是左右节点跨越根的环形路径，一种为父子节点的直线路径 在递归的过程中，若子树的值为负，对最大和无贡献，可置为 0，计算左右子树和根节点的和，更新当前最大值 注意递归的返回值需包含根节点，已构成完整路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    int maxSum = 0;
public:
    int getMax(TreeNode_ root) {
        if (! root) return 0;
        int left = max(0, getMax(root->left));
        int right = max(0, getMax(root->right));
        maxSum = max(maxSum, root->val + left + right);
        return root->val + max(left, right);
    }

    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        getMax(root);
        return maxSum;
    }

};

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。

leetcode222 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 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
class Solution {
public:

    // 计算子树高度
    int getHeight(TreeNode* root) {
        if (! root) return 0;
        return 1 + max(getHeight(root->left), getHeight(root->right));
    }

    // 计算子树节点数
    int countNodes(TreeNode* root) {
        if (! root) return 0;
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        // 比较子树高度
        if (leftHeight == rightHeight) {
            // 递归计算子树节点数，累加完全树节点数
            return countNodes(root->right) + (1 << leftHeight);
        }
        else {
            return countNodes(root->left) + (1 << rightHeight);
        }
    }
};
Posted Updated algorithm

栈算法题目集合

leetcode71 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。 请注意，返回的 规范路径 必须遵循下述格式： 始终以斜杠 '/' 开头。 两个目录名之间必须只有一个斜杠 '/' 。 最后一个目录名（如果存在）不能 以 '/' 结尾。 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。 返回简化后得到的规范路径。

题解

参考题解

leetcode150 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意： 有效的算符为 '+'、'-'、'*' 和 '/' 。 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。

题解

从左向右遍历，用栈存储数字，遇到符号出栈两个数字

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 evalRPN(vector<string>& tokens) {
        long result = 0;
        stack<int> nums;
        for (string token : tokens) {
            if (token != "+" && token != "-" && token != "*" && token != "/") {
                nums.push(stoi(token));
                continue;
            }
            int n2 = nums.top();nums.pop();
            int n1 = nums.top();nums.pop();
            if (token == "+") {
                nums.push(n1 + n2);
            }
            else if (token == "-") {
                nums.push(n1 - n2);
            }
            else if (token == "*") {
                nums.push(n1 * n2);
            }
            else if (token == "/") {
                nums.push(n1 / n2);
            }
        }
        return nums.top();
    }
};

leetcode84 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

单调栈获取两端更小值的索引

刚接触到题目以为与最大盛水量是相同解法，这题的不同之处在于面积取决于区间内的最小值，而不是两端的最小值 由此，对于柱高上升的区间，起始柱总能取其高计算面积，若新加入的柱高小于栈顶高，则表示已到达栈顶对应开区间的右端点，将栈顶弹出，新的栈顶表示开区间的左端点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int largestRectangleArea(vector<int>& heights) {
    int maxS = 0;
    // 方便计算开头与末尾的柱面积
    heights.insert(heights.begin(), 0);
    heights.emplace_back(0);
    int n = heights.size();
    // 单调栈
    stack<int> rise;
    rise.emplace(0);
    for (int i = 1; i < n; i ++) {
        // 触及右边界，出栈直到栈再次单调或为空
        while (! rise.empty() && heights[rise.top()] > heights[i]) {
            int h = heights[rise.top()]; rise.pop();
            int w = i - rise.top() - 1;
            maxS = max(maxS, h * w);
        }
        rise.emplace(i);
    }
    return maxS;
}

leetcode85 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 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
int maximalRectangle(vector<vector<char>>& matrix) {
    int maxS = 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<int> heights(n + 2, 0);
    stack<int> rise;
    // 遍历每一行
    for (int i = 0; i < m; i ++) {
        rise.emplace(0);
        // 计算当前高度
        for (int j = 0; j < n + 1; j ++) {
            if (j < n) {
                // 若为0则高度置0
                if (matrix[i][j] - '0') heights[j + 1] += 1;
                // 若为1高度加1
                else heights[j + 1] = 0;
            }
            // 区间判断
            while (! rise.empty() && heights[rise.top()] > heights[j + 1]) {
                int h = heights[rise.top()]; rise.pop();
                int w = (j + 1) - rise.top() - 1;
                maxS = max(maxS, h * w);
            }
            rise.emplace(j + 1);
        }
        while (! rise.empty()) rise.pop();
    }
    return maxS;
}

leetcode739 每日温度

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

单调递减栈

若当前温度比当前栈顶高，则必为最近一个高温，否则记录在栈中待找寻下一个高温

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ret(n, 0);
    stack<int> down;
    down.emplace(0);
    for (int i = 1; i < n; i ++) {
        while (! down.empty() && temperatures[down.top()] < temperatures[i]) {
            ret[down.top()] = i - down.top();
            down.pop();
        }
        down.emplace(i);
    }
    return ret;
}
Posted Updated algorithm

哈希表算法题目集合

leetcode380 O(1) 时间插入、删除和获取随机元素

实现 RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。 bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。 int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

题解

STL 关联式容器中： set 和 map 的底层数据结构为红黑树，因为 map 和 set 要求是自动排序的，红黑树能够实现这一功能，并且各个操作的时间复杂度都较低，而 unordered_set 和 unordered_map 的底层数据结构为哈希表，查找时间复杂度为常数级

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
class RandomizedSet {
public:
    vector<int> data;
    unordered_map<int, int> record;

    RandomizedSet() {

    }

    bool insert(int val) {
        if (record.contains(val)) {
            return false;
        }
        data.push_back(val);
        record[val] = data.size() - 1;
        return true;
    }

    bool remove(int val) {
        if (! record.contains(val)) {
            return false;
        }
        data[record[val]] = data[data.size() - 1];
        record[data[record[val]]] = record[val];
        data.pop_back();
        record.erase(val);
        return true;
    }

    int getRandom() {
        return data[rand() % data.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

leetcode128 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题解

  • unordered_set 去重
  • 遍历找到各个连续子序列的头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for (auto n : nums) num_set.insert(n);
        int max_len = 0;
        for (auto n : num_set) {
            if (!num_set.count(n - 1)) {
                int cur_num = n;
                while (num_set.count(cur_num + 1)) {
                    cur_num ++;
                }
                max_len = max(cur_num - n + 1, max_len);
            }
        }
        return max_len;
    }
};
Posted Updated algorithm

双指针算法题目集合

思路

指针从两端收缩

遍历解空间为上三角，参考解析

leetcode11 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明：你不能倾斜容器

题解

两端逼近，优先短边收缩

leetcode167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[] 和 numbers[] ，则 1 <= index1 < index2 <= numbers.length 。 以长度为 2 的整数数组 [, ] 的形式返回这两个整数的下标 和 。 你可以假设每个输入只对应唯一的答案 ，而且你不可以重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。

题解

两端逼近，< target 收缩左值，> target 收缩右值

Follow

Categories

Links

Tags

AI Agent1
CL1
CV6
CVPR20221
CVPR20233
Data Synthesis1
Data enhancement1
GAN1
Generative Model1
HPC1
Image Process2
LLM3
Multimodal1
NLP2
Prototype1
Python Lib1
Pytorch1
RAG1
Semantic Segmentation1
Transformer1
ZSL1
algorithm1
computer network1
data structure1
dataset1
deep learning1
high-performance computing1
interview2
language2
leetcode14
machine learning1
math1
prompt1
tree1
written test1
二分法1
企业1
动态规划1
区间1
区间合并1
双指针1
哈希表1
图1
堆1
多模态2
字符串1
扩散模型2
排序辅助1
操作系统1
数学推理1
文生图1
栈1
树1
正则匹配1
滑动窗口1
矩阵处理1
编译工具1
链表1
风格迁移1

Recents

p

×