leetcode spring LCCUP

季度赛果真打酱油，水了三道题，前三道题目确实难度太低了。

LCP 72. 补给马车

远征队即将开启未知的冒险之旅，不过在此之前，将对补给车队进行最后的检查。supplies[i] 表示编号为 i 的补给马车装载的物资数量。考虑到车队过长容易被野兽偷袭，他们决定将车队的长度变为原来的一半（向下取整），计划为：

找出车队中物资之和最小两辆相邻马车，将它们车辆的物资整合为一辆。若存在多组物资之和相同的马车，则取编号最小的两辆马车进行整合；
重复上述操作直到车队长度符合要求。
请返回车队长度符合要求后，物资的分布情况。

示例 1：

输入：supplies = [7,3,6,1,8]

输出：[10,15]

解释： 第 1 次合并，符合条件的两辆马车为 6,1，合并后的车队为 [7,3,7,8]； 第 2 次合并，符合条件的两辆马车为 (7,3) 和 (3,7)，取编号最小的 (7,3)，合并后的车队为 [10,7,8]； 第 3 次合并，符合条件的两辆马车为 7,8，合并后的车队为 [10,15]； 返回 [10,15]

示例 2：

输入：supplies = [1,3,1,5]

输出：[5,5]

解释：

2 <= supplies.length <= 1000
1 <= supplies[i] <= 1000

地址

https://leetcode.cn/problems/hqCnmP/description/

题意

直接模拟

思路

题目比较简单了，假设数组长度为 $n$，每次整合将减小一辆马车，一共需要整合 $\frac{n}{2}$ 次，直接模拟即可，每次找到最大相邻元素，然后进行合并即可
复杂度分析：

时间复杂度：$O(n^2)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    vector<int> supplyWagon(vector<int>& supplies) {
        int n = supplies.size();
        for (int i = 0; i < (n + 1) / 2; i++) {
            int minSum = INT_MAX;
            int start = 0;
            for (int j = 0; j < supplies.size() - 1; j++) {
                if (supplies[j] + supplies[j + 1] < minSum) {
                    minSum = supplies[j] + supplies[j + 1];
                    start = j;
                }
            }
            supplies[start] = supplies[start] + supplies[start + 1];
            for (int j = start + 1; j < supplies.size() - 1; j++) {
                supplies[j] = supplies[j + 1]; 
            }
            supplies.pop_back();
        }
        return supplies;
    }
};

LCP 73. 探险营地

探险家小扣的行动轨迹，都将保存在记录仪中。expeditions[i] 表示小扣第 i 次探险记录，用一个字符串数组表示。其中的每个「营地」由大小写字母组成，通过子串->连接。

例："Leet->code->Campsite"，表示到访了 "Leet"、"code"、"Campsite" 三个营地。

expeditions[0] 包含了初始小扣已知的所有营地；对于之后的第 i 次探险(即 expeditions[i] 且 i > 0)，如果记录中包含了之前均没出现的营地，则表示小扣新发现的营地。

请你找出小扣发现新营地最多且索引最小的那次探险，并返回对应的记录索引。如果所有探险记录都没有发现新的营地，返回 -1

注意：
大小写不同的营地视为不同的营地；
营地的名称长度均大于 0。
示例 1：

输入：expeditions = ["leet->code","leet->code->Campsite->Leet","leet->code->leet->courier"]

输出：1

解释： 初始已知的所有营地为 "leet" 和 "code" 第 1 次，到访了 "leet"、"code"、"Campsite"、"Leet"，新发现营地 2 处："Campsite"、"Leet" 第 2 次，到访了 "leet"、"code"、"courier"，新发现营地 1 处："courier" 第 1 次探险发现的新营地数量最多，因此返回 1

示例 2：

输入：expeditions = ["Alice->Dex","","Dex"]

输出：-1

解释： 初始已知的所有营地为 "Alice" 和 "Dex" 第 1 次，未到访任何营地； 第 2 次，到访了 "Dex"，未新发现营地； 因为两次探险均未发现新的营地，返回 -1

示例 3：

输入：expeditions = ["","Gryffindor->Slytherin->Gryffindor","Hogwarts->Hufflepuff->Ravenclaw"]

