图论第三天|127. 单词接龙 841.钥匙和房间 463. 岛屿的周长 1971. 寻找图中是否存在路径 684.冗余连接 685.冗余连接II

本文主要是介绍图论第三天|127. 单词接龙 841.钥匙和房间 463. 岛屿的周长 1971. 寻找图中是否存在路径 684.冗余连接 685.冗余连接II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • Leetcode127. 单词接龙
  • Leetcode841.钥匙和房间
  • Leetcode463. 岛屿的周长
  • Leetcode1971. 寻找图中是否存在路径
  • Leetcode684.冗余连接
  • Leetcode685.冗余连接II

Leetcode127. 单词接龙

文章链接:代码随想录
题目链接:127. 单词接龙

思路:广搜搜出来直接就是最短路径,深搜还需要判断;广搜相当于先把这一层路径的单词下一步走法都扫出来再走下一步;而深搜找到一条路径就先走到头,再返回来走下一条路径,需要判断路径长度,麻烦
另外需要标记位,wordMap,避免死循环

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> wordSet(wordList.begin(), wordList.end());if (wordSet.find(endWord) == wordSet.end()) return 0;unordered_map<string, int> wordMap;wordMap.insert(pair<string, int>(beginWord, 1));queue<string> que;que.push(beginWord);while(!que.empty()){string word = que.front();que.pop();int path = wordMap[word];for (int i = 0; i < word.size(); i++){string newword = word;for (int j = 0; j < 26; j++){newword[i] = j + 'a';if (newword == endWord) return path + 1;if (wordSet.find(newword) != wordSet.end() && wordMap.find(newword) == wordMap.end()) {wordMap.insert(pair<string, int>(newword, path + 1));que.push(newword);}}}}return 0;}
};

Leetcode841.钥匙和房间

文章链接:代码随想录
题目链接:841.钥匙和房间

思路:dfs

class Solution {
public:void dfs(vector<vector<int>>& rooms, vector<bool>& visited, int key){if (visited[key]) return;visited[key] = true;for (int i : rooms[key]){dfs(rooms, visited, i);}}bool canVisitAllRooms(vector<vector<int>>& rooms) {vector<bool> visited(rooms.size(), false);dfs(rooms, visited, 0);for(int i : visited){if (i == false) return false;}return true;}
};

Leetcode463. 岛屿的周长

文章链接:代码随想录
题目链接:463. 岛屿的周长

思路:不用深搜或广搜,遍历就好,不要想复杂。

class Solution {
public:int count = 0;int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};    int islandPerimeter(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 1){for (int k = 0; k < 4; k++){int nex = i + dir[k][0];int ney = j + dir[k][1];if (nex < 0 || nex >= grid.size() || ney < 0 || ney >= grid[0].size() || grid[nex][ney] == 0){count++;}}}}}return count;}
};

Leetcode1971. 寻找图中是否存在路径

文章链接:代码随想录
题目链接:1971. 寻找图中是否存在路径

思路:并查集入门

class Solution {
private:int n = 200005;vector<int> father = vector<int> (n);void init(){for (int i = 0; i < n; i++) father[i] = i;}int find(int u){return u == father[u] ? u : father[u] = find(father[u]);}bool isSame(int u, int v){u = find(u);v = find(v);return u == v;}void join(int u, int v){u = find(u);v = find(v);if (u == v) return ;father[v] = u;}public:bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {init();for (int i = 0; i < edges.size(); i++){join(edges[i][0], edges[i][1]);}return isSame(source, destination);}
};

Leetcode684.冗余连接

文章链接:代码随想录
题目链接:684.冗余连接

思路:并查集入门,用于解决无向有环图问题

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

Leetcode685.冗余连接II

文章链接:代码随想录
题目链接:685.冗余连接II

思路:将有向图问题拆解成两个无向图有环问题。
另外注意const int n = 1005; n前需加const,否则用n初始化数组会报错,因为n 是一个可变的值

class Solution {
private:const int n = 1005;vector<int> father = vector<int>(n);void init(){for (int i = 0; i < n; i++){father[i] = i;}}int find(int u){return u == father[u] ? u : father[u] = find(father[u]);}bool isSame(int u, int v){u = find(u);v = find(v);return u == v;}void join(int u, int v){u = find(u);v = find(v);if (u == v) return;father[v] = u;}vector<int> getRemoveEdge(const vector<vector<int>>& edges){init();for (int i = 0; i < edges.size(); i++){if (isSame(edges[i][0], edges[i][1])) return edges[i];join(edges[i][0], edges[i][1]);}return {};}bool isTree(const vector<vector<int>>& edges, int i){init();for (int j = 0; j < edges.size(); j++){if (j == i) continue;if (isSame(edges[j][0], edges[j][1])) return false;join(edges[j][0], edges[j][1]);}return true;}public:vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {int inDegree[1005] = {0};for (int i = 0; i < edges.size(); i++){inDegree[edges[i][1]]++;}vector<int> vec;for (int i = edges.size() - 1; i >= 0; i--){if(inDegree[edges[i][1]] == 2) vec.push_back(i);}if (vec.size() > 0){if (isTree(edges, vec[0])) return edges[vec[0]];else return edges[vec[1]];}return getRemoveEdge(edges);}
};

图论第三天打卡,目前随想录上的图论问题刷完,加油!!!

这篇关于图论第三天|127. 单词接龙 841.钥匙和房间 463. 岛屿的周长 1971. 寻找图中是否存在路径 684.冗余连接 685.冗余连接II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

W外链微信推广短连接怎么做?

制作微信推广链接的难点分析 一、内容创作难度 制作微信推广链接时,首先需要创作有吸引力的内容。这不仅要求内容本身有趣、有价值,还要能够激起人们的分享欲望。对于许多企业和个人来说,尤其是那些缺乏创意和写作能力的人来说,这是制作微信推广链接的一大难点。 二、精准定位难度 微信用户群体庞大,不同用户的需求和兴趣各异。因此,制作推广链接时需要精准定位目标受众,以便更有效地吸引他们点击并分享链接

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题:墙体两侧特征混淆误匹配,导致建图和定位偏差,表现为过门跳变、外月台走歪等 ·解决思路:预期的根治方案IGICP需要较长时间完成上线,先使用切分地图的工程化方案,即墙体两侧切分为不同地图,在某一侧只使用该侧地图进行定位 方案思路 切分原理:切分地图基于关键帧位置,而非点云。 理论基础:光照是直线的,一帧点云必定只能照射到墙的一侧,无法同时照到两侧实践考虑:关

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

Java 连接Sql sever 2008

Java 连接Sql sever 2008 /Sql sever 2008 R2 import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.Statement; public class TestJDBC

寻找身高相近的小朋友

题目描述: 小明今年升学到小学一年级,来到新班级后发现其他小朋友们身高参差不齐,然后就想基于各小朋友和自己的身高差对他们进行排序,请帮他实现排序。 输入描述: 第一行为正整数H和N,0<H<200,为小明的身高,0<N<50,为新班级其他小朋友个数。第二行为N个正整数H1-HN,分别是其他小朋友的身高,取值范围0<Hi<200(1<=i<=N),且N个正整数各不相同。 输出描述: 输出

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop