目录
一，3127. 构造相同颜色的正方形
二，3128. 直角三角形
三，3129. 找出所有稳定的二进制数组 I
编辑
四，3130. 找出所有稳定的二进制数组 II
一，3127. 构造相同颜色的正方形
本题就是问在一个3x3的正方形中是否存在一个2x2的正方形，其中存在大于等于3个白色或黑色的格子，如果有，返回true，没有，返回false。
代码如下：
class Solution {
public boolean canMakeSquare(char[][] grid) {
return isValid(grid,0,0) || isValid(grid,0,1) || isValid(grid,1,0) || isValid(grid,1,1);
}
boolean isValid(char[][] grid, int i, int j){
int cnt = 0;
if(grid[i][j]=='W')
cnt++;
if(grid[i][j+1]=='W')
cnt++;
if(grid[i+1][j]=='W')
cnt++;
if(grid[i+1][j+1]=='W')
cnt++;
return cnt>=3 || cnt<=1;
}
}二，3128. 直角三角形
本题求直角三角形的个数，注意这题直角三角形的定义：只要A与B在同一行，且B与C在同一列，它就是一个直角三角形。
思路：需要枚举B所在的位置，计算出B所在行和B所在列中1的个数（row，col），然后相乘，再把其加入到答案中，注意这里B不能算在行和列中，所以是（row-1）*（col-1）。又因为每次都要使用行列中1的个数，所以可以提前使用数组预处理一下。
代码如下：
class Solution {
public long numberOfRightTriangles(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[] row = new int[n];//每一行有几个1
int[] col = new int[m];//每一列有几个1
//预处理出每行每列1的个数
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
row[i] += grid[i][j];
col[j] += grid[i][j];
}
}
long ans = 0;
//枚举B的位置
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 1){
ans += (row[i]-1)*(col[j]-1);
}
}
}
return ans;
}
}三，3129. 找出所有稳定的二进制数组 I
本题直接想到的做法是dfs枚举选哪个，枚举每一个位置选择的是0还是1，题目还要求连续的数不能超过limit，并且如果需要知道是否是连续的，还需要知道前一个数选的是0/1。
定义dfs(z，o，pre，cnt)：剩余z个0，o个1，前一个数为pre，且同样的数连续出现了cnt次的合法方案数。
- 当z>0时，当前数可以选0，它可以由 dfs(z-1，o，0，0==pre?cnt+1:limit) 转移过来
- 当o>0时，当前数可以选1，它可以由 dfs(z，o-1，1，1==pre?cnt+1:limit) 转移过来
- 终止条件：cnt==limit，return 0；o+z==0 即它是一个合法数，return 1
注：该方法如果使用哈希记忆化会超时，只能使用memo[][][][]来记忆化
代码如下：
class Solution {
int limit;
int MOD = (int)1e9+7;
int[][][][] memo;
public int numberOfStableArrays(int zero, int one, int limit) {
this.limit = limit;
memo = new int[zero+1][one+1][3][limit+1];
for(int i=0; i<zero+1; i++){
for(int j=0; j<one+1; j++){
for(int k=0; k<3; k++){
Arrays.fill(memo[i][j][k],-1);
}
}
}
return dfs(0, 2, zero, one);
}
int dfs(int cnt, int pre, int z, int o){
if(cnt == limit) return 0;
if(o+z==0){
return 1;
}
if(memo[z][o][pre][cnt]!=-1) return memo[z][o][pre][cnt];
int res = 0;
if(z > 0)
res = (res+dfs(pre==0?cnt+1:0, 0, z-1, o))%MOD;
if(o > 0)
res = (res + dfs(pre==1?cnt+1:0, 1, z, o-1))%MOD;
memo[z][o][pre][cnt] = res%MOD;
return res%MOD;
}
}四，3130. 找出所有稳定的二进制数组 II
本题和上一题一样，但是数据范围变大了，所以上述的方法不能在此使用，会超时。
重新定义一个dfs(i，j，k)：i个0，j个1，且第i+j个数为k的合法方案数
- 当 k = 0 时，我们要求的就变成了，i-1个0，j个1，且第i-1+j个数为0/1的合法方案数，即 dfs(i，j，0) = dfs(i-1，j，0) + dfs(i-1，j，1)，但是dfs(i-1，j，0)中包含了最后连续limit个位置填0的方案，如果在这个方案末尾在加一个0，就有连续limit+1个0，这对于dfs(i，j，0)是不合法的，所以要减去 dfs(i-limit-1，j，1)，即 dfs(i，j，0) = dfs(i-1，j，0) + dfs(i-1，j，1) - dfs(i-limit-1，j，1)
- 当 k = 1 时，同理：dfs(i，j，1) = dfs(i，j-1，0) + dfs(i，j-1，1) - dfs(i，j-limit-1，0)
代码如下：
class Solution {
int limit;
int MOD = (int)1e9+7;
int[][][] memo;
public int numberOfStableArrays(int zero, int one, int limit) {
this.limit = limit;
memo = new int[zero+1][one+1][2];
for(int i=0; i<zero+1; i++){
for(int j=0; j<one+1; j++){
Arrays.fill(memo[i][j],-1);
}
}
return (dfs(zero, one, 0)+dfs(zero, one, 1))%MOD;
}
int dfs(int z, int o, int k){
if(z == 0)
return k==1 && limit>=o ? 1 : 0;
if(o == 0)
return k==0 && limit>=z ? 1 : 0;
if(memo[z][o][k]!=-1) return memo[z][o][k];
if(k == 0)
memo[z][o][k] = (int)(((long)dfs(z-1, o, 1) + dfs(z-1, o, 0) + (z>limit ? MOD-dfs(z-limit-1, o, 1) : 0))%MOD);
else
memo[z][o][k] = (int)(((long)dfs(z, o-1, 1) + dfs(z, o-1, 0) + (o>limit ? MOD-dfs(z, o-limit-1, 0) : 0))%MOD);
return memo[z][o][k];
}
}
