力扣-图论-17【算法学习day.67】

devtools/2024/12/24 21:06:01/

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!


习题

1.检查网格中是否存在有效路径

题目链接:1391. 检查网格中是否存在有效路径 - 力扣(LeetCode)分析:就是dfs,判断条件比较繁琐 

代码:

java">class Solution {int[][] grid;int n,m;int[][] flag;boolean ans = false;public boolean hasValidPath(int[][] grid) {this.grid = grid;n = grid.length;m = grid[0].length;flag = new int[n][m];flag[0][0] = 1;recursion(0,0);return ans;}public void recursion(int x,int y){// System.out.println(x+"          "+y);if(x==n-1&&y==m-1){ans = true;return;}if(x+1<n&&flag[x+1][y]==0){flag[x+1][y] = 1;if(grid[x][y]==2&&grid[x+1][y]==2){recursion(x+1,y);}if(grid[x][y]==2&&(grid[x+1][y]==5||grid[x+1][y]==6)){recursion(x+1,y);}if((grid[x][y]==3||grid[x][y]==4)&&grid[x+1][y]==2){recursion(x+1,y);}if((grid[x][y]==3||grid[x][y]==4)&&(grid[x+1][y]==5||grid[x+1][y]==6)){recursion(x+1,y);}flag[x+1][y] = 0;}if(x-1>=0&&flag[x-1][y]==0){flag[x-1][y] = 1;if(grid[x][y]==2&&grid[x-1][y]==2){recursion(x-1,y);}if((grid[x][y]==5||grid[x][y]==6)&&(grid[x-1][y]==3||grid[x-1][y]==4)){recursion(x-1,y);}if((grid[x][y]==5||grid[x][y]==6)&&grid[x-1][y]==2){recursion(x-1,y);}if(grid[x][y]==2&&(grid[x-1][y]==3||grid[x-1][y]==4)){recursion(x-1,y);}flag[x-1][y] = 0;}if(y+1<m&&flag[x][y+1]==0){flag[x][y+1] = 1;if(grid[x][y]==1&&grid[x][y+1]==1){recursion(x,y+1);}if(grid[x][y]==1&&(grid[x][y+1]==3||grid[x][y+1]==5)){recursion(x,y+1);}if((grid[x][y]==4||grid[x][y]==6)&&grid[x][y+1]==1){recursion(x,y+1);}if((grid[x][y]==4||grid[x][y]==6)&&(grid[x][y+1]==3||grid[x][y+1]==5)){recursion(x,y+1);}flag[x][y+1] = 0;}if(y-1>=0&&flag[x][y-1]==0){flag[x][y-1]=1;if(grid[x][y]==1&&grid[x][y-1]==1){recursion(x,y-1);}if(grid[x][y]==1&&(grid[x][y-1]==4||grid[x][y-1]==6)){recursion(x,y-1);}if((grid[x][y]==3||grid[x][y]==5)&&grid[x][y-1]==1){recursion(x,y-1);}if((grid[x][y]==3||grid[x][y]==5)&&(grid[x][y-1]==4||grid[x][y-1]==6)){recursion(x,y-1);}flag[x][y-1] = 0;}}
}

2.太平洋大西洋水流问题

题目链接:417. 太平洋大西洋水流问题 - 力扣(LeetCode) 

题面:

分析:dfs,用两个变量来判断是否既能流入太平洋又能流入大西洋,复杂度较高 

代码: 

