力扣面试题 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的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Java中Scanner的用法示例小结

《Java中Scanner的用法示例小结》有时候我们在编写代码的时候可能会使用输入和输出,那Java也有自己的输入和输出,今天我们来探究一下,对JavaScanner用法相关知识感兴趣的朋友一起看看吧... 目录前言一 输出二 输入Scanner的使用多组输入三 综合练习:猜数字游戏猜数字前言有时候我们在

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

springboot项目如何开启https服务

《springboot项目如何开启https服务》:本文主要介绍springboot项目如何开启https服务方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录springboot项目开启https服务1. 生成SSL证书密钥库使用keytool生成自签名证书将

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据