這題若用迴圈,要如何判定當前遇到的"1"是獨立的島嶼?是否曾經有找過?
使用 memo 去記錄已經搜尋過的"1",並且遇到"1"的時候用遞迴函數再往四周找出所有鄰近的"1"
class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 landNums = 0 memo = set() rows, cols = len(grid), len(grid[0]) def search(y,x): if y == rows or y < 0 or x == cols or x < 0: return if (y,x) in memo: return else: memo.add((y,x)) if grid[y][x] == "1": search(y-1,x) search(y+1,x) search(y,x-1) search(y,x+1) for y in range(rows): for x in range(cols): if (y,x) not in memo and grid[y][x] == "1": search(y,x) landNums += 1 return landNums如果想省點空間,把傳入的二維串列當成 memo 使用也是一種選擇,還能稍微加速。