输出：2
解释： 初始未发现任何营地； 第 1 次，到访 "Gryffindor"、"Slytherin" 营地，其中重复到访 "Gryffindor" 两次， 因此新发现营地为 2 处："Gryffindor"、"Slytherin" 第 2 次，到访 "Hogwarts"、"Hufflepuff"、"Ravenclaw" 营地； 新发现营地 3 处："Hogwarts"、"Hufflepuff"、"Ravenclaw"； 第 2 次探险发现的新营地数量最多，因此返回 2

提示：

1 <= expeditions.length <= 1000
0 <= expeditions[i].length <= 1000
探险记录中只包含大小写字母和子串"->"

地址

https://leetcode.cn/problems/0Zeoeg/description/

题意

简单题目了

思路

简单的哈希统计即可，每次插入新的字符串数组时，首先检测当前插入的组中有多少之前未出现的元素，然后再将当前组全部插入一遍即可。
复杂度分析：

时间复杂度：$O(nm)$，其中 $n$ 为给定数组的长度，$m$ 表示每个字符串数组的长度。
空间复杂度：$O(nm)$。

代码

class Solution {
public:
    vector<string> split(string &s) {
        vector<string> res;
        unordered_set<string> cnt;
        int i = 0;
        while (i < s.size()) {
            string t;
            while (i < s.size() && s[i] != '-') {
                t.push_back(s[i]);
                i++;
            }
            if (!cnt.count(t)) {
                res.emplace_back(t);
                cnt.emplace(t);
            }
            if (i < s.size() && s[i] == '-') {
                i += 2;
            }
        }
        return res;
    }
    
    int adventureCamp(vector<string>& expeditions) {
        vector<string> arr = split(expeditions[0]);
        unordered_set<string> cnt;
        for (auto v : arr) {
            cnt.emplace(v);
        }
        int res = -1;
        int maxVal = 0;
        for (int i = 1; i < expeditions.size(); i++) {
            vector<string> camp = split(expeditions[i]);
            int diff = 0;
            for (auto v : camp) {
                if (!cnt.count(v)) {
                    diff++;
                }
            }
            if (diff > maxVal) {
                maxVal = diff;
                res = i;
            }
            for (auto v : camp) {
                cnt.emplace(v);
            }
        }
        return res;
    }
};

LCP 74. 最强祝福力场

小扣在探索丛林的过程中，无意间发现了传说中“落寞的黄金之都”。而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场。经过不断的勘测记录，小扣将所有力场的分布都记录了下来。forceField[i] = [x,y,side] 表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。

若任意一点的力场强度等于覆盖该点的力场数量，请求出在这片地带中力场强度最强处的力场强度。

注意：

力场范围的边缘同样被力场覆盖。
示例 1：

输入： forceField = [[0,0,1],[1,0,1]]

输出：2

解释：如图所示，（0.5, 0) 处力场强度最强为 2， （0.5，-0.5）处力场强度同样是 2。image.png

示例 2：

输入： forceField = [[4,4,6],[7,5,3],[1,6,2],[5,6,3]]

输出：3

解释：如下图所示， forceField[0]、forceField[1]、forceField[3] 重叠的区域力场强度最大，返回 3image.png

提示：

1 <= forceField.length <= 100
forceField[i].length == 3
0 <= forceField[i][0], forceField[i][1] <= 10^9
1 <= forceField[i][2] <= 10^9

地址

https://leetcode.cn/problems/xepqZ5/

题意

差分数组

思路

本题与「850. 矩形面积 II」非常相似的题目，如果知道该题的解法，则本题目非常类似。
首先需要将矩形按照横坐标 $x$ 的最小区域进行切分，然后求每个切分部分的最大重叠即可，所谓的最小区域即不可能再被某个矩形的边再次切分。
每次在横坐标的区域中，依次对 $y$ 坐标进行差分统计，统计当前区域中的最大重叠值即可。
复杂度分析：

时间复杂度：$O(n^2 \log n)$，其中 $n$ 为矩形的数量。
空间复杂度：$O(n)$。

代码

