Collections工具列表

DatatypesFunction descriptionnamedtuple()factory function for creating tuple subclasses with named fieldsdequelist-like container with fast appends and pops on either endChainMapdict-like class for creating a single view of multiple mappingsCounterdict subclass for counting hashable objectsOrderedDictdict subclass that remembers the order entries were addeddefaultdictdict subclass that calls a factory function to supply missing valuesUserDictwrapper around dictionary objects for easier dict subc

General Learning · 11 天前

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 天前

Flash-attn安装踩坑记录

FlashAttention 安装学习笔记在安装和编译 FlashAttention 的过程中，遇到如下问题，进行记录，以防后面再次踩坑CUDA 环境变量设置问题描述在编译 flash-attn 的时候，系统找不到 CUDA 相关头文件或编译器，表现为：nvcc not foundcannot find cuda.h排查过程运行 ls /usr/local/cuda/include 确认是否存在 cusparse.h、cusparse_v2.h 等头文件执行 which nvcc 或 ps -ef | grep nvcc 检查 nvcc 是否在路径中解决办法需要在 环境变量 中显式指定 CUDA 路径：export CUDA_HOME=/usr/local/cuda export PATH=/usr/local/cuda/bin:$PATH export LD_LIBRARY_PATH=/usr/local/cuda/lib64:$LD_LIBRARY_PATH这样 nvcc 就能被找到，头文件和库路径也能被正常识别CUDA 运行时与 PyTorch 编译版本不对应使用conda安装p

General Learning · 26 天前

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