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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2019-11-17

二维网格迁移

  • 思路:按题意模拟即可。
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
展开全部 9 讨论