class Solution {
public:
    int fieldOfGreatestBlessing(vector<vector<int>>& forceField) {
        int n = forceField.size();
        vector<long long> arrX;
        for (int i = 0; i < forceField.size(); i++) {
            arrX.emplace_back((long long)forceField[i][0] * 2 - forceField[i][2]);
            arrX.emplace_back((long long)forceField[i][0] * 2 + forceField[i][2]);
        }
        sort(arrX.begin(), arrX.end());
        int res = 0;
        for (int i = 1; i < arrX.size(); i++) {
            long long left = arrX[i - 1];
            long long right = arrX[i];
            map<long long, int> cnt;
            for (int j = 0; j < n; j++) {
                long long start = (long long)forceField[j][0] * 2 - forceField[j][2];
                long long end = (long long)forceField[j][0] * 2 + forceField[j][2];
                if (start <= left && right <= end) {
                    start = (long long)forceField[j][1] * 2 - forceField[j][2];
                    end = (long long)forceField[j][1] * 2 + forceField[j][2];
                    cnt[start]++;
                    cnt[end + 1]--;
                }
                
            }
            int curr = 0;
            for (auto [_, x] : cnt) {
                curr += x;
                res = max(res, curr);
            }
        }
        return res;
    }
};

LCP 75. 传送卷轴

相关企业
随着不断的深入，小扣来到了守护者之森寻找的魔法水晶。首先，他必须先通过守护者的考验。

考验的区域是一个正方形的迷宫，maze[i][j] 表示在迷宫 i 行 j 列的地形：

若为 .，表示可以到达的空地；
若为 # ，表示不可到达的墙壁；
若为 S ，表示小扣的初始位置；
若为 T，表示魔法水晶的位置。

小扣每次可以向上、下、左、右相邻的位置移动一格。而守护者拥有一份「传送魔法卷轴」，使用规则如下：

魔法需要在小扣位于空地时才能释放，发动后卷轴消失；；
发动后，小扣会被传送到水平或者竖直的镜像位置，且目标位置不得为墙壁(如下图所示)；
在使用卷轴后，小扣将被「附加负面效果」，因此小扣需要尽可能缩短传送后到达魔法水晶的距离。而守护者的目标是阻止小扣到达魔法水晶的位置；如果无法阻止，则尽可能增加小扣传送后到达魔法水晶的距离。假设小扣和守护者都按最优策略行事，返回小扣需要在「附加负面效果」的情况下最少移动多少次才能到达魔法水晶。如果无法到达，返回 -1。

注意：

守护者可以不使用卷轴；
传送后的镜像位置可能与原位置相同。

示例 1：

输入：maze = [".....","##S..","...#.","T.#..","###.."]

输出：7

解释：如下图所示： 守护者释放魔法的两个最佳的位置为 [2,0] 或 [3,1]： 若小扣经过 [2,0]，守护者在该位置释放魔法， 小扣被传送至 [2,4] 处且加上负面效果，此时小扣还需要移动 7 次才能到达魔法水晶； 若小扣经过 [3,1]，守护者在该位置释放魔法， 小扣被传送至 [3,3] 处且加上负面效果，此时小扣还需要移动 9 次才能到达魔法水晶； 因此小扣负面效果下最少需要移动 7 次才能到达魔法水晶。image.png

示例 2：

输入：maze = [".#..","..##",".#S.",".#.T"]

输出：-1

解释：如下图所示。 若小扣向下移动至 [3,2]，守护者使其传送至 [0,2]，小扣将无法到达魔法水晶； 若小扣向右移动至 [2,3]，守护者使其传送至 [2,0]，小扣将无法到达魔法水晶；image.png

示例 3：

输入：maze = ["S###.","..###","#..##","##..#","###.T"]

输出：5

解释：如下图所示： 守护者需要小扣在空地才能释放，因此初始无法将其从 [0,0] 传送至 [0,4]; 当小扣移动至 [2,1] 时，释放卷轴将其传送至水平方向的镜像位置 [2,1]（为原位置） 而后小扣需要移动 5 次到达魔法水晶image.png

提示：

4 <= maze.length == maze[i].length <= 200
maze[i][j] 仅包含 "."、"#"、"S"、"T"

地址

https://leetcode.cn/problems/rdmXM7/

题意

二分查找

思路

题目的难点有以下几点：

如果找到从某个坐标开始最少移动到达魔法水晶的步数，这个问题比较容易解决，我们从魔法水晶开始广度优先搜索即可得到每个位置到达水晶的最小步数；
假设小扣和守护者都按最优策略行事，如何理解最优策略；

如果理解最优策略：

