当前位置：首页 > article >正文

LeetCode --- 139双周赛

article 2024/9/23 20:21:02

题目列表

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

查看全文

http://www.kler.cn/news/316529.html