leetcode biweekly contest 129

T4 确实太难了，确实不太好做，T3 竟然暴力 DFS 就出来了。

100286. 构造相同颜色的正方形

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

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

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

示例 1：

输入：grid = [[“B”,”W”,”B”],[“B”,”W”,”W”],[“B”,”W”,”B”]]

输出：true

解释：

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

示例 2：

输入：grid = [[“B”,”W”,”B”],[“W”,”B”,”W”],[“B”,”W”,”B”]]

输出：false

解释：

只改变一个格子颜色无法满足要求。

示例 3：

输入：grid = [[“B”,”W”,”B”],[“B”,”W”,”W”],[“B”,”W”,”W”]]

输出：true

解释：

grid 已经包含一个 2 x 2 颜色相同的正方形了。

提示：

• grid.length == 3
• grid[i].length == 3
• grid[i][j] 要么是 'W' ，要么是 'B' 。

地址

https://leetcode.cn/contest/biweekly-contest-129/problems/make-a-square-with-the-same-color/

题意

直接模拟

思路

1. 统计每个 $2\times2$ 的正方形格子中 $w,b$ 的数目即可，此时只需要满足 $|cnt(b)-cnt(w)| = 2, 4$ 即可。
2. 复杂度分析：

• 时间复杂度：$O(mn)$。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    bool canMakeSquare(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                int w = 0, b = 0;
                for (int l = 0; l <= 1; l++) {
                    for (int r = 0; r <= 1; r++) {
                        if (grid[i + l][j + r] == 'W') {
                            w++;
                        } else {
                            b++;
                        }
                    }
                }
                if (abs(w - b) == 2 || abs(w - b) == 4) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

100278. 直角三角形

给你一个二维 boolean 矩阵 grid 。

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

注意：

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

示例 1：

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

输出：2

解释：

有 2 个直角三角形。

示例 2：

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

输出：0

解释：

没有直角三角形。

示例 3：

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

输出：2

解释：

有两个直角三角形。

提示：

• 1 <= grid.length <= 1000
• 1 <= grid[i].length <= 1000
• 0 <= grid[i][j] <= 1

地址

https://leetcode.cn/contest/biweekly-contest-129/problems/right-triangles/

题意

模拟，数学计算

思路

1. 本质是个简单的数学问题，设 $i$ 行中的 $1$ 的数目为 $cntRow$, $j$ 列中的 $1$ 的数目为 $cntCol[j]$，此时如果满足 $grid[i][j] = 1$ 时，此时以 $(i,j)$ 为顶点的构成的直角三角形数目即为 $(cntCol[j] - 1) \times (cntRow[i] - 1)$ 。
2. 复杂度分析：

• 时间复杂度：$O(mn)$，其中 $m,n$ 表示给定矩阵的行数与列数。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        cntRow = [sum(grid[i]) for i in range(len(grid))]
        cntCol = [0] * n
        for i in range(n):
            for j in range(m):
                cntCol[i] += grid[j][i]
        return sum(sum([(cntCol[j] - grid[i][j]) * (cntRow[i] - grid[i][j]) for j in range(n) if grid[i][j] == 1]) for i in range(m))

100292. 找出所有稳定的二进制数组 I

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

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

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

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

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

示例 1：

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

输出：2

解释：

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

示例 2：

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

输出：1

解释：

唯一稳定的二进制数组是 [1,0,1] 。

二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。

示例 3：

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

输出：14

解释：

所有稳定的二进制数组包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1] ，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0] ，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0] ，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

提示：

• 1 <= zero, one, limit <= 200

地址

https://leetcode.cn/contest/biweekly-contest-129/problems/find-all-possible-stable-binary-arrays-i/

题意

记忆化搜索, 动态规划

思路

1. 设 $f(x,y,cnt, flag)$ 表示当前已经填充了 $x$ 个 $0$ ，$y$ 个 $1$ ，则最后一个元素的连续数目为 $cnt$，且元素为 $flag$ 的数目，此时我们知道一定满足如下条件:

   • $x \le zero, y \le one, cnt \le limit$；
   • $flag \in [0, 1]$;

   当前已经填充了 $x+ y$ 个元素，此时我们填充下一个元素即 $x + y+1$ 个元素，此时需要遵循以下原则：

   • 如果 $x = zero, y = one$ 此时已经填充完成，直接返回 $0$；
   • 如果 $x = zero$ ，则此时表示剩余的空间只能填充 $1$，此时计算最后填充的数目中 $1$ 的连续数目是否大于 $limit$, 此时需要填充的 $1$ 的数目为 $one - y$；
     • 如果上一个元素当前最后填充的 $0$, 此时只需要检测 $one - y \le limit$ 是否满足即可，如果满足即可构成合法序列；
     • 如果上一个元素当前最后填充的 $1$, 此时只需要检测 $cnt + one - y \le limit$​ 是否满足即可，如果满足即可构成合法序列；
   • 如果 $y = zero$ ，则此时表示剩余的空间只能填充 $0$，此时计算最后填充的数目中 $0$ 的连续数目是否大于 $limit$, 此时需要填充的 $0$ 的数目为 $zero- x$；
     • 如果上一个元素当前最后填充的 $1$, 此时只需要检测 $zero - x \le limit$ 是否满足即可，如果满足即可构成合法序列；
     • 如果上一个元素当前最后填充的 $0$, 此时只需要检测 $cnt + zero - x \le limit$​ 是否满足即可，如果满足即可构成合法序列；
   • 如果满足 $x \neq zero, y \neq one$, 此时当前位置即可填充 $1$ ，也可以填充 $0$；
     • 如果上一个元素当前最后填充的 $0$：
       • 如果当前序列填充的为 $1$ , 则此时填充的序列数目即为 $f(x, y + 1, 1, 1)$;
       • 如果当前序列填充的为 $0$ , 则此时填充的序列数目即为 $f(x+1, y, cnt + 1, 0)$​​;
       • 总的填充数目即为： $f(x, y + 1, 1, 1) + f(x+1, y, cnt + 1, 0)$;
     • 如果上一个元素当前最后填充的 $1$：
       • 如果当前序列填充的为 $0$ , 则此时填充的序列数目即为 $f(x+1, y, 1, 0)$;
       • 如果当前序列填充的为 $1$ , 则此时填充的序列数目即为 $f(x, y+1, cnt + 1, 1)$​;
       • 总的填充数目即为：$f(x+1, y, 1, 0) + f(x, y+1, cnt + 1, 1)$;

2. 复杂度：

• 时间复杂度：$O(zeor \times one \times limit)$，其中 $zeor,one,limit$ 表示给定的元素；
• 空间复杂度：$O(zeor \times one \times limit)$；

代码

class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        long long mod = 1e9 + 7;
        int memo[zero + 1][one + 1][limit + 1][2];
        memset(memo, 0xff, sizeof(memo));
        
        function<int(int, int, int, int)> dfs = [&](int x, int y, int cnt, int flag) -> int {
            if (x > zero || y > one || cnt > limit) {
                return 0;
            }
            if (x == zero && y == one) {
                return 1;
            } else if (x == zero) {
                if ((flag == 1 && cnt + one - y <= limit) || (flag == 0 && one - y <= limit)) {
                    return 1;
                } else {
                    return 0;
                }
            } else if (y == one) {
                if ((flag == 0 && cnt + zero - x <= limit) || (flag == 1 && zero - x <= limit)) {
                    return 1;
                } else {
                    return 0;
                }
            }

            if (memo[x][y][cnt][flag] != -1) {
                return memo[x][y][cnt][flag];
            }
            
            long long ret = 0;
            if (flag == 1) {
                ret = (dfs(x + 1, y, 1, 0) + dfs(x, y + 1, cnt + 1, 1)) % mod;
            } else {
                ret = (dfs(x, y + 1, 1, 1) + dfs(x + 1, y, cnt + 1, 0)) % mod;
            }
            memo[x][y][cnt][flag] = ret;
            return ret;
        };
        
        return (dfs(1, 0, 1, 0) + dfs(0, 1, 1, 1)) % mod;
    }
};

100293. 找出所有稳定的二进制数组 II

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

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

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

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

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

示例 1：

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

输出：2

解释：

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

示例 2：

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

输出：1

解释：

唯一稳定的二进制数组是 [1,0,1] 。

二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。

示例 3：

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

输出：14

解释：

所有稳定的二进制数组包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1] ，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0] ，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0] ，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

提示：

• 1 <= zero, one, limit <= 1000

地址

https://leetcode.cn/contest/biweekly-contest-129/problems/find-all-possible-stable-binary-arrays-ii/

题意

动态规划

思路

1. 确实是个好题目，有一点关键的转换没有想明白，但根据题目给定的数据，肯定可以知道算法的时间复杂度一定是 $O(mn)$，此时自然需要想到用动态规划的解题思路。设 $dp[i][j][k]$ 表示使用 $i$ 个 $0$ 与 $j$ 个 $1$ 且最后一个数字为 $k$ 的合法方案数。此时我们可以得到如下递推：

