精巧算法

精巧算法

起因是在刷题的时候遇到了一些独特的算法

他们针对于某一类问题很好用，但是训练的机会可能比较少

所以在这里专门开一份笔记记录一下

最长回文子串问题

LeetCode 题目链接

这道题使用 Manacher 算法，戏称为”马拉车“ 算法，用来统计回文子串长度

这里借鉴一下来自 b 站的 讲解视频 中的一些图解

算法思路

1. 首先将一个字符串进行规范化，这样我们奇偶的回文串统一为一种处理方法

也就是在字母之间插入一个相同的字符，同时在首尾插入不相同的哨兵边界值

注意到：这里的伞帽大小就是原始串中回文串的长度

2. 观察每一个位置的回文长度性质，可以很明显看到回文的对称性

也就是字母 c 处是左侧三个 ”蘑菇“ 的对称轴，右半边可以快速对称过去

3. 但是有的时候有些”蘑菇“并不是完全处于最外层的覆盖下的，例如第二个字母 c并不能对称过去

那么我们只能知道这个蘑菇最小的范围，对这个情况我们需要从最小值向外检查大小

代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        Manacher 算法，整体 O(n) 时间，O(n) 空间
        - 通过预处理把奇偶回文统一成“奇数长度回文”
        - p[i] 表示：在预处理串 t 中，以 i 为中心的回文“半径”（向左右能扩展的字符数）
        """
        # 预处理
        t = "^#" + "#".join(s) + "#$"
        n = len(t)
        p = [0] * n # 回文半径长度

        # center/right：当前已知“最右回文”的中心与其右边界（right 为该回文最右端索引）
        center = 0
        right = 0

        best_center = 0     # z最长字符串在预处理串 t 中的中心位置

        # 线性扫描每个中心 i
        for i in range(1, n - 1):
            mirror = 2 * center - i  # i 关于 center 的对称点

            #  i 在当前最右回文覆盖范围内，可以用对称性给 p[i] 一个下界
            if i < right:
                # right - i：i 到右边界还剩多少可用空间
                # p[mirror]：对称点的半径
                p[i] = min(right - i, p[mirror])

            # 在已有半径基础上继续向两侧暴力扩展
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1

            # 如果以 i 为中心的回文超出了当前 right，则更新 center/right
            if i + p[i] > right:
                center = i
                right = i + p[i]

            # 维护全局最优
            if p[i] > p[best_center]:
                best_center = i

        # 映射回原串，注意到原来的 radius 就是回文串长度
        start = (best_center - p[best_center]) // 2
        return s[start:start + p[best_center]]

前缀和与差分

前缀和

就是用来求某个区间的和的算法，本质是一个离散数据的差分公式

也是用空间来换取计算速度的方法

nums = [1, 2, 3, 4, 5]

# 前缀和数组，长度 n+1，pre[0] = 0
pre = [0] * (len(nums) + 1)

for i in range(len(nums)):
    pre[i + 1] = pre[i] + nums[i]

# 查询区间 [l, r]（闭区间）
def range_sum(l, r):
    return pre[r + 1] - pre[l]

print(range_sum(1, 3))  # 2 + 3 + 4 = 9

前缀和可以和各种有（隐含）顺序的数据结构结合，例如二叉树

前缀和中有一个查表的步骤，可以用 hash 压缩到 O(1) 的复杂度

• LeetCode 437: 结合二叉树

差分数组

差分和的数组优势是：对于一个区间整体执行操作（例如加法）的时候，可以只更改区间头尾就行了

diff[i] = a[i] - a[i-1]
a[i] = diff[1] + diff[2] + ... + diff[i]

# 如果想对区间 [l, r] 整体 + val
diff[l] += val
diff[r+1] -= val

这个思想结合 Fenwick Tree，可以得到差分树状数组，应用于 3841. 查询树上回文路径

Moris 算法

这是一个二叉树遍历中的一个算法

二分查找本质

二分查找边界的本质：一个结构，对某一个 bool 表达式的值呈现单调性，我们通过对半取区间来找到第一个发生变化的区间

False False False True True True
                ↑
           我们要找的点

所以说，找下界就是找到第一个让 nums[i] >= target 从 false 变为 true 的点，上界就是第一个让 nums[i] > target 从 false 变为 true的点

我们列出循环不变量的表达式（伪代码）：bool [0, l) == Talse , bool [r, n) == True

所以有这个通用公式（面向于我们从 False 转到 True 的数组单调性）：

if f(mid) == True: # f(mid) == True, 保证了 [r, n) 是 True
    r = mid
else:  # 保证了 [0, mid + 1) 是 False
    l = mid + 1

Fenwick Tree

Fenwick Tree，又叫 Binary Indexed Tree (BIT)，是一种用于维护“前缀信息”的数据结构。

应用在：频繁对节点做加法a[i] += delta, 查询区间内和：sum(l, r)

时间复杂度是：$O(\log n)$ 空间复杂度：$O(n)$

利用 lowbit(x) = x & (-x) 可以拿到一个二进制的最低位所代表的数（利用二进制补码 -x = (~x) + 1）

例如 10100 计算出来是 4, 因为他的最低位的二进制数是第 2 位，2 ^ 2 = 4

Fenwick Tree 存储数据方式是：tree[i] 存储长度为 lowbit(i) 的区间和

例如 tree[8] 管理 [1..8]， tree[6] 管理 [5..6]，tree[4] 管理 [1..4]

def query(i): # 查询节点的值
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s
def update(i, delta): # 更新某个节点
    while i <= n:
        tree[i] += delta
        i += i & -i