Posted Updated algorithm

区间题目集合

leetcode 打气球

右端点排序，合并区间

美团种树

随着种树数量的增加，树总量单调递增，可以通过二分法查询种树量

美团流星

左端点和右端点分开排序，计算最大经过区间数量

Posted Updated algorithm

图算法题目集合

两个顶点的最短路径

leetcode433 最小基因变化

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中） 给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

题解

BFS

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
int minMutation(string startGene, string endGene, vector<string>& bank) {

    if (bank.size() == 0) return -1;

    int total_diff = 0;
    vector<bool> visit(bank.size(), false);

    queue<string> genes;
    genes.push(startGene);

    while (genes.size()) {

        total_diff ++;
        for (int n = genes.size(); n > 0; n --) {

            string gene = genes.front();
            genes.pop();
            for (int i = 0; i < bank.size(); i ++) {

                if (visit[i]) continue;
                int count_diff = 0;
                for (int j = 0; j < gene.size(); j ++) {
                    if (gene[j] != bank[i][j]) count_diff ++;
                }
                if (count_diff == 1) {
                    if (bank[i] == endGene) return total_diff;
                    genes.push(bank[i]);
                    visit[i] = true;
                }
            }
        }
    }

    return -1;
}

leetcodeLCP35 电动车游城市

小明的电动车电量充满时可行驶距离为 cnt，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间。小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 0 ~ N-1。他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths，表示城市 A、B 间存在双向通路。初始状态，电动车电量为 0。每个城市都设有充电桩，charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end。

思路

通过 Dijkstra 方法，更新起点到各个顶点的最短花费单位时间 代码参考

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
55
56
57
58
59
60
int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) {

    int n = charge.size();

    // 记录每条相邻边，以及边的距离
    vector<vector<pair<int, int>>> edges(n);
    for (auto p : paths) {
        edges[p[0]].emplace_back(p[1], p[2]);
        edges[p[1]].emplace_back(p[0], p[2]);
    }

    // 计算以不同油量到达各个端点的最短单位时间
    vector<vector<int>> cost(n, vector<int>(cnt + 1, INT_MAX));
    cost[start][0] = 0;

    // 优先队列按照单位时间排序 (消耗时间, 节点, 油量)
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> q;
    q.emplace(0, start, 0);

    while (q.size()) {

        // 获取当前消耗时间最短的下一条路径
        auto [cost1, n1, o1] = q.top(); q.pop();

        // 若现有消耗时间比已有记录还大，跳过判断
        if (cost1 > cost[n1][o1]) continue;

        // 若已到达终点，则跳出循环
        if (n1 == end) return cost1;

        // 考虑不同的充电状态
        if (o1 < cnt) {
            int new_cost = cost1 + charge[n1];
            if (new_cost < cost[n1][o1 + 1]) {
                cost[n1][o1 + 1]  = new_cost;
                // 为节点新增不同的油量状态
                q.emplace(new_cost, n1, o1 + 1);
            }
        }

        // 遍历当前节点的相邻边
        for (auto [n2, cost2] : edges[n1]) {
            // 若油量不足往下走，则跳过
            if (o1 < cost2) continue;
            int new_cost = cost1 + cost2;
            int new_o = o1 - cost2;
            // 若从当前节点走到n2且油量为new_o，比已有起点到n2且油量
            // 为new_o的时间短，则更新
            if (new_cost < cost[n2][new_o]) {
                cost[n2][new_o] = new_cost;
                // 新增到达n2的时间，并减去消耗的油量
                q.emplace(new_cost, n2, new_o);
            }
        }

    }

    return -1;

}

leetcode909 蛇梯棋

给你一个大小为 n x n 的整数矩阵 board ，方格按从 1 到 n2 编号，编号遵循 转行交替方式 ，从左下角开始 （即，从 board[n - 1][0] 开始）每一行交替方向。

玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。

每一回合，玩家需要从当前方格 curr 开始出发，按下述要求前进：

选定目标方格 next ，目标方格的编号符合范围 [curr + 1, min(curr + 6, n2)] 。 该选择模拟了掷 六面体骰子 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。 传送玩家：如果目标方格 next 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 next 。 当玩家到达编号 n2 的方格时，游戏结束。 r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。编号为 1 和 n2 的方格上没有蛇或梯子。

注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 不能 继续移动。

举个例子，假设棋盘是 [[-1,4],[-1,3]] ，第一次移动，玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ，但 不能 顺着方格 3 上的梯子前往方格 4 。 返回达到编号为 n2 的方格所需的最少移动次数，如果不可能，则返回 -1。

思路

