我们在写某些字符串问题上经常需要用到一些基础架构, 当然你可以选择直接暴力。一般，我会选择一些效率够高的函数模板,因为你需要多次调用。以下是我总结的几个关于常用的字符串操作模板: 判断x是否为y的子序列: class Solution: def isSubsequence(self, s: str, t: str) -> bool: i = …

离散化（discretization）是一种数据处理技术，特别适用于数值范围较大但实际数据分布较稀疏的情况。以下是一些离散化的主要用途和优点： 减少数值范围： 离散化可以将较大范围的数值数据映射到较小范围的整数，减少处理复杂度和计算开销。 处理重复值： 在原始数据中，可能存在重复值，通过离散化可以将这些值映射到同一个整数值，从而更容易进行后续的处理…

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/…