Re: [閒聊] 每日leetcode
看板Marginalman作者sustainer123 (caster )時間2周前 (2024/04/19 10:31)推噓3(3推 0噓 1→)留言4則, 4人參與討論串134/181 (看更多)
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/number-of-islands/description
: 200. Number of Islands
: 給你一個二維陣列 1 表示陸地 0 表示海水，相連的陸地是一的島嶼，求出有幾個島。
: 思路：
: 1.找到 grid[i][j] == 1 的格子就把島嶼數量+1，並以該點為中心 dfs 附近相鄰的陸地
: 標記為已經走過。
: 2.返回島嶼數量。
: py code：
: ------------------------------------------------
: class Solution:
: def numIslands(self, grid: List[List[str]]) -> int:
: res = 0
: m, n = len(grid), len(grid[0])
: for i in range(m):
: for j in range(n):
: if grid[i][j] == '1':
: self.dfs(grid, i, j)
: res += 1
: return res
: def dfs(self, grid: List[List[str]], y: int, x: int):
: m, n = len(grid), len(grid[0])
: if y < 0 or y == m or x < 0 or x == n or grid[y][x] != '1':
: return
: grid[y][x] = '-1'
: self.dfs(grid, y + 1, x)
: self.dfs(grid, y - 1, x)
: self.dfs(grid, y, x + 1)
: self.dfs(grid, y, x - 1)
: ------------------------------------------------
思路:
跟昨天差不多 dfs收工
Python Code:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(x,y):
dx = [1,-1,0,0]
dy = [0,0,1,-1]
visited.add((x,y))
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
if new_x>=0 and new_x<n and new_y>=0 and new_y<m:
if grid[new_y][new_x] == "1":
if(new_x,new_y) not in visited:
dfs(new_x,new_y)
visited = set()
m,n = len(grid),len(grid[0])
result = 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1" and ((j,i)) not in visited:
result += 1
dfs(j,i)
return result
感覺改值比多搞個visited方便
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.137.148 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713493883.A.325.html
推
04/19 10:31,
2周前
, 1F
04/19 10:31, 1F
→
04/19 10:34,
2周前
, 2F
04/19 10:34, 2F
推
04/19 10:35,
2周前
, 3F
04/19 10:35, 3F
推
04/19 10:37,
2周前
, 4F
04/19 10:37, 4F
討論串 (同標題文章)
