Biweekly Contest 17

Posted on | In , | |
Words count in article: 488 | Reading time ≈ 3

1313. Decompress Run-Length Encoded List

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums) {
        vector<int> ret;
        for(int i=0; i+1<nums.size(); i+=2)
            for(int j=0; j<nums[i]; j++)
                ret.push_back(nums[i+1]);
        return ret;
    }
};

1314. Matrix Block Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> ret(m, vector<int>(n, 0));
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                int lx = max(0, i-K);
                int hx = min(m-1, i+K);
                int ly = max(0, j-K);
                int hy = min(n-1, j+K);
                int sum = 0;
                for(; lx<=hx; lx++)
                    for(int z=ly; z<=hy; z++)
                        sum += mat[lx][z];
                ret[i][j] = sum;
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int row = mat.size();
        int col = mat[0].size();
        vector<vector<int>> ret(row, vector<int>(col));
        vector<vector<int>> dp(row+1, vector<int>(col+1)); // +1边缘处理
        for(int i=0; i<row; i++)
            for(int j=0; j<col; j++)
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j];
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                int r1 = max(i-K, 0), c1 = max(j-K, 0);
                int r2 = min(i+K, row-1), c2 = min(j+K, col-1);
                ret[i][j] = dp[r2+1][c2+1]-dp[r1][c2+1]-dp[r2+1][c1]+dp[r1][c1];
            }
        }
        return ret;
    }
};

1315. Sum of Nodes with Even-Valued Grandparent

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumEvenGrandparent(TreeNode* root) {
        int sum = 0;
        if(!root) return 0;
        if(root->val % 2 == 0){   
            if(root->left){
                if(root->left->left) sum += root->left->left->val;
                if(root->left->right) sum += root->left->right->val;
            }
            if(root->right){
                if(root->right->left) sum += root->right->left->val;
                if(root->right->right) sum += root->right->right->val;
            }
        }
        return sum + sumEvenGrandparent(root->left) + sumEvenGrandparent(root->right);
    }
};
Donate? comment?