做快消品的网站,千助网站公司,网站页面框架设计影响用户,湛江人才网招聘信息网刷题记录 *110. 字符串接龙105. 有向图的完全可达性邻接矩阵邻接表 106. 岛屿的周长深搜简化代码 *110. 字符串接龙
题目地址
使用广搜。 本题相当于求最短路径#xff0c;因此使用广搜。如何应用广搜是一个难点#xff0c;因为题目给的是字符串而非图的表示#xff08;邻… 刷题记录 *110. 字符串接龙105. 有向图的完全可达性邻接矩阵邻接表 106. 岛屿的周长深搜简化代码 *110. 字符串接龙
题目地址
使用广搜。 本题相当于求最短路径因此使用广搜。如何应用广搜是一个难点因为题目给的是字符串而非图的表示邻接矩阵、邻接表因此需要自行构建连接关系。
题目要求每一步只能修改一个字符因此从起始字符串开始对字符串中的每一个字符进行修改修改后在输入的字符串列表中查找是否存在若存在则放入队列中用于广搜同时记录步数1。若修改后的字符串等于结束字符则直接输出当前步数1.
使用广搜时搜索的每一圈内的字符串所记录的步数是一致的。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n 2 ) O(n^2) O(n2)
// c
#includebits/stdc.h
using namespace std;int main(){string beginStr, endStr, str;int n;unordered_setstring strSet;cinn;cinbeginStrendStr;for(int i0; in; i){cinstr;strSet.insert(str);}// 记录访问过的路径以及路径长度unordered_mapstring, int visitMap;visitMap.insert({beginStr, 1});// BFSqueuestring que;que.push(beginStr);while(!que.empty()){string word que.front();que.pop();int path visitMap[word];// coutword: wordendl;// 更换单词里的一个字符for(int i0; iword.size(); i){string newWord word;// coutnewWord: newWordendl;for(int j0; j26; j){newWord[i] j a;// 可以到达结束字符则直接结束输出if(newWord endStr){coutpath1endl;return 0;}if(strSet.find(newWord)!strSet.end() visitMap.find(newWord) visitMap.end()){// visitMap[word] path 1;// 存入路径记录里visitMap.insert({newWord, path 1});// 入队 BFSque.push(newWord);// coutnewWordendl;}}}}cout0endl;return 0;
}105. 有向图的完全可达性
leetcode题目地址
使用深度优先遍历探查是否能够到达每个结点。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n 2 ) O(n^2) O(n2)
邻接矩阵
// c
#includebits/stdc.h
using namespace std;
int direction[][2] {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vectorvectorint matrix,vectorbool result,int x, int y){result[y] true;for(int i1; imatrix.size(); i){if(matrix[y][i] !result[i]) dfs(matrix, visited, result, y, i);}}
int main(){int n,k;cinnk;vectorvectorint matrix(n1, vectorint(n1, 0));vectorbool result(n1, false); // result[1] 1;int row,col;for(int i0; ik; i){cinrowcol;matrix[row][col] 1;}for(int j1; jn; j) {if(!result[j] matrix[1][j]){dfs(matrix, result, 1, j);}}for(int i2; in; i) {if(!result[i]){cout -1 endl;return 0;}}cout1endl;return 0;
}邻接表
// c
#includebits/stdc.h
using namespace std;
int direction[][2] {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vectorlistint matrix,vectorbool result, int x){result[x] true;listint keys matrix[x];for(int key: keys){if(!result[key]){dfs(matrix, result, key);}}}
int main(){int n,k;cinnk;vectorlistint matrix(n1);vectorbool result(n1, false); int row,col;for(int i0; ik; i){cinrowcol;matrix[row].push_back(col);}dfs(matrix, result, 1);for(int i1; in; i) {if(!result[i]){cout -1 endl;return 0;}}cout1endl;return 0;
}106. 岛屿的周长
题目地址
遍历图当计算每一个岛屿方格的外周长。
初始状态下单个方格的周长为4。若当前方格的上下左右四个方向有相邻的岛屿方格则减去相邻方格数重合边数即为当前方格的外周长。将所有岛屿方格的外周长求和即为本题答案。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n 2 ) O(n^2) O(n2)
深搜
// c
#includebits/stdc.h
using namespace std;
int direction[][2] {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vectorvectorint matrix,vectorvectorbool visited,int result, int x, int y){visited[x][y] true;// 单个方格(x,y)的周长int count 4;for(int i0; i4; i){int nextx x direction[i][0];int nexty y direction[i][1];if(nextxmatrix.size()|| nextymatrix[0].size()|| nextx0 || nexty0) {continue;}if(matrix[nextx][nexty]) {// 减去重合边count--;if(!visited[nextx][nexty]) dfs(matrix, visited, result, nextx, nexty);}}// coutx y countendl;result count;
}
int main(){int n,m;cinnm;vectorvectorint matrix(n, vectorint(m, 0));vectorvectorbool visited(n, vectorbool(m, false));for(int i0; in; i){for(int j0; jm; j){cinmatrix[i][j];// coutmatrix[i][j] ;}// coutendl;}int result0;for(int i0; in; i){for(int j0; jm; j){if(matrix[i][j] !visited[i][j]){dfs(matrix, visited, result, i, j);}}}coutresult;return 0;
}简化代码
其实无需深搜既可实现本题目标只需要查看每个岛屿单元格的外周长直接遍历邻接矩阵就可以实现。
时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( 1 ) O(1) O(1)
// c
#includebits/stdc.h
using namespace std;
int direction[][2] {0, 1, 0, -1, -1, 0, 1, 0};
int main(){int n,m;cinnm;vectorvectorint matrix(n, vectorint(m, 0));for(int i0; in; i){for(int j0; jm; j){cinmatrix[i][j];}}int result0;for(int i0; in; i){for(int j0; jm; j){if(matrix[i][j]){// 初始化单元格周长int count 4;// 查看四个方向for(int k0; k4; k){int nextx i direction[k][0];int nexty j direction[k][1];// 越界if(nextxmatrix.size()|| nextymatrix[0].size()|| nextx0 || nexty0) {continue;}if(matrix[nextx][nexty]) {// 减去重合边count--;}} // couti j countendl;result count;}}}coutresult;return 0;
}
