力扣面试题 16.19. 水域大小(java DFS解法)

2023-12-20 13:52

本文主要是介绍力扣面试题 16.19. 水域大小(java DFS解法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Problem: 面试题 16.19. 水域大小

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

在这里插入图片描述

思路

该问题可以归纳为一类遍历二维矩阵的题目,此类中的一部分题目可以利用DFS来解决,具体到本题目(该题目可以的写法大体不变可参看前面几个题目:):

Problem: 力扣面试题 08.10. 颜色填充(java DFS解法)
Problem: 力扣200. 岛屿数量(java DFS解法)
Problem: 力扣LCR 130. 衣橱整理(DFS 解法)

具体到本题目中:

我们只需要将记录方位的数组扩展成记录上、下、左、右、左上、右上、左下、右下即可,其余操作大体一致。

解题方法

1.定义并初始化给定矩阵的行,列(rows, cols),int类型变量count(记录连通水域的个数)定义用于存储数据的List集合result。遍历二维数组land若当前位置元素为0则调用编写的DFS函数,退出DFS后将当前连通位置的水域个数添加到result中,最后将将集合中元素拷贝到一个数组中排序并返回。
2. dfs函数实现

2.1 每次将当count加一,land当前位置置为1(标记当前位置是已经遍历过的合法位置)
2.2 二维数组记录八个方位int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
2.3 for循环开始查找遍历(循环范围1-8),每次得到一个新的坐标(int newI = sr + directions[i][0];int newJ = sc + directions[i][1];
2.4 条件判断新得到的横纵坐标不超过给定二维数组的索引范围,同时新的到的横纵坐标所在位置的值等于0则继续DFS

复杂度

时间复杂度:

O ( m n ) O(mn) O(mn)

空间复杂度:

O ( m n ) O(mn) O(mn)

Code

class Solution {//Recode the count of watersprivate int count = 0;//Recode the rows and columns of matrixprivate int rows;private int cols;/*** Get all Connected waters** @param land Given matrix* @return int[]*/public int[] pondSizes(int[][] land) {rows = land.length;cols = land[0].length;//Result listList<Integer> result = new ArrayList<>();for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {if (land[i][j] == 0) {count = 0;dfs(i, j, land);result.add(count);}}}//Sortint[] finalResult = new int[result.size()];for (int i = 0; i < finalResult.length; ++i) {finalResult[i] = result.get(i);}Arrays.sort(finalResult);return finalResult;}/*** Access all connected waters by DFS** @param row  Abscissa* @param col  Ordinate* @param land Given matrix*/private void dfs(int row, int col, int[][] land) {count++;//Change the current position to 1//which shows that it has be visitedland[row][col] = 1;//Record eight bearingsint[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};for (int i = 0; i < 8; ++i) {int newI = row + directions[i][0];int newJ = col + directions[i][1];if (newI >= 0 && newI < rows && newJ >= 0 && newJ < cols&& land[newI][newJ] == 0) {dfs(newI, newJ, land);}}}
}

这篇关于力扣面试题 16.19. 水域大小(java DFS解法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

springboot security验证码的登录实例

《springbootsecurity验证码的登录实例》:本文主要介绍springbootsecurity验证码的登录实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录前言代码示例引入依赖定义验证码生成器定义获取验证码及认证接口测试获取验证码登录总结前言在spring

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s