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

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

image.png

3 分 - 二维网格迁移
4 分 - 在受污染的二叉树中查找元素
5 分 - 可被三整除的最大和
8 分 - 推箱子

展开讨论

这把扑街了。。。果然睡不够会影响思维速度。。。

第一题:

很简单,就把整个矩阵拉成一个数组,然后从n*m-k位置开始填充即可

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        vector<int> a;
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                a.push_back(grid[i][j]);
            }
        }
        
        vector<vector<int>> ret(n, vector<int>(m, 0));
        int p = (int)a.size() - k;
        p = (p % (n * m) + (n * m)) % (n * m);
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                ret[i][j] = a[p++];
                p %= (n * m);
            }
        }
        return ret;
    }
};

第二题:

没啥难度,dfs填充,全局用一个map保存填充的值,后续的find方法直接用map返回即可

class FindElements {
public:
    set<int> s;
    void dfs(TreeNode* root, int val) {
        if (!root) {
            return;
        }
        root->val = val;
        s.insert(val);
        dfs(root->left, val * 2 + 1);
        dfs(root->right, val * 2 + 2);
    }
    FindElements(TreeNode* root) {
        s.clear();
        dfs(root, 0);
    }
    
    bool find(int target) {
        return s.find(target) != s.end();
    }
};

第三题:

简单的数学题,全部数累加,如果余数是1,那么找最小的一个余数1的数,和两个余数2的数,看看哪个小减去哪个,余数为2也是一样。然而我是用递推过的。。。

数学版本:

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> p1, p2;
        sort(nums.begin(), nums.end());
        int ret = 0;
        for (int i = 0;i < nums.size();i++) {
            ret += nums[i];
            if (nums[i] % 3 == 1 && p1.size() < 2) {
                p1.push_back(nums[i]);
            }
            if (nums[i] % 3 == 2 && p2.size() < 2) {
                p2.push_back(nums[i]);
            }
        }
        cout << ret % 3 << endl;
        if (ret % 3 == 0) {
            return ret;
        } else if (ret % 3 == 1) {
            int num = 1000000000;
            if (p1.size() >= 1) {
                num = min(num, p1[0]);
            } 
            if (p2.size() >= 2) {
                num = min(num, p2[0] + p2[1]);
            }
            return ret - num;
        } else {
            int num = 1000000000;
            if (p1.size() >= 2) {
                num = min(num, p1[0] + p1[1]);
            } 
            if (p2.size() >= 1) {
                num = min(num, p2[0]);
            }
            return ret - num;
        }
    }
};

递推版本:

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp(3, -1);
        dp[0] = 0;
        
        for (int i = 0;i < nums.size();i++) {
            vector<int> temp = dp;
            for (int j = 0;j < 3;j++) {
                if (dp[j] == -1) {
                    continue;
                }
                int next = (j + nums[i]) % 3;
                temp[next] = max(dp[next], dp[j] + nums[i]);
            }
            dp = temp;
        }
        return dp[0];
    }
};

题目4:

额。。。这个题。。。一开始看错了,以为是求移动的最小距离,等到拍完测了一下才发现,原来是求箱子的最小移动次数
明显是bfs题,玩家和箱子的位置一起构成的状态。由于箱子的移动次数跟bfs的长度不构成线性函数,因此需要用优先队列来保证每次移动的是当前最小移动次数的状态

class Solution {
public:
    int minPushBox(vector<vector<char>>& grid) {
        //Q里面的元素有5维,0:当前状态最小推箱子次数 1:人的x坐标 2:人的y坐标 3:箱子的x坐标 4:箱子的y坐标
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> Q;
        
        int n = grid.size();
        int m = grid[0].size();
        vector<int> p1;
        vector<int> p2;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid[i][j] == 'S') {
                    grid[i][j] = '.';
                    p1 = {i, j};
                }
                if (grid[i][j] == 'B') {
                    grid[i][j] = '.';
                    p2 = {i, j};
                }
            }
        }
        Q.push({0, p1[0], p1[1], p2[0], p2[1]});
        map<vector<int>, int> dist;
        dist[{p1[0], p1[1], p2[0], p2[1]}] = 0;
        
        int vx[] = {0,0,1,-1};
        int vy[] = {1,-1,0,0};
        while (!Q.empty()) {
            vector<int> res = Q.top();
            Q.pop();
            
            for (int i = 0;i < 4;i++) {
                vector<int> next_s = {res[1] + vx[i], res[2] + vy[i]};
                if (next_s[0] < 0 || next_s[0] >= n || next_s[1] < 0 || next_s[1] >= m || grid[next_s[0]][next_s[1]] == '#') {
                    continue;
                }

                vector<int> next_b = {res[3], res[4]};
                int d = res[0];
                if (next_s[0] == res[3] && next_s[1] == res[4]) {
                    next_b = {res[3] + vx[i], res[4] + vy[i]};
                    if (next_b[0] < 0 || next_b[0] >= n || next_b[1] < 0 || next_b[1] >= m || grid[next_b[0]][next_b[1]] == '#') {
                        continue;
                    }
                    d++;
                }
                
                if (grid[next_b[0]][next_b[1]] == 'T') {
                    return d;
                }
                if (dist.find({next_s[0], next_s[1], next_b[0], next_b[1]}) != dist.end()) {
                    continue;
                } 
                dist[{next_s[0], next_s[1], next_b[0], next_b[1]}] = d;
                Q.push({d, next_s[0], next_s[1], next_b[0], next_b[1]});
                    
            }
        }
        return -1;
    }
};
24
展开全部 9 讨论