ToB企服应用市场:ToB评测及商务社交产业平台

标题: 图论第5天 [打印本页]
作者: 花瓣小跑    时间: 2024-6-24 19:07
标题: 图论第5天
 127.单词接龙
 需要cout看一下过程。
  1. #include <iostream>
  2. #include <queue>
  3. #include <stack>
  4. #include <unordered_map>
  5. #include <unordered_set>
  6. #include <vector>
  7. using namespace ::std;
  9. class Solution
  10. {
  11. public:
  12.     int ladderLength(string beginWord, string endWord, vector<string> &wordList)
  13.     {
  14.         unordered_set<string> wordSet(wordList.begin(), wordList.end()); // 换成unordered_set后查询速度增加
  15.         if (wordSet.find(endWord) == wordSet.end())
  16.             return 0;
  17.         unordered_map<string, int> visitMap; //<word，查询到的路径长度>
  18.         queue<string> que;
  19.         que.push(beginWord);
  20.         visitMap.insert(pair<string, int>(beginWord, 1));
  21.         while (!que.empty())
  22.         {
  23.             string cur_word = que.front();
  24.             que.pop();
  25.             int path = visitMap[cur_word];
  26.             for (int i = 0; i < cur_word.size(); i++)
  27.             {
  28.                 string new_word = cur_word;
  29.                 for (int j = 0; j < 26; j++)
  30.                 {
  31.                     new_word[i] = j + 'a';
  32.                     if (new_word == endWord)
  33.                         return path + 1;
  34.                     if (wordSet.find(new_word) != wordSet.end() && visitMap.find(new_word) == visitMap.end())
  35.                     {
  36.                         visitMap.insert(pair<string, int>(new_word, path + 1));
  37.                         que.push(new_word);
  38.                     }
  39.                 }
  40.                 cout << cur_word << endl;
  41.                 cout << i << endl;
  42.                 for (pair<string, int> x : visitMap)
  43.                 {
  44.                     cout << "visitMap[" << x.first << "] = " << x.second << "   ";
  45.                 }
  46.                 cout << endl;
  47.             }
  48.         }
  49.         return 0;
  50.     }
  51. };
  53. int main()
  54. {
  55.     Solution syz;
  56.     string beginWord = "hit", endWord = "cog";
  57.     vector<string> wordList;
  58.     wordList.push_back("hot");
  59.     wordList.push_back("dot");
  60.     wordList.push_back("dog");
  61.     wordList.push_back("lot");
  62.     wordList.push_back("log");
  63.     wordList.push_back("cog");
  64.     syz.ladderLength(beginWord, endWord, wordList);
  65.     return 0;
  66. }
复制代码
cout运行效果需要看一下，明白一下过程：
所有的word的字母都需要执行一次，以是是0、1、2，
hit 改 h是没有单词加入的，改i会有个hot，改t没有单词加入，以是visitMap里不变。hit这时候已经pop()。
hot改h，增加两个dot\lot，改o\t没有，hot.pop()。
竟然是先dot后lot，跟push顺有关。hot会先push “ d ” 后 push " l "
dot，d\o都没有，t改完，出现一个dog，g会继续往下走,dot.pop() 
lot，l\o都没有，出现log.pop()
这时候que里，front 是dog，然后是 log
dog直接知道cog。visitMap[dog] = 4，4 + 1 = 5
  1. hit
  2. 0
  3. visitMap[hit] = 1
  4. hit
  5. 1
  6. visitMap[hot] = 2   visitMap[hit] = 1
  7. hit
  8. 2
  9. visitMap[hot] = 2   visitMap[hit] = 1
  10. hot
  11. 0
  12. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  13. hot
  14. 1
  15. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  16. hot
  17. 2
  18. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  19. dot
  20. 0
  21. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  22. dot
  23. 1
  24. visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  25. dot
  26. 2
  27. visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  28. lot
  29. 0
  30. visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  31. lot
  32. 1
  33. visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
  34. lot
  35. 2
  36. visitMap[log] = 4   visitMap[dog] = 4   visitMap[dot] = 3   visitMap[lot] = 3   visitMap[hot] = 2   visitMap[hit] = 1
复制代码
广搜更得当这道题，会把所有大概性在起始点周边的大概性，一点点往外扩，不会造成走冤枉路。
图论看来一道题就要很刺激啊。 T _ T。明天摸鱼看能不能做两道吧。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4