自学内容网 自学内容网

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

原文地址:https://blog.csdn.net/V_zjs/article/details/142386801

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!