算法学习——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出现,直接返回0
if (wordSet.find(endWord) == wordSet.end()) return 0;
// 记录word是否访问过
unordered_map<string, int> visitMap; // <word, 查询到这个word路径长度>
// 初始化队列
queue<string> que;
que.push(beginWord);
// 初始化visitMap
visitMap.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]文章来源:https://www.toymoban.com/news/detail-844971.html
提示
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ui, vi <= n文章来源地址https://www.toymoban.com/news/detail-844971.html
代码解析
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);
}
};
到了这里,关于算法学习——LeetCode力扣图论篇3(127. 单词接龙、463. 岛屿的周长、684. 冗余连接、685. 冗余连接 II)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!