自学内容网 自学内容网
自学内容网 > 正文

【代码随想录day53】【C++复健】 110. 字符串接龙；105. 有向图的完全可达性；106. 岛屿的周长

🕗 发布于 2024-12-10 15:20 宽度优先  算法  

110. 字符串接龙

卡哥：“大家可能会感觉 广搜不过如此，都刷出自信了。”

我：我不是我没有，别乱说嗷。

本题确实看了之后有一点思路，想到了算距离，也想对了第一步都是与beginStr的距离为1的元素，因此我想着加一个每个元素到beginStr的距离来判断第几次for循环中，能访问到哪些单词，但是这个想法有诸多问题，比如说单词A与beginStr的距离是2，那我还需要分析存不存在一个距离为1的单词B能够下一步转换成单词A，此时就变成了计算单词B与单词A的距离，那与beginStr的距离是2的条件也就没用了。

然后就去看了解析。看完之后，发现卡哥的BFS主要分三层循环：

  • 外层 while 循环：用于BFS遍历单词。
  • 中层 for 循环：遍历当前单词的每个字符位置。
  • 内层 for 循环：遍历字母表中的每个字母，进行字符替换。

然后思考了半天“需要写这么麻烦吗”的问题，最后感觉自己想不明白就去问了问GPT：

外层 while 循环

