Easy
题目描述
给你一个大小为 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
解释：网格中已经包含一个相同颜色的 2 x 2 正方形。
约束条件：
grid.length == 3grid[i].length == 3grid[i][j]是 ‘W’ 或 ‘B’
提示：
- 当所有正方形中 ‘W’ 或 ‘B’ 的数量为 2 时，无法通过改变至多一个单元格的颜色来创建相同颜色的 2 x 2 正方形。
解题思路
解题思路
这道题要求我们在 3×3 的网格中找到是否能通过改变至多一个单元格，使得存在一个 2×2 的同色正方形。
核心观察： 在一个 3×3 的网格中，总共有 4 个可能的 2×2 正方形：
- 左上角：(0,0), (0,1), (1,0), (1,1)
- 右上角：(0,1), (0,2), (1,1), (1,2)
- 左下角：(1,0), (1,1), (2,0), (2,1)
- 右下角：(1,1), (1,2), (2,1), (2,2)
解法思路：
- 遍历每个 2×2 正方形
- 统计每个正方形中 ‘B’ 和 ‘W’ 的数量
- 判断条件：
- 如果某个正方形已经全是同色（4个相同），直接返回 true
- 如果某个正方形有3个相同颜色，只需改变1个即可，返回 true
- 如果所有正方形都是2:2的情况，则需要改变2个才能达成目标，返回 false
关键insight： 只要存在一个 2×2 区域中同色格子数量≥3，就能通过至多改变一个格子达成目标。
代码实现
class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
// 检查所有可能的2x2正方形
vector<vector<int>> squares = {{0,0}, {0,1}, {1,0}, {1,1}};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
int countB = 0, countW = 0;
// 统计当前2x2正方形中B和W的数量
for (int di = 0; di < 2; di++) {
for (int dj = 0; dj < 2; dj++) {
if (grid[i + di][j + dj] == 'B') {
countB++;
} else {
countW++;
}
}
}
// 如果有3个或4个相同颜色，可以通过改变至多1个格子达成目标
if (countB >= 3 || countW >= 3) {
return true;
}
}
}
return false;
}
};
class Solution:
def canMakeSquare(self, grid: List[List[str]]) -> bool:
# 检查所有可能的2x2正方形
for i in range(2):
for j in range(2):
count_b = 0
count_w = 0
# 统计当前2x2正方形中B和W的数量
for di in range(2):
for dj in range(2):
if grid[i + di][j + dj] == 'B':
count_b += 1
else:
count_w += 1
# 如果有3个或4个相同颜色，可以通过改变至多1个格子达成目标
if count_b >= 3 or count_w >= 3:
return True
return False
public class Solution {
public bool CanMakeSquare(char[][] grid) {
// 检查所有可能的2x2正方形
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
int countB = 0, countW = 0;
// 统计当前2x2正方形中B和W的数量
for (int di = 0; di < 2; di++) {
for (int dj = 0; dj < 2; dj++) {
if (grid[i + di][j + dj] == 'B') {
countB++;
} else {
countW++;
}
}
}
// 如果有3个或4个相同颜色，可以通过改变至多1个格子达成目标
if (countB >= 3 || countW >= 3) {
return true;
}
}
}
return false;
}
}
/**
* @param {character[][]} grid
* @return {boolean}
*/
var canMakeSquare = function(grid) {
for (let i = 0; i < 2; i++) {
for (let j = 0; j < 2; j++) {
let countB = 0;
let countW = 0;
if (grid[i][j] === 'B') countB++;
else countW++;
if (grid[i][j+1] === 'B') countB++;
else countW++;
if (grid[i+1][j] === 'B') countB++;
else countW++;
if (grid[i+1][j+1] === 'B') countB++;
else countW++;
if (countB >= 3 || countW >= 3) {
return true;
}
}
}
return false;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(1) | 固定检查4个2×2正方形，每个正方形检查4个格子，总共16次操作 |
| 空间复杂度 | O(1) | 只使用常数额外空间存储计数变量 |