Solution of Biweekly Contest 17

, ,

[Easy] 1313. Decompress Run-Length Encoded List

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are a elements with value b in the decompressed list.

Return the decompressed list.

Example

1
2
Input: nums = [1,2,3,4]
Output: [2,4,4,4]

Solution

Actually, the description of this problem would be confusing, but the main idea behind that would be how to get a, b. Frist, we have to calculate the elements we have by sum of a and using b to fill the arr.

Code

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
// time:O(n) space:O(n)
    public int[] decompressRLElist(int[] nums) {
        if (nums == null || nums.length == 0) return new int[]{};
        List<Integer> list = new ArrayList<>();
        for (int i = 0; 2 * i + 1 < nums.length; i++) {
            int a = nums[2 * i];
            int b = nums[2 * i + 1];
            for (int j = 0; j < a; j++) {
                list.add(b);
            }
        }
        int[] res = new int[list.size()];
        int k = 0;
        for (int num : list) {
            res[k++] = num;
        }
        return res;
    }

    // time:O(n) space:O(1)
    public int[] decompressRLElist2(int[] nums) {
        if (nums == null || nums.length == 0) return new int[]{};
        int count = 0;
        for (int i = 0; i < nums.length; i += 2) {
            count += nums[i];
        }
        int[] res = new int[count];
        int k = 0;
        for (int i = 0; i < nums.length; i += 2) {
            for (int j = 0; j < nums[i]; j++) {
                res[k++] = nums[i + 1];
            }
        }
        return res;
    }

[Medium] 1314. Matrix Block Sum

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example

1
2
3
4
5
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Solution

We have to calculate the prefix sum of 2d array. Be careful of index.

Code

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
// time:O(m * n) space:O(m * n)
public int[][] matrixBlockSum(int[][] mat, int K) {
        if (mat == null || mat.length== 0) return new int[][]{};
        int m = mat.length;
        int n = mat[0].length;
        int[][] res = new int[m][n];
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - 
                    dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int r1 = Math.max(0, i - K);
                int c1 = Math.max(0, j - K);
                int r2 = Math.min(m - 1, i + K);
                int c2 = Math.min(n - 1, j + K);
                res[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];
            }
        }
        return res;
    }

[Medium] 1315. Sum of Nodes with Even-Valued Grandparent

Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

Example

1
2
3
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Solution

We have to iterate each node and when it backs to root node, we just need to verify root.left and root.right .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// time:O(n) space:O(n)
public int res = 0;
    public int sumEvenGrandparent(TreeNode root) {
        if (root == null) return res;
        helper(root);
        return res;
    }
    
    public void helper(TreeNode root) {
        if (root == null) return;
        helper(root.left);
        if (root.left != null && root.val % 2 == 0) {
            if (root.left.left != null) res += root.left.left.val;
            if (root.left.right != null) res += root.left.right.val;
        }
        helper(root.right);  
        if (root.right != null && root.val % 2 == 0) {
            if (root.right.left != null) res += root.right.left.val;
            if (root.right.right != null) res += root.right.right.val;
        }
    }

[Hard] 1316. Distinct Echo Substrings

Rank: 898 / 3489. Solve 3/4 in 33 min.