分享 | python 的一些模板总结（待更新）

观铃 🔔

2884

2023.06.16

2023.06.23

发布于未知归属地

Python3 技术交流

前言
python 模板
结尾

前言

上周周赛不会写 st 表结果坐牢了，于是痛定思痛，整理了一些模板。随着以后学习，可能会更新（比如线段树。。。）

update:

【2023-06-17】更新了树状数组模板，能通用地处理动态区间最值，但最坏时间 $O (l o g^{2} N)$ （有了这个又可以拖延学线段树了。。。）
【2023-06-23】更新了线段树模板，具体运用见分享 | python 线段树入门小结

python 模板

一、区间查询

动态区间和_树状数组

动态区间最值_树状数组

静态区间最值_ST表

区间万能_线段树

class BIT:
    def __init__(self, A):
        self.tree = [0]*(len(A)+1)
        self.A = [0]*len(A)
        for i,a in enumerate(A):
            self.update(i,a)

    def update(self, i, x):
        add = x - self.A[i]
        self.A[i] = x
        i += 1
        while i < len(self.tree):
            self.tree[i] += add
            i += i & (-i)

    def get(self, i):
        res, i = 0, i+1
        while i > 0:
            res += self.tree[i]
            i &= i-1
        return res
    
    def query(self,l,r):
        return self.get(r)-self.get(l-1)

典型题目：

307. 区域和检索 - 数组可修改

2407. 最长递增子序列 II

2736. 最大和查询

class BIT:
    def __init__(self, A):
        self.tree = [0]*(len(A)+1)
        self.A = [0]*len(A)
        for i,a in enumerate(A):
            self.update(i,a)

    def update(self, i, x):
        add = x - self.A[i]
        self.A[i] = x
        i += 1
        while i < len(self.tree):
            self.tree[i] += add
            i += i & (-i)

    def get(self, i):
        res, i = 0, i+1
        while i > 0:
            res += self.tree[i]
            i &= i-1
        return res
    
    def query(self,l,r):
        return self.get(r)-self.get(l-1)

class NumArray:

    def __init__(self, nums: List[int]):
        self.tree = BIT(nums)

    def update(self, index: int, val: int) -> None:
        self.tree.update(index,val)

    def sumRange(self, left: int, right: int) -> int:
        return self.tree.query(left,right)

二、字符串匹配

1、 kmp

Python

def kmp(s):
    nxt, j = [-1], -1
    for i in range(len(s)):
        while j >= 0 and s[i] != s[j]:
            j = nxt[j]
        j += 1
        nxt.append(j)
    return nxt     # nxt[i]:i-1结尾的最大真前缀长度

典型题目：

1392. 最长快乐前缀（1876 分）
1397. 找到所有好字符串（2667分）

1392. 最长快乐前缀

1397. 找到所有好字符串

def kmp(s):
    nxt, j = [-1], -1
    for i in range(len(s)):
        while j >= 0 and s[i] != s[j]:
            j = nxt[j]
        j += 1
        nxt.append(j)
    return nxt

class Solution:
    def longestPrefix(self, s: str) -> str:
        i = kmp(s)[-1]
        return s[:i]

2、manacher

Python

def manacher(s):
    n = len(s)
    A, B = [], [1]*n
    mid, r = 0, 0
    for i in range(n):
        a = min(A[2*mid-i], r-i) if r>i else 0
        while i-a and i+a<n-1 and s[i-a-1]==s[i+a+1]:
            a += 1
            B[i+a] = max(B[i+a],a*2+1)
        A.append(a)
        if i+a>r:
            mid, r = i, i+a
    return B                               # B[i]:i结尾的最大回文子串长度（奇数）

ss = '#' + '#'.join(s) + '#'
B = [(b+1)//2 for b in manacher(ss)[1::2]]  # B[i]:i结尾的最大回文子串长度（所有）

典型题目：

214. 最短回文串
1960. 两个回文子字符串长度的最大乘积（2691 分）

214. 最短回文串

1960. 两个回文子字符串长度的最大乘积

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        def manacher(s):
            n = len(s)
            A, B = [], [1]*n
            mid, r = 0, 0
            for i in range(n):
                a = min(A[2*mid-i], r-i) if r>i else 0
                while i-a and i+a<n-1 and s[i-a-1]==s[i+a+1]:
                    a += 1
                    B[i+a] = max(B[i+a],a*2+1)
                A.append(a)
                if i+a>r:
                    mid, r = i, i+a
            return B

        ss = '#' + '#'.join(s) + '#'
        B = [(b+1)//2 for b in manacher(ss)[1::2]]
        for i in range(len(B)-1,-1,-1):
            if B[i]==i+1:
                return s[i+1:][::-1]+s

3、z函数

Python

def zfunc(s):
    n = len(s)
    z, l, r = [0]*n, 0, 0
    for i in range(1,n):
        z[i] = max(min(z[i-l],r-i+1), 0)
        while i+z[i]<n and s[z[i]]==s[i+z[i]]:
            l, r = i, i+z[i]
            z[i] += 1
    return z      # z[i]:lcp(后缀i,后缀0)

典型题目：

2223. 构造字符串的总得分和（2220 分）

三、数学

1、质因数分解

Python

ma = 

def get_primes(M):
    f = [1]*M
    for i in range(2,isqrt(M)+1):
        if f[i]:
            f[i*i:M:i] = [0] * ((M-1-i*i)//i+1)
    return [i for i in range(2,M) if f[i]]

primes = get_primes(isqrt(ma)+1)

@cache
def factor(x):
    ct = Counter()
    for p in primes:
        while x%p==0:
            x//=p
            ct[p] += 1
    if x>1:
        ct[x] += 1
    return ct

典型题目：

2584. 分割数组使乘积互质

1735. 生成乘积数组的方案数

2338. 统计理想数组的数目

ma = 10**6

def get_primes(M):
    f = [1]*M
    for i in range(2,isqrt(M)+1):
        if f[i]:
            f[i*i:M:i] = [0] * ((M-1-i*i)//i+1)
    return [i for i in range(2,M) if f[i]]

primes = get_primes(isqrt(ma)+1)

@cache
def factor(x):
    ct = Counter()
    for p in primes:
        while x%p==0:
            x//=p
            ct[p] += 1
    if x>1:
        ct[x] += 1
    return ct

class Solution:
    def findValidSplit(self, nums: List[int]) -> int:
        n = len(nums)
        d = {p:i for i in range(n) for p in factor(nums[i])}
        r = 0
        for i in range(n-1):
            for p in factor(nums[i]):
                r = max(r,d[p])
            if r==i:
                return i
        return -1

2、乘法逆元

Python

ma = 
mod = 10**9+7
fac, inv = [1]*(ma+1), [1]*(ma+1)
for i in range(1,ma+1):
    fac[i] = fac[i-1]*i%mod
    inv[i] = pow(fac[i],-1,mod)

典型题目：

1569. 将子数组重新排序...

1916. 统计为蚁群构筑房间...

1830. 使字符串有序的最少操作次数

ma = 1000
mod = 10**9+7
fac, inv = [1]*(ma+1), [1]*(ma+1)
for i in range(1,ma+1):
    fac[i] = fac[i-1]*i%mod
    inv[i] = pow(fac[i],-1,mod)

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        def dfs(nums):
            if not nums:
                return 1
            A = [[],[]]
            for x in nums[1:]:
                A[x>nums[0]].append(x)
            a, b = len(A[0]), len(A[1])
            return fac[a+b]*inv[a]*inv[b]*dfs(A[0])*dfs(A[1])%mod

        return dfs(nums)-1

结尾

微信图片_20230616215138.jpg