【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
。
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 mainfunc 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
代表1
,B
代表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) if not sol.canMakeSquare(grid): cannot.append(code)print (cannot)
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