本文主要是介绍LeetCode - 129双周赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一,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];//每一行有几个1int[] 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);elsememo[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];}
}
这篇关于LeetCode - 129双周赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!