破晓的知识屋
0%

2022-0823

发表于 更新于 分类于 ， ， 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

[toc]

第一题:数学规律题(没想通)#

782. 变为棋盘 - 力扣（LeetCode）

看答案也没看懂，主要是没有深入研究规律，没精力了，先放着

1661270748809

1661270976714

第二题:矩阵前缀和应用#

剑指 Offer II 013. 二维子矩阵的和 - 力扣（LeetCode）

1661270797124

做过好几次了， 维护一个dp[y][x]， 表示（y，x）到(0,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
25
26
27
28
29
30
31
32
33
34
class NumMatrix {
    int[][] dp;
    int ylen;
    int xlen;
    public NumMatrix(int[][] matrix) {
        ylen = matrix.length;
        xlen = matrix[0].length;
        dp = new int[ylen][xlen];
        for (int y = 0;y<ylen;y++) {
            int sum = 0;
            for (int x = 0; x < xlen; x++) {
                sum += matrix[y][x];
                dp[y][x] = sum + (y-1>=0?dp[y-1][x]:0);
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum(row2, col2) - sum(row2, col1-1) - sum(row1-1, col2) + sum(row1-1, col1-1);
    }

    int sum(int y, int x) {
        if (y <0 || x < 0) {
            return 0;
        }
        return dp[y][x];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

第三题:树和递归#

606. 根据二叉树创建字符串 - 力扣（LeetCode）

1661270915678

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        String left = "(" + tree2str(root.left) + ")";
        String right = "(" + tree2str(root.right) + ")";
        if (left.length() == 2 && right.length() == 2) {
            left = "";
            right = "";
        } else if(left.length() != 2 && right.length() == 2) {
            right = "";
        }
        return root.val + left + right;
    }
}