while (!que.empty()) {
    string word = que.front();
    que.pop();
    int path = visitMap[word];
  • 作用：这是BFS的核心循环，队列 que 中保存的是当前待访问的单词，每次从队列中取出一个单词，并继续搜索其邻居。path 保存了当前单词的路径长度。
  • 必要性：必须有这个循环才能逐步扩展从beginStr到endStr的路径。BFS是逐层遍历的，确保找到最短路径。

中层 for 循环

for (int i = 0; i < word.size(); i++) {
    string newWord = word;
  • 作用：遍历当前单词的每一个字符，准备替换字符以产生新的单词。这是为了尝试所有可能的一个字符变换。
  • 必要性：每个字符都需要被替换，因为题目要求每次变换一个字符。这个循环是必须的，用来生成所有可能的相邻词。

内层 for 循环

for (int j = 0 ; j < 26; j++) {
    newWord[i] = j + 'a';
    if (newWord == endStr) {
        cout << path + 1 << endl;
        return 0;
    }
  • 作用：遍历字母表中的每个字母，替换当前位置的字符。这是为了产生所有可能的字符替换。
  • 必要性：每次替换一个字符，这个内层循环也必须存在。它确保了对当前字符位的所有可能替换。

我主要的一个疑问在于，最后两个循环相当于每个字符都把26个字母都查了一遍，相当于26n的复杂度，我如果直接去遍历每个元素会不会更快一点？

答案是并不会，因为虽然我们遍历所有字符串只需要n的复杂度，但是后续我们还需要再判断这两个字符之间的距离是不是为1，此时需要再遍历想大于字符串长度*2次，实际复杂度是word.size()*n，所以只要字符串长度大于13就会更复杂？我是这么算的，当然也可能算错。

GPT如是说：

内层循环为什么要遍历 26 个字母

这个内层循环的目的是：对当前单词的每个字符位置尝试替换成26个字母中的每一个字母。我们之所以要做这个操作，而不是直接遍历字典中的所有单词，是因为字典中的每个单词与当前单词之间只有一个字符的差异。

具体原因：
  1. 每次只能修改一个字符：
    • 根据题意，你每次变换一个字符，这意味着从一个单词转换到另一个单词，只能有一个字符是不同的。你不能同时更改多个字符，否则就不满足题目的要求。
  2. 所有可能的字符替换：
    • 因为每个单词的字符都可能被替换为任意一个字母（a 到 z），所以你必须检查当前单词每个字符位置的 26 个可能替代字符。
  3. 遍历字典的效率问题：
    • 假设你直接遍历字典中的所有单词，检查哪些单词与当前单词只有一个字符不同，那你需要遍历整个字典，并对每个字典中的单词与当前单词进行比较。这种做法的时间复杂度较高，因为字典中可能有很多单词。
  4. 内层循环的作用是优化搜索空间：
    • 如果你直接遍历字典中的所有单词，你需要在每次循环中判断每个单词是否与当前单词有一个字符的差异，这可能需要比较多个单词。相比之下，直接遍历26个字母来替换字符，是直接生成所有可能的单词。这比逐个查字典要高效得多。

 

此外，就是看完整个思路之后，自己实现时的问题：

1. 访问判断条件有问题
else if (dict.find(top) != dict.end() && visited.find(top) != visited.end()) {
  • 问题：这里检查了 visited.find(top) != visited.end()，但这个条件意味着 top 已经被访问过了，而你想要检查的是 top 是否 未被访问，即它不在 visited 中。正确的应该是 visited.find(top) == visited.end()。
  • 解决方法：修改为 visited.find(top) == visited.end()，这样才能正确判断该单词是否已经被访问过。
2. 修改字符串时未恢复原字符
top[i] = j;
  • 问题：你在内层循环中替换了 top[i] 为新字符 j，但是没有恢复原字符。这样会导致同一字符位置被多个字母替换时，影响后续的判断。
  • 解决方法：你需要在每次内层循环结束时恢复原字符，避免修改对后续字符替换的影响。可以在替换之前保存字符，最后再恢复。
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<queue>
using namespace std;

int main(){
    int n;
    cin >> n;
    string beginStr, endStr;
    cin >> beginStr >> endStr;
    unordered_set<string> dict;
    string temp;
    for(int i=0; i<n; i++){
        cin >> temp;
        dict.insert(temp);
    }
    unordered_map<string, int> visited;
    visited.insert(pair<string, int>(beginStr, 1));
    queue<string> que;
    que.push(beginStr);
    while(!que.empty()){
        string top = que.front();
        que.pop();
        int pathlength = visited[top];
        for(int i=0; i<top.size(); i++){
            string temptop = top; 
            for(char j='a'; j<='z'; j++){
                temptop[i] = j;
                if(temptop == endStr){
                    cout << pathlength + 1;
                    return 0;
                }
                else if(dict.find(temptop) != dict.end() && visited.find(temptop) == visited.end()){
                    visited[temptop] = pathlength + 1;
                    que.push(temptop);
                }
            }
        }
        
    }
    cout << 0;
    return 0;
}

105. 有向图的完全可达性

本题复杂度上面比前面简单了不少，不过因为没写过类似的代码，导致没有什么思路，所以去看了解析的做法。一开始像岛屿问题一样把visited定义成了一个二维数组，并且传了x和y两个int参数，甚至在调用的时候还是按两层for循环然后调用dfs，但其实这些都没有必要，只要调用一遍dfs，visited数组一维的也已经足够了。

此外就是自己实现的时候，出现了一些小问题，比如在dfs里面写了这样一个代码：

for(int i=0; i<graph[start]; i++){

这个代码在graph[start]是一个list的情况下，这样写是会报错的，因为list并不支持下标访问。应该使用 for (int neighbor : graph[start]) 来遍历 graph[start] 中的每个邻居。

#include<iostream>
#include<vector>
#include<list>
using namespace std;

void dfs(int start, vector<list<int>>& graph, vector<bool>& visited){
    for(int i:graph[start]){
        if(!visited[i]){
            visited[i] = true;
            dfs(i, graph, visited);
        }
    }
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<list<int>> graph(n+1);
    int in, out;
    for(int i=0; i<k; i++){
        cin >> in >> out;
        graph[in].push_back(out);
    }
    vector<bool> visited(n+1);
    visited[1] = true;
    dfs(1, graph, visited);
    for(int i=1; i<=n; i++){
        if(visited[i] == false){
            cout << -1;
            return 0;
        }
    }
    cout << 1;
    return 0;
}

106. 岛屿的周长

看了卡哥的提示说“不要惯性思维”，不过还是稍微惯性思维了一点点。首先我的确想明白了这道题不需要dfs或者bfs，只要对每个格子进行一下遍历就能做出来。

不过还是习惯性的写了个visited数组，但在并非dfs和bfs的情况下，并不需要记录每个格子访问与否，只要遍历就行了。

除此之外思路上就没什么难度了，很容易就想出来了。

#include<iostream>
#include<vector>
using namespace std;

int dir[4][2] = {0,1,0,-1,1,0,-1,0};
int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> island(n, vector<int>(m));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> island[i][j];
        }
    }
    int length = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(island[i][j]){
                for(int k=0; k<4; k++){
                    int nextx = i + dir[k][0];
                    int nexty = j + dir[k][1];
                    if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m){
                        length++;
                    }
                    else if(!island[nextx][nexty]){
                        length++;
                    }
                }
            }
        }
    }
    cout << length;
    return 0;
}


原文地址：https://blog.csdn.net/yumenohimiko/article/details/144354472

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024