LeetCode刷题:695. Max Area of Island(JAVA代码详解)

2023-11-10 14:38

本文主要是介绍LeetCode刷题:695. Max Area of Island(JAVA代码详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode刷题:695. Max Area of Island

原题链接:https://leetcode.com/problems/max-area-of-island/description/

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,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:
[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

这个题目的意思是给定了一个非空的二维数组,单元格的值由0和1构成。1代表岛(陆地),0代表水。岛是由上下左右相邻的陆地构成。
假设二维数组的四周边界之外都是水。
在给定的二维数组中找到岛(陆地)的最大面积。如果给定的二维数组中没有岛,则岛的最大面积为0。

问题分析

这个题目可以考虑从二维数组的左上角位置,其坐标为[0,0]开始进行遍历,采用DFS搜索算法,找出某一个位置,其上下左右相邻的位置均为1的最大数,即为岛的面积。

对于二维数组中某一个元素的位置 [i,j] 来说,搜索的方向有4个,分别确定其坐标进行搜索:

[ i + 1 , j ] , [ i , j + 1 ] , [ i − 1 , j ] , [ i , j − 1 ] [i+1,j],[i,j+1],[i-1,j],[i,j-1] [i+1,j],[i,j+1],[i1,j],[i,j1]

算法实现

编写一个方法maxAreaOfIsland()来求岛的最大面积,返回值即为所求的最大面积。

public int maxAreaOfIsland(int[][] grid) {int max = 0//......return max;
}

编写一个双重循环,从给定的二维数组的左上角,即[0,0]位置开始搜索,当满足条件 grid[i][j] == 1 时,调用DFS算法向其周围的四个方向进行搜索。代码如下:

public int maxAreaOfIsland(int[][] grid) {//如果grid为空或者grid的长度为0,则返回。结束。if (grid == null || grid.length == 0) {return 0;}//获得M*N矩阵的维度int m = grid.length;int n = grid[0].length;//设置max初始值为0int max = 0;//双重循环for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//如果grid[i][j]的值为1,则进行搜索if (grid[i][j] == 1) {int area = dfs(grid, i, j, m, n, 0);//取最大值max = Math.max(area, max);}}}//返回最大值return max;}

DFS算法如何设计呢?

/** DFS搜索算法思路* 输入参数:* grid—矩阵* i,j 表示矩阵元素的坐标* m,n 表示矩阵的行和列* area表示最大面积* */int dfs(int[][] grid, int i, int j, int m, int n, int area) {if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {return area;}//标记为0,搜索过的单元格位置标记为0grid[i][j] = 0;//area加1area++;//继续向4个方向搜索area = dfs(grid, i + 1, j, m, n, area);area = dfs(grid, i, j + 1, m, n, area);area = dfs(grid, i - 1, j, m, n, area);area = dfs(grid, i, j - 1, m, n, area);//返回areareturn area;}
完整的算法实现
package com.bean.algorithmbasic;public class MaxAreaofIsland {public int maxAreaOfIsland(int[][] grid) {//如果grid为空或者grid的长度为0,则返回。结束。if (grid == null || grid.length == 0) {return 0;}//获得M*N矩阵的维度int m = grid.length;int n = grid[0].length;//设置max初始值为0int max = 0;//双重循环for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//如果grid[i][j]的值为1,则进行搜索if (grid[i][j] == 1) {int area = dfs(grid, i, j, m, n, 0);//取最大值max = Math.max(area, max);}}}//返回最大值return max;}int dfs(int[][] grid, int i, int j, int m, int n, int area) {if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {return area;}//标记为0grid[i][j] = 0;//area加1area++;//继续向4个方向搜索area = dfs(grid, i + 1, j, m, n, area);area = dfs(grid, i, j + 1, m, n, area);area = dfs(grid, i - 1, j, m, n, area);area = dfs(grid, i, j - 1, m, n, area);//返回areareturn area;}public static void main(String args[]) {int[][] map= {		{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}};MaxAreaofIsland maos=new MaxAreaofIsland();int ANSWER=maos.maxAreaOfIsland(map);System.out.println("ANSWER = "+ANSWER);}
}

运行结果:

ANSWER = 6

(完)

这篇关于LeetCode刷题:695. Max Area of Island(JAVA代码详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/383304

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof