题目链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/我的思路典型的双指针/滑动窗口类型题目，想到初始化左右两个指针$l=0, r=n-1$，$n$为所给数组的长度，因为我们要找的是最小操作数，那么在判断左右两边到底减哪个时，采用贪心策略，选更大的那一个，就能让$x$减的更快，更快到0，有几种情况：$nums[l]>nums[r]$:$nums[l]\leq x$: 说明此时$nums[l]$可以作为一个操作数，$x-nums[l]$，同时操作数$ans+1$，左指针右移$l+1$$nums[l]>x\geq nums[r]$：则$x-nums[r]$，同样$ans+1$，右指针左移$r-1$$nums[r]>x$：说明中断了，不再满足题目中的条件，直接break$nums[l]\leq nums[r]$:$nums[r]\leq x$：$x-nums[r], ans+1, r-1$$nums[r]>x\geq nums[l]$：$x-nums[l], ans+1, l + 1$$nums[l]>x$：break初始化的$ans=0$，循环条件为$l\leq r,x>0$，当循环跳出后，如果$x\neq0$，则返回-1，反之返回$ans$纠正这个思路看上去很正确，但实际上考虑得并不周全。采用“从两端贪心减x”的策略，这是一种局部决策法。贪心策略失败的根本原因在于：每次“取较大的一端”并不能保证最终组合的和恰好为 x；局部选择（谁大取谁）可能导致后续无解；问题的全局约束是前缀+后缀的组合，而不是连续的减法过程；直观来看，比如下面这个步骤：步骤可选两端贪心选择实际后果1左=9500, 右=9400取左9500看似很好，x减少很多2左=8500, 右=9200取右9200x再减一大块………余下 x=610，后面全是大于610的数，再也无法取到刚好为0贪心能保证局部最优解，但可能会因此掠过全局最优解的进入条件，使得解法陷入到一个死局，本来左边的数一直可以减下去使得$x$最终减到0，尽管这样操作数会变多，但能够实现最终的目的，贪心时可能右边会减掉一个很大的数，导致左边无法再进入后续解中，看似找到了最优实则掉进了陷阱，因此需要用“滑动窗口”或“前缀和”在整个数组范围内找到最优区间，而不能局部决策采用逆向思维，正难则反，题目中说要移除$nums$最左边或最右边的元素，那么剩下的元素是什么呢？其实是$nums$的一个连续子数组，因为左右两边去除的元素之和为$x$，那么剩下的这个子数组中的元素和就应该为$\mathrm{sum}(nums)-x$，那么问题就转化为了我们要找到和为这个数的一个最长子数组（去掉两边的元素数最少，那么中间剩下的要最长，因此是最长子数组）初始化$l=0,target=\mathrm{sum}(nums)-x,ans=-1$，如果$target<0$，那么说明$nums$的所有元素还不够$x$来减的，直接返回-1，接着用enumerate枚举$nums$中的$r,y$，定义一个中间变量$s$，初始化为0，每次枚举时$s+y$，当$s>target$时，说明当前$[l,r]$包含了我们所要的子数组，此时移动左指针缩短窗口（用while循环来实现判断），当$s=target$时，记录下此时的窗口长度，和之前的相比，如果这个长度更大，就更新$ans$，最终返回$n-ans$，因为我们实际要求的还是两边元素的减少个数，因此要做个减法反思为什么$ans$要初始化为-1呢，因为有可能我们要把所有的元素都用上，即这个子数组的长度为0，如果初始化为0，那么我们无法判断是否真正存在符合要求的子数组，在不符合的情况下我们应该返回-1结果时间复杂度：$O(N)$空间复杂度：$O(1)$已是最优解
Perl-speaks-NONMEM (PsN) is a collection of Perl modules and programs aiding in the development of non-linear mixed effect models using NONMEM. The functionality ranges from solutions to simpler tasks such as parameter estimate extraction from output files, data file sub setting and resampling, to advanced computer-intensive statistical methods. PsN includes stand-alone tools for the end-user as well as development libraries for method developers.安装步骤：安装系统环境依赖：sudo apt update sudo apt install -y \ r-base \ pandoc \ libssl-dev \ libcurl4-openssl-dev \ libmariadb-dev \ libgmp-dev \ libmpfr-dev \ libxml2-dev \ libudunits2-dev \ libblas-dev \ liblapack-dev \ libmagick++-dev安装Perl附属依赖：直接一个指令，换源，不然直接一个个安装很慢：sudo cpan -i -M https://mirrors.tuna.tsinghua.edu.cn/CPAN/ Mouse MouseX::Params::Validate Archive::Zip YAML Capture::Tiny File::Copy::Recursive File::HomeDir Math::SigFigs Statistics::Distributions安装PsN安装PsN：解压安装包tar -xvf PsN-5.6.0.tar.gz，cd到文件夹，输入sudo perl setup.pl，安装过程中建议全部默认，直接按回车和输入y，系统会自动找nonmem的安装路径，在是否要添加另一个nonmem环境时输入n，其他全部默认常用功能与指令：准备文件：.mod模型文件，.csv数据文件，.scm描述文件，放在同一个目录下vpc -samples=1000 -no_of_bins=8 -bin_by_count=1 -dir=\<dir\> \<.mod\>scm -config_file=\<.scm\> -model=\<.mod\>bootstrap -samples=50 -threads=4 -dir=\<dir\> \<.mod\>踩坑：.mod文件中的数据路径要改成./MDATA.csv，写成相对路径的同时.csv不能是大写，因为文件名里是小写的，而linux命令行区分大小写部署docker时需要同步安装nonmem和PsN，如果挂载宿主机安装的模型会经常报错找不到相应的附属依赖，而且路径挂载映射也比较麻烦，不如直接安装，但PsN安装过程中涉及到交互，所以使用dockerfile在build时安装也比较麻烦，可以进入到docker的bash界面手动安装，但就要注意重启后失效遇到PsN安装过程中下载包比较慢的问题，需要改其环境下的pip源，地址为：/usr/local/share/perl/5.32.1/PsN_5_6_0/pyvenv/bin/python -m pip install --upgrade pip使用第2步的方法进入到docker中安装完psn后，可以用docker commit <current_name> <new_image_name>创建一个新的docker镜像，不然每次重启后都要再安装一遍psn，下次启动时直接启动新的docker镜像即可
2962. 统计最大元素出现至少 K 次的子数组
题目链接：https://leetcode.cn/problems/count-subarrays-where-max-element-appears-at-least-k-times/description/我的思路想到用滑动窗口双指针，但是在结果计算和指针移动的判断上还是有些不太对，思路是清晰的，离正确答案之差一点点。首先求出$nums$中的最大值记为$m$，初始化左指针$l=0$，定义一个变量$cnt$统计枚举过程中最大值出现了几次，接着用enumerator枚举$r,x$，如果$x=m$，则将$cnt+1$，当$cnt\geq k$时，进入while循环判断，此时意味着到了某个符合条件子数组的边界，$ans+1$，如果$nums[l]=m$，则将$cnt-1$，同时将左指针右移$l+1$，因为我们要统计的是子数组的个数，所以在考察完每个$r,x$时，再将左指针重置，$l=0$，以免漏掉情况，如此循环判断下去，返回$ans$分析这个思路看上去很正确，但存在考察不全的情况，尽管想到了重置左指针，但由于$cnt$的值动态变化，所以会漏掉计数。比如案例$[1,3,2,3,3], k = 2$，按照上面的思路，将每一步计算的$cnt$值和子数组打印出来得到：2 [1, 3, 2, 3]2 [3, 2, 3]2 [1, 3, 2, 3, 3]2 [3, 2, 3, 3]到这里程序就退出运行了，原因出在考察到第三个3时。在$r=3$时，对应的$nums[3]=3$为第二个3，此时$cnt=2$，满足while循环进入条件，接着开始计数，做指针开始右移，得到一开始的两个结果（前两行），但由于$l$移动到1时，$nums[1]$也是3，因此$cnt-1$，$cnt$变为1，跳出循环，$l$重置为0，继续考察数组元素，$r=4,x=3$，$cnt$再加1，得到$cnt=2$，满足while进入条件，开始计数，得到后面两行的结果，但同样的，当$l$再次移动到1时，$nums[1]=3$，使得$cnt-1$，变成1，不再符合while的条件，便跳出循环了，得到错误的结果。纠正滑动窗口问题中，应该不走回头路，试想当$r=3$时，左指针开始移动，滑动到$l=1$时碰到最大值，那么说明$nums[1]$的这个3不能再用了（不要回头，不然会很复杂），我们要将这种情况下的所有可能全部计算出来，接着考虑后面的元素，每一个元素都如此，便能计算到最准确的结果回到上面那个情况，$r=3,x=3$，进入while判断，$l$到1后$cnt-1$，$l$再加1后跳出循环（因为$l+1$是写在while中的最后一句），此时$l$变为2，那么此时对应的，在右边界为$r=3$的情况下，符合条件的数组数不就是2个吗？因此只需要$ans+l$即可，非常巧妙换句话说，其实我们只要找到每个“临界”情况，再将此时的$l$累加起来，就是最后的答案。再看$r=4$的情况，上一个循环中$l$被赋值为2，那么同样地，$l$会以4跳出while循环，此时对应的符合条件的数组不就是4个嘛，分别是$[1,3,2,3,3],[3,2,3,3],[2,3,3],[3,3]$，因为有最后一个元素的加进来，所以不会考察到与之前重复的情况，最后将4和2相加，6就是最终的答案反思双指针/滑动窗口问题中，一般不会将左指针进行重置，一方面容易考察重复情况产生错误，另一方面思路会不够清晰，容易搞混这题还有一个优化的点是，可以直接利用$k$，节省内存占用，遇到最大值就将其减1，while的循环进入条件为$k=0$，当左指针滑到最大值时，再将$k+1$即可，这样可以节约一些内存其实做题也是一个编码-解码的过程，我们的大脑中存在着latent空间，需要将题目进行解码，知道它是什么意思，同时也要将答案进行编码，二者要在latent上匹配，本质上讲的都是一个东西，二者在高维空间中应该有相似的表示，这样才是最佳的解答结果时间复杂度：$O(N)$空间复杂度：$O(1)$已是最优解
连接步骤安装VScode客户端，这步没有什么好说的，直接在官网下载安装包安装即可安装remote-ssh插件，结合网上众多教程和踩坑案例，不要安装最新版本的该插件，选择107.1版本安装，并且将自动更新勾选给去掉插件装完后VScode左侧会新增一个remote connection的标志，点进去，点击右上方加号添加服务器地址，在输入栏输入ssh username@ip，接着会让选择config配置文件，选择第一个即可打开配置文件，可以在首行Host将服务器名字进行修改，改成你想要的显示名称右键刚刚添加的服务器，选择连接，此时会让选择系统类型，并要求输入密码在file explorer界面，可以打开任意的文件夹进行文件访问，即可开始写代码了第一次使用时的踩坑卡在安装vscode server上：为了让vscode能正常访问远程服务器，需要在服务器上下载一个客户端，具体的说明可以参考https://code.visualstudio.com/docs/remote/vscode-server，初次使用时vscode会自动在远程服务器上下载，但由于是外网，访问速度很慢，直接下载需要一两个小时，解决办法为：首先获取本地vscode的commit id，可以从关于vscode中copy得到，将那一长串叽里咕噜的id记录下来本地下载server的安装文件：https://update.code.visualstudio.com/commit:{commit id}/server-linux-x64/stable，将其中的commit id替换为第一步中复制到的id，下载tar.gz文件连接到远程服务器，在用户目录下新建.vscode-server文件夹，如果该文件夹已经存在，则先将里面的内容全部删除清空，然后在该文件夹下新建bin文件夹，将刚刚下载的压缩包上传到bin文件夹中，接着解压：tar -zxf vscode-server-linux-x64.tar.gz，最后再重命名：mv vscode-server-linux-x64 ${commit_id}，同样将这里的commit id换成第一步中得到的id重启本地vscode，重新连接，此时应该就能正常访问，如果还是不能，则尝试回退remote ssh插件的版本卡在scp复制上：打开vscode的setting，搜索local server download，找到remote.ssh: local server download，将atuo改为always，始终本地下载（其实本地直接下载的话也很慢，但本地可以更方便开代理下载）
题目链接：https://leetcode.cn/problems/valid-triangle-number/description/我的思路这题是很典型的初中数学题，根据三条边的大小来判断是否能组成一个三角形，想到判断条件为：两边之和大于第三边，两边之差小于第三边。很容易想到暴力枚举法，但这样的效率很低，因此联想到用双指针法，但也没有做进一步的思考，就直接开始动手了纠正首先将nums排序，从中取出已经排好序的三个数$a\leq b\leq c$，那么根据判断条件，要让这三条边能构成一个三角形，有：$a+b>c,a+c>b,b+c>a$，因为已经排好序了，那么后面两个条件必然成立，因此我们的目标转换为判断$a+b$是否大于$c$这里有一个很容易困惑的点，就是第二个条件“两边之差小于第三边”是否能满足？根据上面的讨论，$a+c>b$和$b+c>a$是必然成立的，那么根据这两个式子可以推出：$|b-a|=a-b<c,|b-c|=c-b<a,|a-c|=c-a<b$也必然成立（分别将两个变量移到不等号右边），那么第二个条件天然地满足了，只剩下要判断两个短边的和是否大于长边因此我们可以固定长边，取$c=\mathrm {nums}[i],\forall i\in [2, n-1]$，接着在$[0,i-1]$中进行双指针判断，初始化$l=0,r=i-1$，如果$\mathrm{nums}[l]+\mathrm{nums}[r]>\mathrm {nums}[i]$，就说明从$l$到$r$之间的每个数都满足这个条件，能够构成三角形（因为已经事先排好序），就可以让$ans$加上$r-l$优化这题还有一个更巧妙的操作，但理解起来比较困难，就是用卷积+快速傅里叶变换，numpy包包含了快速傅里叶算法，能有效降低时间复杂度（因为这道题中数组中数字范围小于1000，比较小，因此这个方案可行）。计算不符合条件的情况数（两边之和小于第三边），然后再用一共有几种情况$C_{nums.size}^3$减掉不合理的情况数，就能够得到最终答案，为什么要这样做，通过下面的讨论可以找到答案这里用到了两个关键定理：卷积定理：频域相乘等价于时域卷积，时域卷积等价于频域相乘，即$\mathcal{F}\{f*g\}=\mathcal{F}\{f\}\cdot\mathcal{F}\{g\},\mathcal{F}\{f\cdot g\}=\mathcal{F}\{f\}*\mathcal{F}\{g\}$时域卷积的定义：$(f∗g)[k]=\sum_i​f[i]⋅g[k−i]$，对于每一个可能的和$k$，把所有能组成$i+j=k$的组合的乘积$f[i]g[j]$累加，换句话说可以写成：$(f*f)[s]=\sum_{x+y=s}f[x]f[y]$，表示两数相加和为$s$的组合次数首先构建频率数组，$cnt[x]$表示$x$在所给数组中的出现频次，接着结合快速傅里叶变换做自卷积，得到$cnt2[s]$，表示两边之和为$s$的组合数（可能有几种情况）。参照上面的类似思路，我们固定$cnt$，取其中的元素所对应的边长作为最长边来考虑（考虑的背景是，根据三角形组成判断条件，对每个三元组，最大边必须小于另外两边之和），那么我只需要考察$cnt2[:cnt.size]$这部分的元素，后面的部分没有合理的最长边来与之对应了，因此不在考虑范围内需要注意的是，卷积过程中会出现两种情况：（1）自己加自己；（2）顺序调换相加得到相同结果，这两种情况都会算入到计数中，如下表所示：因此我们需要对$cnt2$中的值进行修正，考虑上面说到的两种情况：自己加自己，相当于把自己*2，因此得到的数一定为偶数，这种情况只会出现在$cnt2$的偶数索引处，因此只需要将$cnt2$偶数位置处的值减掉原来的值$cnt$即可（比如这里$cnt[4]=2$，意味着原来数组中有2个4，$cnt2[8]$中会包含2个自相加的结果，在这道题中我们不能重复利用元素，因此需要减掉2），写成表达式就是：$cnt2[::2]=cnt2[::2]-cnt[:]$，但因为我们上一步中对$cnt2$进行了截取，只取了$cnt.size$这一部分，在取偶数索引部分时，其实只对应了$cnt$的$(cnt.size+1)//2$部分，因此在代码实现时，需要写成$cnt2[::2]-=cnt[:(cnt.size+1)//2]$（以上表为例，$cnt2$被截取$[0:4]$这部分，取偶数索引，对应0,2,4，只有三个元素，这几个元素才会包含自相加的情况，我们为了修正，需要减掉其对应原始数组中元素的出现频次，即0,1,2这三个元素的频次，而在$cnt$中，这三个元素对应前$5+1//2=3$个元素，因此需要这么计算）顺序调换得到相同结果，这种情况比较好处理，在完成第一种情况的处理后，再将$cnt2$整体整除2即可，就能得到修正值这样一来，我们便得到了截取和修正后的$cnt2$数组，接着固定长边进行不合理情况的计算。对于$cnt[i]$，$\mathrm{sum}(cnt2[:i])$表示了两边和小于等于$cnt[i]$的情况总数，我们可以用一个$\mathrm{cumsum}$函数来计算累计求和，实现上面的步骤，得到$pre2=\mathrm{cumsum}(cnt2)$，若某个边长在数组中出现多次，其不合理情况也应按出现次数重复计算，因此还需要将$pre2*cnt$，得到每个长边所对应的不合理的情况总数，最后我们将视角放回到全局，计算出总的不合理情况数$\mathrm{sum}(pre2*cnt)$，再用$C_{nums.size}^3$减掉这个数，即可得到最终结果$C_{nums.size}^3-\mathrm{sum}(pre2*cnt)$反思在FFT法中：因为我们算出的$cnt$是“计数数组”，表示每个元素的出现频次，因此其长度天然地等于$\max (nums)+1$，其末尾元素对应的索引就表示了原始数组中的最大值，通过自卷积操作，算出了任意两边和的情况计数数组$cnt2$，对应的长度天然地等于$2*cnt.size+1$，其末尾元素对应了原始数组中的最大值*2对于这类题我们要找到一个固定约束，比如这道题中固定最长边，再考虑其他边的情况，这样才能不失一般性，不然会很容易重复计算/漏掉情况结果时间复杂度：$O(N+m\log m), m=\max(nums)$空间复杂度：$O(N)$已是最优解
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 subclassingUserListwrapper around list objects for easier list subclassingUserStringwrapper around string objects for easier string subclassing
题目链接：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)$已是最优解
题目链接：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)$已是最优解
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安装pytorch及其几个附属包的指令：conda install pytorch torchvision torchaudio cpuonly -c pytorch问题描述nvcc --version 显示 CUDA 12.4nvidia-smi 显示驱动支持 CUDA 12.2conda 安装的 torch 版本默认为 +cu124，导致和本地驱动版本对不上排查过程使用 nvcc --version 和 nvidia-smi 对比 CUDA 版本检查pytorch是否正确安装以及cuda是否可用：进入python命令行，import torch, torch.cuda.is_available()，查看返回是否为True解决办法如果上面排查的返回为True，就算nvcc --version返回的cuda支持版本和系统实际的cuda版本不一致，那也没问题，只要能正常调用就可以找不到 pybind11 文件问题描述编译时出现：fatal error: pybind11/pybind11.h: No such file or directory排查过程检查 conda list | grep pybind11，发现并没有安装。解决办法安装 pybind11：pip install pybind11额外依赖：packaging 和 ninja在编译过程中还需要两个辅助包：packaging：用于 setup.py 判断环境版本pip install packagingninja：更快的编译工具，比 make 高效pip install ninja如果不提前安装，编译 FlashAttention 时会报错提示找不到对应模块。安装验证官方的Git仓库中包含了示例代码，在benchmark文件夹中，在flash-attn编译安装完成后，测试是否安装成功，可以运行 benchmark/benchmark_flash_attn.py，结果显示：FlashAttention 前向 + 反向比 PyTorch 标准 Attention 提速 8-9 倍能够正常运行并输出 benchmark 结果 → 安装成功
题目链接：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)$已是最优解