代码随想录打卡Day58

今天一共三道题，前两道看题解的，最后一道自己AC的，总体不算特别难。

110.字符串接龙

这道题没什么思路，直接看的题解，这道题用广度优先搜索是最合适的，这里我也明白了一个道理，到凡涉及到最短路径问题，用BFS是最合适的，要么就找不到，一旦找到了，就一定是最短的。这道题的字符串字典用unordered_set来实现，用来存储strList中的字符串。此外，本题还需要定义一个哈希表，键为字符串字典中的各个字符串，值为从beginStr到该字符串的最短距离，当然，这个哈希表会在遍历的过程中逐步完善，而不是一开始定义就是完善的。
从beginStr出发，进行广度优先搜索，具体来说，先将beginStr入队，然后使用一个while循环，当队列为空时循环终止，在队头的字符串出队后，代表遍历到该字符串current_word，依次遍历字符串的每一个位置，每个位置上的字母依次用26个小写字母替换，判断替换后是否等于endStr，如果相等的话就直接输出哈希表中存储的当前字符串对应的距离+1，并直接结束主函数流程，而过不等于endStr，再判断组成的新字符串new_word是否在unordered_set中出现过，如果出现了，再判断哈希表中是否存在这个键，如果已经存在，就说明这个字符串被重复访问了，这是不被允许的，此时应该什么都不做，如果这个字符串出现在unordered_set但是不在哈希表中，说明这个字符串是第一次被访问，应该向哈希表中添加这个键，对应的值为hash[current_word] + 1，并且及时将new_word加入队列。如果while循环结束了都没有到达终点，说明永远也到不了了，直接输出0即可。

#include<iostream>
#include<vector>
#include<string>
#include <unordered_set>
#include <unordered_map>
#include <queue>using namespace std;int main(){int N;cin >> N;  //N行strList中的字符串string beginStr, endStr;cin >> beginStr >> endStr;unordered_set<string> strSet;  //字符串字典string str;for(int i = 0; i < N; i++){cin >> str;strSet.insert(str);  //将字符串依次加入字符串字典}unordered_map<string, int> visitMap;  //键为字符串字典中的字符串，值为从beginStr出发到达这个字符串的长度//初始化队列queue<string> My_Queue;My_Queue.push(beginStr);//初始化哈希表visitMap[beginStr] = 1;//开始循环遍历寻找路径while(!My_Queue.empty()){string current_word = My_Queue.front();My_Queue.pop();int path = visitMap[current_word];  //记录当前所探索的路径for(int i = 0; i < current_word.size(); i++){string new_word = current_word;//试探当前所在的字符串能否只改动一个字符就到达endStrfor(int j = 0; j < 26; j++){new_word[i] = 'a' + j;if(new_word == endStr){ //到达终点cout << path + 1 << endl;return 0;}if(strSet.find(new_word) != strSet.end()&& visitMap.find(new_word) == visitMap.end()){//在字符字典中出现,且从未被访问过visitMap[new_word] = path + 1;My_Queue.push(new_word);}}}}cout << 0 << endl;return 0;
}

105. 有向图的完全可达性

这道题目首先需要将图构建出来，由于涉及到状态转移，用邻接表来构建图是最合适的，用深度优先搜索和广度优先搜索都可以，这道题我用DFS来做。这道题的思路比较奇特，用dfs来做，先定义一个大小为N + 1的vector，其中下标1-N是我们要用到的，每到达一个节点，就将这个节点的值设置为true，说明从节点1出发，经过若干次转移可以到达当前节点，如果从节点1可以到达其他所有节点，则调用dfs函数后整个向量下标为1到下标为N的元素都应该为true。这道题的终止条件也很简单，当层层递归，到达的节点已经为true时，说明当前节点已经被访问过，再向下递归没有意义，因为还会再次回来，所以此时应该直接return ;否则将当前节点X标记为true,并跳转到X所能到达的其他节点。当递归结束以后，在主函数中检查下标从1到N的元素是否为true，只要出现一个false，就直接输出-1，并结束主函数，如果全为true，则在循环结束以后输出1.

