1091. 二进制矩阵中的最短路径

题目链接：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）结构来进行遍历而非栈，按层次进行遍历。深度优先搜

搜索 · 13 天前

51. N皇后

题目链接：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

搜索 · 20 天前

46. 全排列

题目链接：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个元素（把每一个节点都放到第一个，然后遍历

搜索 · 08-20

417. 太平洋大西洋水流问题

题目链接：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)] 的形式定义初始化矩阵，能够保证每个元素都是独立的变量，在修改时不会一整块都被修改了反思用好反向思维：题目要求的是满足向下流能到达两个大洋的位置，如果我们对所

搜索 · 08-08

547. 省份数量

题目链接：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条边，表示自己和自己相连（代表矩阵的对角元素）。这道题里，我们无法直接修改原始矩阵的值，而且直接修改没有什么意义，回顾一下之前我们做标记的初衷：为了标识这个岛屿的这个位置我们已经访问过了，已经

搜索 · 07-17

200. 岛屿数量

题目链接：https://leetcode.cn/problems/number-of-islands/description/我的思路刚接触搜索算法，有点不知所措，拿到这道题也是不知道该咋办，依旧是看了题解才写出来的。思路假设你是一个冒险家，开始探索这片土地，你的规则是只能上下左右走，而不能斜着走。现在你要判断这片土地上有多少个独立的不直接相连的岛屿。那么你可以边走边做标记，首先遍历网格，依次作为起点，如果遇到元素为1，说明你登上了一个新的岛，为了防止漏探索或重复探索，你先把这个位置标记为2，表示已经探索过了，接着尝试往上下左右走，看是否还是这个岛的范围，依次重复这个步骤，假设往上走一步，发现还是1，那就再把这里标记为2，然后再尝试从这个位置起上下左右走，直到把这个岛的所有区域都标记为2，则意味着探索完了这个岛探索完某个岛的条件是，你从这个岛的最后一个位置出发，上下左右走都已经是2或者是0，表示这个岛已经被探索完了。同时在这个过程中，还有可能触及到你探索区域的边界（Gird的尺寸），这时候也意味着这个岛被探索完了以上思路被称作深度优先搜索算法（Depth-First Search），

搜索 · 07-02

347. 前 K 个高频元素

题目链接：https://leetcode.cn/problems/top-k-frequent-elements/description/我的思路乍一看这题好像还挺简单的，找到前K个高频元素，那么很自然可以想到先统计每个元素的出现频率，然后再排序，输出前K个频率最高的即可。直接暴力求解：1. count = [[num, nums.count(num)] for num in set(nums)] 统计元素出现频率，和元素一起放到count列表中；2. count = sorted(count, key = lambda x: x[1], reverse = True) 按频次从大到小排序；3. return [x[0] for x in count[:k]] return排序好的count数组的前k个元素即可。但显然这不是最优解，这样的算法时间复杂度为$O(N\log n)$，对于特别长的序列，耗时特别久，最终结果为1378ms，也是第一次见到这么久的解题过程。那么显然要想提高时间和内存表现的话，就必须采用其他的降低复杂度的算法。纠正这里用“顶堆法”，会很方便和快捷，大幅度提高时间

排序 · 06-17

215. 数组中的第k个最大元素

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/description/我的思路又是一道中等题目的题，并且今天也是才学排序算法，因此拿到这题还是有点发怵，除了最基本的用排序方法外没有什么别的思路，但这样的时间复杂度不符合题意，所以还是要想别的办法。题解：快速选择法核心包括两部分，哨兵划分和递归哨兵：随机取数组中的一个数作为基准数（最左、最右或者随机取），之后遍历剩下的元素，把小于基准数的放到哨兵的左边，大于的放到哨兵的右边递归：继续对左子数组和右子数组执行哨兵划分，直到子数组的长度为1时终止以上过程可以用题解的图来很好解释：放到算法层面，我们可以定义三个列表来实现上述操作：small, equal和big，把和pivot相等的值放进equal，更小的放进small，更大的放进big，这样一来我们就得到了这个数组中前len(big)大的数字，执行完放数字操作后比较len(big)和k的大小：如果len(big) < k，说明我们的pivot选得刚好（我们想要的值全都在equal里）或者选大了（我们想

排序 · 06-09