题目列表
一、构造相同颜色的正方形
这题直接暴力就行，代码如下
class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
// 枚举2x2正方形的左上角
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
int cnt = (grid[i][j]=='W') + (grid[i+1][j]=='W') + (grid[i][j+1]=='W') + (grid[i+1][j+1]=='W');
if(cnt<=1||cnt>=3) return true;
}
}
return false;
}
};二、直角三角形
这题数直角三角形的个数，只要得到数学公式，一切就迎刃而解了。
如何算出直角三角形的个数呢？我们枚举直角三角形的直角，这样的点能构成的直角三角形的个数为 上*左 + 上*右 +下*左 + 下*右 = 上*( 左 + 右 ) + 下*( 左 + 右 ) = ( 上 + 下 )*( 左 + 右 )，其中上下左右分别代表各个方向上1的个数，即(该点所在行中1的个数-1) * (该点所在列中1的个数 - 1)
显然是要提前处理得到每一行的1的个数和每一列的1的个数，代码如下
class Solution {
public:
long long numberOfRightTriangles(vector<vector<int>>& grid) {
long long ans = 0;
int n = grid.size(), m = grid[0].size();
vector<int> col(m),row(n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
row[i]+=grid[i][j];
col[j]+=grid[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j])
ans += (row[i]-1)*(col[j]-1);
}
}
return ans;
}
};三、找出所有稳定的二进制数组I&II
题目要求：给定one个1和zero个0，共能将它们排列组合成多少个不同的数组，其中不能出现连续大于limit个0/1。
求方案数这种题目如果没啥其他想法的话，一般都是动态规划问题。这里我们先来考虑用记忆化搜索解决，后续在转成递推。
那么递归的参数如何设计？首先我们肯定需要知道0的个数i和1的个数j，但是这还不够，我们还需要考虑不能出现连续的limit个0/1的情况。这里我们添加一个参数k用来表示当前位置填的数。
故递归函数为dfs(i，j，k)表示用i个0，j个1组成的合法方案数个数，其中第i+j个位置填k
递归转移方程为
- 当k==0时，dfs(i，j，0) = dfs(i-1，j，0) + dfs(i-1，j，1) - dfs(i-1-limit，j，1)
- 当k==1时，dfs(i，j，1) = dfs(i，j-1，0) + dfs(i，j-1，1) - dfs(i，j-1-limit，1)
相信大家对上面的转移方程或多或少会感到一些困惑，下面来解释一下
代码如下
class Solution {
const int MOD = 1e9+7;
public:
int numberOfStableArrays(int zero, int one, int limit) {
long long memo[zero+1][one+1][2];
memset(memo,-1,sizeof(memo));
function<long long(int,int,int)>dfs=[&](int i,int j,int k)->long long{
if(i<0||j<0) return 0; // 方案不合法返回0
// 如果没有0了，前面一个数必然是0，后面必然全填1，1的个数<=limit
if(i==0) return k==1&&j<=limit;
// 如果没有1了，前面一个数必然是1，后面必然全填0，0的个数<=limit
if(j==0) return k==0&&i<=limit;
if(memo[i][j][k]!=-1) return memo[i][j][k];
if(k==0) return memo[i][j][k]=((long long)dfs(i-1,j,1)+dfs(i-1,j,0)-dfs(i-limit-1,j,1)+MOD)%MOD; // 防止溢出
else return memo[i][j][k]=((long long)dfs(i,j-1,1)+dfs(i,j-1,0)-dfs(i,j-limit-1,0)+MOD)%MOD; //防止溢出
};
return (dfs(zero,one,1)+dfs(zero,one,0))%MOD;
}
};
class Solution {
const int MOD = 1e9+7;
public:
int numberOfStableArrays(int zero, int one, int limit) {
long long f[zero+1][one+1][2];
memset(f,0,sizeof(f));
for(int i=0;i<=limit;i++){
f[0][min(i,one)][1] = f[min(i,zero)][0][0] = 1;
}
for(int i=1;i<=zero;i++){
for(int j=1;j<=one;j++){
f[i][j][0]=(f[i-1][j][1]+f[i-1][j][0]+(i-limit-1>=0?MOD-f[i-limit-1][j][1]:0))%MOD;
f[i][j][1]=(f[i][j-1][0]+f[i][j-1][1]+(j-limit-1>=0?MOD-f[i][j-limit-1][0]:0))%MOD;
}
}
return (f[zero][one][0]+f[zero][one][1])%MOD;
}
};