WBY's Blog - 搜索
type: channel
link: https://wbyblog.cn/category/%E6%90%9C%E7%B4%A2/
items: 1091. 二进制矩阵中的最短路径
items: 51. N皇后
items: 46. 全排列
items: 417. 太平洋大西洋水流问题
items: 547. 省份数量
items: 200. 岛屿数量

1091. 二进制矩阵中的最短路径
type: item
date: 2025-09-24T13:23:26+08:00
description: 题目链接：https://leetcode.cn/problems/shortest-path-in-binary-matrix/description/我的思路尝试用dfs的思路，思维定势了，已知起点在左上角，终点在右下角，那么自然想到要找到最短路径，那只能往右或者往右下走，于是在dfs中设置了(i + 1, j)和(i + 1, j + 1)两个位置的考察，同时定义一个结果ans变量，当走到终点后，比较当前路径的长度distance和ans的大小，将更小的那个值保留，不断比较，找到最终的答案但这样的想法存在两个问题：1. 可走的方向考虑欠妥，太理想化了，万一右边和右下的路都被挡住了，只能往右上或者向上走，那这样的做法就永远找不到正确的路径，这个问题非常致命，在这道题里应该要考察八个方向：上下左右、左上左下、右上右下；2. dfs的方法不是不可以，但是随着矩阵大小的增加，其遍历所需时间会呈指数级暴涨，很容易就出现超时，效率非常低纠正这道题应该用bfs(breadth-first search)的方法，广度优先算法，用到队列（queue）结构来进行遍历而非栈，按层次进行遍历。深度优先搜索和广度优先搜索都可以处理可达性问题，即从一个节点开始是否能达到另一个节点，dfs用到了递归的思路，但在实际工程应用中，递归的写法很少见到，一方面是难以理解，另一方面很容易遇到栈溢出的情况这里我们用到python内置的队列来进行操作，从collections中导入deque，用q = deque([0,0,1]) 定义一个队列：队列存放的是 当前层要访问的节点，在这里就是网格中的坐标 (row, col)，以及从起点走到这里的路径长度每次从队首 popleft() 取出一个位置，遍历它的 8 个可能方向（上下左右和对角线）如果新位置合法（没有越界、没有障碍、没有访问过），就把它加入队尾 append()，并记录步数BFS 保证了最先到达终点的路径一定是最短的，因为搜索是按层推进的BFS 为什么能保证最短？关键点在于：队列是先进先出，所以 BFS 是一层一层扩展的以案例[[0,0,0],[1,1,0],[1,1,0]]为例，当把 (0,2,3) 或 (1,2,3) 入队时，steps=3 说明它们是从 起点出发，用 3 步到达的所有格子BFS 保证 所有 steps=3 的节点都在 steps=4 之前被处理，先将(0,2,3)出队，因为此时(1,2)已经被访问过了，在队列中，所以从(0,2)开始不会再往下走，(0,2,3)出队后，之后没有能走通的路，那么这个元素就不管了，消失，继续处理之后的元素。这一步背后的逻辑是，在从起点开始能走3步的情况下，能到达(0,2)和(1,2)这两个位置，原来(0,2)可以继续往下走到(1,2)，这样就要4步，但我已经在三步的时候走到了，并也将这个路径记录在了我的队列中，所以就不用管从(0,2)出发的情况了所以，当终点 (2,2) 第一次被加入队列时，它一定是用 最少的步数到达的。之后即使 (2,2) 有别的路径能到，但那些路径的 steps 一定 ≥ 当前最小步数，所以不会比第一次更优结果时间复杂度：$O(N^2)$空间复杂度：$O(N^2)$已是最优解

