kmp def prep(p): pi = [0] * len(p) j = 0 for i in range(1, len(p)): while j != 0 and p[j] != p[i]: j = pi[j - 1] if p[j] == p[i]: j += 1 pi[i] = j return pi 匹配： $ 仅作为标识符，分割战场。…

先从一个例题出发 假设有一个数组array[0…n-1]，里面有n个元素，现在我们要经常对这个数组做两件事： 更新数组元素的数值 求数组任意一段区间里元素的总和（或者平均值） 我有哪些方法实现上述操作? 1. 方法一：遍历一遍数组 时间复杂度：O(n) 方法二：线段树☑️ 时间复杂度：O(logn) 直接奉上线段树模板： 线段树：单点修改，区间查询…

字典树 https://leetcode.cn/problems/implement-trie-prefix-tree/description/ # 定义Trie节点类 class TrieNode: __slots__ = 'children', 'is_end_of_word' def __init__(…

树状数组（时间复杂度On）：常用于处理动态数组的前缀和/区间和查询和单点更新 leetcode原题链接：https://leetcode.cn/problems/range-sum-query-mutable/description/?envType=daily-question&envId=2023-11-13 class Fenwick…

时间复杂度不高，复杂度为logU（U为遍历最大值） https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/description/ class Solution: def numberOfPairs(self, nums1: List[int], nums2: List[int]…

有时，由于我们无法预估未来数值带来的变化，我们可能会先保存未来答案用不到的值，放在堆里。当发现一个更好的值可以替代时，我们会反悔答案，替换掉堆顶元素。 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,…