将棋盘的各个格子看作图顶点，顶点之间的移动步数作为边长，可将问题转换为最短路径问题。 在使用 Dijkstra 算法时可能会遇到一些细节问题：

  1. 在建立连接路径时

    • 建立 6 步跳跃关系时，可以通过编号循环累加
    • 建立梯子和蛇的关系时，可以利用编号与坐标的对应关系，通过二维数组判断当前是否可以跳跃

  2. 不能连续跳跃，且必须跳跃

    • 在判断下一个节点时，处理跳跃关系（具体在代码中体现），这样就避免了连跳的可能性

  3. 可以不使用优先队列

    • 由于每次遍历时，每条路径的增长均为 1，所以不存在更短的路径

leetcode 公交路线

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。 现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -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
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    // 若起点和重点一致则无需坐公交
    if (source == target) return 0;
    int n = routes.size();
    unordered_map<int, set<int>> stationRoute; // 记录站点对应的线路
    queue<int> iterRoutes; // 遍历各条路线
    vector<int> dis(n, 10e7); // 记录到达该线路的最短经过线路数
    for (int i = 0; i < n; i ++) {
        auto route = routes[i];
        bool find = false;
        for (auto station : route) {
            // 记录车站对应的线路
            stationRoute[station].insert(i);
            if (station == source) {
                find = true;
            }
        }
        if (find) {
            // 记录起始点所在线路并初始化经过线路数
            iterRoutes.emplace(i);
            dis[i] = 1;
        }
    }
    vector<int> visited(n, false);
    while (iterRoutes.size()) {
        // 取当前的最近线路
        int curRoute = iterRoutes.front(); iterRoutes.pop();
        // 判断是否已计算过该线路
        if (visited[curRoute]) continue;
        visited[curRoute] = true;
        // 遍历线路中的各个站点，寻找可能的下一条线路
        for (auto station : routes[curRoute]) {
            // 若重点就在本线路，则返回线路数
            if (station == target) return dis[curRoute];
            // 遍历站点对应的多条线路
            for (auto route : stationRoute[station]) {
                if (visited[route]) continue;
                // 更新经过线路的最短距离
                if (dis[curRoute] + 1 < dis[route]) {
                    dis[route] = dis[curRoute] + 1;
                    iterRoutes.emplace(route);
                }
            }
        }
    }
    return -1;
}

判断图中节点可达

leetcode399 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。 注意：输入总是有效的。你可以假设除法运算中不会出现除数为 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    vector<double> result;
    map<string, int> nodes;
    for (auto eq : equations) {
        string a = eq[0], b = eq[1];
        if (! nodes.count(a)) {
            nodes[a] = nodes.size();
        }
        if (! nodes.count(b)) {
            nodes[b] = nodes.size();
        }
    }
    int nodeNum = nodes.size();
    vector<vector<double>> connect(nodeNum, vector<double>(nodeNum, -1.0));
    // 构建自身算式连接
    for (int i = 0; i < nodeNum; i ++) {
        connect[i][i] = 1.0;
    }
    // 构建已有算式连接
    for (int i = 0, len = equations.size(); i < len; i ++) {
        auto eq = equations[i];
        double val = values[i];
        string a = eq[0], b = eq[1];
        int ia = nodes[a], ib = nodes[b];
        connect[ia][ib] = val;
        connect[ib][ia] = 1.0 / val;
    }
    // 构建可达连接
    for (int k = 0; k < nodeNum; k ++) {
        for (int i = 0; i < nodeNum; i ++) {
            for (int j = 0; j < nodeNum; j ++) {
                // 已有连接不重复赋值（在此题背景下不同路径结果相同）
                if (connect[i][j] == -1 && connect[i][k] != -1 && connect[k][j] != -1) {
                    connect[i][j] = connect[i][k] * connect[k][j];
                }
            }
        }
    }
    // 值查询
    for (auto query : queries) {
        string a = query[0], b = query[1];
        int ia = nodes.find(a) != nodes.end() ? nodes[a] : -1;
        int ib = nodes.find(b) != nodes.end() ? nodes[b] : -1;
        if (ia != -1 && ib != -1) {
            result.push_back(connect[ia][ib]);
        }
        else {
            result.push_back(-1);
        }
    }
    return result;
}

判断有向图存在环路

