土巴兔网站开发,开封景区网站建设方案,网站软件免费下载,一诺千金 网站建设算法学习——LeetCode力扣图论篇3 127. 单词接龙
127. 单词接龙 - 力扣#xff08;LeetCode#xff09;
描述
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - … - sk#xff1a;
每一对相…算法学习——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 i0 ; is1.size() ;i){if(s1[i] ! s2[i]) no_same_num;}return no_same_num;}void track_back(string beginWord, string endWord, vectorstring wordList , int indix, vectorbool path){for(int i0 ; iwordList.size() ;i){if(wordList[indix] endWord path[i] false){if(tmp_result result) result tmp_result;// coutendl;return;}else if(cheak(wordList[indix],wordList[i]) 1 path[i] false){// coutwordList[i] ;tmp_result ;path[i] true;track_back(beginWord,endWord,wordList,i,path);path[i] false;tmp_result--;}}}int ladderLength(string beginWord, string endWord, vectorstring wordList) {vectorbool path(wordList.size(),false);for(int i0 ; iwordList.size() ;i){if(cheak(beginWord,wordList[i]) 1 path[i]false){// coutwordList[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, vectorstring wordList) {// 将vector转成unordered_set提高查询速度unordered_setstring wordSet(wordList.begin(), wordList.end());// 如果endWord没有在wordSet出现直接返回0if (wordSet.find(endWord) wordSet.end()) return 0;// 记录word是否访问过unordered_mapstring, int visitMap; // word, 查询到这个word路径长度// 初始化队列queuestring que;que.push(beginWord);// 初始化visitMapvisitMap.insert(pairstring, 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返回path1// wordSet出现了newWord并且newWord没有被访问过if (wordSet.find(newWord) ! wordSet.end() visitMap.find(newWord) visitMap.end()) {// 添加访问信息visitMap.insert(pairstring, 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(vectorvectorint grid ,int x , int y){for(int i0 ; i4 ;i){int next_x x dir[i][0];int next_y y dir[i][1];if(next_x0||next_xm||next_y0||next_yn) result;else if(grid[next_x][next_y] 0) result;}return;}int islandPerimeter(vectorvectorint grid) {m grid.size();n grid[0].size();for(int i0 ; im ;i){for(int j0 ; jn ;j){if(grid[i][j] 1)dfs(grid,i,j);}}return result;}
};684. 冗余连接
684. 冗余连接 - 力扣LeetCode
描述
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1n) 的树中添加一条边后的图。添加的边的两个顶点包含在 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 , vectorint father){if(u father[u]) return father[u];father[u] find(father[u] , father);return father[u];}void join(int u , int v , vectorint father){u find(u , father);v find(v , father);if(u v) return;father[v] u;}bool same(int u , int v , vectorint father){u find(u , father);v find(v , father);return u v;}vectorint findRedundantConnection(vectorvectorint edges) {n edges.size() 1;vectorint father(n,0);for(int i0 ; in ; i)father[i] i;for(int i0 ; iedges.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 n0;int find(int u , vectorint father){if(u father[u]) return father[u];father[u] find(father[u],father);return father[u];}void join(int u , int v , vectorint father ){u find(u,father);v find(v,father);if(u v) return;father[v] u; }bool same(int u , int v , vectorint father){u find(u,father);v find(v,father);return u v;}bool tree_remove_edga(vectorvectorint edges , int delete_edge , vectorint father){for(int i0 ; in ;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;}vectorint get_remove_edge(vectorvectorint edges , vectorint father){for(int i0 ; in ;i){if(same(edges[i][0] , edges[i][1] , father) true) return edges[i];join(edges[i][0] , edges[i][1] , father);}return {};}vectorint findRedundantDirectedConnection(vectorvectorint edges) {n edges.size();vectorint father(n1,0);vectorint inDegree(n1,0);for(int i0 ; in ;i){father[i] i;inDegree[edges[i][1]] 1;}father[n] n;vectorint inDeg_2;for(int in-1 ; i0 ;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);}
};
