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

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

image.png

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

共 9 个回复

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

第一题:

很简单,就把整个矩阵拉成一个数组,然后从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 / 1603(PS:第一次全国前10,全球前50,开心)

5263. 二维网格迁移

在这里插入图片描述
思路:我知道Leetcode这个Easy难度的暴力没啥问题吧,所以直接暴力了。
代码:

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int> >ans;
        ans.resize(n);
        for(int i=0; i<n; i++) ans[i].resize(m);
        while(k--){
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(j+1<m) ans[i][j+1]=grid[i][j];
                    else if(j==m-1&&(i+1<n)) ans[i+1][0]=grid[i][j];
                    else if(i==n-1&&j==m-1) ans[0][0]=grid[i][j];
                }
            }
            grid = ans;
        }
        return grid;
    }
};

5264. 在受污染的二叉树中查找元素

在这里插入图片描述
思路:DFS按照题意建树,保存到vector里排序用二分查找,似乎本身就是有序的,排序多此一举了。也可以用map映射。

class FindElements {
public:
    vector <int> v;
    void dfs(TreeNode* root, int val){
        v.push_back(val);
        if(root->left != NULL){
            dfs(root->left, val*2+1);
        }
        if(root->right != NULL){
            dfs(root->right, val*2+2);
        }
        return;
    }
    FindElements(TreeNode* root) {
        v.clear();
        dfs(root, 0);
        sort(v.begin(), v.end());
    }

    bool find(int target) {
        int pos = lower_bound(v.begin(), v.end(), target) - v.begin();
        if(pos < v.size() && v[pos] == target) return true;
        else return false;
    }
};

5265. 可被三整除的最大和

在这里插入图片描述
思路:将整个数组排序,然后求出总和sum,如果sum能被3整除那么显然答案就是sum,否则还剩下2种情况,一种是模上3还剩下1,一种是模上3还剩下2的。对于模上3还剩下1的,我们只需要找一个最小的模上3的数记作a,或者两个模上3等于2的数字和记作b,然后答案就是max(sum-a, sum-b),因为已经排序了,所以顺序找就好了。对于模上3还剩下1的,和这个情况完全一样。
代码:

class Solution
{
public:
    int maxSumDivThree(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
        }
        if (sum % 3 == 0)
            return sum;
        else if (sum % 3 == 1)
        {
            bool flag = false;
            int t = -1;
            for (int i = 0; i < nums.size(); i++)
            {
                if (nums[i] % 3 == 1)
                {
                    t = nums[i];
                    flag = true;
                    break;
                }
            }
            int ans = 0;
            if (flag)
                ans = max(ans, sum - t);

            int cnt = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                if (nums[i] % 3 == 2)
                {
                    cnt++;
                }
            }
            if (cnt >= 2)
            {
                cnt = 2;
                int t = 0;
                for (int i = 0; i < nums.size(); i++)
                {
                    if (nums[i] % 3 == 2 && cnt)
                    {
                        cnt--;
                        t += nums[i];
                    }
                }
                ans = max(ans, sum - t);
            }
            return ans;

        }
        else if (sum % 3 == 2)
        {
            bool flag = false;
            int t = -1;
            for (int i = 0; i < nums.size(); i++)
            {
                if (nums[i] % 3 == 2)
                {
                    t = nums[i];
                    flag = true;
                    break;
                }
            }
            int ans = 0;
            if (flag)
                ans = max(ans, sum - t);

            int cnt = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                if (nums[i] % 3 == 1)
                {
                    cnt++;
                }
            }
            if (cnt >= 2)
            {
                cnt = 2;
                t = 0;
                for (int i = 0; i < nums.size(); i++)
                {
                    if (nums[i] % 3 == 1 && cnt)
                    {
                        cnt--;
                        t += nums[i];
                    }
                }
                ans = max(ans, sum - t);
            }
            return ans;
        }
        return sum;
    }
};

5266. 推箱子

在这里插入图片描述
思路:和大概2月前的周赛的BFS题思路一样,开一个4维数组having记录人所在的位置i,j和箱子所在的位置x,y是否被标记过,当然也需要一个vis数组来记录一下哪些点被访问过了,然后就是正常的BFS了。
代码:

const int maxn=22;
class Solution {
public:

    struct Node{
        int px,py;
        int x,y,step;
    };
    bool vis[maxn][maxn],having[maxn][maxn][maxn][maxn];
    int mp[22][22],n,m,sx,sy,sx1,sy1;
    int mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    void dfs(int x,int y){
        for(int i=0;i<4;++i){
            int xx=x+mov[i][0];
            int yy=y+mov[i][1];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&mp[xx][yy]!=1&&!vis[xx][yy]){
                vis[xx][yy]=true;
                dfs(xx,yy);
            }
        }
    }
    int bfs(){
        queue<Node>Q;
        Node u;int i,j,k;
        u.x=sx;u.y=sy;u.step=0;
        u.px=sx1;u.py=sy1;
        Q.push(u);
        while(!Q.empty()){
            u=Q.front();Q.pop();
            memset(vis,false,sizeof(vis));
            vis[u.px][u.py]=true;vis[u.x][u.y]=true;
            dfs(u.px,u.py);
            for(i=0;i<4;++i){
                int xx=u.x+mov[i][0];
                int yy=u.y+mov[i][1];
                if(xx>=0&&xx<n&&yy>=0&&yy<m&&mp[xx][yy]!=1){
                    int x1=u.x-mov[i][0];
                    int y1=u.y-mov[i][1];
                    if(x1>=0&&x1<n&&y1>=0&&y1<m&&vis[x1][y1]){
                        if(having[u.x][u.y][x1][y1])continue;
                        having[u.x][u.y][x1][y1]=true;
                        Node v;
                        v.x=xx;v.y=yy;v.step=u.step+1;
                        if(mp[xx][yy]==3)return v.step;
                        v.px=x1;v.py=y1;
                        Q.push(v);
                    }
                }
            }
        }
        return -1;
    }
    int minPushBox(vector<vector<char>>& grid) {
        memset(having, false, sizeof(having));
        memset(mp, 0, sizeof(mp));
        n = grid.size();
        m = grid[0].size();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(grid[i][j]=='S'){
                    mp[i][j]=4;
                }
                else if(grid[i][j]=='.'){
                    mp[i][j]=0;
                }
                else if(grid[i][j]=='#'){
                    mp[i][j]=1;
                }
                else if(grid[i][j]=='B'){
                    sx=i, sy=j;
                    mp[i][j]=2;
                }
                else if(grid[i][j]=='T'){
                    sx1=i,sy1=j;
                    mp[i][j]=3;
                }
            }
        }
        return bfs();
    }
};

欢迎关注我的微信公众号:GiantPadaCV,期待和你一起交流机器学习,深度学习,图像算法,优化技术,比赛及日常生活等。

9

第3题的python解答:
dp[i]: 当前模3余i的最大和。

dp = [0, float('-inf'), float('-inf')]
for n in nums:
	dp = [max(dp[i], dp[(3 - n%3 + i)%3]+n) for i in range(3)]
return dp[0]
5

好想打周赛,可惜人在火车站吃瓜

4

二维网格迁移

  • 思路:按题意模拟即可。
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int n=(int)grid.size(),m=(int)grid[0].size();
        for (;k--;){
            vector<vector<int> >res;res.clear();
            for (int i=0;i<n;++i){
                vector<int> t;t.clear();
                for (int j=0;j<m;++j){
                    t.push_back(0);
                }
                res.push_back(t);
            }
            for (int i=0;i<n;++i){
                for (int j=0;j<m-1;++j){
                    res[i][j+1]=grid[i][j];
                }
                if (i<n-1) res[i+1][0]=grid[i][m-1];
            }
            res[0][0]=grid[n-1][m-1];
            for (int i=0;i<n;++i){
                for (int j=0;j<m;++j){
                    grid[i][j]=res[i][j];
                }
            }
        }
        return grid;
    }
};

在受污染的二叉树中查找元素

  • 思路:按题意模拟还原二叉树,可以直接开一个范围[1,106][1,10^6]的数组记录这个数在不在二叉树中,这样查询就是O(1)O(1),我赛时直接开了个map记录,带一个log,查询就是O(logn)O(logn),不过都能通过就是了。
class FindElements {
public:
    map<int,int>mp;
    void dfs(TreeNode* root){
        if (root->left!=NULL){
            root->left->val=root->val*2+1;
            mp[root->val*2+1]=1;
            dfs(root->left);
        }
        if (root->right!=NULL){
            root->right->val=root->val*2+2;
            mp[root->val*2+2]=1;
            dfs(root->right);
        }
        
    }
    FindElements(TreeNode* root) {
        mp.clear();
        root->val=0;mp[0]=1;
        dfs(root);
    }
    
