847访问所有节点的最短路径

使用三个量来标记 分别是当前的位置，经过的位置，走过的路径长度。这题还有一个要点，使用二进制数的形式来表示经过的路径

  1. class Solution {
  2. public:
  3.     int shortestPathLength(vector<vector<int>>& graph) {
  4.         int n = graph.size();
  5.         queue<tuple<int, int, int>> q;
  6.         vector<vector<int>> seen(n, vector<int>(1 << n));
  7.         for (int i = 0; i < n; ++i) {
  8.             q.emplace(i, 1 << i, 0);//代表经过了第几位
  9.             seen[i][1 << i] = true;
  10.         }
  11.         int ans = 0;
  12.         while (!q.empty()) {
  13.             auto [u, mask, dist] = q.front();
  14.             q.pop();
  15.             if (mask == (1 << n) - 1) {//全是1，代表经过了所有节点
  16.                 ans = dist;//此时路径长度确定
  17.                 break;
  18.             }
  19.             // 搜索相邻的节点
  20.             for (int v: graph[u]) {
  21.                 // 将 mask 的第 v 位置为 1
  22.                 int mask_v = mask | (1 << v);
  23.                 if (!seen[v][mask_v]) {//减枝操作
  24.                     q.emplace(v, mask_v, dist + 1);
  25.                     seen[v][mask_v] = true;//经过的地方设为true；
  26.                 }
  27.             }
  28.         }
  29.         return ans;
  30.     }
  31. };
  32. //这里的主要的关于剪枝的想法，不只是处于相同的节点，还要经过的节点一样。放在题
  33. 目中就是说v和mask一样。如果题目要求只看终点而不是经过所有的路径的话，这里凡是经
  34. 过相同的节点都要剪枝。

934最短桥(用到三色法，层级)

非常标准的广度优先搜索的题目，找到最短的路径，因为是需要一层层的遍历的，所以需要先入先出的队列来进行遍历。深搜查找第一个岛屿的所有位置，然后使用bfs寻找第二个岛屿，并把过程经过的0赋值为2。

  1. class Solution {
  2. public:
  3.     vector<int> direction{-1, 0, 1, 0, -1};
  4. // 主函数
  5. int shortestBridge(vector<vector<int>>& grid) {
  6.     int m = grid.size(), n = grid[0].size();
  7.     queue<pair<int, int>> points;
  8. // dfs寻找第一个岛屿,并把1全部赋值为2
  9.     bool flipped = false;
  10.     for (int i = 0; i < m; ++i) {
  11.         if (flipped) break;
  12.         for (int j = 0; j < n; ++j) {
  13.             if (grid[i][j] == 1) {
  14.                 dfs(points, grid, m, n, i, j);
  15.                 flipped = true;
  16.                 break;
  17.             }
  18.         }
  19.     }
  20. // bfs寻找第二个岛屿,并把过程中经过的0赋值为2
  21.     int x, y;
  22.     int level = 0;
  23.     while (!points.empty()){
  24.         ++level;
  25.         int n_points = points.size();
  26.         while (n_points--) {//这个设计很关键，能够满足一层层遍历的要求。
  27.             auto [r, c] = points.front();
  28.             points.pop();
  29.             for (int k = 0; k < 4; ++k) {
  30.                 x = r + direction[k], y = c + direction[k+1];
  31.                 if (x >= 0 && y >= 0 && x < m && y < n) {
  32.                     if (grid[x][y] == 2) {
  33.                     continue;
  34.                 }
  35.                 if (grid[x][y] == 1) {
  36.                     return level;
  37.                 }
  38.                 points.push({x, y});
  39.                 grid[x][y] = 2;
  40.                 }
  41.             }
  42.         }
  43.     }
  44. return 0;
  45. }
  46. // 辅函数
  47. void dfs(queue<pair<int, int>>& points, vector<vector<int>>& grid, int m, int n
  48. , int i, int j) {
  49. if (i < 0 || j < 0 || i == m || j == n || grid[i][j] == 2) {
  50. return;
  51. }
  52. if (grid[i][j] == 0) {
  53. points.push({i, j});//存进去的都是从第一个岛屿出发所能到达的第一层为0的部分。
  54. return;
  55. }
  56. grid[i][j] = 2;
  57. dfs(points, grid, m, n, i - 1, j);
  58. dfs(points, grid, m, n, i + 1, j);
  59. dfs(points, grid, m, n, i, j - 1);
  60. dfs(points, grid, m, n, i, j + 1);
  61. }
  62. };

