图论part4|827. 最大人工岛、127. 单词接龙、463. 岛屿的周长

827. 最大人工岛

  • 🔗:827. 最大人工岛 - 力扣(LeetCode)827. 最大人工岛 - 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后,grid 中最大的岛屿面积是多少?岛屿 由一组上、下、左、右四个方向相连的 1 形成。 示例 1:输入: grid = [[1, 0], [0, 1]]输出: 3解释: 将一格0变成1,最终连通两个小岛得到面积为 3 的岛屿。示例 2:输入: grid = [[1, 1], [1, 0]]输出: 4解释: 将一格0变成1,岛屿的面积扩大为 4。示例 3:输入: grid = [[1, 1], [1, 1]]输出: 4解释: 没有0可以让我们变成1,面积依然为 4。 提示: * n == grid.length * n == grid[i].length * 1 <= n <= 500 * grid[i][j] 为 0 或 1https://leetcode.cn/problems/making-a-large-island/description/
  • 思路:
  • 代码:        
class Solution {/**思路:1. 先把已经存在的岛找出来,并且计算他们的面积(dfs)2. 遍历为0的点,计算加上附近的岛的面积之后的最大面积3. 去重:避免把一个相邻的岛的面积计算两遍*/private final int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};public int largestIsland(int[][] grid) {int n = grid.length;// 计算每一个存在的岛的面积List<Integer> area = new ArrayList<>();for(int i=0; i<n; i++){for(int j=0; j<n; j++){if(grid[i][j] == 1)//找到小岛area.add(dfs(grid, i, j, area.size()+2));}}// int maxSquare = 0;Set<Integer> s = new HashSet<>();for(int i=0; i<n; i++){for(int j=0; j<n; j++){//遍历为0的点,计算加上附近的岛的面积之后的最大面积if(grid[i][j] == 0){int square = 1;s.clear();for(int[] dir: dirs){int newi = dir[0] + i;int newj = dir[1] + j;if(newi>=0 && newj>=0 && newi<grid.length && newj < grid.length && grid[newi][newj]!=0 && s.add(grid[newi][newj])){square += area.get(grid[newi][newj]-2);}}maxSquare = Math.max(square, maxSquare);}}}// 考虑小岛不需要添加任何1的情况return maxSquare == 0 ? n*n : maxSquare;}private int dfs(int[][] grid, int row, int col, int island){// 标记小岛的编号grid[row][col] = island;int square = 1;for(int[] dir: dirs){int newr = row + dir[0];int newc = col + dir[1];if(newc>=0 && newr>=0 && newc<grid.length && newr < grid.length && grid[newr][newc]==1){// 计算岛屿的大小square += dfs(grid, newr, newc, island);}}return square;}
}

127.  单词接龙 

  • 🔗:127. 单词接龙 - 力扣(LeetCode)127. 单词接龙 - 字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk: * 每一对相邻的单词只差一个字母。 *  对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。 * sk == endWord给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0 。 示例 1:输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]输出:5解释:一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。示例 2:输入:beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]输出:0解释:endWord "cog" 不在字典中,所以无法进行转换。 提示: * 1 <= beginWord.length <= 10 * endWord.length == beginWord.length * 1 <= wordList.length <= 5000 * wordList[i].length == beginWord.length * beginWord、endWord 和 wordList[i] 由小写英文字母组成 * beginWord != endWord * wordList 中的所有字符串 互不相同https://leetcode.cn/problems/word-ladder/description/
  • 思路1:广度优先遍历
    • 用图论的思想去看待这道题,返回begin-->end的最短路径
  • 代码1(广度优先遍历)        