#include<iostream>
#include<vector>
#include<list>using namespace std;void dfs(const vector<list<int>> &graph, int current, vector<bool> &visited);int main(){int N, K;cin >> N >> K;  //N个节点，K条边vector<list<int>> graph(N + 1);  //用邻接表来表示有向图//构造有向图for(int i = 1; i <= K; i++){int s, t;cin >> s >> t;graph[s].push_back(t);  //可以从s号节点到达t节点（单向）}//初始化一个访问向量，未被访问过就为falsevector<bool> visited(N + 1, false);dfs(graph, 1, visited);for(int i = 1; i < visited.size(); i++){if(!visited[i]){cout << -1 << endl;return 0;}}cout << 1 << endl;return 0;
}//深度优先
void dfs(const vector<list<int>> &graph, int current, vector<bool> &visited){//终止条件,当前节点在之前就已经被访问过，则搜索停止if(visited[current]) return ;visited[current] = true;for(int next : graph[current])  //遍历节点current所能到达的下一个节点dfs(graph, next, visited);
}

106. 岛屿的周长

这道题思路并不难想，这道题我用的BFS。先讨论最一般的情况，假设矩阵中的岛屿为孤岛，四周已经被矩阵内的水域包围，直接调用bfs或者dfs函数将该岛屿探索出来，但是在探索的过程中需要额外对下一地点为水域的情况判断，假设当前地点的下一个地点为水域，则说明当前地点为岛屿边缘，对整个岛屿的周长是有贡献的，因此需要及时将周长C加一，如果当前地点的下一个地点为陆地，则说明当前地点在该探索方向上对周长是没有贡献的，这种情况下周长无需改动。下面讨论一种特殊的情况，就是岛屿在地图边缘，有些陆地在进行BFS时会出现访问越界的情况，这种情况下，不能再简单地跳过当前循环，由于当前访问的地点一定是陆地，在向某一个方向探索时出现了访问越界，则说明该地点也处于岛屿边缘，该地点在当前的探索方向上对周长也是有贡献的，应视同下一位置为水域，周长也应该加一。和之前的题目一样，在主函数中遍历整个地图，只要遇到未访问的陆地，则开始调用bfs函数，将当前陆地所在的整个岛屿探索出来，当函数调用结束后，岛屿探索完成，周长也随之统计完成，直接将C输出即可。

#include<iostream>
#include<vector>
#include<queue>using namespace std;vector<vector<int>> dirs = {{0, 1},  //向右{0, -1}, //向左{-1, 0}, //向上{1, 0}   //向下
};
int C = 0;  //周长void bfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y);int main(){int N, M;cin >> N >> M;  //N行M列vector<vector<int>> graph(N, vector<int> (M));vector<vector<bool>> visited(N, vector<bool> (M, false));//构造地图矩阵for(int i = 0; i < N; i++){for(int j = 0; j < M; j++)cin >> graph[i][j];}for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){if(graph[i][j] == 1 && !visited[i][j])//遇到岛屿，开始搜索bfs(graph, visited, i, j);}}cout << C << endl;return 0;
}//广度优先搜索函数,调用时默认当前点为陆地
void bfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y){queue<pair<int, int>> My_Queue;My_Queue.push({x, y});visited[x][y] = true;while(!My_Queue.empty()){pair<int, int> current = My_Queue.front();My_Queue.pop();for(auto dir : dirs){int next_x = current.first + dir[0];int next_y = current.second + dir[1];if(next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size()){//越界访问 C++;continue;}if(graph[next_x][next_y] == 0)C++;if(graph[next_x][next_y] == 1 && !visited[next_x][next_y]){//下一个地点为未访问过的陆地My_Queue.push({next_x, next_y});visited[next_x][next_y] = true;}}}}

离训练营结束又近一步，加油加油加油！！