126. 单词接龙 II（dfs+bfs，必看）

  • 想要进行bfs，因为本题并没有图，所以第一步先建图

  • 注意维护一个哈希表方便查找。

    1. class Solution {
    2. public:
    3.   vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
    4.       vector<vector<string>> res;
    5.       // 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
    6.       unordered_set<string> dict = {wordList.begin(), wordList.end()};
    7.       // 修改以后看一下，如果根本就不在 dict 里面，跳过
    8.       if (dict.find(endWord) == dict.end()) {
    9.           return res;
    10.       }
    11.       // 特殊用例处理
    12.       dict.erase(beginWord);
    14.       // 第 1 步：广度优先遍历建图
    15.       // 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层
    16.       unordered_map<string, int> steps = {{beginWord, 0}};
    17.       // 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系
    18.       unordered_map<string, set<string>> from = {{beginWord, {}}};
    19.       int step = 0;
    20.       bool found = false;
    21.       queue<string> q = queue<string>{{beginWord}};
    22.       int wordLen = beginWord.length();
    23.       while (!q.empty()) {
    24.           step++;
    25.           int size = q.size();
    26.           for (int i = 0; i < size; i++) {
    27.               const string currWord = move(q.front());
    28.               string nextWord = currWord;
    29.               q.pop();
    30.               // 将每一位替换成 26 个小写英文字母
    31.               for (int j = 0; j < wordLen; ++j) {
    32.                   const char origin = nextWord[j];
    33.                   for (char c = 'a'; c <= 'z'; ++c) {
    34.                       nextWord[j] = c;
    35.                       if (steps[nextWord] == step) {//这里的意思是如果同一层也有相同的部分，就可以直接进入from里面，因为后面的dict.erase已经能够扩展出来的，防止后面又出现且距离更远。
    36.                          from[nextWord].insert(currWord);
    37.                       }
    38.                       if (dict.find(nextWord) == dict.end()) {
    39.                           continue;
    40.                       }
    41.                       // 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，且距离更远的单词，需要将它从 dict 中删除
    42.                       dict.erase(nextWord);
    43.                       // 这一层扩展出的单词进入队列
    44.                       q.push(nextWord);
    45.                       // 记录 nextWord 从 currWord 而来
    46.                       from[nextWord].insert(currWord);
    47.                       // 记录 nextWord 的 step
    48.                       steps[nextWord] = step;
    49.                       if (nextWord == endWord) {
    50.                           found = true;
    51.                       }
    52.                   }
    53.                   nextWord[j] = origin;
    54.               }
    55.           }
    56.           if (found) {
    57.               break;
    58.           }
    59.       }
    60.       // 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
    61.       if (found) {
    62.           vector<string> Path = {endWord};
    63.           dfs(res, endWord, from, Path);
    64.       }
    65.       return res;
    66.   }
    68.   void dfs(vector<vector<string>> &res, const string &Node, unordered_map<string, set<string>> &from,
    69.            vector<string> &path) {
    70.       if (from[Node].empty()) {//这是把里面所有路径都走一遍。
    71.           res.push_back({path.rbegin(), path.rend()});
    72.           return;
    73.       }
    74.       for (const string &Parent: from[Node]) {
    75.           path.push_back(Parent);
    76.           dfs(res, Parent, from, path);
    77.           path.pop_back();
    78.       }
    79.   }
    80. };

    386. 字典序排数（巧妙）

    非常巧妙的使用广搜的方法来写。

    1. class Solution {
    2. public:
    3.   vector<int> lexicalOrder(int n) {
    4.       vector<int> ret(n);
    5.       int number = 1;
    6.       for (int i = 0; i < n; i++) {
    7.           ret[i] = number;
    8.           if (number * 10 <= n) {//这里符合字典排序规则
    9.               number *= 10;
    10.           } else {
    11.               while (number % 10 == 9 || number + 1 > n) {//这个相当于向前退一位
    12.                   number /= 10;
    13.               }
    14.               number++;
    15.           }
    16.       }
    17.       return ret;
    18.   }
    19. };

    675. 为高尔夫比赛砍树（寻路算法，很重要）

  • 题目限定了我们只能按照从低到高的顺序进行砍树，并且图中不存在高度相等的两棵树，这意味着整个砍树的顺序唯一确定，就是对所有树进行高度排序，就是完整的路线。

  • 另外一个重要的性质是，点与点之间的最短路径，不会随着砍树过程的进程而发生变化，

  • 综上所述，砍树的路线唯一确定，当我们求出每两个相邻的砍树点最短路径，并进行累加就是答案，求最短路径使用BFS比较好。

    1. class Solution {
    2. public:
    3.   int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//四个方向
    4.   //BFS求最短路径，即可
    5.   int bfs(vector<vector<int>>& forest, int sx, int sy, int tx, int ty) {
    6.       if (sx == tx && sy == ty) {//当起点和终点是同一个位置的时候直接返回0
    7.           return 0;
    8.       }
    10.       int row = forest.size();
    11.       int col = forest[0].size();
    12.       int step = 0;
    13.       queue<pair<int, int>> qu;//队列的先进先出，保存每一层。
    14.       vector<vector<bool>> visited(row, vector<bool>(col, false));//记忆化         
    15.       qu.emplace(sx, sy);
    16.       visited[sx][sy] = true;//记忆化
    17.       while (!qu.empty()) {
    18.           step++;
    19.           int sz = qu.size();
    20.           for (int i = 0; i < sz; ++i) {
    21.               auto [cx, cy] = qu.front();
    22.               qu.pop();
    23.               for (int j = 0; j < 4; ++j) {
    24.                   int nx = cx + dirs[j][0];
    25.                   int ny = cy + dirs[j][1];
    26.                   if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
    27.                       if (!visited[nx][ny] && forest[nx][ny] > 0) {
    28.                           if (nx == tx && ny == ty) {
    29.                               return step;
    30.                           }
    31.                           qu.emplace(nx, ny);
    32.                           visited[nx][ny] = true;
    33.                       }
    34.                   }
    35.               }
    36.           }
    37.       }
    38.       return -1;
    39.   }
    41.   int cutOffTree(vector<vector<int>>& forest) {
    42.       vector<pair<int, int>> trees;
    43.       int row = forest.size();
    44.       int col = forest[0].size();
    45.       for (int i = 0; i < row; ++i) {
    46.           for (int j = 0; j < col; ++j) {
    47.               if (forest[i][j] > 1) {
    48.                   trees.emplace_back(i, j);//把所有的树按照高度排序
    49.               }
    50.           }
    51.       }
    52.       sort(trees.begin(), trees.end(), [&](const pair<int, int> & a, const pair<int, int> & b) {
    53.           return forest[a.first][a.second] < forest[b.first][b.second];
    54.       });
    56.       int cx = 0;
    57.       int cy = 0;
    58.       int ans = 0;
    59.       for (int i = 0; i < trees.size(); ++i) {
    60.           int steps = bfs(forest, cx, cy, trees[i].first, trees[i].second);//找两个点之间的最短距离
    61.           if (steps == -1) {//其中任意两个点无法到达，就直接返回-1
    62.               return -1;
    63.           }
    64.           ans += steps;
    65.           cx = trees[i].first;
    66.           cy = trees[i].second;
    67.       }
    68.       return ans;
    69.   }
    70. };

    0-1BFS 最短路径问题（双端队列）

    参考链接
    https://blog.csdn.net/Mr_dimple/article/details/116864052

    6081. 到达角落需要移除障碍物的最小数目(比较有细节)

  • 从起点开始，加入队列。

  • while队列非空，取队首元素，用这个节点更新其他节点。
  • 如果可以更新的话：
  • 1、边权为0，放到队首。（从边权为0的边走，不增加消耗，得多走这样的边）
  • 2、边权为其他，放到队尾。（增加消耗，少用）