    bool find(int target) {
        if (mp.find(target)!=mp.end()) return true;
        return false;
    }
};

可被三整除的最大和

  • 思路:没有动脑的写了个dp吧..定义dp[i][0/1][0..2]dp[i][0/1][0..2]为考虑前i个数字,第i个数字不取或取,总和余数为0,1,2的最大和,答案就是max(dp[n][0][0],dp[n][1][0]),转移其实也很简单,相当于刚开始dp数组全设为1,只有max(dp[n][0][0],dp[n][1][0]),转移其实也很简单,相当于刚开始dp数组全设为-1,只有dp[0][0][0]=0,不选的时候就从前一个,不选的时候就从前一个dp[i-1]$的相应取或不取的状态取一个max转移过来,选的时候就看第i个数的余数,如果是1,那么相应的比如说dp[i][1][1]就是max(dp[i-1][0][0],dp[i-1][1][0])+nums[i],相当于如果考虑第i个数字后要求总和余数为1的最大值,那么肯定是从前一个余数和为0的地方转移过来的,需要注意的是dp值为-1的时候是不能转移过来的,这表示没有这种组合,当然肯定会有简单的方法,这样写起来比较麻烦,可能你可以对余数分个组,看总和的余数是多少然后看能不能贪心的丢掉一些值就可以了,不过我没什么把握就写dp了(然而还是因为数组开小RE了一发...)。
    代码:
class Solution {
public:
    #define N 40010
    int dp[N][2][3];
    int get(int a,int b,int c){
        if (a==-1 && b==-1) return -1;
        else if (a==-1 && b!=-1) return b+c;
        else if (a!=-1 && b==-1) return a+c;
        else return max(a,b)+c;
    }
    int maxSumDivThree(vector<int>& nums) {
        memset(dp,-1,sizeof(dp));
        dp[0][0][0]=0;
        int n=(int)nums.size();
        for (int j=0,i=1;j<(int)nums.size();++j,++i){
            int x=nums[j]%3;
            dp[i][0][0]=get(dp[i-1][0][0],dp[i-1][1][0],0);
            dp[i][0][1]=get(dp[i-1][0][1],dp[i-1][1][1],0);
            dp[i][0][2]=get(dp[i-1][0][2],dp[i-1][1][2],0);
            if (x==0){
                x=nums[j];
                dp[i][1][0]=get(dp[i-1][0][0],dp[i-1][1][0],x);
                dp[i][1][1]=get(dp[i-1][0][1],dp[i-1][1][1],x);
                dp[i][1][2]=get(dp[i-1][0][2],dp[i-1][1][2],x);
            }
            else if (x==1){
                x=nums[j];
                dp[i][1][0]=get(dp[i-1][0][2],dp[i-1][1][2],x);
                dp[i][1][1]=get(dp[i-1][0][0],dp[i-1][1][0],x);
                dp[i][1][2]=get(dp[i-1][0][1],dp[i-1][1][1],x);
            }
            else{
                x=nums[j];
                dp[i][1][0]=get(dp[i-1][0][1],dp[i-1][1][1],x);
                dp[i][1][1]=get(dp[i-1][0][2],dp[i-1][1][2],x);
                dp[i][1][2]=get(dp[i-1][0][0],dp[i-1][1][0],x);
            }
        }
        int ans=get(dp[n][0][0],dp[n][1][0],0);
        return ans==-1?0:ans;
    }
};

推箱子

  • 思路:考虑到目标是箱子的最小推动次数,所以其实人走多少步都没关系,乱走都行。那么如果箱子自己长脚了,肯定是直接bfs一下即可,但现在它是靠人推动的,所以其实我们在bfs箱子的时候需要看箱子推动反方向的位置人是否能到达即可,因为推动的时候人肯定是要在箱子推动反方向的那一个格子上,所以我们在对箱子bfs的时候check一下人是否能到达这个反方向的位置即可,也可以跑一遍bfs,问题解决了,剩下来就只管写写写好了。当时看到题目其实就知道自己做过原题,然后翻了下是HDU1254,然后。。。就直接把两年前自己写的代码贴过来改一下过了(逃),看一下当年的码风还是奇奇怪怪的,大括号居然不换行= =。
    333.png
