leetcode 200. 岛屿数量python
2021/11/5 17:10:54
本文主要是介绍leetcode 200. 岛屿数量python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
题解:DFS
是在学习回溯算法的时候遇到的这道题,但其实就是DFS的思想。
本来想通过在回溯的过程中,根据每个节点的周围节点为0和1的数量,判断该节点属于一个之前搜索过的大岛屿还是属于一个新的岛屿,但是好像不太可行。
基本思路:
对输入的grid依次进行搜索,如果遇到一个grid[i][j]=='1',说明该位置对应一个岛屿或者处在一个大岛屿中,岛屿数量加一,对该位置上下左右四个位置进行DFS,将为1的节点全都设为0,避免重复计算。
class Solution(object): def numIslands(self, grid): m = len(grid) n = len(grid[0]) directions = [(0,-1),(0,1),(-1,0),(1,0)] number = 0 def dfs(posx,posy): if 0<=posx<m and 0<=posy<n and grid[posx][posy]=='1': grid[posx][posy]='0' for dx,dy in directions: newx = posx+dx newy = posy+dy dfs(newx,newy) for i in range(m): for j in range(n): if grid[i][j]=='1': number = number+1 dfs(i,j) return number
这篇关于leetcode 200. 岛屿数量python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Python编程基础
- 2024-11-01Python 基础教程
- 2024-11-01用Python探索可解与不可解方程的问题
- 2024-11-01Python编程入门指南
- 2024-11-01Python编程基础知识
- 2024-11-01Python编程基础
- 2024-10-31Python基础入门:理解变量与数据类型
- 2024-10-30Python股票自动化交易资料详解与实战指南
- 2024-10-30Python入行:新手必读的Python编程入门指南
- 2024-10-30Python入行:初学者必备的编程指南