力扣算法刷题 Day 53

110 字符串接龙题目链接添加链接描述思路可以模拟成无向图的最短路径。两个相邻单词仅一位不同可以连一条边。关键点在于将点连起来以及使用广搜找到第一个终点即为最短路径。文章详解添加链接描述#includeiostream#includevector#includestring#includeunordered_set#includeunordered_map#includequeueusingnamespacestd;intmain(){string beginStr,endStr,str;intn;cinn;unordered_setstringstrSet;cinbeginStrendStr;for(inti0;in;i){cinstr;strSet.insert(str);}// 记录strSet里的字符串是否被访问过同时记录路径长度unordered_mapstring,intvisitMap;// 记录的字符串路径长度// 初始化队列queuestringque;que.push(beginStr);// 初始化visitMapvisitMap.insert(pairstring,int(beginStr,1));while(!que.empty()){string wordque.front();que.pop();intpathvisitMap[word];// 这个字符串在路径中的长度// 开始在这个str中挨个字符去替换for(inti0;iword.size();i){string newWordword;// 用一个新字符串替换str因为每次要置换一个字符// 遍历26的字母for(intj0;j26;j){newWord[i]ja;if(newWordendStr){// 发现替换字母后字符串与终点字符串相同coutpath1endl;// 找到了路径return0;}// 字符串集合里出现了newWord并且newWord没有被访问过if(strSet.find(newWord)!strSet.end()visitMap.find(newWord)visitMap.end()){// 添加访问信息并将新字符串放到队列中visitMap.insert(pairstring,int(newWord,path1));que.push(newWord);}}}}// 没找到输出0cout0endl;}105 有向图的完全联通题目链接添加链接描述思路要使用深搜由于是有向图且需要回溯且需要根据每个节点的相连的边去搜索因此使用邻接矩阵来存储图。dfs三部曲返回值和入口参数返回值void, 参数graph下一层数字key已访问过的节点数组终止当前节点已被访问返回单层搜索将当前搜索节点相连的边都加入队列依次向下搜素。文章详解添加链接描述// 写法一dfs 处理当前访问的节点#includeiostream#includevector#includelistusingnamespacestd;voiddfs(constvectorlistintgraph,intkey,vectorboolvisited){if(visited[key]){return;}visited[key]true;listintkeysgraph[key];for(intkey:keys){// 深度优先搜索遍历dfs(graph,key,visited);}}intmain(){intn,m,s,t;cinnm;// 节点编号从1到n所以申请 n1 这么大的数组vectorlistintgraph(n1);// 邻接表while(m--){cinst;// 使用邻接表 表示 s - t 是相连的graph[s].push_back(t);}vectorboolvisited(n1,false);dfs(graph,1,visited);//检查是否都访问到了for(inti1;in;i){if(visited[i]false){cout-1endl;return0;}}cout1endl;}106 岛屿周长题目链接添加链接描述思路避免惯性思维用不到搜索直接遍历就很简单总的陆地块数 * 4 - 相邻的边数 * 2文章详解添加链接描述#includeiostream#includevectorusingnamespacestd;intmain(){intn,m;cinnm;vectorvectorintgrid(n,vectorint(m,0));for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}intdirection[4][2]{0,1,1,0,-1,0,0,-1};intresult0;for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]1){for(intk0;k4;k){// 上下左右四个方向intxidirection[k][0];intyjdirection[k][1];// 计算周边坐标x,yif(x0// x在边界上||xgrid.size()// x在边界上||y0// y在边界上||ygrid[0].size()// y在边界上||grid[x][y]0){// x,y位置是水域result;}}}}}coutresultendl;}