class Solution {/**beginword: -->   -->       -->    --> endwordhit      hot      dot      dog       cog用图论的思想去看待这道题,begin--》end的最短路径*/// to judge whether there is an edgeprivate boolean isEdge(String cur, String next){if(cur.length()!=next.length()) return false;int diff = 0;for(int i=0; i<cur.length(); i++){if(diff > 1) return false;if(cur.charAt(i) != next.charAt(i)){diff++;}}return diff == 1;}// public int ladderLength(String beginWord, String endWord, List<String> wordList) {Set<String> visited = new HashSet<>();if(!wordList.contains(endWord)) return 0;Queue<String> neighbours = new LinkedList<>();neighbours.add(beginWord);visited.add(beginWord);int length = 1;while(!neighbours.isEmpty()){int size = neighbours.size();for(int i=0; i<size; i++){String currentword = neighbours.poll();if(isEdge(currentword,endWord)) return length+1;for(String word: new HashSet<>(wordList)){if(visited.contains(word)) continue;if(isEdge(currentword,word)){neighbours.add(word);visited.add(word);}}}// 现在的数值和endword间有边length++;}return 0;}
}
  • 思路2: 优化方式--用双向bfs缩短遍历的流程
    • 1. 除了visited(所有访问过的节点)之外,采用startvisited和endvisited存储前后向遍历的节点(非全部节点,而是要处理的新一层的节点)
    • 交替处理startvisited和endvisited中需要处理的数据,每次处理节点数小的那个list
    • 如果startvisited的下一层(nextvisited)中,包含endvisited中的元素,则表示找到了最短的路径
    • 图示:(来源weiwei)
  • 代码2:
    • public class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 第 1 步:先将 wordList 放到哈希表里,便于判断某个单词是否在 wordList 里Set<String> wordSet = new HashSet<>(wordList);if (wordSet.size() == 0 || !wordSet.contains(endWord)) {return 0;}// 第 2 步:已经访问过的 word 添加到 visited 哈希表里Set<String> visited = new HashSet<>();// 分别用左边和右边扩散的哈希表代替单向 BFS 里的队列,它们在双向 BFS 的过程中交替使用Set<String> beginVisited = new HashSet<>();beginVisited.add(beginWord);Set<String> endVisited = new HashSet<>();endVisited.add(endWord);// 第 3 步:执行双向 BFS,左右交替扩散的步数之和为所求int step = 1;while (!beginVisited.isEmpty() && !endVisited.isEmpty()) {// 优先选择小的哈希表进行扩散,考虑到的情况更少if (beginVisited.size() > endVisited.size()) {Set<String> temp = beginVisited;beginVisited = endVisited;endVisited = temp;}// 逻辑到这里,保证 beginVisited 是相对较小的集合,nextLevelVisited 在扩散完成以后,会成为新的 beginVisitedSet<String> nextLevelVisited = new HashSet<>();for (String word : beginVisited) {if (changeWordEveryOneLetter(word, endVisited, visited, wordSet, nextLevelVisited)) {return step + 1;}}// 原来的 beginVisited 废弃,从 nextLevelVisited 开始新的双向 BFSbeginVisited = nextLevelVisited;step++;}return 0;}/*** 尝试对 word 修改每一个字符,看看是不是能落在 endVisited 中,扩展得到的新的 word 添加到 nextLevelVisited 里** @param word* @param endVisited* @param visited* @param wordSet* @param nextLevelVisited* @return*/private boolean changeWordEveryOneLetter(String word, Set<String> endVisited,Set<String> visited,Set<String> wordSet,Set<String> nextLevelVisited) {char[] charArray = word.toCharArray();for (int i = 0; i < word.length(); i++) {char originChar = charArray[i];for (char c = 'a'; c <= 'z'; c++) {if (originChar == c) {continue;}charArray[i] = c;String nextWord = String.valueOf(charArray);if (wordSet.contains(nextWord)) {if (endVisited.contains(nextWord)) {return true;}if (!visited.contains(nextWord)) {nextLevelVisited.add(nextWord);visited.add(nextWord);}}}// 恢复,下次再用charArray[i] = originChar;}return false;}
      }

105. 有向图的完全可达性 

  • 🔗:105. 有向图的完全可达性https://kamacoder.com/problempage.php?pid=1177
  • 思路:不难做,主要练习一下acm模式,用的是广度优先的搜索方式,用深度是一样的
  • 代码:
    import java.util.*;class Main{private static Set<Integer> visited = new HashSet<>();public static void main(String[] args){Scanner scanner = new Scanner(System.in);int num_node = scanner.nextInt();int num_edge = scanner.nextInt();// if there is only 1 node//if(num_node==1) return 1;List<int[]> edges  = new ArrayList<>();for(int i=0 ;i<num_edge; i++){int[] edge = new int[2];edge[0] = scanner.nextInt();edge[1] = scanner.nextInt();edges.add(edge);}int currentNode = 1;Queue<Integer> que = new LinkedList<>();que.add(currentNode);visited.add(currentNode);while(!que.isEmpty()){int size = que.size();for(int j=0; j<size; j++){currentNode = que.poll();for(int[] edge1: edges){//// System.out.println(edge1[0]+" "+edge1[1]);if(edge1[0] == currentNode){// 如果加不进去代表重复visited了if(visited.add(edge1[1])){que.add(edge1[1]);}}}}}if(visited.size()==num_node)System.out.println(1);elseSystem.out.println(-1);}}

463. 岛屿的周长

  • 🔗:463. 岛屿的周长 - 力扣(LeetCode)463. 岛屿的周长 - 给定一个 row x col 的二维网格地图 grid ,其中:grid[i][j] = 1 表示陆地, grid[i][j] = 0 表示水域。网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。 示例 1:[https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/island.png]输入:grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]输出:16解释:它的周长是上面图片中的 16 个黄色的边示例 2:输入:grid = [[1]]输出:4示例 3:输入:grid = [[1,0]]输出:4 提示: * row == grid.length * col == grid[i].length * 1 <= row, col <= 100 * grid[i][j] 为 0 或 1https://leetcode.cn/problems/island-perimeter/description/
  • 思路:深度优先搜索
    • dfs遍历的方式可扩展至统计多个岛屿各自的周长。

  • 代码:
    class Solution {int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};public int islandPerimeter(int[][] grid) {int circle = 0;int m = grid.length;int n = grid[0].length;for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(grid[i][j]==1){circle = dfs(grid, i, j);return circle;}}}return circle;    }private int dfs(int[][] grid, int row, int column){if(grid[row][column]==2) return 0;int circle = 0;grid[row][column] = 2;for(int[] dir: dirs){int x = row + dir[0];int y = column + dir[1];if(x<0 || y<0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0){circle += 1;}else if(grid[x][y] == 1){circle += dfs(grid, x, y);}}return circle;}
    }

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/33692.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpeechCraf论文学习

