Biweekly Contest 129

欢迎大家加QQ群：623375442，可以方便群里面交流。

100286. Make a Square with the Same Color

给你一个二维 3 x 3 的矩阵 grid ，每个格子都是一个字符，要么是 'B' ，要么是 'W' 。字符 'W' 表示白色，字符 'B' 表示黑色。

你的任务是改变 至多一个 格子的颜色，使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。

如果可以得到一个相同颜色的 2 x 2 正方形，那么返回 true ，否则返回 false 。

测试样例：

输入：grid = [["B","W","B"],["B","W","W"],["B","W","B"]]

输出：true

解释：修改 grid[0][2] 的颜色，可以满足要求。

解答：暴力。

class Solution {
    public boolean canMakeSquare(char[][] grid) {
        for (int i = 1; i < 3; ++i) {
            for (int j = 1; j < 3; ++j) {
                int b = 0, w = 0;
                for (int d1 = -1; d1 <= 0; ++d1) {
                    for (int d2 = -1; d2 <= 0; ++d2) {
                        if (grid[i + d1][j + d2] == 'B') {
                            ++b;
                        } else {
                            ++w;
                        }
                    }
                }
                if (b <= 1 || w <= 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

100278. Right Triangles

给你一个二维 boolean 矩阵 grid 。

请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目，且满足 3 个元素值 都 为 1 。

注意：

• 如果 grid 中 3 个元素满足：一个元素与另一个元素在 同一行，同时与第三个元素在 同一列 ，那么这 3 个元素称为一个 直角三角形 。这 3 个元素互相之间不需要相邻。

测试样例：

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]

输出：2

解释：有 2 个直角三角形。

解答：利用乘法配合计数。

class Solution {
    public long numberOfRightTriangles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] row = new int[m], col = new int[n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                row[i] += grid[i][j];
                col[j] += grid[i][j];
            }
        }

        long res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    long r = row[i] - 1L, c = col[j] - 1L;
                    // 满足要求的直角数量 = 当前列可选点 * 当前行可选点
                    // 可选 = 除去当前点之外的所有点都满足要求
                    res += r * c;
                }
            }
        }
        return res;
    }
}

100293. Find All Possible Stable Binary Arrays II

给你 3 个正整数 zero ，one 和 limit 。

一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：

• 0 在 arr 中出现次数 恰好 为 zero 。
• 1 在 arr 中出现次数 恰好 为 one 。
• arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。

请你返回 稳定 二进制数组的 总 数目。

由于答案可能很大，将它对 10^9 + 7 取余 后返回。

测试样例：

输入：zero = 1, one = 1, limit = 2

输出：2

解释：两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。

解答：可以用动态规划。不能连续出现limit + 1的0或者1，同时0和1总出现次数也有限制。可以利用链表来转移矩阵（暴力遍历复杂度会爆炸）。

class Solution {
    private static final int mod = 1_000_000_007;

    public int numberOfStableArrays(int zero, int one, int limit) {
        LinkedList<Integer>[] zeros = new LinkedList[zero + 1], ones = new LinkedList[one + 1];
        for (int i = 0; i <= zero; ++i) {
            zeros[i] = new LinkedList<>();
        }
        for (int i = 0; i <= one; ++i) {
            ones[i] = new LinkedList<>();
        }
        int[] zeroSum = new int[zero + 1], oneSum = new int[one + 1];

        zeros[zero - 1].add(1);
        zeroSum[zero - 1] = 1;

        ones[one - 1].add(1);
        oneSum[one - 1] = 1;

        for (int i = 2; i <= zero + one; ++i) {
            int[] nextZeroSum = new int[zero + 1], nextOneSum = new int[one + 1];
            for (int j = 0; j < zero; ++j) {
                int used = zero - j;
                // 首先判断是否满足要求：1. 期望使用的个数不能大于总个数 2. 当前的选择不能使另一个数字超过使用上限
                if (used > i) {
                    nextZeroSum[j] = 0;
                    zeros[j] = new LinkedList<>();
                } else if (one - (i - used) < 0) {
                    nextZeroSum[j] = 0;
                    zeros[j] = new LinkedList<>();
                } else {
                    // 位移运算，因为连续增加，可以认为把上一个队列移过来
                    zeros[j] = zeros[j + 1];
                    // 前缀和来加速计算
                    nextZeroSum[j] = zeroSum[j + 1];
                    if (zeros[j].size() == limit) {
                        nextZeroSum[j] = sub(nextZeroSum[j], zeros[j].removeLast());
                    }

                    // 1个连续，可以认为从另一个数字那边增加一个当前数，租借过来。
                    nextZeroSum[j] = add(nextZeroSum[j], oneSum[one - (i - used)]);
                    zeros[j].addFirst(oneSum[one - (i - used)]);
                }
            }
            zeros[zero] = new LinkedList<>();

            for (int j = 0; j < one; ++j) {
                int used = one - j;
                if (used > i) {
                    nextOneSum[j] = 0;
                    ones[j] = new LinkedList<>();
                } else if (zero - (i - used) < 0) {
                    nextOneSum[j] = 0;
                    ones[j] = new LinkedList<>();
                } else {
                    ones[j] = ones[j + 1];
                    nextOneSum[j] = oneSum[j + 1];
                    if (ones[j].size() == limit) {
                        nextOneSum[j] = sub(nextOneSum[j], ones[j].removeLast());
                    }

                    nextOneSum[j] = add(nextOneSum[j], zeroSum[zero - (i - used)]);
                    ones[j].addFirst(zeroSum[zero - (i - used)]);
                }
            }
            ones[one] = new LinkedList<>();

            zeroSum = nextZeroSum;
            oneSum = nextOneSum;
        }

        int res = 0;
        for (int n : zeroSum) {
            res = add(n, res);
        }
        for (int n : oneSum) {
            res = add(n, res);
        }
        return (zeroSum[0] + oneSum[0]) % mod;
    }

    private int sub(int x, int y) {
        return (x - y + mod) % mod;
    }

    private int add(int x, int y) {
        return (x + y) % mod;
    }
}