class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
}
};
3127. 构造相同颜色的正方形
给你一个二维 3 x 3 的矩阵 grid ，每个格子都是一个字符，要么是 'B' ，要么是 'W' 。字符 'W' 表示白色，字符 'B' 表示黑色。
你的任务是改变 至多一个 格子的颜色，使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。
如果可以得到一个相同颜色的 2 x 2 正方形，那么返回 true ，否则返回 false 。
示例 1：
输入：grid = [["B","W","B"],["B","W","W"],["B","W","B"]]
输出：true
解释：
修改 grid[0][2] 的颜色，可以满足要求。
示例 2：
输入：grid = [["B","W","B"],["W","B","W"],["B","W","B"]]
输出：false
解释：
只改变一个格子颜色无法满足要求。
示例 3：
输入：grid = [["B","W","B"],["B","W","W"],["B","W","W"]]
输出：true
解释：
grid 已经包含一个 2 x 2 颜色相同的正方形了。
提示：
grid.length == 3grid[i].length == 3grid[i][j] 要么是 'W' ，要么是 'B' 。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-05-01 10:40:37
func canMakeSquare(grid [][]byte) bool {
check := func(i, j int) bool {
cnt := [2]int{}
cnt[grid[i][j]&1]++
cnt[grid[i][j+1]&1]++
cnt[grid[i+1][j]&1]++
cnt[grid[i+1][j+1]&1]++
return cnt[0] >= 3 || cnt[1] >= 3
}
return check(0, 0) || check(0, 1) || check(1, 0) || check(1, 1)
}
java 解法, 执行用时: 0 ms, 内存消耗: 40.9 MB, 提交时间: 2024-05-01 10:40:02
class Solution {
public boolean canMakeSquare(char[][] grid) {
return check(grid, 0, 0) || check(grid, 0, 1) || check(grid, 1, 0) || check(grid, 1, 1);
}
private boolean check(char[][] grid, int i, int j) {
int[] cnt = new int[2];
cnt[grid[i][j] & 1]++;
cnt[grid[i][j + 1] & 1]++;
cnt[grid[i + 1][j] & 1]++;
cnt[grid[i + 1][j + 1] & 1]++;
return cnt[0] >= 3 || cnt[1] >= 3;
}
}
cpp 解法, 执行用时: 7 ms, 内存消耗: 19.2 MB, 提交时间: 2024-05-01 10:39:47
class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
auto check = [&](int i, int j) {
int cnt[2]{};
cnt[grid[i][j] & 1]++;
cnt[grid[i][j + 1] & 1]++;
cnt[grid[i + 1][j] & 1]++;
cnt[grid[i + 1][j + 1] & 1]++;
return cnt[0] >= 3 || cnt[1] >= 3;
};
return check(0, 0) || check(0, 1) || check(1, 0) || check(1, 1);
}
};
python3 解法, 执行用时: 32 ms, 内存消耗: 16.4 MB, 提交时间: 2024-05-01 10:39:33
'''
遍历矩阵中的每个 2×2 子矩形。
对于每个子矩形，统计 B 和 W 的个数，如果其中一个字母的出现次数 ≥3，则返回 true。
如果四个子矩形都不满足要求，返回 false。
'''
class Solution:
def canMakeSquare(self, grid: List[List[str]]) -> bool:
def check(i: int, j: int) -> bool:
cnt = Counter()
cnt[grid[i][j]] += 1
cnt[grid[i][j + 1]] += 1
cnt[grid[i + 1][j]] += 1
cnt[grid[i + 1][j + 1]] += 1
return cnt['B'] >= 3 or cnt['W'] >= 3
return check(0, 0) or check(0, 1) or check(1, 0) or check(1, 1)