讨论/题目交流/🏆 第 167 场力扣周赛/
🏆 第 167 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 二进制链表转整数
5 分 - 顺次数
5 分 - 元素和小于等于阈值的正方形的最大边长
6 分 - 网格中的最短路径

展开讨论

第一题:

文字略

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ret = 0;
        while (head != NULL) {
            ret = ret * 2 + head->val;
            head = head->next;
        }
        return ret;
    }
};

第二题:

这种题本来第一反应就是数位dp的,然而符合条件的数,总共才36个,想办法枚举出来就行了

条件:每一位上的数字都比前一位上的数字大 1 的整数

我们只需要分别枚举第一位是1,2,3...9,后面依此对前面的数字加一,直到有一位数字为9为止,中间产生的所有“顺次数”都记录下来

class Solution {
public:
    vector<int> all;
    void init() {
        if (all.size() != 0) {
            return;
        }
        for (int i = 1;i < 10;i++) {
            int x = 0;
            for (int j = i;j < 10;j++) {
                x = x * 10 + j;
                all.push_back(x);
            }
        }
        sort(all.begin(), all.end());
    }
    vector<int> sequentialDigits(int low, int high) {
        init();
        vector<int> ret;
        for (int i = 0;i < all.size();i++) {
            if (all[i] >= low && all[i] <= high) {
                ret.push_back(all[i]);
            }
        }
        return ret;
    }
};

第三题:

这种题第165场周赛也有,统计全为 1 的正方形子矩阵

原理:枚举所有的正方形(x,y,k),其中(x,y)为正方形左上角的坐标,k为正方形边长,判断每个正方形是否满足元素总和小于或等于阈值

做法:从大到小枚举边长k(这样如果某个边长为k的正方形满足条件,那么可以直接返回),利用滑动数组(或者前缀和),把grid[i]到grid[i+k-1]累加压缩成一维,再利用滑动数组(或者前缀和),寻找符合元素总和小于或等于阈值的长度为k的连续子数组

时间复杂度o(n3)o(n^3)

当然二分k也行。。时间复杂度降到o(n2logn)o(n^2 logn)

class Solution {
public:
    bool find(vector<int>& data, int k, int threshold) {
        int ret = 0;
        for (int i = 0;i < k - 1;i++) {
            ret += data[i];
        }
        for (int i = k - 1;i < data.size();i++) {
            ret += data[i];
            if (ret <= threshold) {
                return true;
            }
            ret -= data[i - k + 1];
        }
        return false;
    }
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        int n = mat.size();
        int m = mat[0].size();
        int k = min(n, m);
        
        while (k > 0) {
            vector<int> data(m, 0);
            for (int i = 0;i < k - 1;i++) {
                for (int j = 0;j < m;j++) {
                    data[j] += mat[i][j];
                }
            }
            for (int i = k - 1;i < n;i++) {
                for (int j = 0;j < m;j++) {
                    data[j] += mat[i][j];
                }
                if (find(data, k, threshold)) {
                    return k;
                }
                for (int j = 0;j < m;j++) {
                    data[j] -= mat[i - k + 1][j];
                }
            }
            k--;
        }
        return k;
    }
};

第四题:

bfs题,跟一般迷宫题不一样,这个题需要增加一维k,状态点:dist[{x, y, k}],表示从(0,0)到(x,y),还剩k次消除机会的最短路径,原点就变成了(0,0,k),我们bfs的目标是min(dist({n,m-1,k})),状态转移时,根据grid[x][y]是否为障碍,判断转移状态的第二维(k)是否需要减1,注意如果k小于0,状态点无效

时间复杂度理论上为o(n2k)o(n^2*k)

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<vector<bool>>> flag(n, vector<vector<bool>>(m, vector<bool>(k + 1, false)));
        queue<vector<int>> Q;
        
        int vx[] = {0,0,1,-1};
        int vy[] = {1,-1,0,0};
        
        //第一维:横坐标
        //第二维:纵坐标
        //第三维:剩下的消除次数
        //第四维:该状态下的最短路径
        Q.push({0, 0, k, 0});
        flag[0][0][k] = true;
        while (!Q.empty()) {
            auto last = Q.front();
            Q.pop();
            
            if (last[0] == n - 1 && last[1] == m - 1) {
                return last[3];
            }
            
            for (int i = 0;i < 4;i++) {
                vector<int> next = {last[0] + vx[i], last[1] + vy[i], last[2], last[3] + 1};
                if (next[0] < 0 || next[0] >= n || next[1] < 0 || next[1] >= m) {
                    continue;
                }
                if (grid[next[0]][next[1]] == 1) {
                    next[2]--;
                }
                if (next[2] < 0 || flag[next[0]][next[1]][next[2]]) {
                    continue;
                }
                flag[next[0]][next[1]][next[2]] = true;
                Q.push(next);
            }
        }
        return -1;
    }
};
17
展开全部 10 讨论