java数据结构与算法刷题-----LeetCode417. 太平洋大西洋水流问题

本文主要是介绍java数据结构与算法刷题-----LeetCode417. 太平洋大西洋水流问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

文章目录

    • 深度优先遍历

在这里插入图片描述
在这里插入图片描述

深度优先遍历

解题思路:时间复杂度O( m ∗ n m*n mn),空间复杂度O($$)
  1. 从地图中找高点,然后推出是否能流入两个海洋显然不明智
  2. 我们很清楚,两座海洋的水都是从相邻的岸边流入的。与其找当前地点的水流到哪,不如逆向思维。
  3. 将题目变为,两座海洋的水从哪来?
  4. 因此我们遍历陆地的上下左右边界,找到这水从哪流过来的。只要相邻地点比当前位置高,那么水就从高地点流过来的。
  5. 我们可以创建两个数组,分别记录太平洋的水从哪来(标志为true),大西洋的水从哪里来(标志为true)
  6. 最后两个数组同时为true的位置,就是既可以流向太平洋又可以流向大西洋的位置。
代码

在这里插入图片描述

class Solution {int[][] heights;int n,m;public List<List<Integer>> pacificAtlantic(int[][] heights) {this.heights = heights;this.n = heights.length;this.m = heights[0].length;ArrayList<List<Integer>> ans = new ArrayList<>();//保存最终答案boolean pacificOcean[][] = new boolean[n][m];//太平洋boolean atlanticOcean[][] = new boolean[n][m];//大西洋for(int j = 0;j<m;j++) dfs(0,j,pacificOcean);//上边界的太平洋进行广度优先for(int i = 0;i<n;i++) dfs(i,0,pacificOcean);//左边界的太平洋进行广度优先for(int j = 0;j<m;j++) dfs(n-1,j,atlanticOcean);//下边界的大西洋for(int i = 0;i<n;i++) dfs(i,m-1,atlanticOcean);//右边界的大西洋for(int i = 0;i<n;i++){//遍历整个数组for(int j = 0;j<m;j++){//如果太平洋和大西洋的水流都可以到达某个地点if(pacificOcean[i][j] && atlanticOcean[i][j]) {//这个地点就是一个答案,因为题目要求我们找到同时可以到达两个海洋的地点ArrayList<Integer> list = new ArrayList<Integer>();list.add(i);list.add(j);ans.add(list);}}}return ans;}//深度优先int [][] directions = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};//上左下右方向public void dfs(int i,int j,boolean[][] ocean){ocean[i][j] = true;for(int[] direction : directions){int nextI = i+direction[0];int nextJ = j+direction[1];//如果下一个方向合理,并且没有访问过if(nextI < 0 || nextJ < 0 || nextI >= n || nextJ >= m || ocean[nextI][nextJ]) continue;//如果下一个地点比当前地点高,就说明当前水流可以从下一个地点流过来if(heights[i][j]<=heights[nextI][nextJ]) dfs(nextI,nextJ,ocean);}}
}

这篇关于java数据结构与算法刷题-----LeetCode417. 太平洋大西洋水流问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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