AC第六天

Jie2025-04-272025-05-06

1. 统计被覆盖的建筑 LeetCode

public class LeetCodeTest {
    @Test
    public void test() {
        int n = 5;
        int[][] buildings = {{1, 3}, {3, 2}, {3, 3}, {3, 5}, {5, 3}};
        System.out.println(countCoveredBuildings(n, buildings));
    }

    public int countCoveredBuildings(int n, int[][] buildings) {
        Map<Integer, int[]> rowMinMax = new HashMap<>();
        Map<Integer, int[]> colMinMax = new HashMap<>();
        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            rowMinMax.compute(x, (k, v) -> v == null ? new int[]{y, y} : new int[]{Math.min(v[0], y), Math.max(v[1], y)});
            colMinMax.compute(y, (k, v) -> v == null ? new int[]{x, x} : new int[]{Math.min(v[0], x), Math.max(v[1], x)});
        }

        int ans = 0;
        for (int[] p : buildings) {
            int x = p[0], y = p[1];
            int[] row = rowMinMax.get(x);
            int[] col = colMinMax.get(y);
            if (row[0] < y && y < row[1] && col[0] < x && x < col[1]) {
                ans++;
            }
        }
        return ans;
    }
}

思路: 按行和列分别求出存在的最小值和最大值作为边界，在这个边界内查找，只要有符合条件的建筑就计数+1。

2. 平衡二叉树 LeetCode

public class LeetCodeTest {
    public static 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;
        }
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(3,
                new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7))
        );
        System.out.println(isBalanced(root));
    }

    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int leftHeight = height(node.left);
        if (leftHeight == -1) return -1;
        int rightHeight = height(node.right);
        if (rightHeight == -1) return -1;
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        return Math.max(leftHeight,rightHeight) + 1;
    }
}