当前位置:网站首页>[leetcode] 200 number of islands
[leetcode] 200 number of islands
2022-07-02 15:36:00 【Crisp ~】
Here you are ‘1’( land ) and ‘0’( water ) A two-dimensional mesh of , Please calculate the number of islands in the grid .
Islands are always surrounded by water , And each island can only be combined by horizontal direction / Or a vertical connection between adjacent lands .
Besides , You can assume that all four sides of the mesh are surrounded by water .
Example 1:
Input :
grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
Output : 1
Example 2:
Input : grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
Output : 3
Tips :
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] The value of is ‘0’ or ‘1’
notes :
In case of 1 Immediately set as 0, Don't wait from the queue or Take it out of the stack and set it to 0, It will cause a large number of coordinate points to be repeated into the team or Push , Make the time exceed the limit !!!
## Breadth first traversal
class Solution(object):
def numIslands(self, grid):
n = len(grid)# Get array length
if n == 0:
return 0
m = len(grid[0])# Get array width
cnt = 0# Number of Islands
queue = []# Queue container
for i in range(n):
for j in range(m):
if grid[i][j] == "1":# If you meet land, start traversing
cnt+=1# The number of islands plus one
grid[i][j]="0"# Set as 0, Avoid repeated visits to
queue.append((i,j))# Join the queue , To traverse the
while queue:
x,y = queue[0]
queue.pop(0)
for xx,yy in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:# Traverse in four directions
if 0<=xx<n and 0<=yy<m and grid[xx][yy]=="1":
grid[xx][yy]="0"
queue.append((xx,yy))
return cnt
## Depth-first traversal
class Solution(object):
def numIslands(self, grid):
n = len(grid)
if n == 0:
return 0
m = len(grid[0])
cnt = 0
stack = []
for i in range(n):
for j in range(m):
if grid[i][j] == "1":
cnt+=1
grid[i][j]="0"
stack.insert(0,(i,j))
while stack:
x,y = stack[0]
stack.pop(0)
for xx,yy in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if 0<=xx<n and 0<=yy<m and grid[xx][yy]=="1":
grid[xx][yy]="0"
stack.insert(0,(xx,yy))
return cnt
边栏推荐
猜你喜欢
19_Redis_宕机后手动配置主机
Semantic segmentation learning notes (1)
PTA 天梯赛习题集 L2-001 城市间紧急救援
终于搞懂了JS中的事件循环,同步/异步,微任务/宏任务,运行机制(附笔试题)
Leetcode skimming - remove duplicate letters 316 medium
Leetcode skimming -- count the number of numbers with different numbers 357 medium
10_Redis_geospatial_命令
04_ 栈
Let your HMI have more advantages. Fet-g2ld-c core board is a good choice
LeetCode刷题——两整数之和#371#Medium
随机推荐
Tidb data migration scenario overview
Pytoch saves tensor to Mat file
自定义异常
How to find a sense of career direction
Practice of compiling principle course -- implementing an interpreter or compiler of elementary function operation language
Data analysis thinking analysis methods and business knowledge - business indicators
高考录取分数线爬虫
Leetcode question brushing - parity linked list 328 medium
Yolo format data set processing (XML to txt)
工程师评测 | RK3568开发板上手测试
02. After containerization, you must face golang
[network security] network asset collection
Deploy tidb cluster with tiup
LeetCode刷题——验证二叉树的前序序列化#331#Medium
07_ Hash
Leetcode skimming -- incremental ternary subsequence 334 medium
Bing. Site Internet
11_ Redis_ Hyperloglog_ command
How to solve the problem of database content output
Download blender on Alibaba cloud image station