51. N皇后
type: item
date: 2025-09-17T20:11:00+08:00
description: 题目链接：https://leetcode.cn/problems/n-queens/description/思路依旧是回溯法，深度优先搜索，dfs，从第一行的第一列第一个元素出发，把所有横向纵向的可能性都判断一遍，在遍历的过程中加入判断条件进行剪枝。仔细阅读一下这道题，可以把限制条件抽象为以下两点，并通过对应的方法来进行判断：同列不能有两个元素，定义一个col列表，长度为n，表示每次遍历中每一列的元素占有情况，如果某一列上放了queen，就将对应位置更改为True，这个变量在每次循环中需要回溯对角线上不能有两个元素，通常而言，对角线上的元素比较特殊，满足某种数学关系，我们可以抓住这个数学关系来进行判断，在↘方向上的对角线元素满足$i - j$始终为固定值，在↗方向上的对角线元素始终满足$i + j$为固定值，如下图所示也就意味着，比如当前在$[2, 3]$位置处放了queen，那么对于其他任意满足$i+j=2+3 =5$以及$i-j=-1$的位置都不能再放queen了。于是乎，我们可以定义两个对角元素的考察列表ldiag和rdiag，因为n是固定的，有$0\leq i + j\leq n-1+n-1=2n-2$，$0-(n-1)=-n+1\leq i-j\leq n-1$，那么两个考察列表的长度分别为$2n-2+1=2n-1$以及$n-1-(-n+1)+1=2n-1$，是相同的，这样一来就能把所有可能的情况涵盖进去（这里尽管$i - j$可能会是负数，但是我们只要定义了足够长的列表，当索引为负值时，从逆向取值，也是能够满足我们的要求的，我们在这里只是要判断某个$i - j$是否已经被占用了），如果在某个位置$[i, j]$放了queen，那么就分别将ldiag$[i + j]$以及rdiag$[i - j]$的位置设置为True即可，这两个变量也是需要回溯的于是乎，根据上面的讨论，我们就得到了以下dfs函数中的核心部分：for j, ok in enumerate(col): #需要考察col的情况 if not ok and not ldiag[i+j] and rdiag[i+j]: queen[i] = j #记录下在第i列中，queen被放到了第几行中，这个变量不需要回溯，因为如果前一个不满足的话，后面会直接覆盖掉前一个值，直到找到合适的解 col[j] = ldiag[i + j] = rdiag[i - j] = True backtrack(i + 1) #递归下一列 col[j] = ldiag[i + j] = rdiag[i - j] = False #回溯，防止污染下一次判断dfs函数传入的变量为i，表示当前考察的是第几列以上整个递归过程可以用下面的递归树来表示，红色实线箭头表示递归，虚线表示回溯，由于判断条件的存在，不会递归到底，而是会在树内进行剪枝，提高运行效率：反思不能加上“在一行只尝试放一个皇后的位置”的判断条件以试图减少判断次数来优化算法，因为这样可能会漏掉可能的解，在n比较大的时候，可能在一行会有若干个符合条件的位置，因此不能在找到一个答案后就不遍历后面的位置了，会出错以后可以用递归树的形式来帮助自己理清思路，弄清楚有几个节点、题目是什么意思结果时间复杂度：$O(N!)$空间复杂度：$O(N)$已是最优解

