东莞南城网站制作,网站站制做,高端网站建设 引擎技,网址目录 Leetcode127. 单词接龙Leetcode841.钥匙和房间Leetcode463. 岛屿的周长Leetcode1971. 寻找图中是否存在路径Leetcode684.冗余连接Leetcode685.冗余连接II Leetcode127. 单词接龙 文章链接#xff1a;代码随想录 题目链接#xff1a;127. 单词接龙 思路#xff1a;广搜搜… 目录 Leetcode127. 单词接龙Leetcode841.钥匙和房间Leetcode463. 岛屿的周长Leetcode1971. 寻找图中是否存在路径Leetcode684.冗余连接Leetcode685.冗余连接II Leetcode127. 单词接龙 文章链接代码随想录 题目链接127. 单词接龙 思路广搜搜出来直接就是最短路径深搜还需要判断广搜相当于先把这一层路径的单词下一步走法都扫出来再走下一步而深搜找到一条路径就先走到头再返回来走下一条路径需要判断路径长度麻烦 另外需要标记位wordMap避免死循环
class Solution {
public:int ladderLength(string beginWord, string endWord, vectorstring wordList) {unordered_setstring wordSet(wordList.begin(), wordList.end());if (wordSet.find(endWord) wordSet.end()) return 0;unordered_mapstring, int wordMap;wordMap.insert(pairstring, int(beginWord, 1));queuestring 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(pairstring, int(newword, path 1));que.push(newword);}}}}return 0;}
};Leetcode841.钥匙和房间 文章链接代码随想录 题目链接841.钥匙和房间 思路dfs
class Solution {
public:void dfs(vectorvectorint rooms, vectorbool visited, int key){if (visited[key]) return;visited[key] true;for (int i : rooms[key]){dfs(rooms, visited, i);}}bool canVisitAllRooms(vectorvectorint rooms) {vectorbool 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(vectorvectorint 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;vectorint father vectorint (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, vectorvectorint 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;vectorint father vectorint(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:vectorint findRedundantConnection(vectorvectorint 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;vectorint father vectorint(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;}vectorint getRemoveEdge(const vectorvectorint 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 vectorvectorint 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:vectorint findRedundantDirectedConnection(vectorvectorint edges) {int inDegree[1005] {0};for (int i 0; i edges.size(); i){inDegree[edges[i][1]];}vectorint 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);}
};图论第三天打卡目前随想录上的图论问题刷完加油