class Solution {
public:
    int n,m,ri,rj,di,dj,bi,bj;
    int dir[4][2] = { { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 } };
    int mp[30][30];
    int vir[30][30][30][30];
    struct node{
        int bx, by;
        int rx, ry;
        int cnt;
    };
    struct man{
        int x, y;
    };
    bool check(int i, int j){
        if (i<1 || i>m || j<1 || j>n || mp[i][j] == '#')
            return 0;
        return 1;
    }
    int bfs2(int si, int sj, int di, int dj, int bi, int bj){
        int vis[30][30];
        memset(vis, 0, sizeof(vis));
        queue<man>qu;
        man st, ed;
        st.x = si;
        st.y = sj;
        vis[si][sj] = 1;
        qu.push(st);
        while (!qu.empty()){
            st = qu.front();
            qu.pop();
            if (st.x == di&&st.y == dj)
                return 1;
            for (int i = 0; i < 4; i++){
                ed.x = st.x + dir[i][0];
                ed.y = st.y + dir[i][1];
                if (check(ed.x, ed.y)&& !vis[ed.x][ed.y]&& (ed.x != bi||ed.y != bj)){
                    vis[ed.x][ed.y] = 1;
                    qu.push(ed);
                }
            }
        }
        return 0;
    }

    int bfs(int bi, int bj, int ri, int rj, int di, int dj){
        queue<node>q;
        node f, d;
        f.bx = bi;
        f.by = bj;
        f.rx = ri;
        f.ry = rj;
        f.cnt = 0;
        vir[bi][bj][ri][rj] = 1;
        q.push(f);
        while (!q.empty()){
            f = q.front();
            q.pop();
            if (f.bx == di&&f.by == dj)
                return f.cnt;
            for (int i = 0; i<4; i++){
                d.bx = f.bx + dir[i][0];
                d.by = f.by + dir[i][1];
                d.rx = f.bx - dir[i][0];
                d.ry = f.by - dir[i][1];
                if (check(d.bx, d.by)&&check(d.rx,d.ry) && !vir[d.bx][d.by][d.rx][d.ry]){
                    if (bfs2(f.rx, f.ry, d.rx, d.ry, f.bx, f.by)){
                        vir[d.bx][d.by][d.rx][d.ry] = 1;
                        d.cnt = f.cnt + 1;
                        q.push(d);
                    }
                }
            }
        }
        return -1;
    }
    int minPushBox(vector<vector<char>>& grid) {
        m=(int)grid.size(),n=(int)grid[0].size();
        for (int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                mp[i][j]=grid[i-1][j-1];
                if (mp[i][j]=='S'){
                    ri=i;
                    rj=j;
                }
                if (mp[i][j]=='B'){
                    bi=i;
                    bj=j;
                }
                if (mp[i][j]=='T'){
                    di=i;
                    dj=j;
                }
            }
        }
        int ans=bfs(bi,bj,ri,rj,di,dj);
        return ans;   
    }
};

最后.. 原文链接

3

第一题:

数据规模比较小,因此有很多种做法,例如将二维矩阵展开成一维矩阵后再还原,先进行行变换再进行列变换等。我的题解中的做法是先找出左上角的元素被移动到的位置,再从该位置开始依次填入矩阵中的元素。
题解传送门

第二题:

感觉这题比第一题还简单些,直接按照题目要求将二叉树进行还原,再将所有元素放入集合中方便查询即可。
题解传送门

第三题:

这道题有很多种做法,都可以在较优的时间复杂度内得出答案。我的题解中给出了三种方法,前两种基于贪心,后一种基于动态规划。
题解传送门

第四题:

看到有很多同学说这道题只用 BFS(不是 BFS 套 BFS)没法做,我想说其实是可以做的。因为转移的权值只有 0 和 1 两种,因此只要在 0 转移时直接加入队列,1 转移时加入一个新的队列即可。具体可以看一看我的题解。
题解传送门

1
1

1.numpy大法好
2.队列压入和弹出节点(BFS?)
3.讨论总和的余数为1和为2的情况,似乎还是动态规划来的好一点。
扔个python3的题解链接就跑:
https://www.bilibili.com/read/cv3986686
我好菜啊。

1

java代码、简单易懂
1、模拟
2、树的基本递归操作
3、贪心和dp两种做法
4、深搜广搜两次搜索
题解传送门