46. 全排列
type: item
date: 2025-08-20T11:09:00+08:00
description: 题目链接：https://leetcode.cn/problems/permutations/思路这道题要用到回溯法，本质上是在一棵决策树上做DFS，每个节点做选择，递归深入，回退恢复，再做下一个选择。排列组合里，我们要考虑到所有的情况，因此这里的节点就是列表中的元素，比如[1, 2, 3]，那就有三个节点，分别考虑这三个节点在第一位的情况，就能把所有的可能都列举出来：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]我们定义一个回溯函数backscattering，传入当前的数组和一个中间变量level，以及最终的结果存储列表result首先判断，如果level到达了len(nums) - 1，那么说明没有元素可以再考虑了，将此时的nums放进result中，然后跳出函数，不继续执行下去如果level没有达到len(nums) - 1，那就说明还有可能性没有考虑完，需要继续做搜索：从当前的 level 位置开始，依次尝试把每一个候选元素放到 level 这个位置上，因为我每次已经固定了第1个元素（把每一个节点都放到第一个，然后遍历所有的可能性），所以在子循环中，我的i取值范围是[level, len(nums))，尝试后面的每个元素都是否能放到level这个位置为了实现这个操作，代码里用到了 交换：nums[i], nums[level] = nums[level], nums[i]。这样可以把第 i 个元素放到 level 的位置上，相当于“选择了这个元素”做出选择之后，调用递归函数 backscattering(nums, level + 1, result)，进入下一层，去决定下一个位置该放谁当递归返回时，说明这一条选择路径已经搜索结束，为了不影响接下来的其他可能性，需要把之前交换的两个元素 再交换回来，恢复原来的数组状态，这一步就是“回溯”整个 for 循环会把所有能放在 level 位置的元素都尝试一遍，并在递归过程中不断生成新的排列。当所有循环结束时，说明以当前 level 开头的所有情况都考虑完毕，函数返回上层举例反思回溯的核心思想就是 枚举 + 恢复，每次在当前位置尝试所有可能的元素，把它放进去，然后继续往下递归搜索；当一条路径走完，就退回来恢复现场，再尝试下一种可能这种“搜索 → 回退 → 再搜索”的过程，就像在一棵“决策树”上做深度优先遍历，最终会遍历出所有排列这个问题中我们递归的是列表的索引值，这点一定要弄清楚，level代表了“侯选位置”的索引其实回溯的过程可以类比为在一棵 树形结构的决策树 上进行深度优先遍历。它的基本思想是：从根节点出发，沿着某一条路径不断向下递归，直到到达叶子节点（对应于所有位置都被填满，得到一个完整解）；然后回退一步（回溯），撤销上一步的选择，转而尝试下一个可选分支；在当前节点的所有子节点都遍历完成后，再回退到父节点，继续探索父节点的下一个分支；如此反复，直到整棵决策树的所有路径都被遍历。此类题目的套路：在回溯函数中先修改当前节点的状态（如记录，把它append到结果列表中，或者修改为True，表示已经访问），接着递归所有可能的子节点，子节点递归完成后再将当前节点的状态给修改回来，回退，为了实现剪枝降低算法复杂度，在回溯函数的开始可以设置if语句判断条件，在触及边界/特殊情况下及时停止，避免无用功类推77 组合，$O(C[N, k])$, $O(k)$，已是最优解，每次循环完了以后要pop一下79 单词搜索，$O(MN*4)$, $O(MN)$，已是最优解，在遍历的时候会做剪枝，理论上的时间复杂度应该是$O(MN*4^L)$，但因为在回溯函数中设置了条件，“及时止损”，所以复杂度能够降低结果时间复杂度：$O(N!)$空间复杂度：$O(N)$已是最优解

417. 太平洋大西洋水流问题
type: item
date: 2025-08-08T16:19:00+08:00
description: 题目链接：https://leetcode.cn/problems/pacific-atlantic-water-flow/description/我的思路看了一下提示，采用逆向DFS的方法，与其直接看某个点是否能同时流向两个海洋，不如直接从四个边出发，能“逆流而上”，说明这个点能够流向对应的海洋，且从四条边出发也能很好分辨两个海洋，分别设定两个矩阵，最后取两个矩阵都为1的公共部分作为答案即可但是在实现上面的步骤时遇到一个坑，还是对python的变量定义内部原理不是很清晰，知道要用两个矩阵来表示某个点是否能流向对应的洋，于是乎直接定义is_p = [[0] * n] * m ，这样实际上里每一行都是同一个对象的引用，在修改 is_p[x][y] 的时候，会导致这一列在所有行都被修改，所以DFS标记访问的时候，访问一行等于整列都变化，结果乱掉，称为浅拷贝陷阱纠正采用is_p = [[0] * n for _ in range(m)] 的形式定义初始化矩阵，能够保证每个元素都是独立的变量，在修改时不会一整块都被修改了反思用好反向思维：题目要求的是满足向下流能到达两个大洋的位置，如果我们对所有的位置进行搜索，那么在不剪枝的情况下复杂度会很高。因此我们可以反过来想，从两个大洋开始向上流，这样我们只需要对矩形四条边进行搜索浅拷贝问题：Python 变量：名字 → 对象（引用关系）=：拷贝的是引用浅拷贝：拷贝容器本身，但里面的引用不变（常见 bug 来源）深拷贝：完全递归复制，最安全避免浅拷贝 bug：二维数组初始化：用列表推导式，对象拷贝：用 deepcopy，一维简单拷贝：切片 / list()结果时间复杂度：$O(mn)$空间复杂度：$O(mn)$已是最优解

