算法学习——LeetCode力扣图论篇3(127. 单词接龙、463. 岛屿的周长、684. 冗余连接、685. 冗余连接 II)

算法学习——LeetCode力扣图论篇3

在这里插入图片描述

127. 单词接龙

127. 单词接龙 - 力扣(LeetCode)

描述

字典 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 中的所有字符串 互不相同

代码解析

深度搜索(超时)
class Solution {
public:int result = INT_MAX;int tmp_result = 1;int cheak(string s1 , string s2){int no_same_num = 0;for(int i=0 ; i<s1.size() ;i++){if(s1[i] != s2[i]) no_same_num++;}return no_same_num;}void track_back(string beginWord, string endWord, vector<string>& wordList , int indix, vector<bool> &path){for(int i=0 ; i<wordList.size() ;i++){if(wordList[indix] == endWord && path[i] == false){if(tmp_result < result) result = tmp_result;// cout<<endl;return;}else if(cheak(wordList[indix],wordList[i]) == 1 && path[i] == false){// cout<<wordList[i]<<' ';tmp_result ++;path[i] = true;track_back(beginWord,endWord,wordList,i,path);path[i] = false;tmp_result--;}}}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {vector<bool> path(wordList.size(),false);for(int i=0 ; i<wordList.size() ;i++){if(cheak(beginWord,wordList[i]) == 1 && path[i]==false){// cout<<wordList[i]<<' ';path[i] = true;tmp_result++;track_back(beginWord,endWord,wordList,i,path);tmp_result--;path[i] = false;}}if(result == INT_MAX) return 0;return result;}
};
广度搜索
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {// 将vector转成unordered_set,提高查询速度unordered_set<string> wordSet(wordList.begin(), wordList.end());// 如果endWord没有在wordSet出现,直接返回0if (wordSet.find(endWord) == wordSet.end()) return 0;// 记录word是否访问过unordered_map<string, int> visitMap; // <word, 查询到这个word路径长度>// 初始化队列queue<string> que;que.push(beginWord);// 初始化visitMapvisitMap.insert(pair<string, int>(beginWord, 1));while(!que.empty()) {string word = que.front();que.pop();int path = visitMap[word]; // 这个word的路径长度for (int i = 0; i < word.size(); i++){string newWord = word; // 用一个新单词替换word,因为每次置换一个字母for (int j = 0 ; j < 26; j++) {newWord[i] = j + 'a';if (newWord == endWord) return path + 1; // 找到了end,返回path+1// wordSet出现了newWord,并且newWord没有被访问过if (wordSet.find(newWord) != wordSet.end() && visitMap.find(newWord) == visitMap.end()) {// 添加访问信息visitMap.insert(pair<string, int>(newWord, path + 1));que.push(newWord);}}}}return 0;}
};

463. 岛屿的周长

463. 岛屿的周长 - 力扣(LeetCode)

描述

给定一个 row x col 的二维网格地图 grid ,其中:grid[i][j] = 1 表示陆地, grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。

岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例

示例 1:

在这里插入图片描述

输入: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 或 1

代码解析

class Solution {
public:int result = 0;int m,n;int dir[4][2] = {0,-1,0,1,-1,0,1,0};void dfs(vector<vector<int>>& grid ,int x , int y){for(int i=0 ; i<4 ;i++){int next_x = x + dir[i][0];int next_y = y + dir[i][1];if(next_x<0||next_x>=m||next_y<0||next_y>=n) result++;else if(grid[next_x][next_y] == 0) result++;}return;}int islandPerimeter(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();for(int i=0 ; i<m ;i++){for(int j=0 ; j<n ;j++){if(grid[i][j] == 1)dfs(grid,i,j);}}return result;}
};

684. 冗余连接

684. 冗余连接 - 力扣(LeetCode)

描述

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。

示例

示例 1:

在这里插入图片描述

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

示例 2:
在这里插入图片描述

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

提示

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中无重复元素
给定的图是连通的

代码解析

class Solution {
public:int n = 0;int find(int u , vector<int> &father){if(u == father[u]) return father[u];father[u] = find(father[u] , father);return father[u];}void join(int u , int v , vector<int> &father){u = find(u , father);v = find(v , father);if(u == v) return;father[v] = u;}bool same(int u , int v , vector<int> &father){u = find(u , father);v = find(v , father);return u == v;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {n = edges.size() + 1;vector<int> father(n,0);for(int i=0 ; i<n ; i++)father[i] = i;for(int i=0 ; i<edges.size() ; i++){if(same(edges[i][0] , edges[i][1] , father)) return edges[i];else join(edges[i][0] , edges[i][1] , father);}return {};}
};

685. 冗余连接 II

685. 冗余连接 II - 力扣(LeetCode)

描述

在本问题中,有根树指满足以下条件的 有向 图。该树只有一个根节点,所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点,而根节点没有父节点。

输入一个有向图,该图由一个有着 n 个节点(节点值不重复,从 1 到 n)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi],用以表示 有向 图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。

返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。

示例

示例 1:
在这里插入图片描述

输入:edges = [[1,2],[1,3],[2,3]]
输出:[2,3]
示例 2:
在这里插入图片描述

输入:edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]
输出:[4,1]

提示

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n

代码解析

class Solution {
public:int n=0;int find(int u , vector<int> &father){if(u == father[u]) return father[u];father[u] = find(father[u],father);return father[u];}void join(int u , int v , vector<int> &father ){u = find(u,father);v = find(v,father);if(u == v) return;father[v] = u; }bool same(int u , int v , vector<int> &father){u = find(u,father);v = find(v,father);return u == v;}bool tree_remove_edga(vector<vector<int>>& edges , int delete_edge , vector<int> &father){for(int i=0 ; i<n ;i++){if(i == delete_edge) continue;if(same(edges[i][0] , edges[i][1] , father) == true) return false;join(edges[i][0] , edges[i][1] , father);}return true;}vector<int> get_remove_edge(vector<vector<int>>& edges , vector<int> &father){for(int i=0 ; i<n ;i++){if(same(edges[i][0] , edges[i][1] , father) == true) return edges[i];join(edges[i][0] , edges[i][1] , father);}return {};}vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {n = edges.size();vector<int> father(n+1,0);vector<int> inDegree(n+1,0);for(int i=0 ; i<n ;i++){father[i] = i;inDegree[edges[i][1]] += 1;}father[n] = n;vector<int> inDeg_2;for(int i=n-1 ; i>=0 ;i--)if(inDegree[edges[i][1]] >= 2) inDeg_2.push_back(i);if(inDeg_2.size() > 0){if(tree_remove_edga(edges,inDeg_2[0] , father) == true) return edges[inDeg_2[0]];else return edges[inDeg_2[1]];}return get_remove_edge(edges,father);}
};

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

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

相关文章

REPLUG:检索增强的黑盒语言模型

论文题目&#xff1a;REPLUG: Retrieval-Augmented Black-Box Language Models   论文日期&#xff1a;2023/05/24   论文地址&#xff1a;https://arxiv.org/abs/2301.12652 文章目录 Abstract1. Introduction2. Background and Related Work2.1 Black-box Language Model…

HarmonyOS 应用开发之FA模型绑定Stage模型ServiceExtensionAbility

本文介绍FA模型的三种应用组件如何绑定Stage模型的ServiceExtensionAbility组件。 PageAbility关联访问ServiceExtensionAbility PageAbility关联访问ServiceExtensionAbility和PageAbility关联访问ServiceAbility的方式完全相同。 import featureAbility from ohos.ability…

MySQL经验分享:Shell开发问题

背景 之前整理过Python连接使用MySQL的经验&#xff0c;链接如下&#xff1a; pymysql封装总结_pymysql封装类-CSDN博客 相比高级语言&#xff0c;Shell与MySQL开发使用相对会更麻烦一些&#xff1b;由于 shell是linux命令集的概称&#xff0c;是属于命令行的人机界面。Shel…

java计算机网络(一)-- url,tcp,udp,socket

网络编程&#xff1a; 计算机网络 计算机网络指将地理位置不同的具有独立功能的多台计算机及其外部设备&#xff0c;通过通信线路连接起来&#xff0c;在网络操作系统、网络管理软件及网络通信协议的管理和协调下&#xff0c;实现资源共享和信息传递的计算机系统。 网络协议…

Git如何修改commit注释

1. 修改commit注释 1.1 修改最后一次注释 通过git log查看提交历史信息 输入命令&#xff1a; git commit --amend 进入修改注释界面 第一行是最后一次的注释信息。后续的操作步骤&#xff1a; 1. 按i键进行编辑状态&#xff0c;修改注释信息。 2. 按Esc&#xff0c;wq保…

Rabbit简单模式理解

简单模式 我们以最普通的方式去理解&#xff0c;并没有整合Springboot的那种 这是最简单的模式&#xff0c;一个生产者&#xff0c;一个消费者&#xff0c;一个队列 测试 1、 导包&#xff0c;没整合&#xff0c;不需要编写配置 2、需要生产者消费者 导包 <dependency…

使用Postman进行websocket接口测试

因为最近要搞关于基于AI的文本接口测试.需要用到websocket协议,于是看了一下发现postman也可以测而且很方便 位置 File->New->WebSocket 可以看到不止WebSocket还支持其他的各种协议 使用 首先先点击connect进行连接 连接成功之后可以选择多种文本格式添加请求参数 每…

EXCEL-VB编程实现自动抓取多工作簿多工作表中的单元格数据

一、VB编程基础 1、 EXCEL文件启动宏设置 文件-选项-信任中心-信任中心设置-宏设置-启用所有宏 汇总文件保存必须以宏启动工作簿格式类型进行保存 2、 VB编程界面与入门 参考收藏 https://blog.csdn.net/O_MMMM_O/article/details/107260402?spm1001.2014.3001.5506 二、…

鱼眼相机的测距流程及误差分析[像素坐标系到空间一点以及测距和误差分析]

由于最近在整理单目测距的内容&#xff0c;顺手也总结下鱼眼相机的测距流程和误差分析&#xff0c;如果有错误&#xff0c;还请不吝赐教。 参考链接: 鱼眼镜头的成像原理到畸变矫正&#xff08;完整版&#xff09; 相机模型总结&#xff08;针孔、鱼眼、全景&#xff09; 三维…

手机无线投屏到windows11电脑

1 安装无线投影组件 2 电脑端打开允许其他设备投影的开关 3 手机找到投屏选项 4 手机搜索可用设备连接即可 这里的官方文档给的不太好,给了一些让人眼花撩乱的信息,以下是经过整合的有效信息

Linux USB驱动(二)

1. Linux USB驱动软件框架 应用程序有两种访问硬件的途径&#xff1a;通过设备驱动程序来访问和跳过设备驱动程序&#xff08;直接使用host驱动程序&#xff09;来访问。 当直接使用Host驱动程序时&#xff0c;可以调用libusb库中已经封装好的函数接口。 2. USB电气信号 一个…

牛客NC92 最长公共子序列(二)【中等 动态规划 Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/6d29638c85bb4ffd80c020fe244baf11 思路 https://blog.csdn.net/qq_36544411/article/details/120021203 思路 动态规划法&#xff0c; 我们以dp[i][j]表示在s1中以第i个元素结尾&#xff0c;s2中以第j个元素结…

网页布局案例 浮动

这里主要讲浮动 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><style>*{padding: 0;margin: 0;}.header{height: 40px;background-color: #333;}.nav{width: 1226px;heig…

(更新)中国农村经营管理统计年报 2015-2022

时间跨度&#xff1a;2015-2022年数据范围&#xff1a;全国各个省市自治区&#xff08;不含港澳台&#xff09;数据说明&#xff1a;《中国农村经营管理统计年报》根据农村经营管理情况统计报表调查数据和分析报告编写而成。系统收录了全国各省份当年农村经营管理各项数据&…

了解XSS和CSRF攻击与防御

什么是XSS攻击 XSS&#xff08;Cross-Site Scripting&#xff0c;跨站脚本攻击&#xff09;是一种常见的网络安全漏洞&#xff0c;它允许攻击者在受害者的浏览器上执行恶意脚本。这种攻击通常发生在 web 应用程序中&#xff0c;攻击者通过注入恶意脚本来利用用户对网站的信任&…

微信小程序如何进行npm导入组件

文章目录 目录 文章目录 前言 一、安装node 二、微信小程序通过npm安装组件&#xff08;以Vant-weapp为例&#xff09; 一、Vant-weapp下载 二 、修改 app.json 三 、修改 project.config.json 四 、 构建 npm 包 前言 微信小程序使用npm导入有很多的教程&#xff0c;我…

webGIS 之 智慧校园案例

1.引入资源创建地图 //index.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content&qu…

Java 中的单例模式

引言&#xff1a; 在 Java 编程中&#xff0c;单例模式是一种常见的设计模式&#xff0c;它保证一个类只能创建一个实例&#xff0c;并提供一个全局访问点。单例模式在很多场景下都非常有用&#xff0c;比如线程池、日志系统、数据库连接池等。本文将详细介绍 Java 中单例模式的…

百度资源平台链接提交

百度资源平台是百度搜索引擎提供的一个重要工具&#xff0c;用于帮助网站主将自己的网站链接提交给百度搜索引擎&#xff0c;以便更快地被收录和展示在搜索结果中。以下将就百度资源平台链接提交的概念、操作方法以及其对网站收录和曝光的影响进行探讨&#xff1a; 什么是百度资…

字符串(java)

字符串的特点&#xff1a; 1&#xff0e;String是java定义好的一个类&#xff0c;定义在java.lang包里面&#xff0c;所以使用的时候是不需要进行导包的 2.java程序中的所有字符串文字&#xff0c;都被实为此类的对象。也就是说当我们就算是进行赋值&#xff0c;这个也会创造…