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

【LetMeFly】3127.构造相同颜色的正方形:打表瘾犯了

力扣题目链接:https://leetcode.cn/problems/make-a-square-with-the-same-color/

给你一个二维 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 == 3
  • grid[i].length == 3
  • grid[i][j] 要么是 'W' ,要么是 'B'

解题方法一:正常枚举

枚举每一个四方块的右下角,统计这个四方块中有多少个W。只要W的个数不是2,就能直接返回true。原因如下:

  • W = 0,则全黑
  • W = 1,则1白,1次修改可变成全黑
  • W = 3,则1黑,1次修改可变成全白
  • W = 4,则全白

如果枚举完了所有的四方块,则返回false

  • 时间复杂度$O(1)$
  • 空间复杂度$O(1)$

AC代码

写代码的时候忘记看数据范围了,写完了才发现一定是3x3。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
bool canMakeSquare(vector<vector<char>>& grid) {
for (int i = 1; i < grid.size(); i++) {
for (int j = 1; j < grid.size(); j++) {
if ((grid[i][j] == 'W') + (grid[i - 1][j] == 'W') + (grid[i][j - 1] == 'W') + (grid[i - 1][j - 1] == 'W') != 2) {
return true;
}
}
}
return false;
}
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

func canMakeSquare(grid [][]byte) bool {
for i := 1; i < len(grid); i++ {
for j := 1; j < len(grid[0]); j++ {
cntW := 0
for x := -1; x < 1; x++ {
for y := -1; y < 1; y++ {
if grid[i + x][j + y] == 'W' {
cntW++
}
}
}
if cntW != 2 {
return true
}
}
}
return false
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean canMakeSquare(char[][] grid) {
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[0].length; j++) {
int cntW = 0;
for (int x = -1; x < 1; x++) {
for (int y = -1; y < 1; y++) {
if (grid[i + x][j + y] == 'W') {
cntW++;
}
}
}
if (cntW != 2) {
return true;
}
}
}
return false;
}
}

Python

1
2
3
4
5
6
7
8
9
from typing import List

class Solution:
def canMakeSquare(self, grid: List[List[str]]) -> bool:
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
if (grid[i][j] == 'W') + (grid[i - 1][j] == 'W') + (grid[i][j - 1] == 'W') + (grid[i - 1][j - 1] == 'W') != 2:
return True
return False

解题方法二:打表

做完后发现表格大小固定为3x3,然而方法一写成了mxn。怎么办?只把len(grid)和len(grid[0])改成3然后再提交一次?好像意义不大。

既然3x3的表格最多有$2^{3\times3}=512$种情况,因此来个痛快的打表吧。

由于方法一中,W(范围0-4)只有为2这一种情况时不可行,因此不可行的情况比较少。所以决定打表枚举不可行的情况。

如何将表格和整数互相转换?grid[i][j]对应整数二进制下的低i * 3 + j位即可。W代表1B代表0,完美。

  • 时间复杂度$O(1)$,一共有14种返回false的情况,可视为常数1
  • 空间复杂度$O(1)$

AC代码

Python:打表求不可行的有哪些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from typing import List

class Solution:
def canMakeSquare(self, grid: List[List[str]]) -> bool:
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
if (grid[i][j] == 'W') + (grid[i - 1][j] == 'W') + (grid[i][j - 1] == 'W') + (grid[i - 1][j - 1] == 'W') != 2:
return True
return False

cannot = []
sol = Solution()
for code in range(1 << 9):
grid = [['W' if (code & (1 << (i * 3 + j))) else 'B' for j in range(3)] for i in range(3)]
if grid == [['B', 'W', 'B'], ['W', 'B', 'W'], ['B', 'W', 'B']]:
print(code)
# print(grid)
if not sol.canMakeSquare(grid):
cannot.append(code)
print(cannot)

# [56, 113, 146, 149, 170, 173, 227, 284, 338, 341, 362, 365, 398, 455]

Python:由表差答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from typing import List

cannot = [56, 113, 146, 149, 170, 173, 227, 284, 338, 341, 362, 365, 398, 455]

class Solution:
def grid2code(self, grid: List[List[str]]) -> int:
ans = 0
for i in range(3):
for j in range(3):
if grid[i][j] == 'W':
ans |= (1 << (i * 3 + j))
return ans

def canMakeSquare(self, grid: List[List[str]]) -> bool:
return self.grid2code(grid) not in cannot

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

Tisfy:https://letmefly.blog.csdn.net/article/details/141756605


3127.构造相同颜色的正方形
https://blog.letmefly.xyz/2024/08/31/LeetCode 3127.构造相同颜色的正方形/
作者
Tisfy
发布于
2024年8月31日
许可协议