547. 省份数量
type: item
date: 2025-07-17T20:55:00+08:00
description: 题目链接：https://leetcode.cn/problems/number-of-provinces/description/我的思路尝试用第200题的思路，但是又理解错了题目意思，没有好好读题。这道题和第200题不一样的是，给的矩阵表示了节点之间的连接情况，而不是表示“地图”，并且在提示中也清晰说明了 isConnected[i][i] == 1以及isConnected[i][j] == isConnected[j][i] ，同时尝试用类似的题解来答，会给出错误的答案，因为一方面isConnected的意思并不是我们想象的那样，另一方面其并不能被原地修改，因此插旗法不适用，如果强制用原先的办法，就会返回矩阵里有几个1值纠正仍使用广度优先搜索算法，但采用递归的方法。假设矩阵有$n$个元素，意味着有$n$个城市（节点），每个节点可以有$n$个边，表示和所有城市都相连（都是朋友），最少可以有1条边，表示自己和自己相连（代表矩阵的对角元素）。这道题里，我们无法直接修改原始矩阵的值，而且直接修改没有什么意义，回顾一下之前我们做标记的初衷：为了标识这个岛屿的这个位置我们已经访问过了，已经走过，所以打标记为0或#，同时我们的算法代码能够保证一次性把所有符合条件的位置都走遍，防止我们重复走，可以类比成“染色”：从某个城市出发，把能走到的所有城市都染成已访问在这里我们不能直接改原来的值，那么换一个思路，定义一个长度为$n$的列表，访问过的城市记录为True，不就可以了吗？无论是间接还是直接，接下来的DFS函数都能把这条链给完整找出来，同时也能把这些城市都给访问一遍，标记为True，这样就不会出现重复判断的问题了。算法过程如下：从某个未访问的城市 i 开始。动作：标记 i 已访问。遍历所有城市 k：如果 i 和 k 相连，且 k 没访问过 → 递归 dfs(k)。递归展开过程：像“连锁反应”一样，会一直把 i 所在连通分量里的所有城市都访问完。这样说还是有点复杂，举个例子说明：假设 isConnected = [[1,1,0],[1,1,0],[0,0,1]]：城市 0 → 连着城市 1城市 2 自成一组执行过程：j=0：未访问 → DFS(0)，递归会顺带访问 1 → ans=1j=1：已访问，跳过j=2：未访问 → DFS(2)，只访问自己 → ans=2最终答案：2 个省份反思这道题还可以用并查集，并查集是一种数据结构，三个字分别代表不同的意思：合并、查找、集合这题本质是连通分量计数，dfs 函数的递归作用：把从某个起点出发能到达的所有节点“一网打尽”，每次外层循环找到一个未访问城市，就意味着发现一个新省份结果时间复杂度：$O(N^2)$空间复杂度：$O(N)$已是最优解

