高清做 视频在线观看网站,网站备案 ip,pc端购物网站建站,佛山市多语言营销型网站建站Leetcode 第 129 场双周赛题解 Leetcode 第 129 场双周赛题解题目1#xff1a;3127. 构造相同颜色的正方形思路代码复杂度分析 题目2#xff1a;3128. 直角三角形思路代码复杂度分析 题目3#xff1a;3129. 找出所有稳定的二进制数组 I思路代码复杂度分析 题目4#xff1a;… Leetcode 第 129 场双周赛题解 Leetcode 第 129 场双周赛题解题目13127. 构造相同颜色的正方形思路代码复杂度分析 题目23128. 直角三角形思路代码复杂度分析 题目33129. 找出所有稳定的二进制数组 I思路代码复杂度分析 题目43130. 找出所有稳定的二进制数组 II思路代码复杂度分析 Leetcode 第 129 场双周赛题解
题目13127. 构造相同颜色的正方形
思路
枚举 计数。
枚举矩阵中的每个 2×2 子矩形。
对于每个子矩形统计 B 和 W 的个数如果其中一个字母的出现次数 ≥3则返回 true。
如果 4 个子矩形都不满足要求返回 false。
代码
/** lc appleetcode.cn id3127 langcpp** [3127] 构造相同颜色的正方形*/// lc codestart
class Solution
{
public:bool canMakeSquare(vectorvectorchar grid){// 判断以 (row, col) 为左上角的 2*2 的正方形是否满足要求auto check [](int row, int col) - bool{int cntB 0, cntW 0;for (int i row; i row 1; i)for (int j col; j col 1; j){if (grid[i][j] B)cntB;elsecntW;}return cntB 3 || cntW 3;};// 对于 3*3 的矩阵只需要考虑 4 种情况return check(0, 0) || check(0, 1) || check(1, 0) || check(1, 1);}
};
// lc codeend复杂度分析
时间复杂度O(1)。
空间复杂度O(1)。
题目23128. 直角三角形
思路
套路有三个顶点枚举「中间」的直角顶点更容易计算。
设第 i 行有 rows[i] 个 1第 j 列有 cols[j] 个 1。根据乘法原理直角顶点为 (i,j) 的直角三角形有 (rows[i] - 1) * (cols[j] - 1) 个加到答案中。
代码
/** lc appleetcode.cn id3128 langcpp** [3128] 直角三角形*/// lc codestart
class Solution
{
public:long long numberOfRightTriangles(vectorvectorint grid){int m grid.size(), n m ? grid[0].size() : 0;// 每行 1 的个数vectorint rows(m, 0);for (int i 0; i m; i){int row 0;for (int j 0; j n; j)row grid[i][j];rows[i] row;}// 每列 1 的个数vectorint cols(n, 0);for (int j 0; j n; j){int col 0;for (int i 0; i m; i)col grid[i][j];cols[j] col;}long long ans 0LL;for (int i 0; i m; i)for (int j 0; j n; j)if (grid[i][j] 1){// 直角顶点为 (i,j) 的直角三角形有 (rows[i] - 1) * (cols[j] - 1) 个ans (rows[i] - 1) * (cols[j] - 1);}return ans;}
};
// lc codeend复杂度分析
时间复杂度O(m*n)其中 m 和 n 分别是矩阵 grid 的行数和列数。
空间复杂度O(mn)其中 m 和 n 分别是矩阵 grid 的行数和列数。
题目33129. 找出所有稳定的二进制数组 I
思路
记忆化搜索。
dfs(i, j, count) 表示还剩 i 个 0j 个 1已经连用 count 个 i 对应的数字的组合数。
边界dfs(0, 0, count) 1。
转移为
当 count limit 时换另一个数字开始计数 dfs(j-1, i, 1)当 count limit 时为 dfs(i-1, j, count1) dfs(j-1, i, 1)
入口dfs(zero, one, 0)。
代码
/** lc appleetcode.cn id3129 langcpp** [3129] 找出所有稳定的二进制数组 I*/// lc codestart
class Solution
{
private:const int MOD 1e9 7;public:int numberOfStableArrays(int zero, int one, int limit){int mx max(zero, one);int memo[mx 1][mx 1][limit 1];memset(memo, -1, sizeof(memo));// 还剩 i 个 0j 个 1已经连续使用了 count 个 i 对应的数字functionint(int, int, int) dfs [](int i, int j, int count) - int{if (i 0 || j 0)return 0;if (i 0 j 0)return 1;int res memo[i][j][count];if (res ! -1)return res;if (count limit){// 换另一个数字开始计数res dfs(j - 1, i, 1) % MOD;}else{// 两种都可以res (dfs(i - 1, j, count 1) dfs(j - 1, i, 1)) % MOD;}return res;};return dfs(zero, one, 0);}
};
// lc codeend复杂度分析
时间复杂度O(zero*one*limit)。
空间复杂度O(mx2*limit)其中 mx max(zero, one)。
题目43130. 找出所有稳定的二进制数组 II
思路
题解两种方法动态规划 / 组合数学Python/Java/C/Go
定义 dfs(i, j, k, limit) 为用 i 个 0j 个 1 构造稳定数组的方案数其中第 ij 个位置要填 k其中 k 为 0 或 1。 边界 入口dfs(zero, one, 0, limit) dfs(zero, one, 1, limit)。
代码
/** lc appleetcode.cn id3130 langcpp** [3130] 找出所有稳定的二进制数组 II*/// lc codestart
class Solution
{
private:const int MOD 1e9 7;public:int numberOfStableArrays(int zero, int one, int limit){int memo[zero 1][one 1][2];memset(memo, -1, sizeof(memo));// 用 i 个 0j 个 1 构造稳定数组的方案数其中第 ij 个位置要填 kfunctionint(int, int, int, int) dfs [](int i, int j, int k, int limit) - int{if (i 0){ // 递归边界return k 1 j limit;}if (j 0){ // 递归边界return k 0 i limit;}int res memo[i][j][k];if (res ! -1)return res;if (k 0){res ((long long)dfs(i - 1, j, 0, limit) dfs(i - 1, j, 1, limit) (i limit ? MOD - dfs(i - limit - 1, j, 1, limit) : 0)) %MOD;}else{res ((long long)dfs(i, j - 1, 0, limit) dfs(i, j - 1, 1, limit) (j limit ? MOD - dfs(i, j - limit - 1, 0, limit) : 0)) %MOD;}return res;};return (dfs(zero, one, 0, limit) dfs(zero, one, 1, limit)) % MOD;}
};
// lc codeend复杂度分析
时间复杂度O(zero*one)。
空间复杂度O(zero*one)。
