695. Max Area of Island@python
2024-09-30 10:35:18
Given a non-empty 2D array grid
of 0's and 1's, an island is a group of 1
's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1:
[[0,0,,0,0,0,0,,0,0,0,0,0],
[0,0,0,0,0,0,0,,,,0,0,0],
[0,,,0,,0,0,0,0,0,0,0,0],
[0,,0,0,,,0,0,,0,,0,0],
[0,,0,0,,,0,0,,,,0,0],
[0,0,0,0,0,0,0,0,0,0,,0,0],
[0,0,0,0,0,0,0,,,,0,0,0],
[0,0,0,0,0,0,0,,,0,0,0,0]]
Given the above grid, return 6
. Note the answer is not 11, because the island must be connected 4-directionally.
题意:在一个二维数组中,找出能够连接在一起的数字1的最大长度
思路:DFS
代码:
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
res = 0
m = len(grid)
n = len(grid[0])
for i in range(m): # 遍历数组
for j in range(n):
if grid[i][j] == 1:
res = max(res, self.dfs(grid, i, j))
return res def dfs(self, grid, i, j):
m = len(grid)
n = len(grid[0])
if i < 0 or i > m-1 or j < 0 or j > n-1 \
or grid[i][j] == 0:
return 0
count = 1
grid[i][j] = 0 # 将值变为0,防止重复计数或者递归栈溢出
count += self.dfs(grid, i+1, j) + \
self.dfs(grid, i-1, j) + \
self.dfs(grid, i, j-1) + \
self.dfs(grid, i, j+1) return count
时间复杂度: O(mn)
空间复杂度:O(1)
最新文章
- html中label宽度设置、非替换元素和替换元素
- MVP设计模式的实现
- PHP自动加载__autoload的工作机制
- jquery中的事件进阶
- Erlang generic standard behaviours -- gen_server module
- POJ 3276
- android动画学习
- runtime 运行时机制 完全解读
- js 判断字符串中是否有某字符串
- mysql语句sum求和为null的问题
- Eclipse快捷键大全,导包快捷键:ctrl+Shift+/【转】
- STDOUT/STDERR重定向到ALOG中
- USACO 铂金 T1
- Django的DateTimeField和DateField
- 20162314 《Program Design &; Data Structures》Learning Summary Of The Seventh Week
- iOS 一些常见问题
- Android进程注入
- 常用脚本--SQL Server获取OS日志
- 总结:从Node爬取数据到前端图表展示
- 改造的unity3d文件打包脚本
热门文章
- Eclipse中,open declaration;open implementation;open super implementation的区别
- E20180420-hm
- Swift3的闭包相关
- Codeforces - 1118D2 - Coffee and Coursework (Hard Version) - 二分
- bzoj 2560: 串珠子【状压dp】
- nginx部署h5项目
- 跟我一起玩Win32开发(20):浏览文件夹
- 用CSS绘制三角形
- [BZOJ3916/WOJ3815]Friends
- Codeforces Round #405 (rated, Div. 2, based on VK Cup 2017 Round 1) C