有时，由于我们无法预估未来数值带来的变化，我们可能会先保存未来答案用不到的值，放在堆里。当发现一个更好的值可以替代时，我们会反悔答案，替换掉堆顶元素。 https://leetcode.cn/problems/course-schedule-iii/solutions/2436667/tan-xin-huan-neng-fan-hui-python…

容斥定理有三种方法：回溯，二进制枚举和库函数combinations，我比较喜欢用combinations，因为比较快，注意每comb多一位就多乘一个-1，因为容斥定理是正负交替的 https://leetcode.cn/problems/sum-multiples/description/ class Solution: def sumOfMul…

题解 模板： cnt = dict() for i, x in enumerate(nums): cnt = {or_ | x : left for or_, left in cnt.items()} cnt[x] = i for or_, left in cnt.items(): ...... 练习：https://www.lanqiao.cn/…

回文串是指字符串从左往右从右往左都是一样的，详细看灵神题解 class Solution: def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]: cnt = [0] for c in s: cnt.append(cnt[-1] ^ (1 &l…

我们时常用dp(动态规划)去解决某一些问题,但有没想过如果要你返回搜索路径,你该怎么做? 下面一题是用dp要求一份最小答案,我们返回最小答案那段路径,我们可以用在get_ans中查询路径是否和已存在dfs_cache中的dfs(i， j)进行比较,同时保留路径ans class Solution: def findPermutation(self,…

拓扑排序是对事件先后顺序有要求的排序,但只能是对无向图AOV图,有环图无效(因为没有顺序可言) g = defaultdict(list) indeg = [0] * n #入度 #建图 for x, y in nums: g[y].append(x) indeg[x] += 1 cnt = 0 order = []#拓扑排序表 q = deque…

二进制枚举,在处理在n个选numSelect个1的情况,适合用Gosper's Hack subset = (1 << numSelect) - 1#起始位置 while subset<...: lb = subset & -subset#lower bound left = ((subset ^ x) // lb >…

并查集底层是由森林构成的，森林里的一个树相当于一个集合，并查集可以对集合进行合并（并）和查询（查），“查”的底层是find根节点，目的是区分集合；而“并”就是先找到两个节点的根节点（两个集合），在对根节点进行合并（一般是小树合并到大树），这样就完成了并查集的基本定义。下面是py模板： # 并查集模板 class UnionFind: __slots…

质数也叫素数，指大于1的自然数中，除了1和它本身外不再有其他因数的自然数，比如2、3、5、7、11、13。 以下是有关质数的一些板子: 素数筛 常用的质数筛算法有试除法、线性筛和埃氏筛。我个人喜欢用的是埃氏筛。时间复杂度：试除法>埃氏筛>线性筛 试除法 MX = 10 ** 5 + 1 primes = [] [primes.appen…

货仓选址问题常用来求在几个数（一个数组）值中间选一个数，使得这个数到数组所有数的距离之和代价最小。这时选取中间的数是最优的想法（奇数中位数，偶数[nums[(n-1)//2], nums[n//2]]范围内都可以），下面是两种代码模板： 滑窗+前缀和 def maxFrequencyScore(self, nums: List[int], k: i…