算法练习专栏——leetcode——leetcode129双周赛

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

原题

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

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

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

示例 1：

image-20240427234531713

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

输出：true

解释：

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

示例 2：

image-20240427234540762

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

输出：false

解释：

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

示例 3：

image-20240427234551386

输入：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' 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
    bool canMakeSquare(vector<vector<char>>& grid) {
        // for (int i = 0; i < 3; i++) {
        //     for (int j = 0; j < 3; j++) {
        //         if 
        //     }
        // } 
        int dx[8] = {-1, -1, 0, 1, 1, 1,0, -1},dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
        int B = 0, M = 0;
        if (grid[1][0] == 'B') B++; else M++;
        
        if (grid[0][0] == 'B') B++; else M++;
        
        if (grid[0][1] == 'B') B++; else M++;
        
        if (B == 3 || M == 3) return true;
        else if (B == 2 && grid[1][1] == 'B'){
            return true;
        } else if (M == 2 && grid[1][1] == 'W') {
            return true;
        }
            
        
        B = 0;
        M = 0;
        if (grid[0][1] == 'B') B++; else M++;

        if (grid[0][2] == 'B') B++; else M++;
        
        if (grid[1][2] == 'B') B++; else M++;
                
        if (B == 3 || M == 3) return true;
        else if (B == 2 && grid[1][1] == 'B'){
            return true;
        } else if (M == 2 && grid[1][1] == 'W') {
            return true;
        }
            
            
        
        B = 0;
        M = 0;
        
        if (grid[1][2] == 'B') B++; else M++;
        
        if (grid[2][2] == 'B') B++; else M++;
        
        if (grid[2][1] == 'B') B++; else M++;
                
        if (B == 3 || M == 3) return true;
        else if (B == 2 && grid[1][1] == 'B'){
            return true;
        } else if (M == 2 && grid[1][1] == 'W') {
            return true;
        }
            
            
        
        B = 0;
        M = 0;
        
        if (grid[2][1] == 'B') B++; else M++;
            
        if (grid[2][0] == 'B') B++; else M++;
        
        if (grid[1][0] == 'B') B++; else M++;
        
        if (B == 3 || M == 3) return true;
        else if (B == 2 && grid[1][1] == 'B'){
            return true;
        } else if (M == 2 && grid[1][1] == 'W') {
            return true;
        }
            
            
        
        return false;
    }
};

100278.直角三角形

给你一个二维 boolean 矩阵 grid 。

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

注意：

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

示例 1：

0 1 0
0 1 1
0 1 0
0 1 0
0 1 1
0 1 0

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

输出：2

解释：

有 2 个直角三角形。

示例 2：

1 0 0 0
0 1 0 1
1 0 0 0

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

输出：0

解释：

没有直角三角形。

示例 3：

1 0 1
1 0 0
1 0 0
1 0 1
1 0 0
1 0 0

输入：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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
        int n = grid.size(), m = grid[0].size();
        long long cols[m + 10], rows[n + 10];
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            rows[i] = 0;
        }
        
        for (int j = 0; j < m; j++) {
            cols[j] = 0;
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    cols[j]++;
                    rows[i]++;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    ans += (cols[j] - 1) * (rows[i] - 1);
                }
            }
        }
        return ans;
    }
};

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

思路

​ 与下面一题一致。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        int mod = 1e9 + 7;
        vector dp(zero + 1 + one, vector(one + 1, vector(2, 0ll)));
        dp[0][0][0] = 1, dp[0][0][1] = 1;
        dp[1][1][1] = 1, dp[1][0][0] = 1;
        limit++;
        for(int i = 2; i <= zero + one; ++i)
        {
            for(int j = 0; j <= one && j <= i; ++j)
            {
                dp[i][j][0]=(dp[i - 1][j][0] + dp[i - 1][j][1])%mod;
                
                if(j)
                dp[i][j][1]=(dp[i - 1][j - 1][1] + dp[i - 1][j - 1][0])%mod;
                if(j >= limit)
                dp[i][j][1] = (dp[i][j][1] - dp[i - limit][j - limit][0] + mod)%mod;
                if(i - j>= limit)
                dp[i][j][0] = (dp[i][j][0] - dp[i - limit][j][1] + mod)%mod;
                // if(i == limit)
                // dp[i][j][0] = (dp[i][j][0] -  + mod)%mod;
                // cout<<dp[i][j][0]<<' '<<dp[i][j][1]<<' '<<i<<' '<<j<<endl;
            }
        }
        return (dp[one + zero][one][0] + dp[one + zero][one][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/problems/find-all-possible-stable-binary-arrays-ii/solutions/2758672/dong-tai-gui-hua-mei-ju-shu-zu-mo-wei-li-x45n/

image-20240428004241728

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int f[1005][1005][2] = {0};
class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int mod = 1e9 + 7;
        
        for(int i = 0; i <= zero; ++i)
            f[i][0][0] = (i <= limit), f[i][0][1] = 0;
        for(int j = 0; j <= one; ++j) 
            f[0][j][0] = 0, f[0][j][1] = (j <= limit);
        
        int sum1[one + 1];
        for(int j = 0; j <= one; ++j) sum1[j] = f[0][j][1];
        
        for(int i = 1; i <= zero; ++i) {
            for(int j = 1, sum0 = f[i][0][0]; j <= one; ++j) {
                f[i][j][0] = sum1[j];
                f[i][j][1] = sum0;
                
                sum0 = (sum0 + f[i][j][0]) % mod;
                if(j - limit >= 0) 
                    sum0 = (sum0 + mod - f[i][j-limit][0]) % mod;
                
                sum1[j] = (sum1[j] + f[i][j][1]) % mod;
                if(i - limit >= 0) 
                    sum1[j] = (sum1[j] + mod - f[i-limit][j][1]) % mod;
            }
        }
        
        return (f[zero][one][0] + f[zero][one][1]) % mod;
    }
};