Abstract 核心问题 挑战 语音风格包含细微的多样化信息&#xff08;如情感、语调、节奏&#xff09;&#xff0c;传统基于标签/模板的标注方法难以充分捕捉&#xff0c;制约了语音-语言多模态模型的性能。 数据瓶颈&#xff1a; 大规模数据收集与高质量标注之间存在矛盾&…

SAIL-RK3576核心板应用方案——无人机视觉定位与地面无人设备通信控制方案

本方案以 EFISH-RK3576-SBC工控板 或 SAIL-RK3576核心板 为核心&#xff0c;结合高精度视觉定位、实时通信与智能控制技术&#xff0c;实现无人机与地面无人设备的协同作业。方案适用于物流巡检、农业植保、应急救援等场景&#xff0c;具备高精度定位、低延迟通信与强环境适应性…

PostgreSQL的学习心得和知识总结(一百七十一)|深入理解PostgreSQL数据库之 外连接消除 的使用和实现

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《PostgreSQL数据库内核分析》 2、参考书籍&#xff1a;《数据库事务处理的艺术&#xff1a;事务管理与并发控制》 3、PostgreSQL数据库仓库…

C语言实现括号匹配检查及栈的应用详解

目录 栈数据结构简介 C语言实现栈 栈的初始化 栈的销毁 栈的插入 栈的删除 栈的判空 获取栈顶数据 利用栈实现括号匹配检查 总结 在编程中&#xff0c;经常会遇到需要检查括号是否匹配的问题&#xff0c;比如在编译器中检查代码的语法正确性&#xff0c;或者在…

【机器学习chp12】半监督学习(自我训练+协同训练多视角学习+生成模型+半监督SVM+基于图的半监督算法+半监督聚类)

目录 一、半监督学习简介 1、半监督学习的定义和基本思想 2、归纳学习 和 直推学习 &#xff08;1&#xff09;归纳学习 &#xff08;2&#xff09;直推学习 3、半监督学习的作用与优势 4、半监督学习的关键假设 5、半监督学习的应用 6、半监督学习的常见方法 7、半…

2024 年第四届高校大数据挑战赛-赛题 A:岩石的自动鉴定

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

基于WebRTC与P2P技术,嵌入式视频通话EasyRTC实现智能硬件音视频交互,适配Linux、ARM、RTOS、LiteOS

EasyRTC不仅仅是一个连接工具&#xff0c;更是一个经过深度优化的通信桥梁。它在嵌入式设备上进行了特殊优化&#xff0c;通过轻量级SDK设计、内存和存储优化以及硬件加速支持&#xff0c;解决了传统WebRTC在嵌入式设备上的适配难题&#xff0c;显著节省了嵌入式设备的资源。 1…

[c语言日寄]字符串进阶:KMP算法

【作者主页】siy2333 【专栏介绍】⌈c语言日寄⌋&#xff1a;这是一个专注于C语言刷题的专栏&#xff0c;精选题目&#xff0c;搭配详细题解、拓展算法。从基础语法到复杂算法&#xff0c;题目涉及的知识点全面覆盖&#xff0c;助力你系统提升。无论你是初学者&#xff0c;还是…

Android源码学习之Overlay

在 Android Framework 开发中&#xff0c;Overlay 主要用于修改和替换系统或应用的资源&#xff0c;而无需直接修改源码&#xff0c;与源码解耦。Overlay 机制可以分为 两种类型&#xff1a; 静态 Overlay&#xff08;Static Resource Overlay, SRO&#xff09; 在 编译时 覆…

