回文串是指字符串从左往右从右往左都是一样的，详细看灵神题解 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…

数位dp变通较大, 需要理解题意运用何种变量 eg.(变量名可以任取) i : 不必多言, dp核心 limitHigh : 表示当前是否受到了 finish 的约束（我们要构造的数字不能超过 finish）。若为真，则第 i 位填入的数字至多为 finish[i]，否则至多为 9，这个数记作 hi。如果在受到约束的情况下填了 finish[i]，…

ans = i = 0 n = len(s) while i < n: if i + 1 < n and ord(s[i]) != ord(s[i + 1]) - 1: i += 1 ans = max(ans, 1) st = i i += 1 while i < n and ord(s[i]) == ord(s[i - 1])…

https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150 class Solution: def merge(self, intervals: List[List[int]]) -> L…