力扣算法刷题 Day 53
110 字符串接龙
题目链接
添加链接描述
思路
可以模拟成无向图的最短路径。两个相邻单词（仅一位不同）可以连一条边。关键点在于将点连起来以及使用广搜找到第一个终点即为最短路径。
文章详解
添加链接描述
#include<iostream>#include<vector>#include<string>#include<unordered_set>#include<unordered_map>#include<queue>usingnamespacestd;intmain(){string beginStr,endStr,str;intn;cin>>n;unordered_set<string>strSet;cin>>beginStr>>endStr;for(inti=0;i<n;i++){cin>>str;strSet.insert(str);}// 记录strSet里的字符串是否被访问过，同时记录路径长度unordered_map<string,int>visitMap;// <记录的字符串，路径长度>// 初始化队列queue<string>que;que.push(beginStr);// 初始化visitMapvisitMap.insert(pair<string,int>(beginStr,1));while(!que.empty()){string word=que.front();que.pop();intpath=visitMap[word];// 这个字符串在路径中的长度// 开始在这个str中，挨个字符去替换for(inti=0;i<word.size();i++){string newWord=word;// 用一个新字符串替换str，因为每次要置换一个字符// 遍历26的字母for(intj=0;j<26;j++){newWord[i]=j+'a';if(newWord==endStr){// 发现替换字母后，字符串与终点字符串相同cout<<path+1<<endl;// 找到了路径return0;}// 字符串集合里出现了newWord，并且newWord没有被访问过if(strSet.find(newWord)!=strSet.end()&&visitMap.find(newWord)==visitMap.end()){// 添加访问信息，并将新字符串放到队列中visitMap.insert(pair<string,int>(newWord,path+1));que.push(newWord);}}}}// 没找到输出0cout<<0<<endl;}105 有向图的完全联通
题目链接
添加链接描述
思路
要使用深搜，由于是有向图且需要回溯，且需要根据每个节点的相连的边去搜索，因此使用邻接矩阵来存储图。dfs三部曲：
- 返回值和入口参数：返回值：void, 参数：graph，下一层数字key，已访问过的节点数组
- 终止：当前节点已被访问，返回；
- 单层搜索：将当前搜索节点相连的边都加入队列，依次向下搜素。
文章详解
添加链接描述
// 写法一：dfs 处理当前访问的节点#include<iostream>#include<vector>#include<list>usingnamespacestd;voiddfs(constvector<list<int>>&graph,intkey,vector<bool>&visited){if(visited[key]){return;}visited[key]=true;list<int>keys=graph[key];for(intkey:keys){// 深度优先搜索遍历dfs(graph,key,visited);}}intmain(){intn,m,s,t;cin>>n>>m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>>graph(n+1);// 邻接表while(m--){cin>>s>>t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}vector<bool>visited(n+1,false);dfs(graph,1,visited);//检查是否都访问到了for(inti=1;i<=n;i++){if(visited[i]==false){cout<<-1<<endl;return0;}}cout<<1<<endl;}106 岛屿周长
题目链接
添加链接描述
思路
避免惯性思维，用不到搜索，直接遍历就很简单！总的陆地块数 * 4 - 相邻的边数 * 2
文章详解
添加链接描述
#include<iostream>#include<vector>usingnamespacestd;intmain(){intn,m;cin>>n>>m;vector<vector<int>>grid(n,vector<int>(m,0));for(inti=0;i<n;i++){for(intj=0;j<m;j++){cin>>grid[i][j];}}intdirection[4][2]={0,1,1,0,-1,0,0,-1};intresult=0;for(inti=0;i<n;i++){for(intj=0;j<m;j++){if(grid[i][j]==1){for(intk=0;k<4;k++){// 上下左右四个方向intx=i+direction[k][0];inty=j+direction[k][1];// 计算周边坐标x,yif(x<0// x在边界上||x>=grid.size()// x在边界上||y<0// y在边界上||y>=grid[0].size()// y在边界上||grid[x][y]==0){// x,y位置是水域result++;}}}}}cout<<result<<endl;}