java leetcode之[动态规划 中等]695. 岛屿的最大面积

java leetcode之[动态规划 中等]695. 岛屿的最大面积

题目的链接在这里：https://leetcode-cn.com/problems/max-area-of-island/

目录

• 题目大意
• 一、示意图
• 二、解题思路
• • dfs
  • bfs

---

题目大意

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

---

一、示意图

二、解题思路

DFS和BFS

dfs

代码如下：

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        //就是求这个岛屿的最大面积 这里需要注意的是 是需要从每一个角开始判断的
        //DFS写法
        int x=grid.length;
        int y=grid[0].length;
        //先进行边界判断
        if(grid==null||grid.length==0) {
            return 0;
        }
        int maxNum=0;
        //需要从每一个 都作为起点来 开始遍历一遍
        for(int i=0;i=grid.length||j<0||j>=grid[0].length||grid[i][j]==0){
            return 0;
        }
        //然后开始遍历 首先说明他是存在的 面积最起码等于1
        int temp_max=1;
        //这里有个细节 就把他设置成0 这样就防止回滚了
        grid[i][j]=0;
        //然后开始遍历他四周的值
        return temp_max+dfs(i+1,j,grid)+dfs(i-1,j,grid)+dfs(i,j+1,grid)+dfs(i,j-1,grid);
        
    }
}

bfs

代码如下：

class Solution {
     int[] stepX={0,0,1,-1};
    int[] stepY={1,-1,0,0};
    public int maxAreaOfIsland(int[][] grid) {
        //就是求这个岛屿的最大面积 这里需要注意的是 是需要从每一个角开始判断的
        //BFS写法
        int x=grid.length;
        int y=grid[0].length;
        //先进行边界判断
        if(grid==null||grid.length==0) {
            return 0;
        }
        int maxNum=0;
        Queue queue=new linkedList<>();
        //需要从每一个 都作为起点来 开始遍历一遍
        for(int i=0;i queue) {
        //直接判断即可
        if(grid[i][j]==0){
            return 0;
        }
        //不然的话 就需要进行队列了
        queue.add(i);
        queue.add(j);
        int temp_max=0;
        //然后就开始遍历了
       while (!queue.isEmpty()){
           int size=queue.size()/2;
           for(int k=0;k=0&&newX=0&&newY 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5574147.html