• 对于第 $i+j$ 个数字，如果其为 $1$:

  • 如果第 $i+j-1$ 个数字为 $0$，前 $i+j-1$ 中含有 $i$ 个 $0$，$j-1$ 个 $1$，则直接在 $i+j$ 处填充 $1$ 即可，即合法的方案数为 $dp[i][j-1][1]$；
  • 如果第 $i+j-1$ 个数字为 $1$，前 $i+j-1$ 中含有 $i$ 个 $0$，$j-1$ 个 $1$，则直接在 $i+j$ 处填充 $1$ 时可能会遇到出现超过 $limit$ 个 $1$ 的情况，由于前 $i+j-1$ 个数字的末尾最多会出现 $limit$ 个 $1$，此时如果 $i+j$ 个数字为 $1$，则会出现 $limit +1$ 个 $1$，因此一定需要去除前 $i+j-1$ 个数字中出现末尾连续 $limit$ 个 $1$ 这种情形，此时这种情形的方案数刚好等于第 $i+j-1-limit$ 处的数字为 $0$ 的方案数；
  • 综上可以得到递推公式 $dp[i][j][1] = dp[i][j-1][0] + dp[i][j-1][1] - dp[i][j-1-limit][0]$;

• 对于第 $i+j$ 个数字，如果其为 $0$:

  • 如果第 $i+j-1$ 个数字为 $1$，前 $i+j-1$ 中含有 $i-1$ 个 $0$，$j$ 个 $1$，则直接在 $i+j$ 处填充 $1$ 即可，即合法的方案数为 $dp[i-1][j][1]$；
  • 如果第 $i+j-1$ 个数字为 $0$，前 $i+j-1$ 中含有 $i-1$ 个 $0$，$j$ 个 $1$，则直接在 $i+j$ 处填充 $0$ 时可能会遇到出现超过 $limit$ 个 $0$ 的情况，由于前 $i+j-1$ 个数字的末尾最多会出现 $limit$ 个 $0$，此时如果第 $i+j$ 个数字为 $0$，则会出现 $limit +1$ 个 $0$，因此一定需要去除前 $i+j-1$ 个数字中出现末尾连续 $limit$ 个 $0$ 这种情形，此时这种情形的方案数刚好等于第 $i+j-1-limit$ 处的数字为 $1$ 的方案数；
  • 综上可以得到递推公式 $dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j][0] - dp[i-1-limit][j][0]$;

2. 复杂度分析:

• 时间复杂度：$O(mn)$，其中 $m,n$ 表示给定的数字；
• 空间复杂度：$O(mn)$，其中 $m,n$ 表示给定的数字；

代码

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        mod = 10**9 + 7
        dp = [[[0 for _ in range(2)] for _ in range(one + 1)] for _ in range(zero + 1)]
        for i in range(1, min(limit, zero) + 1):
            dp[i][0][0] = 1
        for j in range(1, min(limit, one) + 1):
            dp[0][j][1] = 1
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                dp[i][j][0] = (dp[i - 1][j][1] + dp[i - 1][j][0]) % mod
                dp[i][j][1] = (dp[i][j - 1][1] + dp[i][j - 1][0]) % mod
                if i > limit:
                    dp[i][j][0] = (dp[i][j][0] - dp[i - limit - 1][j][1] + mod) % mod
                if j > limit:
                    dp[i][j][1] = (dp[i][j][1] - dp[i][j - limit - 1][0] + mod) % mod
        
        return (dp[zero][one][0] + dp[zero][one][1]) % mod

impl Solution {
    pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
        let MOD: i64 = 1000_000_000 + 7;
        let zero = zero as usize;
        let one = one as usize;
        let limit = limit as usize;
        let mut dp: Vec<Vec<Vec<i64>>> = vec![vec![vec![0; 2]; (one + 1) as usize]; (zero + 1) as usize];

        for i in 1..=zero.min(limit) {
            dp[i][0][0] = 1;
        }
        for j in 1..=one.min(limit) {
            dp[0][j][1] = 1;
        }
        for i in 1..=zero {
            for j in 1..=one {
                dp[i][j][0] = (dp[i- 1][j][1] + dp[i - 1][j][0]) % MOD;
                dp[i][j][1] = (dp[i][j-1][1] + dp[i][j-1][0]) % MOD;
                if i > limit {
                    dp[i][j][0] = (dp[i][j][0] - dp[(i - limit - 1)][j][1] + MOD) % MOD;
                }
                if j > limit {
                    dp[i][j][1] = (dp[i][j][1] - dp[i][(j - limit - 1)][0] + MOD) % MOD;
                }
            }
        }
        ((dp[zero][one][0] + dp[zero][one][1]) % MOD) as i32
    }
}

欢迎关注和打赏，感谢支持！

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu

• 关注我的微信公众号: 哪些奋斗者