有一个leetcode问题是：
给定一个 m x n 二进制矩阵网格。岛屿是一组 4 方向（水平或垂直）连接的 1（代表陆地）。您可以假设网格的所有四个边缘都被水包围。
如果一个岛屿具有相同的形状，或者在旋转（仅限 90、180 或 270 度）或反射（左/右方向或上/下方向）后具有相同的形状，则认为它们是相同的。
返回不同岛屿的数量。
我想出了一个解决方案，它通过了 510 个测试用例中的 508 个。我相信我的解决方案应该有效，但不确定我到底错过了什么，并且想知道是否有人可以添加一些见解或修复我的代码？
以下是我的解决方案：
def numDistinctIslands2(self, grid: List[List[int]]) -> int:
islands = []
visited = set()
def dfs(i, j, curr_island): # standard dfs to find all islands
if (
0 <= i < len(grid)
and 0 <= j < len(grid[0])
and grid[i][j] == 1
and (i, j) not in visited
):
visited.add((i, j))
curr_island.append((i, j))
dfs(i + 1, j, curr_island)
dfs(i - 1, j, curr_island)
dfs(i, j + 1, curr_island)
dfs(i, j - 1, curr_island)
for i in range(len(grid)): # loop over the entire grid
for j in range(len(grid[0])):
if grid[i][j] == 1 and (i, j) not in visited:
curr_island = []
dfs(i, j, curr_island)
islands.append(curr_island)
distinct_islands = set() # keep the representative of all similar islands
def get_distinct_islands(islands):
for island in islands:
island_signature_x = defaultdict(int) # x(row) signature of island
island_signature_y = defaultdict(int) # y(col) signature of island
for x, y in island:
# calculate x signature (number of "1" in each row of the island)
island_signature_x[x] += 1
# calculate y signature (number of "1" in each column of the island)
island_signature_y[y] += 1
x_val = []
# loop through sorted (we need to have the orders intact) signature of rows # ex. [1, 2, 1] is different than [1, 1, 2]
for k, v in sorted(island_signature_x.items(), key=lambda i: i[0]):
x_val.append(str(v))
x_sign = ".".join(x_val) # string of x signature
x_sign_r = ".".join(x_val[::-1]) # reverse string of x signature
y_val = []
# loop through sorted (we need to have the orders intact) signature of columns
for k, v in sorted(island_signature_y.items(), key=lambda i: i[0]):
y_val.append(str(v))
y_sign = ".".join(y_val) # string of y signature
y_sign_r = ".".join(y_val[::-1]) # reverse string of y signature
# if none of the rotations/reflections (8 possibilities) are registered then register it as a new island
if (
(x_sign, y_sign) not in distinct_islands
and (x_sign, y_sign_r) not in distinct_islands
and (x_sign_r, y_sign) not in distinct_islands
and (x_sign_r, y_sign_r) not in distinct_islands
and (y_sign, x_sign) not in distinct_islands
and (y_sign, x_sign_r) not in distinct_islands
and (y_sign_r, x_sign) not in distinct_islands
and (y_sign_r, x_sign_r) not in distinct_islands
):
distinct_islands.add((x_sign, y_sign))
get_distinct_islands(islands)
return len(distinct_islands)
输入示例如下...我的算法返回 68，它说它应该是 69。这是 510 个测试用例中的第 509 个，之前所有（508）个测试用例都通过了：
[[0,1,0,1,0,1,1,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,1,1,1,0,1,1,1,0,1,0,0,0,1,1,1,1],[0,1,1,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,1,1,0,1,0,0,1,1],[0,0,1,1,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,1,1,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,1,1],[1,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0],[0,0,1,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,1,1,0,1,1],[1,1,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,1,0],[0,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,1,1,1,0,0,1,0,1,1,1,1,1,0,0,0,0,1,0,1,0,1,1,1,1,1,1,0,0,1,1,1,0],[0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0,1,1,1,0,0,0,1,1,0,0,0,0,0,1,1,0,1,0,1,1,1,1,0,1,1,0,0,1,0,1,0,1,1,0],[1,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,0,1,1,0,0,1,0,0,1,1,0,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,0,0,1,1,1,1,0],[1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,1,1,0,0,1,1,1,1,0,0,1,1,0,1,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1],[0,1,1,1,0,0,1,1,1,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1],[0,1,0,0,0,1,1,0,1,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,1],[1,1,0,1,1,1,0,0,1,1,0,1,0,0,0,0,0,0,0,1,0,1,1,0,1,1,0,0,1,0,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,0,1,0,0,1],[0,1,1,0,0,1,1,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1],[0,0,1,0,0,0,0,1,1,1,1,1,0,1,1,0,1,0,1,0,0,1,1,1,0,1,0,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1,0],[0,0,0,1,0,0,0,1,1,0,1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,1,1,1,0,0,1,0,1,0,1,1,0,0,1,1,1,1],[1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,1,1,1,1,0,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,1,1,1,1,0,1,1,0,1,1,0],[1,0,0,1,1,0,0,1,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,0,0,0,1,1,1,0,1,0,1,1,0],[1,0,1,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1],[1,0,0,1,0,1,0,1,0,0,1,0,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,0,1,0,1,1],[1,1,0,0,1,1,1,0,0,0,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,1,1,1,0,0,0,0,1,1,0,1,1,1,1,0,0],[1,0,0,1,1,0,1,0,1,0,0,1,0,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,1,0,0,1,1,0,1,1,1,0,0,1,0,0,0,1],[1,1,1,0,0,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0],[1,0,1,1,1,0,1,0,0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,1,0,0,1,1,1,0,1,1,0,0,1,1,1,0,0,0,1,1,0,0,1],[1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,1,1,0,0,0,0,1,1,0,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0],[1,1,1,0,0,1,0,1,1,0,1,0,0,1,1,1,1,1,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,0,1,0,1,1,1,1,0,1,1,0,1,1,0,0,0,0],[1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0],[1,0,1,1,0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,1],[0,1,1,0,1,1,1,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,1,0,1,1,1,1,1,0,0,1,0,0,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,1],[0,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0],[0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,1,1,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,1,0,1,1,1,0,1,1,0,0],[0,0,1,1,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,0,0,0,0,0,1,0],[1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1],[0,0,0,0,1,0,0,0,1,1,1,0,0,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,1,1,0,1,0,1],[1,0,1,1,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,1,1],[0,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,0,0,1,0,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,0,0],[1,0,0,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,0,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1,1,1,0],[0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,1,1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,1,1],[0,0,0,1,0,1,1,1,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,1,0,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,0,1,1],[0,0,1,0,0,1,1,0,0,1,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,1,0,0,0,1,1,0,1,1,1,0,0,0],[1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,1,1,1,1,0],[0,1,1,1,0,0,1,0,0,0,0,0,1,1,0,0,1,1,0,1,0,0,0,1,0,1,0,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,0],[1,0,1,0,1,1,0,0,0,1,1,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,0,1,0],[1,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,1,1,0,1,1,0,1,0,0,0,1,0,1,1,0,0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0,1,0,0],[1,0,0,1,0,1,0,0,1,0,0,0,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,1,1,0,0,0,1,0,0,0,1,0,0,1],[1,1,0,0,0,1,0,0,0,0,1,1,0,0,0,1,0,1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,1,1,0],[1,1,0,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,0,0],[1,0,0,1,0,1,0,1,0,0,0,1,1,0,0,1,0,1,0,1,0,1,0,1,1,1,0,0,1,1,1,1,1,0,1,0,1,0,0,1,0,0,1,0,1,0,0,0,0,0],[1,0,1,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,0,1,1]]
暂时发布部分答案，这可能会帮助您确定哪个岛屿导致了问题：
修改并插入以下代码：
def numDistinctIslands2(self, grid: List[List[int]]) -> int:
duplicate_chars = set()
char_map = {}
def get_distinct_islands(islands):
for island in islands:
...
signature = (x_sign, y_sign)
if signature not in char_map:
char_map[signature] = chr(ord("!") + len(char_map))
else:
duplicate_chars.add(char_map[signature])
for x, y in island:
grid[x][y] = char_map[signature]
get_distinct_islands(islands)
# Optionally, hide duplicate islands:
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] in duplicate_chars:
grid[i][j] = 0
print("\n".join("".join(x if x != 0 else " " for x in row) for row in grid))
return len(distinct_islands)
所有岛屿：
! " #### $$$$ %% %%%%% &&&& ''' ''' ( ))))
!! ## ### ** %%%% % &&&&&&& '' ''''' (( + ))
!! ### %% % % &&&&& ' ' ( + )))
" ## ## " , % %%%%% &&&& -- . " / (( + )
0 ####### , %%% % & --- ... // ((( ++ ++
000 ### # %% %% && & & - (( (( +++
## # 1111 % %%% / &&&&& 2 2 (((((( +++
33 # ## 1 1 %%% // && " 2222 (( ( + ++
333 # ## 111 1 %% 4 55 & " 22 2 " ++++
3 ## # 1 1111 4444 55 &&& , " " + 6
777 ### 11 1 4 ** , 888 99 6
7 ## # 111 " 4 ::: ; 8 88888 9 " 666
77 ### ## < , == >> : ; 888 8 8 999 " 6
77 ## < ? ::: , === > ;; 88 6
7 <<<<< ?? : " === > " ;; 888 @@@@@
" << < ???? ? " = = " ;;; 8 A AA @@@@
BBB <<<< ?? ???? ===== CC D AAAA @@ @@
B ** < <<< ? ?? ===== CCCCC DD DD AAA @ @@
B " < << E == == CC C D DD @@@@@
B " F < < EEE G === G C CC DDD ** " @ @@
BB FFF < E GG ===== GGG C DDDDD HH @@@@
B FF F " I G GGG == GG D D JJ HHH @ "
BBB " " I GGGGG GG " D J H H " K "
B BBB " II GGGGG GGG GGGG LLL ** HHH KK "
B BB M I GGGG GGG GG LLL , N O K
BBB M MM P GGGGGG GG G G G L , NNNN OO OO
BB Q MMM PP G GGGG GGGGG GGG , NNN OOO RR
B QQ MM " PP ** GG G G G " , " " S RRR
QQ MMMM T P " GGGG GGGGG , " UUUU SSS R
MM TT VV V GG G , W U SSSS
" XX M VV VVV VVV G ** W " / " YYY SS
XX M VVVVVVVVVVV " WWWWWWWW // " "
" X MMM VVV VV V ZZZZZ WWWW [ " \ , ]
" VVV VVVV V ZZ " [ \\\ , ]
" ** VVVV VVVVVV VVV " Z ^^^ [ \\\ " ]]
" VVV V V V V VVV " __ ^ " [[[ ```` \\ a
" VVVV V V VVVVVVVV VV __ ^^ [[ `` aaaa
VVVVV VVVVV VVVV V VV ] _ ^^ YYY b , a a
V VV V VVVVVV " ] _ ^ " " bb " , c aaa
" VVVV " V V ]] " d , bb " ccc aa
" VV VV VVV e d , ff b cc ccc
" g VVVVVVVVVVVV e " h d d " ff " c cccccc
ggg V VV VV e h h dddd d ff cccccccc
i g jj JJ VVVV V hhhh dddd ff cccccc "
ii , j " J V VVVV JJ " h kk d l " c "
i , j " V VV J " / h k d l ll m " "
ii j nn " V // hhh oo llll mmm JJ
ii p jj nnnn ::: oo ll " " mm " J
i p j . nn q q : " ooo ooooo l " " m "
i ppp ... qqqqq " oo oooo " " ** " **
重复岛屿：
"
**
" " , . " /
, ... //
/
// "
" "
, " "
** ,
" ::: "
, : "
::: ,
: " "
" " "
**
"
" ** "
" JJ "
" " " J " "
" ** "
,
,
,
" ** " , " "
" , "
,
" ** " / " YYY
" // " "
" " , ]
" " , ]
" ** " " ]]
" " "
"
] YYY ,
" ] " " " ,
" " ]] " , "
" ,
" " " "
JJ "
, " J JJ " " "
, " J " / " "
" // JJ
::: " " " J
. : " " " "
... " " " ** " **
非重复岛屿：
! #### $$$$ %% %%%%% &&&& ''' ''' ( ))))
!! ## ### %%%% % &&&&&&& '' ''''' (( + ))
!! ### %% % % &&&&& ' ' ( + )))
## ## % %%%%% &&&& -- (( + )
0 ####### %%% % & --- ((( ++ ++
000 ### # %% %% && & & - (( (( +++
## # 1111 % %%% &&&&& 2 2 (((((( +++
33 # ## 1 1 %%% && 2222 (( ( + ++
333 # ## 111 1 %% 4 55 & 22 2 ++++
3 ## # 1 1111 4444 55 &&& + 6
777 ### 11 1 4 888 99 6
7 ## # 111 4 ; 8 88888 9 666
77 ### ## < == >> ; 888 8 8 999 6
77 ## < ? === > ;; 88 6
7 <<<<< ?? === > ;; 888 @@@@@
<< < ???? ? = = ;;; 8 A AA @@@@
BBB <<<< ?? ???? ===== CC D AAAA @@ @@
B < <<< ? ?? ===== CCCCC DD DD AAA @ @@
B < << E == == CC C D DD @@@@@
B F < < EEE G === G C CC DDD @ @@
BB FFF < E GG ===== GGG C DDDDD HH @@@@
B FF F I G GGG == GG D D HHH @
BBB I GGGGG GG D H H K
B BBB II GGGGG GGG GGGG LLL HHH KK
B BB M I GGGG GGG GG LLL N O K
BBB M MM P GGGGGG GG G G G L NNNN OO OO
BB Q MMM PP G GGGG GGGGG GGG NNN OOO RR
B QQ MM PP GG G G G S RRR
QQ MMMM T P GGGG GGGGG UUUU SSS R
MM TT VV V GG G W U SSSS
XX M VV VVV VVV G W SS
XX M VVVVVVVVVVV WWWWWWWW
X MMM VVV VV V ZZZZZ WWWW [ \
VVV VVVV V ZZ [ \\\
VVVV VVVVVV VVV Z ^^^ [ \\\
VVV V V V V VVV __ ^ [[[ ```` \\ a
VVVV V V VVVVVVVV VV __ ^^ [[ `` aaaa
VVVVV VVVVV VVVV V VV _ ^^ b a a
V VV V VVVVVV _ ^ bb c aaa
VVVV V V d bb ccc aa
VV VV VVV e d ff b cc ccc
g VVVVVVVVVVVV e h d d ff c cccccc
ggg V VV VV e h h dddd d ff cccccccc
i g jj VVVV V hhhh dddd ff cccccc
ii j V VVVV h kk d l c
i j V VV h k d l ll m
ii j nn V hhh oo llll mmm
ii p jj nnnn oo ll mm
i p j nn q q ooo ooooo l m
i ppp qqqqq oo oooo
大概某个地方有多余的重复项。