目录
Leetcode127. 单词接龙
思路：广搜搜出来直接就是最短路径，深搜还需要判断；广搜相当于先把这一层路径的单词下一步走法都扫出来再走下一步；而深搜找到一条路径就先走到头，再返回来走下一条路径，需要判断路径长度，麻烦
另外需要标记位，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.钥匙和房间
思路：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.冗余连接
思路：并查集入门，用于解决无向有环图问题
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);
}
};
图论第三天打卡，目前随想录上的图论问题刷完，加油！！！