java">class Solution {int[][] heights;int n,m;int[][] flag;int flag2 = 0;int flag3 = 0;List<Integer> list;List<List<Integer>> ans = new ArrayList<>();public List<List<Integer>> pacificAtlantic(int[][] heights) {this.heights = heights;n = heights.length;m = heights[0].length;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){flag2 = 0;flag3 = 0;list = new ArrayList<>();flag = new int[n][m];flag[i][j] = 1;recursion(i,j);if(flag2==1&&flag3==1){list.add(i);list.add(j);ans.add(list);}}}return ans;}public void recursion(int x,int y){if(x==0||y==0)flag2 = 1;if(x==n-1||y==m-1)flag3 = 1;if(flag2==1&&flag3==1)return;if(x+1<n&&heights[x+1][y]<=heights[x][y]&&flag[x+1][y]==0){flag[x+1][y] = 1;recursion(x+1,y);flag[x+1][y] = 0;}if(x-1>=0&&heights[x-1][y]<=heights[x][y]&&flag[x-1][y]==0){flag[x-1][y] = 1;recursion(x-1,y);flag[x-1][y] = 0;}if(y+1<m&&heights[x][y+1]<=heights[x][y]&&flag[x][y+1]==0){flag[x][y+1] = 1;recursion(x,y+1);flag[x][y+1] = 0;}if(y-1>=0&&heights[x][y-1]<=heights[x][y]&&flag[x][y-1]==0){flag[x][y-1] = 1;recursion(x,y-1);flag[x][y-1] = 0;}}
}

 后言

上面是力扣图论专题,下一篇是其他的习题,希望有所帮助,一同进步,共勉!


http://www.ppmy.cn/devtools/145078.html

相关文章

将多个 k8s yaml 配置文件合并为一个文件

如下bash脚本实现功能 “将多个k8s的yaml 配置文件” 合并为一个 yaml&#xff0c;使用 --- 分割文件配置。 创建文件 merge_yaml.sh &#xff0c;内容如下&#xff1a; #!/bin/bash# 默认参数 input_patterns() # 匹配的文件模式数组 output_file"combined.yaml"…

基于Spring Boot的远程教育网站

一、系统背景与意义 随着互联网技术的飞速发展和普及&#xff0c;远程教育已成为现代教育体系中的重要组成部分。它打破了时间和空间的限制&#xff0c;让学习者可以随时随地进行学习。基于Spring Boot的远程教育网站正是为了满足这一需求而设计的&#xff0c;它利用互联网技术…

Android Java Ubuntu系统如何编译出 libopencv_java4.so

Cmake: cd ~ wget https://github.com/Kitware/CMake/releases/download/v3.30.3/cmake-3.30.3-linux-x86_64.tar.gztar -xzvf cmake-3.30.3-linux-x86_64.tar.gz sudo ln -sf $(pwd)/cmake-3.30.3-linux-x86_64/bin/* /usr/bin/cmake --versionAndroid NDK: wget https://…

Oracle创建逻辑目录

Oracle 在执行逻辑备份及还原时&#xff0c;需要用到逻辑目录。 本文就来简单介绍一下逻辑目录相关的操作&#xff0c;希望对大家有所帮助。 ‌1.登录到Oracle数据库‌ 使用具有足够权限的数据库用户登录到Oracle数据库。通常&#xff0c;这需要是管理员账号&#xff0c;如SYS…

深度学习实战之超分辨率算法(tensorflow)——ESPCN

espcn原理算法请参考上一篇论文&#xff0c;这里主要给实现。 数据集如下&#xff1a;尺寸相等即可 针对数据集&#xff0c;生成样本代码preeate_data.py import imageio from scipy import misc, ndimage import numpy as np import imghdr import shutil import os import…

如何通过HTTP API新建Collection

本文介绍如何通过HTTP API创建一个新的Collection。 前提条件 已创建Cluster&#xff1a;创建Cluster。 已获得API-KEY&#xff1a;API-KEY管理。 Method与URL HTTP POST https://{Endpoint}/v1/collections 使用示例 说明 需要使用您的api-key替换示例中的YOUR_API_KEY、…

Oracle筑基篇-调度算法-LRU的引入

常见的调度算法 图1 调度算法思维导图 一、LRU算法的典型使用场景 1. 操作系统中的页面置换 什么时候用到页面置换算法呢&#xff1f; 当CPU发出指令需要访问某个地址时&#xff0c;若该地址在TLB&#xff08;Translation Lookaside Buffer&#xff0c;快表&#xff09;或页…

Matplotlib DAY1 (完)

Matplotlib 是支持 Python 语言的开源绘图库&#xff0c;因为其支持丰富的绘图类型、简单的绘图方式以及完善的接口文档&#xff0c;深受 Python 工程师、科研学者、数据工程师等各类人士的喜欢。本次实验课程中&#xff0c;我们将学会使用 Matplotlib 绘图的方法和技巧。 知识…