200. 岛屿数量
type: item
date: 2025-07-02T10:54:00+08:00
description: 题目链接：https://leetcode.cn/problems/number-of-islands/description/我的思路刚接触搜索算法，有点不知所措，拿到这道题也是不知道该咋办，依旧是看了题解才写出来的。思路假设你是一个冒险家，开始探索这片土地，你的规则是只能上下左右走，而不能斜着走。现在你要判断这片土地上有多少个独立的不直接相连的岛屿。那么你可以边走边做标记，首先遍历网格，依次作为起点，如果遇到元素为1，说明你登上了一个新的岛，为了防止漏探索或重复探索，你先把这个位置标记为2，表示已经探索过了，接着尝试往上下左右走，看是否还是这个岛的范围，依次重复这个步骤，假设往上走一步，发现还是1，那就再把这里标记为2，然后再尝试从这个位置起上下左右走，直到把这个岛的所有区域都标记为2，则意味着探索完了这个岛探索完某个岛的条件是，你从这个岛的最后一个位置出发，上下左右走都已经是2或者是0，表示这个岛已经被探索完了。同时在这个过程中，还有可能触及到你探索区域的边界（Gird的尺寸），这时候也意味着这个岛被探索完了以上思路被称作深度优先搜索算法（Depth-First Search），是一种递归算法，以上问题的实现办法为：定义dfs函数，传入一个坐标(x, y)，主函数中遍历grid，只要遇到1元素，说明登上了一个新岛，转入到dfs函数中开始探索这个岛，直到探索完因为登上了这个岛，登岛的位置也是属于这个岛的，因此dfs函数中要首先将这个位置进行标记，表示已经探索过了，gridx = ‘2’（注意，这里有两个坑，一是这是一个列表形式存储的网格，表示坐标要用索引的索引，不能思维定势写成了[x, y]，二是这道题中岛屿标记是用字符串’1’来代表的，而不是数字1，不能搞混了），接着以这个点为参考，上下左右都走一遍，判断：1. 是否有触及到边界，如果其中有位置已经在边界了，那自然这个位置不需要再探索；2. 走到的新位置是否标记为‘1’，即仍然是这个岛的范围，如果是，就再把这个点作为新的参考点进行判断，将这个位置传入到dfs函数中，先标记为2，然后重复这一步；上下左右分别代表了坐标[x, y + 1], [x, y - 1], [x - 1, y], [x + 1, y]如何判断这四个位置及其各自的相邻上下左右是否属于这个岛的范围呢？很简单，把这四个坐标都传进dfs进行递归判断就好了，如果触及到边界条件，或者新的位置已经为‘2’或者‘0’，则返回一个空值，说明这个位置及其邻近位置都已经探索完了，同时函数内嵌函数保证了能够遍历完所有相邻可能的上下左右位置，判断语句为：if x < 0 or x >= m or y < 0 or y >= m or grid[x][y] != '1': return 返回一个空值主函数中采用enumerate生成每个元素的位置和对应值，因为我们在dfs函数中设置了对于已经探索的位置标记为‘2’，也就意味着只要我们登上了一个岛，dfs就能保证把这个岛给全部探索完，因此，在我们遍历grid的过程中，只有遇到一个新的‘1’时，才将坐标传入到dfs函数中，这表示找到了一个与前面的岛非直接相连的新岛类推695 岛屿的最大面积 为这道题的改编版，这下我们不是要判断有几个岛屿了，而是输出最大的那个岛屿的面积，这次grid中的岛屿和海是用数字的形式存储的了，方便我们直接进行计算题目的形式一模一样，只是要求的量不一样了，思路完全一致，照搬上面的“标记法”即可，同样是做上下左右的尝试，直到越界或到0，这里我们的标记要定为0才行，定为2的话会被计算进去，同时dfs函数返回的是岛屿的面积值，这次不是返回一个空值了（原题目中我们是要靠dfs来把这个岛走完并且将grid中走过的位置都进行标记修改，因此不需要返回任何值，改变grid就好了）130 被围绕的区域 逆向DFS，找到所有被 X 围绕的区域不容易，但是其等价于找到所有没有没有被 X 围绕的区域（连接边界的区域），这样就可以从边界上的 O 开始进行深度优先搜索，因为边界上的 O 很特殊，与之相连的所有 O 无论如何都不能被围绕，因此可以先从这部分入手，先把他们替换成一个标记，比如 #，最后board中剩余的 O 都是能够被包围的，把它们替换成 X，再把 # 替换回 O，就得到了我们要的答案反思今天看到一个评论，说衡量算法好坏不要用耗时和内存来评判，更不要看超越了多少百分比，因为不同编程语言之间的耗时和内存占用都是不一样的，同时总的耗时内存占用大可能是因为某个特别变态的测试案例所导致的，因此直接用全局的算法复杂度来评判，会更加客观和合理结果时间复杂度：$O(mn)$空间复杂度：$O(mn)$已是最优解