6.1 算法解释
深度优先搜索 和 广度优先搜索 是两种最常见的优先搜索方法,它们被广泛应用于图和树等结构中搜索。
6.2 深度优先搜索
深度优先搜索(depth-first search,DFS)在搜索到一个新的节点时,立即对该节点进行遍历;因此遍历需要用先入后出的栈实现,也可以用通过与栈等价的递归实现。
对于树结构而言,由于总是对新节点调用遍历,因此看起来向着更“深”的方向前进。
深度优先搜索也可以用来检测环路:记录每个遍历过的节点的父节点,若一个节点被再次遍历且父节点不同,说明有环。
有时可能需要对已经搜索过的节点进行标记,防止在遍历时重复搜索某个节点,这种做法叫做状态记录或记忆化。
一般来说,深度优先搜索类型的题可以分为主函数和辅函数。
- 主函数用于搜索所有的搜索位置,判断是否可以开始搜索,如果可以就在辅函数进行搜索。
- 辅函数则负责深度优先搜索的递归调用。
当然,也可以使用栈实现深度优先搜索,但因为递归和栈的原理相同,而递归相对容易实现,因此刷题时更推荐递归写法。
不过在实际工程中,栈可能是最好的选择。一是因为便于理解,二是因为不易出现递归栈满的情况。
695. 岛屿的最大面积(中等)
方法一:栈
-
题解
- 首先遍历 grid 的每一个位置,如果当前格子是陆地(grid[i][j] == 1),那么就对其进行深度优先搜索。
- 将当前格子修改为 0,这是为了确保之后不会重复遍历该位置。
- 接着,定义一个栈,存放陆地格子的坐标。
- 然后当前位置的坐标入栈,之后开始遍历栈内格子的四个方向,直到栈为空。对于四个方向的遍历,这里设置了一个二维数组,分别对应上下左右四个方向。每确定下一个要遍历的坐标,都需要判断它的边界条件:是否仍在 grid 的合法坐标内,且当前格子为陆地。
- 每遍历完一次栈,都需要确定当前最大的岛屿面积。
- 最后,当所有格子都遍历一遍后,返回的 area 就是最大的岛屿面积。
-
代码
class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { // 定义方向数组 vector<vector<int>> dir{{0,1}, {0,-1}, {1,0}, {-1,0}}; int m = grid.size(), n = m ? grid[0].size() : 0; int local_area , area = 0, x, y; for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ if(grid[i][j]){ local_area = 1; grid[i][j] = 0; // 确保不会重复搜索 stack<pair<int, int>> island; island.push({i, j}); while(!island.empty()){ auto [r, c] = island.top(); island.pop(); for(int k = 0; k < 4; ++k){ // 遍历 4 个方向 x = r + dir[k][0], y = c + dir[k][1]; if(x>=0 && x <= m-1 && y>=0 && y<=n-1 && grid[x][y] == 1){ grid[x][y] = 0; island.push({x, y}); local_area++; } } } area = max(area, local_area); } } } return area; } };
-
收获
- 思路很简单,需要学习一下模板,可以写起来会快很多。
- 注意不要忽略 记忆化 。
方法二:递归的第一种写法
-
题解
-
主函数遍历 grid 的每一个格子,判断是否可以搜索,如果可以的话,就调用辅函数 dfs 进行深度优先搜索;
-
辅函数 dfs 负责进行深度优先搜索。首先,递归结束的条件是: grid[i][j] == 0,那么不会再增加新的面积,返回 0。
如果递归不会结束,那么将 grid[i][j] 置为 0,防止重复搜索。
接着一样遍历该位置的四个方向,进行边界判断以及确定下一个位置是否也是陆地,如果是的话,就对该位置再次进行递归。
-
-
代码
class Solution { public: vector<vector<int>> dir{{0,1}, {0,-1}, {1,0}, {-1,0}}; int maxAreaOfIsland(vector<vector<int>>& grid) { int m = grid.size(), n = m ? grid[0].size() : 0; int area = 0; for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ if(grid[i][j]){ area = max(area, dfs(grid, i, j)); } } } return area; } int dfs(vector<vector<int>>& grid, int i, int j){ if(grid[i][j] == 0) return 0; grid[i][j] = 0; int x, y, area = 1; for(int k = 0; k < 4; ++k){ x = i + dir[k][0], y = j + dir[k][1]; if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y]){ area += dfs(grid, x, y); } } return area; } };
方法三:递归的第二种写法
-
题解
- 这种写法的主函数和第一种写法的主函数一致,不同之处在于辅函数。
- 辅函数递归结束的条件为:坐标越界 ,或者当前格子不是陆地,那么其面积为 0;
- 否则,先将该格子置为 0,然后直接对该格子的四个方向调用递归。
-
代码
class Solution { public: int maxAreaOfIsland(vector<vector<int>>& grid) { int m = grid.size(), n = m ? grid[0].size() : 0; int area = 0; for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ if(grid[i][j]){ area = max(area, dfs(grid, i, j)); } } } return area; } int dfs(vector<vector<int>>& grid, int i, int j){ if(i<0 || i >= grid.size() || j<0 || j >= grid[0].size() || grid[i][j] ==0) return 0; grid[i][j] = 0; return 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) + dfs(grid, i, j+1) + dfs(grid, i, j-1); } };
547. 省份数量(中等)
-
题解
- isConnected 每一行(列)代表一个节点,它的每列(行)代表是否存在相邻节点。
- 这一题中,一共有 n 个节点,每个节点最多拥有 n 条边。因此,设置一个数组 visited,用于标记已经访问过的节点。
- 首先,对每个节点进行遍历,如果该节点 A 未被访问过,那么就对它进行搜索,看是否存在相邻节点。在主函数中能够进行搜索的节点,一定没有在辅函数中进行搜索过,因此能形成自己的一个圈,即
ans++
; - 判断是否存在相邻节点的方法也很简单,搜索该节点(这一行)的每个列,如果当前位置的节点 B 未被访问过,同时,它与节点 A 存在联系,即 isConnected[i][k] == 1,那么说明它们是相邻节点。此时,对节点 B 继续搜索。
-
代码
class Solution { public: int findCircleNum(vector<vector<int>>& isConnected) { int ans = 0; int n = isConnected.size(); vector<bool> visited(n, false); // 标记这个点是否被访问过 for(int i=0; i<n; ++i){ if(!visited[i]){ dfs(isConnected, i, visited); ans++; } } return ans; } void dfs(vector<vector<int>>& isConnected, int i, vector<bool>& visited){ visited[i] = true; for(int k=0; k<isConnected.size(); ++k){ // 该点未被访问过,且两个点之间存在连接 if(!visited[k] && isConnected[i][k]==1){ dfs(isConnected, k, visited); } } } };
-
收获
- 这道题和上一道题的思路还是有点不一样的,我总以为这类型的题都会像上一题一样,对 1 / 0进行连续成块地搜索。然而,这道题用到了访问数组,思路清晰简单。
417. 太平洋大西洋水流问题(中等)
-
思路
- 虽然题目要求的是满足向下流能到达两个大洋的位置,如果对所有位置进行搜索,那么在不剪枝的情况下复杂度会很高。因此可以反过来想,从两个大洋开始向上流,这样只需要对矩形的四条边进行搜索。搜索完成之后,只需遍历一次矩阵,满足条件的位置即为两个大洋向上流都能到达的位置。
- 定义两个矩阵
can_reach_p
和can_reach_a
,它们分别记录两个大洋能够到达的位置; - 接着,按行遍历
heights
的第一列和最后一列,分别对应两个大洋;同理,按列遍历heights
的第一行和最后一行,以它们作为起点进行搜索。 - 在搜索过程中(即辅函数 dfs),终止条件是:该位置被标记为 can_reach ,那么说明可以达到这个位置。否则将该位置标记为 can_reach ,然后对它上下左右四个方向进行搜索。
- 当搜索结束之后,回到主函数,判断同时满足 can_reach_p 和 can_reach_a 的位置,放入到答案数组 ans 并返回。
-
代码
class Solution { public: vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { int m = heights.size(), n = heights[0].size(); vector<vector<bool>> can_reach_p(m, vector<bool>(n, false)); vector<vector<bool>> can_reach_a(m, vector<bool>(n, false)); vector<vector<int>> ans; for(int i=0; i<m ;++i){ dfs(heights, i, 0, can_reach_p); dfs(heights, i, n-1, can_reach_a); } for(int j=0; j<n; ++j){ dfs(heights, 0, j, can_reach_p); dfs(heights, m-1, j, can_reach_a); } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(can_reach_a[i][j] && can_reach_p[i][j]){ ans.push_back(vector<int> {i, j}); } } } return ans; } void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& can_reach){ if(can_reach[i][j]) return ; can_reach[i][j] = true; int x, y; for(int k=0; k<4; ++k){ int x = i + dir[k][0], y = j + dir[k][1]; if(x >= 0 && x < heights.size() && y >= 0 && y < heights[0].size() && heights[i][j] <= heights[x][y]){ dfs(heights, x, y, can_reach); } } } };
-
收获
- 这道题要反其道而行之,不过总体思路都差不多,从一个点出发,然后一直搜索,直到这条路无法成功再返回上一层。这里用到两个标记数组,遍历时也分成太平洋和大西洋两种情况,方便处理。
总结
-
深度优先搜索
思想:从一个位置出发,沿着一条路一直搜索,直到这条路没办法走通再返回上一层,继续搜索。
关键在于:
- 防止重复访问的数组,可以是数组本身,也可以另外设立一个(
visited
)或多个数组(can_reach_p
和can_reach_a
); - 辅函数 dfs 的返回值:如果只是为了标记访问数组,那么直接在访问数组上操作,返回 void ;如果每一趟搜索需要记录当前的值,那么就需要返回当前的值。
- 辅函数 dfs 的终止条件:通常是该位置已经被访问过。
- 防止重复访问的数组,可以是数组本身,也可以另外设立一个(
6.3 回溯法
回溯法是优先搜索的一种特殊情况,又称为试探法,常用于需要记录节点状态的深度优先搜索。通常来说,排列、组合、选择类问题,使用回溯法比较方便。
回溯法的核心是回溯。在搜索到某一节点的时候,如果我们发现当前节点(及其子节点)不是需求目标,我们回退到原来的节点继续搜索,并且把当前节点修改的状态还原。
在具体的写法上,它与普通的深度优先搜索一样,都有 「修改当前节点状态」-> 「递归子节点」的步骤,不过还多了回溯的步骤,变成了「修改当前节点状态」-> 「递归子节点」-> 「回改当前节点状态」。
回溯法有两个诀窍,一是按引用传状态,二是所有的状态修改在递归完成后回改。
回溯法修改一般有两种情况,一种是修改最后一位输出,比如排列组合;一种是修改访问标记,比如矩阵里搜字符串。
46. 全排列(中等)
-
题解
- 每一个结点表示了求解全排列问题的不同的阶段,这些阶段通过变量的「不同的值」体现,这些变量的不同的值,称之为「状态」;
- 在「回头」以后,状态变量需要设置成为和先前一样,因此在回到上一层结点的过程中,需要撤销上一次的选择,这个操作称之为「状态重置」,回改到上一层节点的状态;
- 首先,这棵树除了根结点和叶子结点以外,每一个结点做的事情其实是一样的,即:在已经选择了一些数的前提下,在剩下的还没有选择的数中,依次选择一个数,这显然是一个递归结构;
- 递归的终止条件:一个排列中的数字已经选够了,因此定义变量 level 来表示当前已经选择的数字个数。
- 具体来说,假设我们已经填到第 level 个位置,那么 nums 数组中 [0,level-1]是已填过的数的集合,[level , n -1]是待填的数的集合。我们肯定是用[level ,n-1]里的数去填第 level 个数,假设待填的数的下标为 i,那么填完以后我们将第 i 个数和第 level 个数交换,即能使得在填第 level+1 个数的时候 nums 数组的[0, level] 部分为已填过的数,[level+1,n-1]为待填的数,回溯的时候交换回来即能完成撤销操作。
- 比如,有 [2,5,8,9,10] 这5个数要填入,已经填了 [8,9] 两个数,那么这个数组目前为[8,9 | 2,5,10] 。假设第三个位置要填 10,为了维护数组,将 2 和 10 交换,保证数组继续保持分隔符左边的数已经填过,右边的待填 ,即 [8,9,10 | 2,5];回溯的时候,将 2 和 10 交换回来,就撤销了之前的操作。
-
代码
class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> ans; backtracking(nums, 0, ans); return ans; } void backtracking(vector<int> &nums, int level, vector<vector<int>> &ans){ // l 表示当前选了几个数 if(level == nums.size()){ ans.push_back(nums); return ; } for(int i=level; i<nums.size(); ++i){ swap(nums[i], nums[level]); // 修改当前节点状态 backtracking(nums, level+1, ans); // 递归子节点 swap(nums[i], nums[level]); // 回改当前节点状态 } } };
-
收获
- 不太熟悉递归和回溯,这类型的题需要多加练习。
77. 组合(中等)
-
思路
-
和上一道例题类似,对于组合的问题,也可以进行回溯,把当前的数字加入结果中。
-
首先画出树形结构。可以发现如下递归结构:
- 如果组合里有 1,那么需要在[2,3,4] 里再找 1 个数;
- 如果组合里有 2,那么需要在[3,4] 里再找 1 个数。注意: 这里不能再考虑1,因为包含1的组合,在第1种情况中已经包含;
- 依次类推,以上描述体现的递归结构是:在以n结尾的候选数组里,选出若干个元素。画出递归结构如下图:
-
递归的终止条件:当数组元素个数等于题目给出的 k 时,说明已经找到满足题目要求的数组。
-
否则,从 1 开始进行搜索,先把 1 填入,然后对这个子节点进行递归,下一次填入的数字将会是 2,此时数组为 [1,2],满足终止条件,退回上一步,将 2 弹出,也就是回改当前节点状态。依次类推,直到将所有节点都遍历一遍。
-
-
代码
class Solution { public: vector<vector<int>> combine(int n, int k) { vector<vector<int>> ans; vector<int> nums(k, 0); backtracing(n, 1, k, ans, nums, 0); return ans; } void backtracing(int n, int pos, int k, vector<vector<int>>& ans, vector<int>& nums, int count){ // pos 表示当前位置要放入的数字 // count 表示当前数组里的元素个数 if(count == k){ // 当数组个数已经达到 k // 说明已经找到一个符合要求的数组 ans.push_back(nums); return ; } for(int i=pos; i<=n; ++i){ nums[count++] = i; // 修改当前节点状态 backtracing(n, i+1, k, ans, nums, count); // 递归子节点 count--; // 回改当前节点状态 } } };
-
收获
- 上一题是排列问题,所以通过交换位置来修改节点状态;这一题是组合问题,通过将当前数字加入结果来修改节点状态。
- 将数字加入数组,我最近习惯于用push_back,然而有时候通过下标赋值,或许更方便,因为这样回退的时候只需要将下标 -1。
- 如果要在子函数中修改主函数的参数,一定记得加上 引用 & 。
79. 单词搜索(中等)
-
思路
- 和排列、组合问题不同,这一题修改的是访问标记;在对任意位置进行深度优先搜索的时候,先标记当前位置为已访问,以避免重复遍历(如防止向右搜索后又向左返回);在完成所有可能的搜索后,再回改当前的位置为未访问,防止干扰其他位置搜索到当前位置(因为这道题的搜索结果存在先后关系)。
-
代码
class Solution { public: // vector<vector<int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool exist(vector<vector<char>>& board, string word) { bool find = false; int m = board.size(), n = board[0].size(); vector<vector<bool>> visited(m, vector<bool>(n, false)); for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ backtracing(i, j, board, word, find, visited, 0); } } return find; } void backtracing(int i, int j,vector<vector<char>>& board,string word,bool& find,vector<vector<bool>>& visited, int pos){ if(i<0 || i>=board.size() || j<0 || j>=board[0].size() || visited[i][j] || find || board[i][j] != word[pos]) return ; if(pos == word.size() - 1){ find = true; return ; } visited[i][j] = true; backtracing(i+1, j, board, word, find, visited, pos+1); backtracing(i-1, j, board, word, find, visited, pos+1); backtracing(i, j+1, board, word, find, visited, pos+1); backtracing(i, j-1, board, word, find, visited, pos+1); visited[i][j] = false; } };
-
收获
- 这道题 11.18 的时候做过,但是当时不怎么会。
- 这一道题和深度优先搜索很像,不同的是:深度优先修改了访问标记,防止重复搜索,而这道题是先将访问标记修改为 true,在完成所有可能的搜索后,再将其回改为 false,因为之后有可能再搜索到这个位置。
51. N 皇后(困难)
-
题解
- 这道题也是选择,和上一题一样,设置并修改状态数组,不同的是,上一题设置了一个二维数组记录状态,这一题设置了多个访问数组:行、列、左斜、右,记录它们是否存在皇后。由于本题有一个隐藏条件,即满足条件的结果中每一行或列有且仅有一个皇后,所以如果我们对每一行遍历插入皇后,就不需要对行建立访问数组,因此只需要设置三个访问数组:列、左斜、右斜。
-
代码
class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> ans; vector<string> board(n, string(n, '.')); // 定义了三个访问数组 vector<bool> column(n, false), ldiag(2*n-1, false), rdiag(2*n-1, false); // 按行遍历 backtracing(n, ans, board, column, ldiag, rdiag, 0); return ans; } void backtracing(int n, vector<vector<string>>& ans, vector<string>& board, vector<bool>& column, vector<bool>& ldiag, vector<bool>& rdiag, int row){ // 每次遍历完一遍行 说明得到了一个答案 if(row == n){ ans.push_back(board); return ; } // i 表示 column for(int i=0; i<n ; ++i){ if(column[i] || ldiag[n-row+i-1] || rdiag[row+i]) continue; // 修改当前状态 board[row][i] = 'Q'; column[i] = ldiag[n-row+i-1] = rdiag[row+i] = true; // 递归子节点 backtracing(n, ans, board, column, ldiag, rdiag, row+1); // 回改至当前的状态 board[row][i] = '.'; column[i] = ldiag[n-row+i-1] = rdiag[row+i] = false; } } };
-
收获
- 这道题和上一道题很像,不同的是使用了多个访问数组,和 6.2 的最后一道练习题有异曲同工之妙,它也是在上一题的思路上使用多个数组。
- 这里对于 ldiag 和 rdiag 的下标,可以通过找规律确定;
-
vector<string> board(n, string(n, '.'))
,感觉类似于二维的字符串数组,一个字符串里嵌套 n 个字符串。 - 辅函数
backtracing
的终止条件是:n == row
,即遍历了所有行就得到一种答案。因为是递归,最后会回到row=0, i=0
开始第二轮的遍历(找下一个可能的结果)。
总结
-
回溯法辅函数
backtracing()
,通常都是返回 void ,直接调用主函数的引用对数组进行修改。核心思想由三个步骤组成:「修改当前节点状态、递归子节点、回改当前节点状态」。 -
分为 排列、组合 和 选择三种题型:
- 排列:回溯的是交换位置 [题 46];
- 组合:回溯的是 是否把当前的数字加入结果 [题 77];
- 选择:修改访问标记,访问数组既可以是单个[题 79],也可以是多个[题 51]。
6.4 广度优先搜索
广度优先搜索(BFS),一层层进行遍历,因此需要使用先入先出的队列。由于是按层次进行遍历的,广度优先搜索时按照“广”的方向进行遍历,也常常用来处理最短路径问题。
934.最短的桥(中等)
-
思路
-
由于 0 代表水域,1 代表陆地,要区分两个岛屿,所以,在遍历 grid 矩阵的时候,只要第一次发现了某个格子为 1,则将发现的新大陆进行编号,即:将 1 变为 2 。
-
首先通过 DFS 的方式寻找第一个岛屿。
- 在深度遍历的过程中,如果我们发现了某个格子为 0,则说明已经遍历到了岛屿的边缘部分,将其放入到队列 points 中,points 中保存着 int 数组,队列中的每个数组长度都是2,即: int[0]保存行,int[1] 保存列。
- 如果发现某个格子为 1 ,说明该格子是岛屿的一部分,那么继续向它的四个方向递归遍历,确保能找到完整的第一个岛屿;
- 如果某个格子为 2,说明这个格子已经遍历过了,由于我们使用了 DFS ,意味着该格子的四个方向肯定也递归过了,因此该递归结束,回到上一层递归;
-
在找到第一个岛屿后,我们使用 BFS,查询其与第二个岛屿之间的距离。由于队列中保存了第一个岛屿的所有“边缘格子”,那么接下来就需要开启 while 循环,对外进行一层的岛屿扩充操作。遍历每个“边缘格子”,再分别从上/下/右/左,四个方向去查看相邻的格子。
- 如果发现是 0,则表明是新的一层边缘格子,将其赋值为 2,并将其加入到队列中,用于下一次while循环。
- 如果发现是 1,说明已经与另一个岛屿接壤了,返回扩展层数即可。
- 如果发现是 2 ,说明遍历到第一个岛屿了,直接遍历下一个位置。
-
-
代码
class Solution { public: int shortestBridge(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; queue<pair<int, int>> points; bool flipped = false; for(int i=0; i<m; ++i){ if(flipped) break; for(int j=0; j<n; ++j){ // 使用dfs 将1均变成2 if(grid[i][j] == 1){ dfs(points, grid, i, j); flipped = true; break; } } } // 使用bfs寻找第二个岛屿 int x, y; int level = 0; while(!points.empty()){ ++ level; int n_points = points.size(); while(n_points--){ auto [r, c] = points.front(); points.pop(); for(int k=0; k<4; ++k){ x = r + dir[k][0], y = c + dir[k][1]; if(x>=0 && x<m && y>=0 && y<n){ if(grid[x][y] == 1){ return level; } else if(grid[x][y] == 0){ grid[x][y] = 2; points.push({x, y}); } else if(grid[x][y] == 2){ continue; } } } } } return 0; } void dfs(queue<pair<int, int>>& points, vector<vector<int>>& grid, int i, int j){ if(i<0 || i>=grid.size() || j<0 || j>=grid[0].size() || grid[i][j]==2) return ; // 如果遇到0,说明可能是路径之一 保存用于之后的遍历 if(grid[i][j] == 0){ points.push({i, j}); return ; } grid[i][j] = 2; dfs(points, grid, i+1, j); dfs(points, grid, i-1, j); dfs(points, grid, i, j+1); dfs(points, grid, i, j-1); } };
-
收获
- 广度优先遍历理解起来不难,队列的操作和栈也有些类似,不过队列的第一个元素是
queue.front()
。这道题思路也比较难,先用了 DFS 查找第一个岛屿,使用 BFS 查找第二个岛屿与第一个岛屿的最短距离。
- 广度优先遍历理解起来不难,队列的操作和栈也有些类似,不过队列的第一个元素是
126. 单词接龙 II(困难)
-
题解
- 我们可以把初始字符串、终止字符串、以及单词表中所有的字符串都想象成节点。如果两个字符串只有一个字符不同,那么它们相连。因为题目要求输出修改次数最少的所有修改方式,因此使用 BFS ,求得起始节点到终止节点的最短距离。
- 同时使用了一个小技巧:双向搜索 。并不是直接从起始节点进行BFS ,而是每轮遍历都从起始节点和终点节点的单词列表中,选择较少单词的列表进行BFS,这样可以减少搜索的总节点数。
- 搜索过程的具体思想见代码注释。
- 在搜索结束后,需要通过回溯,重建所有可能的最短路径。
-
代码
class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { vector<vector<string>> ans; // 因为需要快速判断扩展的单词是否出现在WordList中 // 因此使用哈希表提高效率 unordered_set<string> dict; dict.insert(wordList.begin(), wordList.end()); // 判断 endWord 是否出现在哈希表 if(!dict.count(endWord)) return ans; // 特殊用例处理 // 确保beginWord不在wordList - 题目要求 // 确保endWord不在WordList - 否则对于以下用例会重复输出答案 // "a" "c" ["a","b","c"] dict.erase(beginWord); dict.erase(endWord); // 开始进行 BFS // 定义两个无序集合 分别保存从beginWord/endWord出发变换的字符串列表 unordered_set<string> q1{beginWord}, q2{endWord}; // <key:当前字符串, 由key可以变换的单词列表> unordered_map<string, vector<string>> next; // reversed=false:从beginWord出发变换 // reversed=true:从endWord出发变换 bool reversed=false, found=false; while(!q1.empty()){ // q 保存 当前的单词可以变换到的单词列表 unordered_set<string> q; for(const auto &w : q1){ // 将当前单词保存在 w // 对 s 的每一位替换成26位的小写字母 string s = w; for(int i=0; i<s.size(); ++i){ // 保存要修改的字符 用于后续恢复 char ch = s[i]; for(int j=0; j<26; ++j){ s[i] = j + 'a'; if(q2.count(s)){ // 如果q2出现了s 说明此时已经变换到endWord // reversed=true:说明从后往前,因此是将w插入到s的单词列表(反向操作) // reversed=false:从前往后,因此是将s(变换后)插入到w(未变化)的单词列表 reversed? next[s].push_back(w) : next[w].push_back(s); found = true; } if(dict.count(s)){ // 如果dict出现s 说明变换后的单词在WordList中 reversed? next[s].push_back(w) : next[w].push_back(s); // 将其加入到q 用于后续遍历 q.insert(s); } } s[i] = ch; // 恢复该字符 遍历下一种可能的情况 } } if(found) break; // 要保证最短 因此单词不可以重复出现 // 删除WordList中已经出现过的单词 for(const auto &w : q){ dict.erase(w); } // 如果 q 的单词比 q2 少 // 那么应该遍历 q if(q.size() <= q2.size()){ q1 = q; }else{ // 如果 q2 的单词少 则遍历 q2 // 需要颠倒顺序 reversed = !reversed; q1 = q2; q2 = q; } } if(found){ // 如果能够找到 那么回溯 重建这条最短路径 vector<string> path = {beginWord}; backtracking(beginWord, endWord, next, path, ans); } return ans; } void backtracking(const string& beginWord,const string& endWord, unordered_map<string, vector<string>>& next, vector<string>& path, vector<vector<string>> &ans){ if(beginWord == endWord){ ans.push_back(path); return ; } for(const auto &s : next[beginWord]){ // 修改当前节点状态 path.push_back(s); // 回溯子节点 backtracking(s, endWord, next, path, ans); // 回改当前节点状态 path.pop_back(); } } };
-
收获
- 这道题很难,看了题解勉强看懂。不过这道题有一个 bug,由于LeetCode修改了样例,导致该题解会超时,不过先把这道题的思想理清楚即可。
6.5 练习
130. 被围绕的区域(中等)
-
题解
- 由于边界的 ‘O’ 肯定不会填充为 ‘X’ ,因此可以从边界的 ‘O’ 出发,对于可以到达的 ‘O’ ,说明它与边界的 ‘O’ 相连 ,不可能被 ‘X’ 全包围,此时将遍历到的 ‘O’ 修改为 ‘#’ ;
- 因此,对数组 board 的四条边进行遍历,如果该格子为 ‘O’,那么就对它进行 DFS ,遇到的所有 ‘O’ 都修改成 ‘#’ ,没有被修改的 ‘O’ 说明被 ‘X’ 全包围;
- 遍历结束后,将 board 中的 ‘#’ 修改为 ‘O’ ,将 ‘O’ 修改为 ‘X’。
-
代码
class Solution { public: void solve(vector<vector<char>>& board) { int m = board.size(), n = board[0].size(); for(int i=0; i<m; ++i){ if(board[i][0] == 'O') dfs(board, i, 0); if(board[i][n-1] == 'O') dfs(board, i, n-1); } for(int j=0; j<n; ++j){ if(board[0][j] == 'O') dfs(board, 0, j); if(board[m-1][j] == 'O') dfs(board, m-1, j); } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(board[i][j] == 'O') board[i][j] = 'X'; else if(board[i][j] == '#') board[i][j] = 'O'; } } } void dfs(vector<vector<char>>& board, int i, int j){ if(i<0 || i>=board.size() || j<0 || j>=board[0].size() || board[i][j]== 'X' || board[i][j] == '#') return ; board[i][j] = '#'; // visited[i][j] = true; dfs(board, i+1, j); dfs(board, i-1, j); dfs(board, i, j+1); dfs(board, i, j-1); // return false; } };
-
收获
- 这道题没抓住重点,我是从中心(非边界)开始遍历,如果格子 ‘O’ 的四周都是 ‘X’ ,那么可以将其修改为 ‘X’ 。但是很难实现,因此浪费了很多时间。看了一眼题解后,很快做出来了,说明我掌握了搜索的算法,但是没办法将其应用到实际中。
- 此外,我一开始还设置了一个访问数组防止重复搜索,然后题解中直接用
board[i][j] == '#'
代替访问数组,确实可行,而且不会额外占用内存。
257. 二叉树的所有路径(简单)
-
题解
- 这道题思路很简单,就是对根节点调用 DFS ,如果搜索到的节点不为空,那么就将它的值放入路径 path ,继续判断它是否存在子节点:如果不存在,说明已经找到一条路径,存入答案数组;存在的话继续递归子节点。
-
代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> ans; dfs(root, ans, ""); return ans; } void dfs(TreeNode* root, vector<string>& ans, string path){ if(root != nullptr){ path += to_string(root->val); if(root ->left == nullptr && root -> right == nullptr){ ans.push_back(path); }else{ path += "->"; dfs(root->left, ans, path); dfs(root->right, ans, path); } } } };
-
收获
- 这道题思路不难,用的是最基本的 DFS 模板,但是我对于 《题目给出结构体》 这类型的题不熟悉,不知道如何使用。
- 这道题出错的地方:
- path 一开始定义为
vector<string>
,难怪ans.push_back(path)
出错; - path 不应该加上 引用 & ,因为加上引用的话,会不断修改它,我们在对根节点右子树进行遍历的时候,只希望 path 中有 根节点。
- path 一开始定义为
47. 全排列 II(中等)
-
思路
-
这道题是 46.全排列 的升级版,多了一个条件:「序列包含重复数字」。因此,相比于 46 ,可能会出现重复结果。
-
一开始我想用 set 去重,但是发现不是是很方便。所以,我们在遍历的时候,可以对重复结果进行剪枝。如图所示,显然,对于序列 [1,1*,2] ,如果第一个 1 已经放入在第一个位置上,那么对于 1* 来说,如果再放在第一个位置, 那么肯定和前一种情况重复,因此需要去除。
-
因此,如果第一个 1 已经使用,那么我们就不再考虑同一位置上的 1* 的情况。设置条件为 :
if(i>0 && nums[i] == nums[i-1] && !vis[i-1]) continue;
-
这里,为了方便考虑重复数字,我们再遍历之前应该对数组进行排序,保证相同数字相邻。这里有一个问题,因为我代码使用了 swap 交换两个数字的位置,而每次backtracking 后,swap 都会将 nums变回 backtracking 之前的顺序,因此在回溯的时候,每次都需要对 nums 重新排序。
-
-
代码
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ans; vector<bool> vis(nums.size(), false); backtracking(nums, ans, 0, vis); return ans; } void backtracking(vector<int>& nums, vector<vector<int>>& ans, int level, vector<bool>& vis){ if(level == nums.size()){ ans.push_back(nums); return ; } for(int i=level; i<nums.size(); ++i){ // swap之后可能无序 所以需要重新排序 sort(nums.begin() + level, nums.end()); // 剪枝 if(i>0 && nums[i] == nums[i-1] && !vis[i-1]) continue; vis[i] = true; // 修改当前状态 swap(nums[i], nums[level]); backtracking(nums, ans, level+1, vis); // 递归子节点 vis[i] = false; // 回改当前状态 swap(nums[i], nums[level]); } } };
-
收获
- 这道题做了特别久,可能和今天状态不好也有关系,其实整体思路并不难,但是我没有考虑到swap 都会将 nums变回 backtracking 之前的顺序,导致有一个实例一直没办法通过。 错误实例及原因分析
40. 组合总和 II(中等)
-
题解
- 这道题的思路结合了 77 和 47 ,首先依照 77 的算法思想,完成组合排列,接着利用 47 去重的思想,去除重复组合。
- 对于不出现重复序列的题目,一般都需要排序,便于去重。
- 组合排列:设定一个值 sum ,用于保存当前数组元素之和,当 sum == target ,说明我们已经找到一个符合要求的数组,存入 ans;如果 sum > target ,由于我们的数组是升序排列,那么后续元素肯定比当前元素大,因此该情况一定不可能,此时回退到上一个状态;如果 sum < target ,那么进入循环,取下一个元素继续判断。
- 在选择元素的时候,需要注意需要保存当前元素的下标 pos,递归该节点的时候,应该从当前元素的下一个元素开始考虑,才不会出现一直使用同一元素的情况。
- 去重 思想参考上一道题,思路完全一致。
-
代码
class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { vector<vector<int>> ans; vector<bool> visit(candidates.size(), false); vector<int> option; sort(candidates.begin(), candidates.end()); backtracking(candidates, ans, target, 0, option, 0, visit); return ans; } void backtracking(vector<int> &candidates, vector<vector<int>> &ans, int target, int sum, vector<int> option, int pos, vector<bool> &visit){ if(sum == target){ ans.push_back(option); return ; } else if(sum > target){ return ; } for(int i=pos; i<candidates.size(); ++i){ // 剪枝 if(i>0 && candidates[i] == candidates[i-1] && !visit[i-1]) continue; // 修改当前状态 visit[i] = true; sum += candidates[i]; option.push_back(candidates[i]); // 递归子节点 backtracking(candidates, ans, target, sum, option, i+1, visit); // 回改当前状态 visit[i] = false; sum -= candidates[i]; option.pop_back(); } } };
-
收获
- 昨天在去重的思路上卡了很久,不过总算有收获,今天很快就自己做出来了!
37. 解数独(困难)
-
思路
- 为了防止数字冲突,设置了三个访问数组对已经使用的数字进行标记,分别是行、列 和 3*3 格子。
- 首先,遍历 board ,如果当前元素是数字,那么修改对应的访问数组;如果当前元素是 ‘.’ ,说明之后需要修改这个位置,把它放入 spaces ;
- 接着,递归 spaces 的每一个元素, 设置 pos 标记当前遍历到的元素下标;
- 如果 pos == spaces.size() ,说明我们已经对所有 ‘.’ 进行了修改,将 valid 置为 true ,结束递归;
- 否则,对每个 ‘.’ 进行修改。考虑在该位置上填入 1 - 9,当且仅当 valid = false ,且该数字在三个访问数组中都为 false,那么可以填入,此时需要将该数字填入 board ,同时修改访问数组的状态; 然后递归子节点,回溯的时候需要回改当前状态,不过这里不需要将填入的数字改回 ‘.’ ,因为该位置注定要填入一个数字的,所以无需修改回去。
-
代码
class Solution { public: bool valid = false; void solveSudoku(vector<vector<char>>& board) { // 三个访问数组,分别对应于行、列、3*3 vector<vector<bool>> txt(9, vector<bool>(9, false)); vector<vector<bool>> row(9, vector<bool>(9, false)); vector<vector<bool>> col(9, vector<bool>(9, false)); // 记录需要填入的位置坐标 vector<pair<int, int>> spaces; for(int i=0; i<9; ++i){ for(int j=0; j<9; ++j){ if(board[i][j] != '.'){ // 对已有数字进行标记 防止重复 row[i][board[i][j] - '1'] = true; col[j][board[i][j] - '1'] = true; txt[(i / 3) * 3 + (j / 3)][board[i][j] - '1'] = true; } else{ // 记录需要填入的位置坐标 spaces.push_back({i, j}); } } } backtracking(board, 0, row, col, txt, spaces); } void backtracking(vector<vector<char>>& board, int pos, vector<vector<bool>> &row, vector<vector<bool>> &col, vector<vector<bool>> &txt, vector<pair<int, int>> &spaces){ // pos 表示当前遍历到 spaces的元素下标 // 递归结束的条件 if(pos == spaces.size()){ // 说明每个需要填入的位置都已经遍历了 valid = true; return ; } auto [i, j] = spaces[pos]; for(int k=0; k<9; ++k){ if(!valid && !row[i][k] && !col[j][k] && !txt[(i / 3) * 3 + (j / 3)][k]){ // 说明这个数字还没被使用 // 修改当前节点的状态 board[i][j] = k + '0' + 1; row[i][k] = col[j][k] = txt[(i / 3) * 3 + (j / 3)][k] = true; // 递归子节点 backtracking(board, pos+1, row, col, txt, spaces); // 不需要再改回"." // 回改当前状态 row[i][k] = col[j][k] = txt[(i / 3) * 3 + (j / 3)][k] = false; } } } };
-
收获
- 这道题思路不难,对应于回溯题的 N 皇后 ,需要设置多个访问数组。不过我没想到设置 spaces 来保存需要修改的位置,因此没想到递归的结束条件。
310. 最小高度树(中等)
-
思路
- 这道题是求的是树的最小高度,一般用 BFS 求解。通过画图,可以发现,越靠近里面的节点越有可能是最小高度树的根节点。因此,我们可以从叶子节点(度=1)出发,每一次遍历都剥掉最外层的叶子节点,最后剩下的叶子节点就是最小高度树的根节点。
- 首先使用邻接表存储树,使用一维数组存储每个节点的度;
- 接着,将度为1的节点,即叶子节点,入队;
- 然后对队列中的每一个元素使用 BFS,直到队列为空,此时 ans 保存的就是最后状态的叶子节点,也就是最小高树的根节点。注意,由于 ans 会保存每轮的叶子节点,因此每次进行下一轮搜索的时候,需要将 ans 清空。
-
代码
class Solution { public: vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { if(n==1) return {0}; vector<vector<int>> m(n); // 邻接表 vector<int> degree(n, 0); vector<int> ans; // 保存邻接矩阵和度 for(int i=0; i<edges.size(); ++i){ int u = edges[i][0], v = edges[i][1]; ++degree[u];++degree[v]; m[u].push_back(v); m[v].push_back(u); } queue<int> q; // 叶子节点入队 for(int i=0; i<n; ++i){ if(degree[i] == 1) q.push(i); } // 一层层从外往内剥,剩下的叶子节点就是根节点 while(!q.empty()){ // ans 会保存最后状态下的叶子节点 ans.clear(); int q_size = q.size(); for(int i=0; i<q_size; ++i){ int t = q.front(); q.pop(); ans.push_back(t); for(auto j : m[t]){ // 由于剥掉了外层 因此它的度-1 degree[j] --; // 如果当前节点是叶子节点 入队 if(degree[j] == 1) q.push(j); } } } return ans; } };
-
收获
- 对于树的存储方式(邻接表) 和度,我有想到。不过,“先将叶子节点入队, 然后一层层向内剥” ,这个思路我没有想到,而且 BFS 相对不够熟悉。
17. 电话号码的字母组合(中等)
思路及代码: 17. 电话号码的字母组合
679. 24 点游戏(困难)
文章来源:https://www.toymoban.com/news/detail-407786.html
679. 24 点游戏文章来源地址https://www.toymoban.com/news/detail-407786.html
到了这里,关于【LeetCode】《LeetCode 101》第六章:搜索的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!