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

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

image.png

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

前言

排名: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
展开全部 9 讨论