leetcode207 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

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
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> edges(numCourses);
    vector<int> father(numCourses, 0);
    // 通过二维向量构建有向图
    for (int i = 0, len = prerequisites.size(); i < len; i ++) {
        int a = prerequisites[i][0];
        int b = prerequisites[i][1];
        edges[a].push_back(b);
        father[b] ++;
    }
    // 初始化BFS队列
    queue<int> learn;
    for (int i = 0; i < numCourses; i ++) {
        if (! father[i]) learn.push(i);
    }
    // 计算遍历图的节点访问次数
    int count = 0;
    while (learn.size()) {
        count ++;
        int node = learn.front(); learn.pop();
        for (auto edge : edges[node]) {
            // 保证被访问节点只访问一次
            if (-- father[edge] == 0) {
                learn.push(edge);
            }
        }
    }
    // 判断节点访问次数与节点数是否相同
    return count == numCourses;
}
Posted Updated algorithm

二分法算法题目集合

leetcode300 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

题解

常规做法是通过一维数组存储当前位置作为结尾的最大子序列长度。 而根据推理可知，若在从左向右遍历时，当前元素不能与已有元素构成更长的子序列，那么替换更小的元素将有更大的可能性构成更长子序列。

1
2
3
4
5
6
7
8
9
10
11
int lengthOfLIS(vector<int>& nums) {
    auto end = nums.begin();
    for (int x : nums) {
        auto it = lower_bound(nums.begin(), end, x);
        *it = x;
        if (it == end) {
            end ++;
        }
    }
    return end - nums.begin();
}

排序序列找区间或值

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

思路

  1. 直接定位，向两个方向找到区间边缘
  2. 定位左边界，再定位右边界

leetcode74 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵： 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

思路

  • 二分定位行
  • 二分定位元素
Posted Updated algorithm

堆题目集合

最小堆

排列组合 TopK 问题

优先队列 priority_queue

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
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int,vector<int>,less<int>> p1;     //默认大根堆
    p1.push(2); p1.push(1); p1.push(3);               //输出 3 2 1
    while(p1.empty()== false){
        cout<<p1.top()<<" ";
        p1.pop();
    }

    priority_queue<int,vector<int>,greater<int>> p2;  //小根堆
    p2.push(2); p2.push(1); p2.push(3);               //输出 1 2 3
    while(p2.empty()== false){
        cout<<p2.top()<<" ";
        p2.pop();
    }

    // 基本数据类型-pair-pair类型默认先比较第一个元素，第一个相等比较第二个
    priority_queue<pair<int, int> > a;
    a.push(pair<int,int>{1,2});
    a.push(pair<int,int>{1,3});
    a.push(pair<int,int>{2,5});
    while (a.empty()== false){
        cout<<a.top().first<<" "<< a.top().second<<endl;
        a.pop();
    }
    //输出:
    //2 5
    //1 3
    //1 2

    return 0;
}

多路归并

每次迭代有 N 个选择，将 N 个选择放入堆得到排序后的值

  • 题型
    • 一维
      • 根据题意队列初始化 1 个值
    • 二维
      • 根据题意队列按序初始化 1 个列表
      • 初始化左上角值，set 判断是否重复插入
  • 注意去重的问题

leetcode264 丑数 II（一维）

给你一个整数 n ，请你找出并返回第 n 个 丑数 。 丑数 就是质因子只包含 2、3 和 5 的正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int nthUglyNumber(int n) {
    long times_num[] = {2, 3, 5};
    set<long> record;
    priority_queue<long, vector<long>, greater<long>> q;
    q.push(1);
    int index = 1;
    while (index <= n) {
        int cur_num = q.top();
        if (index == n) return cur_num;
        q.pop();
        for (long t : times_num) {
            long new_num = cur_num * t;
            if (record.contains(new_num)) continue;
            q.push(new_num);
            record.insert(new_num);
        }
        index ++;
    }
    return 0;
}

leetcode373 查找和最小的 K 对数字（二维）