假设在某个点 $(x,y)$，如果将其进行传递，应当选择什么方式传递？
- 如果按照水平位置镜像后则到达点 $(x, n - 1- y)$，此时其到达水晶的距离为 $dist_x$；
- 如果按照竖直位置镜像后则到达点 $(m - 1- x, y)$，此时其到达水晶的距离为 $dist_y$；
- 假设 $dist_x > dist_y$, 则最优策略时按照水平位置传送；否则应按照垂直方向传送；因此此时传递后的移动步数按照最优策略为 $dist(x,y) = \max(dist_x,dist_y)$;
假设选择一个位置进行传送，最优选择应该哪个位置传送？
- 假设小扣选择了某条最优的路径为 $(a_0 \rightarrow a_1 \rightarrow a_2 \rightarrow a_3 \rightarrow \cdots)$，此时在该路径经过的点 $(a_0,a_1,a_2,a_3, \cdots)$ 集合中，对于守护者来说一定是优先选择该路径上传送后移动距离最大的位置，即此时一定优先选择 $\max(dist(a_i))$ 的某个位置 $a_i$，只有这样才尽可能「增加」小扣传送后到达魔法水晶的距离；
- 对于小扣来说，由于守护者是按照最优策略来防守的，此时他的策略是尽可能「减少」小扣传送后到达魔法水晶的距离，因此他在所有可能的路径中选择一条路径，且该路径被守护者按照最优策略施法传送后到达魔法水晶的距离的最小，等价于该路径上所有点被施法后传送到达水晶的最大距离尽可能的小；

根据以上提示我们直接采用二分查找即可，假设当前位置通过传送到达水晶的最大距离大于 $\textit{mid}$，则该点一定不在选择范围内。我们直接采用 $\textit{BFS}$ 遍历整个图即可，我们应该尽量选择传送后距离小于等于 $\textit{mid}$ 点。
当然题目中存在疑惑的点为，假设从起点无法到达终点，此时直接返回 $-1$，还有另外一种情况，假设当前未进行传送时小扣的移动距离更远一些，通过一次传送后，小口可能距离水晶的距离更近了，所以因此这样的传送实际为无效传送，按道理不应该传送；
复杂度分析：

时间复杂度：$O(mn\log(mn))$，其中 $m,n$ 为矩阵的行数与列数；
空间复杂度：$O(mn)$，其中 $m,n$ 为矩阵的行数与列数；

代码

constexpr int INF = 1e9 + 7;

class Solution {
public:
    int challengeOfTheKeeper(vector<string>& maze) {
        int m = maze.size();
        int n = maze[0].size();
        
        int sx = 0, sy = 0;
        int tx = 0, ty = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j] == 'S') {
                    sx = i;
                    sy = j;
                }
                if (maze[i][j] == 'T') {
                    tx = i;
                    ty = j;
                }
            }
        }

        vector<vector<int>> dist(m, vector<int>(n, INF));
        int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        queue<pair<int, int>> qu;
        dist[tx][ty] = 0;
        qu.emplace(tx, ty);
        while (!qu.empty()) {
            auto [x, y] = qu.front();
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] != '#' && dist[nx][ny] == INF) {
                    dist[nx][ny] = dist[x][y] + 1;
                    qu.emplace(nx, ny);
                }
            }
        }
        if (dist[sx][sy] == INF) {
            return -1;
        }

        vector<vector<int>> transfer(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (maze[i][j] == '.') {
                    if (maze[i][n - 1 - j] != '#') transfer[i][j] = max(transfer[i][j], dist[i][n - 1 - j]);
                    if (maze[m - 1 - i][j] != '#') transfer[i][j] = max(transfer[i][j], dist[m - 1 - i][j]);
                }
            }
        }

        int res = INF;
        int L = 0;
        int R = INF;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            queue<pair<int, int>> qu;
            vector<vector<bool>> visit(m, vector<bool>(n, false));
            qu.emplace(sx, sy);
            visit[sx][sy] = true;
            while (!qu.empty()) {
                auto [x, y] = qu.front();
                qu.pop();
                if (x == tx && y == ty) {
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nx = x + dir[i][0];
                    int ny = y + dir[i][1];
                    if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] != '#' && transfer[nx][ny] <= mid && !visit[nx][ny]) {
                        visit[nx][ny] = true;
                        qu.emplace(nx, ny);
                    }
                }
            }
            if (visit[tx][ty]) {
                res = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return res == INF ? -1 : res;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣季度赛

← leetcode contest 342 leetcode biweekly contes 103 →

扫描二维码，分享此文章