- 博客(199)
- 收藏
- 关注
RSS订阅原创 LeetCode面试经典150题 - 5. 哈希表九题
只遍历一次numsset，而不是像之前那样可能在每轮遍历numsset时，都得while寻找终点。的字符映射（相当于保证了s中字符到t中字符的映射的唯一性），中的同一个字符（相当于保证t中字符到s中字符的映射的唯一性）哈希字典法，用Counter也可以，但是Counter会比较慢。更慢，但是处理思路可以在其他题目中有所参考。这一方法比起上一种方法，只需要常数空间。O(n)时间（或者说O(2n)）中已经安排过映射的字母，防止。或者用字典统计然后比较也可以。中的不同字符可以映射到。这样是真正的O(n)
2025-05-28 15:06:42
526
原创 LeetCode面试经典150题 - 4. 矩阵五题
但难点在于：如果这个格子的状态改变，不能直接改变。即题目中说的：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。因此我们需要使用特殊值去标记发生改变的格子，从而根据特殊值可以知道这个格子原状态是什么，要更新的状态是什么。这道题主要就是模拟，遍历每一个格子，然后统计其周围八个格子的活细胞个数，来看这个格子的状态是否改变。1：未更新过的原来是活细胞格子（或者已更新过的活细胞->活细胞）2：已更新过的原来是活细胞的格子，且活细胞->死细胞。思路比较简单，每个格子都检查一遍周围格子的情况。
2025-05-27 22:36:07
755
原创 LeetCode面试经典150题 - 3. 滑动窗口四题（两道困难题）
直到剔除某个配料后，该配料在target中的数量大于0，则说明当前窗口已经缩到了刚好不能满足配料表的情况，右移右边界拓展当前准备材料，如果当前材料属于配料，则配料计入target（target对应配料减一），一旦target中对应配料的数量变为0，则说明满足了一种配料，length要减去一。当length变为0时，说明当前窗口已经满足配料表（当前窗口是符合要求的子串），内所有字母看作配料，一种字母的出现次数为配料需要满足的量，此时右边界暂时固定，右移左边界，不断剔除左边界处的配料，
2025-05-27 16:55:35
1015
原创 LeetCode面试经典150题 - 2. 双指针五题
用接雨水前后缀最大值的思路剪枝，遇到短板就从短板处出发找下一个更大高度（因为只有这样，才可能使容积变大）（虽然这样的做法其实本质上也是双指针，但是写得实在太乱了）京东手撕一面题，没撕出来，明明做了好多遍！其他问题倒是没有，面试官当时说我的解法依然是。，只是思路并没有直接写成双指针那么清晰。，但是我认为不是的，实际上应该就是。原地写法，也是比较简单的。手撕时的问题应当是出在。放在了大循环之外，，否则可能会出问题。
2025-05-25 00:30:29
829
原创 python中的位运算符
例如，5（101） ^ 3（011） ^ 4（100） = 5 ^ (3 ^ 4) = (5 ^ 3) ^ 4。例如，5（101） & 5（101） = 5（101）。例如，5（101） | 5（101） = 5（101）。例如，5（101） << 2 = 20（10100）。例如，20（10100） >> 2 = 5（101）。例如，5（101） | 0 = 5（101）。例如，5（101） ^ 0 = 5（101）。例如，5（101） ^ 5（101） = 0。例如，5（101） & 0 = 0。
2025-05-05 04:19:06
971
原创 18. 多维动态规划五题
这个做法还是比较好理解的，就是从左往右遍历s，每次都以当前索引为回文中心（奇数长度和偶数长度的中心都要处理一次）向左右两边同时扩展计算当前中心的最长回文子串长度。固定行，从左到右遍历列相当于固定子串起点，在s上向右扩展子串终点；固定列，从下到上遍历行相当于固定子串终点，在s上向左扩展子串起点。判断 在短的子串进行左右两边等长的扩展后的子串 是否是回文串。本质上是利用已经计算好的短的子串是否是回文串的bool结果，重点在于dp的定义，定义写对了，后序自然就能想出来了。]是当前新比对的字符，
2025-05-05 02:35:38
854
原创 17. 动态规划十题（一道困难题）
如果没学过动态规划，可以看本人之前写的动态规划文章学习（）本篇文章只是用于作为一个hot100题解集使用70. 爬楼梯 - 力扣（LeetCode）简单而经典的dp题目，同时也约等于斐波那契数列118. 杨辉三角 - 力扣（LeetCode）本题不难，但是要注意res的形状如何生成以及初始化。198. 打家劫舍 - 力扣（LeetCode）279. 完全平方数 - 力扣（LeetCode）这是一个完全背包问题（每种物品可以选 无限次），是求最优方案而不是求方案有几个，非排列组合问题所以石头
2025-05-04 23:47:29
821
原创 16. 贪心算法四题
如果最小买入价格需要更新，那么我们只更新买入价格，不用计算利润（因为事实上利润发生在买入的下一天，现在卖出利润必然是0）；同样不难，可以类比层序遍历，前一道题类似不需要获取层数的层序遍历，但是本题类似需要维护遍历层数的层序遍历。如果最小买入价格不需要更新，那么我们可以计算利润了（因为现在已经可以卖出，且利润必然为正数）。那么我们相当于总是以当前最低的价格买入，然后遍历卖出价格计算差价，以更新得到最大的利润。我们要找的是从左到右的最大差价，所以我们维护一个当前的最低买入价格，我们维护最小的买入价格，
2025-05-04 02:14:08
659
原创 15. 堆三题（一道困难题）
如果添加的数字 num 比较大，比如添加 7，那么把 7 加到 right 中。现在 left 比 right 少 1 个数，不符合前文的规定，所以必须把 right 的最小值从 right 中去掉，添加到 left 中。如此操作后，可以保证 left 的所有元素都小于等于 right 的所有元素。如果添加的数字 num 比较小，比如添加 0，那么把 0 加到 left 中。
2025-05-03 23:46:46
785
原创 13. 二分查找六题（一道困难题）
这困难题是真难啊，这是我第一次做二分法章节，属实有点搞脑子。**对于二分法，灵茶山艾府的视频下面有一个评论(@毫微纳皮飞** ) 写的很好：另外可以学习这里的题解来加深对二分法的三种做法的印象：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）35. 搜索插入位置 - 力扣（LeetCode）引用官方题解下面的评论来解释为什么最后返回，写得非常之好：74. 搜索二维矩阵 - 力扣（LeetCode）直接做法：二分法：（建议开区间写法，比较直观形象）排除法（回想矩
2025-05-03 01:58:54
1062
原创 12. 回溯八题（一道困难题）
这样的设置相当于手动建立了两个很快速的哈希表，加快了原本的集合增删操作（虽然理论上两种方法时间复杂度一致）。startIdx用于控制从哪个数字索引开始考虑方案（避免重复考虑前面的数字）个不同的数，不需要对这里的负数索引特殊处理是因为python的列表的特性，其中diag1和diag2统计对应的斜线使用情况，它们的长度设置为。另外，还巧妙设置了queens，且无需手动回溯。该题解代码与我前面写法不同的地方在于，通过。个不同的数，且索引能一一对应；相同的情况，如(0,0)位置。 的传递，隐式实现了对。
2025-05-01 23:02:37
999
原创 11. 图论四题
第一次做本题的话，很难能做出来，因为题目中对所谓前缀树的定义解释实在是太不清楚了，甚至不知道这个数据结构是干什么用的，也不知道它的具体形状是长什么样。没做出来，实际上是一道拓扑排序题，但是本题弱化了拓扑排序的结果，只需要判断是否能实现拓扑排序即可（也就是是否有环，有环就无法拓扑排序，无环可以）方法一： 从入度思考(从前往后排序，BFS)， 入度为0的节点在拓扑排序中一定排在前面, 然后删除和该节点对应的边, 迭代寻找入度为0的节点。初始化为 O(1)，insert 为 O(n∣Σ∣)，其余为 O(n)，
2025-05-01 16:20:54
904
原创 10. 二叉树十五题（下）（一道困难题）
该结点的子树中不包含另一个结点，则从当前结点向上传递当前结点时，必然会在某个结点与另一个结点上传的信息相遇，此时相遇结点的左右子树信息均非空，且分别是p和q，此时相遇结点就是所求共父结点，需要向上返回当前相遇节点。该结点的子树中包含着另一个结点，当前结点就是所求共父结点，故从当前结点向上传递当前结点时，与该信息汇合的另一条信息必然是None，因此畅通无阻将该结点传递至最开始的递归函数；令root处深度为0，则遍历到root的右子结点时，深度为1，self.res长度为1（内部元素仅有一个root.val）
2025-05-01 12:51:42
598
原创 9. 二叉树十五题（上）
也就是说，我们要找的不是这两个结点，而是要找到这样的一个最低共父结点，该共父结点能够提供所要求的最长路径，而且最长路径一定是。用层序遍历的思路做，但是每次入队都是成对成对，出队也是成对，每一对都是轴对称位置上的两个结点。基于观察可以发现，我们所要求的树内两结点最长路径总是经过该两节点的最低共父结点！然后通过遍历整棵树的所有结点，我们将每个结点都视作潜在的所求共父结点，去获取其。通过递归返回树的最大边深度，我们可以获得当前结点的左右子树分别的最大边深度，
2025-04-30 02:46:13
969
原创 8. 链表十四题（下）（两道困难题）
第二次遍历，每两个结点为一组，组内结点一为原结点，结点二为新结点，根据原结点的random信息，找到原结点的random的下一个结点，就是新结点对应的random。例如 [4,2,1,3]，把第一个节点和第二个节点归并，第三个节点和第四个节点归并，得到 [2,4,1,3]。分割出两段长为 step 的链表，合并，把合并后的链表插到新链表的末尾。排序后，我们得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点。第一次遍历，复制原链表的每个节点的val为新节点，并插入为当前结点的子结点。
2025-04-29 04:16:54
782
原创 7. 链表十四题（上）
这道题比较简单，O(1)额外空间的写法也是比较好想的，主要障碍在于：设置dummy_head和记得剩余链表加入新链表。要记住这样的追及做法，以及循环的终止条件的处理（包含了同时找到相交起点，或者同时抵达路线终点同时成为None）那就需要先找到链表的中间节点，从链表中间节点开始看作一个新链表，翻转该新链表，O(n)空间的做法很简单，遍历链表把值依次保存在数组中，然后双指针即可。O(n)空间只需要开一个哈希集合记录访问过的结点即可。不同长度的处理，以及最终的进位的处理。如果是O(1)空间怎么办呢？
2025-04-28 23:22:48
648
原创 6. 矩阵四题
通过这样不断查询新矩阵右上角元素，删除行列，若能匹配，则True；矩阵以行(n-1)/2为中心线做轴对称变换（其实就是列索引不变，行索引从i变为n-1-i）；由于要求原地算法，所以分为两次对整个矩阵（实际上每次只需要操作半个矩阵）进行操作是更好的选择。若a < target，说明整行的元素都会比target小，直接删除整行；若a > target，说明整列的元素都会比target大，直接删除整列；因此时间复杂度为O(m+n) （顶多一一删除m行和n列直到矩阵为空）总是先查询矩阵右上角的元素，这里简记为a，
2025-04-28 16:22:40
720
原创 5. 普通数组五题（含一道困难题）
先把它计算出来，接下去一边计算后缀积，一边修改前缀积列表，使得前缀积列表变为返回的目标列表。要能想到用前缀和与后缀和做（在不能用除法的限制下，用空间换时间，换取O(n)的时间复杂度）如果用start，end进行当前新区间的更新，则需要把最后一组新区间手动添加进。这道题做过很多遍了，但是依然不会做（贪心不会做，dp的话套公式估计还是会的）要考虑的点特别多，因此手撕过程不能debug的话，其实是非常有难度的！保留前缀积或者后缀积的其中一个列表，例如保留前缀积，困难题，大前天面试刚g的一道手撕题，再做一遍。
2025-04-28 03:23:55
590
原创 4. 子串三题（两道困难题）
因为 left 至多增加 m 次，所以二重循环的时间复杂度为 O(∣Σ∣m)，再算上统计 t 字母出现次数的时间 O(n)，总的时间复杂度为 O(∣Σ∣m+n)。注意 left 只会增加不会减少，left 每增加一次，我们就花费 O(∣Σ∣) 的时间。使用哈希表写法的时间复杂度为 O(m+n)，数组写法的时间复杂度为 O(m+n+∣Σ∣)。方法一的代码每次都要花费 O(∣Σ∣) 的时间去判断是否涵盖，能不能。其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣=128。优化，时间复杂度低。
2025-04-28 00:25:36
1025
原创 3. （首尾与快慢）双指针、（定长与不定长）滑动窗口六题
283. 移动零 - 力扣（LeetCode）灵茶山艾府的写法：原地栈：非零元素入栈，同时为了节省空间，直接在nums内部构建栈双指针：要学习一下这个优雅简洁的写法这个双指针的思路和我的思路还是有些不一样的，但是个人认为这个更好，学会这个在面试过程中也不容易出错。思路： i0是慢指针，i是快指针，用快指针遍历nums，把遇到的非零元素全部往前提（放到i0处）11. 盛最多水的容器 - 力扣（LeetCode）本题难点在于要想到：迭代找到最优解过程中，需要不断优化短板15. 三数之和
2025-04-27 21:06:40
936
原创 1. 缺失的第一个正数
在第三个例子中，虽然 nums[2]=1不等于2，但由于 nums[nums[2]]=nums[1]=1，所以 nums[2] 是个影分身，并且其真身坐在了正确的座位上，所以可以忽略 nums[2]，向后遍历。注意这种情况是不能交换的，因为 nums[2]=nums[1]，交换后 nums=[1,1,2] 是不变的，这会导致死循环。我们要让索引i处的数字nums[i]回到对应的正确索引，也就是nums[nums[i] - 1]特别地，如果所有学生都坐在正确的座位上，那么答案是 n+1。
2025-04-25 15:32:29
716
原创 LeetCode面试经典150题 - 1. 数组、字符串题解二十四题记录（三道困难题）
变长数组可以在 O(1) 的时间内完成获取随机元素操作，但是由于无法在 O(1) 的时间内判断元素是否存在，因此不能在 O(1) 的时间内完成插入和删除操作。为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1)，需要将变长数组和哈希表结合，变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标。获取随机元素操作时，由于变长数组中的所有元素的下标都连续，因此随机选取一个下标，返回变长数组中该下标处的元素。这道题要求实现一个类，满足插入、删除和获取随机元素操作的平均时间复杂度为 O(1)。
2025-04-01 01:12:58
1213
原创 一刷代码随想录完结撒花！
我从一个小白开始，自2025.1.25起，约摸刚好花了两个月时间，慢慢把每一个代码随想录中所提到的每个知识点都过了一遍。这个过程确实是比较折磨，但也收获颇丰。后面可能要开始刷高频题，例如hot100这些，希望高频题我能做得更快一些，毕竟已经有了一定的知识储备了。如果有时间和精力，再回来二刷代码随想录吧。终于，咱也是把代码随想录所有章节都刷完一遍了！一共十一大章，大约170道题，全部做完。希望春招能找到心仪的实习（虽然我很菜）
2025-03-26 01:12:13
136
原创 图论 26. 最短路问题算法总结
除非 源点特别少，且边都是正数，那可以 多次 Dijkstra 求出最短路径，但这种情况很少，一般出现多个源点了，就是想让你用 Floyd 了。， 多少节点多少边算是稠密图，多少算是稀疏图，这个没有量化，如果想量化只能写出两个版本然后做实验去测试，不同的判题机得出的结果还不太一样。对于**A *** ，由于其高效性，所以在实际工程应用中使用最为广泛 ，由于其 结果的不唯一性，也就是可能是次短路的特性，（因为A * 属于启发式搜索，和上面最短路算法并不是一类，不适合一起对比，所以没有放在一起）
2025-03-26 01:04:43
422
原创 图论 23. Bellman_ford算法之单源有限最短路
为什么却又说：“计算minDist数组的时候，基于了本次松弛的 minDist数值，而不是上一次 松弛时候minDist的数值。节点数量为n，起点到终点，最多是 n-1 条边相连。SPFA 节点的进出队列操作，耗时很大，所以相同的时间复杂度的情况下，SPFA 实际上比bellman_ford更耗时了。中的常规bellman_ford写法其实严格来说是不严谨的，这种原地更新的写法会在同一轮更新所有的边，而不是只更新。在原地更新方式下，每条边的更新立即生效，本轮中后续边的松弛可能使用到本轮已经更新的值。
2025-03-25 19:54:11
871
原创 图论 22. Bellman_ford算法之判断负权回路
如果没有发现负权回路，则输出一个整数，表示从城市 1 到城市 n 的最低运输成本（包括政府补贴）。上面的bellman-ford解法中，我们对所有边松弛了n-1次后，再松弛一次，如果出现minDist出现变化就判断有负权回路。如果在这样的图中求最短路的话， 就会在这个环里无限循环 （也是负数+负数 只会越来越小），无法求出最短路径。那么如果出现任意一个节点执行松弛行为的次数超过了 n-1次 ，那么该图就一定有负权回路！本题是要我们判断 负权回路，也就是图中出现环且环上的边总权值为负数。
2025-03-25 17:53:40
992
原创 图论 21. Bellman_ford 队列优化算法（又名SPFA）（无负权回路情况）
大家可以发现 Bellman_ford 算法每次松弛 都是对所有边进行松弛。
2025-03-25 16:37:29
662
原创 图论 20. Bellman_ford 算法（可以计算负权值的单源最短路算法）
先来说什么是 “松弛”。《算法四》里面把这个操作叫做 “放松”， 英文版里叫做 “relax the edge”所以大家翻译过来，就是 “放松” 或者 “松弛”。但《算法四》没有具体去讲这个 “放松” 究竟是个啥？网上很多题解也没有讲题解里的 “松弛这条边，松弛所有边”等等 里面的 “松弛” 究竟是什么意思？这里我给大家举一个例子，
2025-03-25 03:44:50
777
原创 图论 19. dijkstra（堆优化版）
（当然小顶堆里 是 添加元素的时候 排序，还是 取数元素的时候排序，这个无所谓，时间复杂度都是O(E)，总之是一定要排序的，而小顶堆里也不会滞留元素，有多少元素添加 一定就有多少元素弹出）网上的不少分析 会把 n （节点的数量）算进来，这个分析是有问题的，举一个极端例子，在n 为 10000，且是有一条边的 图里，以上代码，大家感觉执行了多少次？我们要选择距离源点近的节点（即：该边的权值最小），所以 我们需要一个 小顶堆 来帮我们对边的权值排序，每次从小顶堆堆顶 取边就是权值最小的边。
2025-03-25 03:03:05
947
原创 图论 17. 拓扑排序
拓扑排序指的是一种 解决问题的大体思路， 而具体算法，可能是广搜也可能是深搜。其实只要能在把 有向无环图 进行线性排序 的算法 都可以叫做 拓扑排序。实现拓扑排序的算法有两种：卡恩算法（BFS）和DFS一般来说我们只需要掌握 BFS （广度优先搜索）就可以了，清晰易懂，如果还想多了解一些，可以再去学一下 DFS 的思路，但 DFS 不是本篇重点。
2025-03-24 23:30:41
683
原创 图论 15. 最小生成树之prim算法
53. 寻宝（第七期模拟笔试）代码随想录卡码网无难度标识思路：（完全不知道怎么做啊，直接摘录代码随想录作为备忘）本题是最小生成树的模板题，那么我们来讲一讲最小生成树。最小生成树可以使用prim算法也可以使用kruskal算法计算出来。本篇我们先讲解prim算法。最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。（重要论断）那么如何选择这n-1条边就是最小生成树算法的任务所在。prim算法是从节点的角度，采用
2025-03-24 21:23:08
1397
原创 图论 13. 冗余连接
在将一条边加入（join）并查集的时候，如果该边两个结点同根，说明两结点的边是冗余的，返回一个True作为标记；只要发现下面这句话的规律就好做了：（手动模拟一下其实就能发现）然后找出最下面的冗余边即可（标记最新的冗余边的索引。用并查集的思路做起来比较简单。否则返回一个False。
2025-03-24 15:49:09
406
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人