字符串接龙
110. 字符串接龙 (kamacoder.com)
主要参考代码随想录 代码随想录 (programmercarl.com)
目标：得到从beginStr转变为endStr所需的最少步数
过程：每次变换一个字母，每次变换的结果要在strList中。
对于一个图来说，相当于我们有1个起点beginStr和一个终点endStr，以及strList中的N个字符串，然后我们需要找到路径来使得beginStr变成endStr，将beginStr连接到endStr的路径即为变化的过程，我们要最小化这个过程。
这里有两个问题：
- 图中的线是如何连在一起的。
- 如何确定当前路径最短。
对于线的连接，我们注意到每次只能变换一个字符，即我们需要判断是一个目标字符串与源字符串是否相差一个字符，若相差一个字符，则他们之间是连通的。
而判断路径最短，考虑使用广度优先算法，只要搜索到了结果，那得到的一定是最短路径，此外，注意这里计算的最短路径不是线的数目，而是节点的数目。
代码随想录里有两个点能方便计算：一是无向图需要标志位，来标记节点是否走过，使用set来检查字符串是否出现在字符串集合中较快。二是利用哈希表来映射字符串和路径长度。
具体代码如下，和代码随想录中结果一样。
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;int main(){int N;cin>>N; // 输入字符串数量 Nunordered_set<string> strSet; // 创建一个无序集合存储所有字符串string beginStr, endStr, str;cin >> beginStr >>endStr; // 输入起始字符串和目标字符串for(int i = 0; i < N; i++){cin>>str; // 输入 N 个字符串strSet.insert(str); // 将字符串插入集合}unordered_map<string , int> visitMap; // 创建一个无序映射记录字符串和对应的路径长度queue<string> Queue; // 创建一个队列用于 BFSQueue.push(beginStr); // 将起始字符串入队列visitMap.insert(pair<string,int>(beginStr, 1)); // 起始字符串路径长度为 1while(!Queue.empty()){ // 当队列不为空时进行 BFSstring word = Queue.front(); // 获取队列首部的字符串Queue.pop();int path = visitMap[word]; // 获取该字符串的路径长度for(int i = 0;i < word.size();i++){ // 遍历字符串的每个字符string newWord = word; // 创建一个新字符串，用于修改字符for(int j = 0; j < 26; j++){ // 遍历 'a' 到 'z'，ASCII码newWord[i] = 'a' + j; // 修改字符串的一个字符if(newWord == endStr){ // 如果新字符串是目标字符串cout<<path + 1<<endl; // 输出路径长度并结束程序return 0;}if(strSet.find(newWord)!= strSet.end() && visitMap.find(newWord) == visitMap.end()){// 如果新字符串在集合中且未被访问过visitMap.insert(pair<string,int>(newWord,path + 1)); // 记录新字符串和路径长度Queue.push(newWord); // 将新字符串入队列}}}}cout<< 0 <<endl; // 如果没有找到路径，输出 0return 0;
}
对每个字符串，长度定位L，在BFS的过程中，每个字符串都可能被访问一次，每个源字符串的每个字符都有修改的可能，共有26*L次操作，由于每个字符串只被访问一次，因此总的时间复杂度为O(N*26*L)。
对空间复杂度，主要需要一个集合、一个哈希表及一个队列，空间复杂度都为O(N*L)，总体空间复杂度为O(N*L)。
有向图的完全可达性
用广度优先搜索，对1的每个可达点进行遍历，并将可达点加入set，最后判断set的长度是否等于节点数即可。
#include <iostream>
#include <vector>
#include <unordered_set>
#include<queue>
using namespace std;int main(){int N,K;cin>>N>>K; // 输入节点总数 N 和边的总数 Kvector<vector<int>> dirgraph(K,vector<int>(2,0)); // 创建一个二维向量，用于存储有向图的边for(int i = 0 ; i < K; i++){cin>>dirgraph[i][0]>>dirgraph[i][1]; // 输入每条边的起始节点和终止节点}unordered_set<int> visited; // 创建一个无序集合，用于存储已访问的节点visited.insert(1); // 将起始节点 1 加入已访问集合queue<int> Queue; // 创建一个队列，用于 BFSQueue.push(1); // 将起始节点 1 加入队列while(!Queue.empty()){ // 当队列不为空时进行 BFSint x = Queue.front(); // 获取队列首部的节点Queue.pop(); // 出队列for(int i = 0; i < K;i++){ // 遍历所有的边if(dirgraph[i][0] == x && visited.find(dirgraph[i][1]) == visited.end()) {// 如果边的起始节点是 x 并且终止节点未被访问过visited.insert(dirgraph[i][1]); // 将终止节点加入已访问集合Queue.push(dirgraph[i][1]); // 将终止节点加入队列}}}if(visited.size()==N) // 如果已访问的节点数等于总节点数cout<<1<<endl;else{ // 否则cout<<-1<<endl;}return 0;
}
算法的时间复杂度为O(N*K),空间复杂度为O(N+K)。
岛屿的周长
emmm，想了半天dfs和bfs，发现并不需要。。。
代码随想录 (programmercarl.com)
遍历每一个空格，遇到岛屿就计算其上下左右的领域情况，若上下左右为0或超出区域，则是一条边。遍历完所有的空格和每个空格的领域，即得到结果。
#include <iostream>
#include <vector>
using namespace std;int result = 0; // 定义一个全局变量，用于存储岛屿周长int main() {int N,M;cin>>N>>M; // 输入网格的行数 N 和列数 Mvector<vector<int>> graph(N,vector<int>(M)); // 创建一个 N 行 M 列的二维向量，用于存储网格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){ // 如果当前单元格是土地if((i + 1) == N || graph[i+1][j] == 0) // 如果下方是网格边缘或水result++; // 结果计数器加 1if((i - 1) == -1 || graph[i-1][j] == 0) // 如果上方是网格边缘或水result++; // 结果计数器加 1if(j + 1 == M || graph[i][j + 1] == 0) // 如果右方是网格边缘或水result++; // 结果计数器加 1if(j - 1 == -1 || graph[i][j - 1] == 0) // 如果左方是网格边缘或水result++; // 结果计数器加 1}}}cout<<result<<endl; // 输出岛屿周长return 0;
}
算法的时间复杂度为O(4*N*M)，空间复杂度为O(1)。
