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-21Python编程基础教程
- 2024-11-20Python编程基础与实践
- 2024-11-20Python编程基础与高级应用
- 2024-11-19Python 基础编程教程
- 2024-11-19Python基础入门教程
- 2024-11-17在FastAPI项目中添加一个生产级别的数据库——本地环境搭建指南
- 2024-11-16`PyMuPDF4LLM`:提取PDF数据的神器
- 2024-11-16四种数据科学Web界面框架快速对比:Rio、Reflex、Streamlit和Plotly Dash
- 2024-11-14获取参数学习:Python编程入门教程
- 2024-11-14Python编程基础入门