给定两个以 非递减顺序排列 的整数数组 和 , 以及一个整数 。 定义一对值 ，其中第一个元素来自 ，第二个元素来自 。 请找到和最小的 k 个数对 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {

    vector<vector<int>> result;
    int l1 = nums1.size(), l2 = nums2.size();

    auto cmp = [&](const auto& a, const auto& b) {
        return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
    for (int i = 0; i < l1; i ++) {
        q.push({i, 0});
    }

    while (result.size() < k) {
        auto [ia, ib] = q.top();
        result.push_back({nums1[ia], nums2[ib]});
        q.pop();
        if (ib + 1 < l2) q.push(pair<int, int>{ia, ib + 1});
    }

    return result;
}
Posted Updated algorithm

字符串题目集合

字符串输入流

  • 库 sstream
  • 类 stringstream

leetcode58 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

1
2
3
4
5
6
int lengthOfLastWord(string s) {
    stringstream ss(s);
    string word;
    while (ss >> word) ;
    return word.size();
}

KMP 算法

在匹配之前需要计算匹配字符串各个位置的最长重合前后缀。初始化第一个位置为 0，后缀末尾位置从 1 开始，若当前前缀的末尾与后缀末尾相同，则更新长度；否则根据当前前缀寻找新的重合前缀，这个阶段是最难理解的部分，如下图所示。

kmp

leetcode28 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int strStr(string haystack, string needle) {
    // next数组表示到该位置的字串的最大相同前后缀的长度
    vector<int> next(needle.size());
    int j = 0;
    next[0] = 0;
    for (int i = 1, len = needle.size(); i < len; i ++) {
        // 末尾不相同则查找以当前前缀的最大重复长度
        while (j && needle[i] != needle[j]) j = next[j - 1];
        // 末尾相同则记录长度
        if (needle[i] == needle[j]) j ++;
        next[i] = j;
    }
    // 通过回溯重合位置减少遍历次数
    for (int i = 0, j = 0, len = haystack.size(); i < len; i ++) {
        // 若当前位置不匹配则变换比对位置
        while (j && haystack[i] != needle[j]) j = next[j - 1];
        // 若比对成功则向后比对
        if (haystack[i] == needle[j]) j ++;
        // 判断是否已完成比对
        if (j == needle.size()) return i - needle.size() + 1;
    }
    return -1;
}

leetcode767 重构字符串

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

题解

参考题解

leetcode228 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出： "a->b" ，如果 a != b "a" ，如果 a == b

思路

参考leetcode 题解

  • to_string 方法快速将数字转换为字符串
  • 使用 i 和 j 表示区间的端点
  • 在遍历的过程中，若位置 j 与位置 j+1 的值相差 1，则向右拓展区间，从而找到完整区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        // Lambda 函数构建字符串
        auto f = [&](int i, int j) {
            return i == j ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[j]);
        };
        // i 在迭代时为上一个区间结尾 + 1
        for (int i = 0, j, n = nums.size(); i < n; i = j + 1) {
            j = i;
            // 若差为 1，右端点移动
            while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
                ++ j;
            }
            // 添加区间
            ans.emplace_back(f(i, j));
        }
        return ans;
    }
};

leetcode820 单词的压缩编码

单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足： words.length == indices.length 助记字符串 s 以 '#' 字符结尾 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等 给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

Trie快速判断末尾重合字串

若字符串s1完全与字符串s2的末尾部分或整体重合，则字符串s1可作为同一部分助记字符串 因此，可以使用Trie构建字符串树 为了正确计算包含关系，需要优先按照字符串长度倒序排序字符串

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
class Solution {
private:
    // 使用长度为26的数组存储下一个字符
    struct Node {
        vector<Node*> next;
    };
public:
    int minimumLengthEncoding(vector<string>& words) {
        int n = words.size();
        // 初始化根节点
        Node* root = new Node();
        root->next.resize(26, nullptr);
        Node* p = nullptr;
        // 按字符串长度排序
        sort(words.begin(), words.end(), [&](const string& a, const string& b) {
            return a.size() > b.size();
        });
        int count = 0;
        // 遍历各个字符串
        for (int i = 0; i < n; i ++) {
            bool include = true;
            string& w = words[i];
            p = root;
            // 从字符串尾部开始遍历
            for (int j = w.size() - 1; j >= 0; j --) {
                int charIndex = w[j] - 'a';
                // 若为非空指针则表示已有该字符序列
                if (p->next[charIndex]) {
                    p = p->next[charIndex];
                }
                // 创建新的字符
                else {
                    include = false; // 标识为新字符串
                    Node* newNode = new Node();
                    newNode->next.resize(26, nullptr);
                    p->next[charIndex] = newNode;
                    p = newNode;
                }
            }
            // 若为新字符串则加上当前字符串长度以及"#"的长度
            if (! include) count += w.size() + 1;
        }
        return count;
    }
};
Posted Updated algorithm

链表题目集合

leetcode86 分隔链表

思路

  • 遍历链表，分两个链表存储

leetcode23 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。

多路归并选择节点

Posted Updated algorithm

滑动窗口题目集合

leetcode209 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的子数组[, , ..., , ] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

题解

确定左值，向右扩展直到满足 target，记录当前窗口大小，移动左值，重复上述动作，直到右值不能再拓展

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 minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int left = 0;
        int right = 0;
        int sum = nums[0];
        int minLen = size + 1;
        while (left < size && right < size) {
            if (sum >= target) {
                minLen = min(minLen, right - left + 1);
                sum -= nums[left];
                left ++;
                continue;
            }
            if (right == size - 1) break;
            right ++;
            sum += nums[right];
        }
        if (minLen == size + 1) return 0;
        return minLen;
    }

};
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

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

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

分类讨论动态规划

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

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

×