Leetcode-第163场周赛

发表于 分类于 阅读次数：

1260. 二维网格迁移

解法：模拟

模拟，就是右下角向后移动跑到左上角，其他依次右移一个单元格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int n=grid.size(),m=grid[0].size();
        vector<vector<int>> res(grid.begin(),grid.end());
        vector<vector<int>> temp(grid.begin(),grid.end());
        while(k--)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    if(i==0&&j==0)
                        temp[i][j]=res[n-1][m-1];
                    else if(j==0)
                    {
                        temp[i][j]=res[i-1][m-1];
                    }
                    else temp[i][j]=res[i][j-1];
                }
            }
            res=temp;
        }
        return res;
    }
};

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

解法1：递归

先前序构造二叉树

然后遍历查找元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class FindElements {
    private:
    TreeNode *root_r;
public:
    FindElements(TreeNode* root) {
        root->val=0;
        recover(root);
        this->root_r=root;
    }
    void recover(TreeNode *root)
    {
        if(root->left!=NULL)
        {
            root->left->val=root->val*2+1;
            recover(root->left);
        }
        if(root->right!=NULL)
        {
            root->right->val=root->val*2+2;
            recover(root->right);
        }
    }
    bool find(int target) {
        TreeNode *root;
        root=root_r;
        return find_tar(root,target);
    }
    bool find_tar(TreeNode* root,int target)
    {
        if(root==NULL)
            return false;
        if(root->val==target)
            return true;
        return find_tar(root->left,target)||find_tar(root->right,target);
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */
解法2：递归+set

提升：可以在构造过程中直接将元素记录下来，节省大量时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class FindElements {
    private:
    TreeNode *root_r;
    set<int> s;
public:
    FindElements(TreeNode* root) {
        root->val=0;
        s.insert(0);
        recover(root);
        this->root_r=root;
    }
    void recover(TreeNode *root)
    {
        if(root->left!=NULL)
        {
            root->left->val=root->val*2+1;
            s.insert(root->left->val);
            recover(root->left);
        }
        if(root->right!=NULL)
        {
            root->right->val=root->val*2+2;
            s.insert(root->right->val);
            recover(root->right);
        }
    }
    bool find(int target) {
        return s.find(target)!=s.end();
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

1262. 可被三整除的最大和

解法：动态规划

1.设dp[i]代表 选取的数字累加和 模3=i 的数字和

2.对dp[0]而言。若num[i]%3=k,那么，和前面选取的数字和模3=3-k的数(dp[3-k])相加，就可以模3得0,表达起来就是dp[0]=max(dp[0],dp[3-k]+num[i])

更一般的得dp[j]=max(dp[j],dp[(3-k+j)%3]+num[i])

3.遍历数组，不断更新dp数组，最后返回dp[0]的值即为结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int dp[3] = {0, 0, 0};
        
        for (int i = 0; i < nums.size(); ++i) {
            int mod = nums[i] % 3;

           /* int a = dp[(3 + 0 - mod) % 3];
            int b = dp[(3 + 1 - mod) % 3];
            int c = dp[(3 + 2 - mod) % 3];*/
            for(int j=0;j<3;j++)
            {
                if(dp[(3-mod+j)%3]||mod==j)
               		dp[j]=max(dp[j],dp[(3-mod+j)%3]+nums[i]);
            }
            //前面三个if是防止a||b||c =0时，执行后面语句产生错误
          /*  if (a || mod == 0) dp[0] = std::max(dp[0], a + nums[i]);
            if (b || mod == 1) dp[1] = std::max(dp[1], b + nums[i]);
            if (c || mod == 2) dp[2] = std::max(dp[2], c + nums[i]);*/
        }
        return dp[0];
    }
};

1263. 推箱子