LeetCode --- 139双周赛

题目列表

3285. 找到稳定山的下标

3286. 穿越网格图的安全路径

3287. 求出数组中最大序列值

3288. 最长上升路径的长度

一、找到稳定山的下标

遍历数组，统计符合要求的答案即可，代码如下

class Solution {
public:vector<int> stableMountains(vector<int>& height, int threshold) {vector<int> ans;int n = height.size();for(int i = 1; i < n; i++){if(height[i-1] > threshold){ans.push_back(i);}}return ans;}
};

 二、穿越网格图的安全路径

题目意思就是要求找到一条路径，要求路径上的1的个数最少，可以将给定的表格看成一张图，每个格子的值，就是相邻点到达该点的边权，要求最短路径，很显然，可以用Dijkstra算法来求解，代码如下

class Solution {const int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
public:bool findSafeWalk(vector<vector<int>>& grid, int health) {int n = grid.size(), m = grid[0].size();vector<vector<int>>dist(n, vector<int>(m, INT_MAX));priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>, greater<>> pq; // [d,x,y]pq.emplace(grid[0][0], 0, 0);dist[0][0] = grid[0][0];while(pq.size()){auto [d, x, y] = pq.top(); pq.pop();if(d != dist[x][y]) continue;for(auto [i, j]: dir){int dx = x + i, dy = y + j;if(dx < 0 || dx >= n || dy < 0 || dy >= m)continue;if(dist[dx][dy] > dist[x][y] + grid[dx][dy]){dist[dx][dy] = dist[x][y] + grid[dx][dy];pq.emplace(dist[dx][dy], dx, dy);}}}return dist.back().back() < health;}
};

但其实我们可以不用priority_queue，我们直接用deque就行，它只有0/1两个边权，我们只要将0边权的点进行头插，1边权的点进行尾插，这样我们每次拿到的结点就是路径长度最少的，代码如下

class Solution {const int dir[4][2] = {1,0,-1,0,0,1,0,-1};
public:bool findSafeWalk(vector<vector<int>>& grid, int health) {int n = grid.size(), m = grid[0].size();deque<pair<int,int>> dq; dq.emplace_back(0, 0);vector<vector<int>> dist(n, vector<int>(m, INT_MAX));dist[0][0] = grid[0][0];while(dq.size()){auto [x, y] = dq.front(); dq.pop_front();for(int i = 0; i < 4; i++){int dx = x + dir[i][0];int dy = y + dir[i][1];if(dx < 0 || dx >= n || dy < 0 || dy >= m) continue;int cost = grid[dx][dy];if(dist[dx][dy] > dist[x][y] + cost){dist[dx][dy] = dist[x][y] + cost;cost == 0 ? dq.emplace_front(dx, dy) : dq.emplace_back(dx, dy);}}}return dist[n-1][m-1] < health;}
};

三、求出数组中最大序列值

这题根据数据范围，可以将seq分成前后两个部分，分别计算出能得到的所有的or值，然后暴力枚举所有可能的xor值，返回最大值即可。

如何计算前缀/后缀中选择的k个数能组成哪些数？

以前缀为例子：我们设f[i][j][x] 表示 能否从前 i 个数中选出 j 个数组成 x

从选或不选两个角度来思考，状态转移方程为 f[i][j][x] = f[i-1][j][x] | f[i-1][j-1][?]，其中 ？表示所有与nums[i]进行或运算得到 x 的数，这显然是很难进行枚举的，但是我们却能很容易知道 x|nums[i] 的结果是什么，所以这里的状态转移方程改为 f[i][j][x] = f[i-1][j][x]，f[i][j][x|v] = f[i-1][j-1][x]，由于x|v的结果可能会重复，所以需要防止出现一开始结果为true，最后却被覆盖成false的情况，后缀的计算也是同理，代码如下

class Solution {const int MX = 1 << 7;
public:int maxValue(vector<int>& nums, int k) {// 前后缀分解：枚举前缀的or值，枚举后缀的or值，暴力枚举，得到最大xor// 如何求前缀or值？// f[i][j][x] 表示前i个数中选出j个数or，结果为x是否存在// 状态转移方程的表示：// 1、填表法// f[i][j][x] = f[i-1][j][x] | f[i-1][j-1][{...}]// 其中{...}表示 | nums[i] 能得到 x 的所有数字的集合// 2、刷表法// f[i][j][x] = f[i-1][j][x]// f[i][j][x|v] = f[i-1][j-1][x]，其中 v = nums[i]int n = nums.size();bool pre[n + 1][k + 1][1<<7];memset(pre, 0, sizeof(pre));for(int i = 0; i <= n; i++) pre[i][0][0] = true;for(int i = 0; i < n; i++){int v = nums[i];for(int j = 1; j <= k; j++){for(int x = 0; x < MX; x++){pre[i+1][j][x] |= pre[i][j][x];pre[i+1][j][x|v] |= pre[i][j-1][x];}}}bool suf[n+1][k+1][1<<7];memset(suf, 0, sizeof(suf));for(int i = 0; i <= n; i++) suf[i][0][0] = true;for(int i = n - 1; i >= 0; i--){int v = nums[i];for(int j = 1; j <= k; j++){for(int x = 0; x < MX; x++){suf[i][j][x] |= suf[i+1][j][x];suf[i][j][x|v] |= suf[i+1][j-1][x];}}}int ans = 0;for(int i = k - 1; i < n - k; i++){ // [0, k), [k+1, n)for(int x = 0; x < MX; x++){if(pre[i + 1][k][x]){for(int y = 0; y < MX; y++){if(suf[i + 1][k][y]){ans = max(ans, x ^ y);}}}}}return ans;}
};

四、最长上升路径的长度

题意简单来说就是找二维的最长上升子序列，其中需要包含一个指定的点。这个和找最长上升子序列的思路是一样的，都是贪心+二分的思路，但是由于条件有所不同，实现也会有差异，具体请看代码，如下

class Solution {
public:int maxPathLength(vector<vector<int>>& coordinates, int k) {int kx = coordinates[k][0], ky = coordinates[k][1];// 根据横坐标进行排序，如果横坐标相同，则纵坐标大的排在前面// 这样在找最长递增子序列的时候，横坐标相同的点最多只能被选中一个ranges::sort(coordinates, [&](const auto& x, const auto& y){return x[0]!=y[0] ? x[0] < y[0] : x[1] > y[1];});vector<int> v;for(auto& coordinate: coordinates){int x = coordinate[0], y = coordinate[1];if(x < kx && y < ky || x > kx && y > ky){auto it = lower_bound(v.begin(), v.end(), y);if(it == v.end()) v.push_back(y);else *it = y;}}return v.size() + 1;}
};