（这样，队列前面的元素值一定比后面的元素值小（可以手动模拟下），每次求队首元素来更新相连的点的距离，完美的替代了优先队列的功能！

  1. const int d[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
  3. class Solution {
  4. public:
  5.     int minimumObstacles(vector<vector<int>>& grid) {
  6.         int n = grid.size(), m = grid[0].size();
  7.         vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
  8.         dis[0][0] = 0;
  9.         deque<pair<int, int>> dq;
  10.         dq.emplace_back(0, 0);
  11.         while (!dq.empty()) {
  12.             auto [i, j] = dq.front();
  13.             dq.pop_front();
  14.             for (int k = 0; k < 4; ++k) {
  15.                 int ni = i + d[k][0], nj = j + d[k][1];
  16.                 if (ni < 0 || ni >= n || nj < 0 || nj >= m || dis[ni][nj] < INT_MAX)//这里就暗含了记忆化的问题，只要便利过就不要再次便利，这种矩阵最好都使用BFS来写。因为队列前面的元素值一定比后面的小
  17.                     continue;
  18.                 dis[ni][nj] = dis[i][j] + grid[ni][nj];
  19.                 if (grid[ni][nj])
  20.                     dq.emplace_back(ni, nj);
  21.                 else
  22.                     dq.emplace_front(ni, nj);
  23.             }
  24.         }
  25.         return dis[n - 1][m - 1];
  26.     }
  27. };