1658. 将 x 减到 0 的最小操作数

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

双指针 · 10 天前

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 =

二分法 · 13 天前

611. 有效三角形的个数

题目链接：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$也必然成立（分别将两个变量移到不等号右边），那么第二个条件天然地满足了，只剩下

二分法 · 21 天前

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

搜索 · 09-24

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

搜索 · 09-17

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