【MySQL】基本操作 —— DDL

目录 DDLDDL 常用操作对数据库的常用操作查看所有数据库创建数据库切换、显示当前数据库删除数据库修改数据库编码 对表的常用操作创建表数据类型数值类型日期和时间类型字符串类型 查看当前数据库所有表查看指定表的创建语句查看指定表结构删除表 对表结构的常用操作给表添加字…

网络安全需要学多久才能入门?

网络安全是一个复杂且不断发展的领域&#xff0c;想要入行该领域&#xff0c;我们需要付出足够多的时间和精力好好学习相关知识&#xff0c;才可以获得一份不错的工作&#xff0c;那么网络安全需要学多久才能入门?我们通过这篇文章来了解一下。 学习网络安全的入门时间因个人的…

【测试语言基础篇】Python基础之List列表

一、Python 列表(List) 序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置&#xff0c;或索引&#xff0c;第一个索引是0&#xff0c;第二个索引是1&#xff0c;依此类推。 Python有6个序列的内置类型&#xff0c;但最常见的是列表和元组。序列都可…

编译系统设计原理概述

目录 简介 词法分析 正则表达式 有穷状态自动机 从正则表达式到有穷自动机的转换 单词识别 简介 主要介绍编译系统设计过程中涉及的原理与技术&#xff0c;主要分为前端设计和后端设计两 个模块。前端部分包括词法分析器、语法分析器的构建和语义分析过程的设计…

ArcGIS Pro 车牌分区数据处理与地图制作全攻略

在大数据时代&#xff0c;地理信息系统&#xff08;GIS&#xff09;技术在各个领域都有着广泛的应用&#xff0c;而 ArcGIS Pro 作为一款功能强大的 GIS 软件&#xff0c;为数据处理和地图制作提供了丰富的工具和便捷的操作流程。 车牌数据作为一种重要的地理空间数据&#xf…

前端登录鉴权全解析:主流方案对比与实现指南

文章目录 一、常见登录鉴权方式概览1.1 主流方案对比1.2 技术特性对比 二、Session/Cookie方案2.1 实现原理2.2 代码实现2.3 优缺点分析 三、JWT方案3.1 实现原理3.2 代码实现3.3 优缺点分析 四、OAuth方案4.1 实现原理4.2 代码实现4.3 优缺点分析 五、SSO方案5.1 实现原理5.2 …

算法系列之回溯算法求解数独及所有可能解

有没有对数独感兴趣的朋友呢&#xff1f;数独作为一款经典的逻辑游戏&#xff0c;其目标是在一个9x9的方格中填入数字1至9&#xff0c;确保每一行、每一列以及每一个3x3的子网格中都包含这些数字且不重复。尽管数独的规则看似简单&#xff0c;但编写一个能够自动求解数独的程序…

华为hcia——Datacom实验指南——TCP传输原理和数据段格式

什么是TCP TCP是一种可靠的端到端的传输层协议&#xff0c;仅应用于单波通信。 采用TCP协议作为传输方式的应用层服务&#xff0c;再进行数据传输前&#xff0c;都需要进行TCP协议的创建。 TCP报文的格式 sequence number&#xff08;序列号&#xff09; 占4个字节&#x…

Vlog 片头制作

打开剪映&#xff0c;新建草稿&#xff0c;导入黑色背景。 拉长时间轴&#xff0c;背景时常调整为4.2秒。 添加文本&#xff0c;输入 5 个“|”&#xff0c;每个中间 2 个空格&#xff0c;如下| | | | |&#xff0c;然后手动放大文本&#xff0c;让中间显示出四个间隔。 继续添…

【Nacos】服务发布之优雅预热上线方案

目录 一、背景二、注册时机2.1、注册机制2.2、分析源码找到注册时机 三、注册前心跳健康检测3.1、方案实施3.2、源码分析3.3、优化代码 四、流量权重配置五、总结5.1、整体完整流程&#xff1a;5.2、流程图&#xff1a;5.1、优化方案完整代码&#xff1a; 一、背景 有些面向广…

VXLAN 组播 RP

一、Anycast RP 在每个 VTEP 上&#xff0c;每个多播组都会建立一个源树 (S,G)&#xff0c;并且在双活 Leaf 设备上到 RP 地址是 ECMP 路径。 在 PIM ASM 模式下&#xff0c;(S,G) 组在 VTEP 端创建。由于每个 VTEP 都能够为特定的多播组发送和接收多播流量&#xff0c;因此每…