LeetCode --- 139双周赛
题目列表
一、找到稳定山的下标
遍历数组，统计符合要求的答案即可，代码如下
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;
}
};原文地址：https://blog.csdn.net/V_zjs/article/details/142386801
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！