LeetCode 题解工作台
构造相同颜色的正方形
给你一个二维 3 x 3 的矩阵 grid ，每个格子都是一个字符，要么是 'B' ，要么是 'W' 。字符 'W' 表示白色，字符 'B' 表示黑色。 你的任务是改变 至多一个 格子的颜色，使得矩阵中存在一个 2 x 2 颜色完全相同的正方形。 如果可以得到一个相同颜色的 2 x 2 正方形，那么…
3
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·matrix
答案摘要
我们可以枚举每个 $2 \times 2$ 的正方形，统计黑色和白色的个数，如果两者个数不相等，那么就可以构造一个相同颜色的正方形，返回 `true`。 否则，遍历结束后返回 `false`。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个二维 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'。
解题思路
方法一：枚举
我们可以枚举每个 的正方形，统计黑色和白色的个数，如果两者个数不相等，那么就可以构造一个相同颜色的正方形，返回 true。
否则，遍历结束后返回 false。
时间复杂度 ，空间复杂度 。
class Solution:
def canMakeSquare(self, grid: List[List[str]]) -> bool:
for i in range(0, 2):
for j in range(0, 2):
cnt1 = cnt2 = 0
for a, b in pairwise((0, 0, 1, 1, 0)):
x, y = i + a, j + b
cnt1 += grid[x][y] == "W"
cnt2 += grid[x][y] == "B"
if cnt1 != cnt2:
return True
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(1) because the grid is always 3x3 and only four 2x2 squares exist. Space complexity is O(1) since no extra data structures proportional to input size are used. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks your ability to enumerate submatrices efficiently.
- question_mark
Tests pattern recognition in small fixed-size matrices.
- question_mark
Looks for handling edge cases where a single change is insufficient.
常见陷阱
外企场景- error
Forgetting to check all four 2x2 submatrices in the 3x3 grid.
- error
Failing to count differing cells correctly within each square.
- error
Returning true when two or more cells differ in a 2x2 square.
进阶变体
外企场景- arrow_right_alt
Consider larger NxN grids where you want to form KxK squares of the same color.
- arrow_right_alt
Allow changing more than one cell and check minimal changes required to form a uniform square.
- arrow_right_alt
Modify the problem to count how many distinct 2x2 uniform squares can be formed after at most one change.