【算法】LeetCode刷题

卡特兰数

一些LeetCode题目和经典问题与卡特兰数 $G(n)$ 有关：

• 22. 括号生成：$n$ 对合法的括号数量
• $n$ 个数可能的入栈出栈顺序的数量
• Dyck路径：从 $(0, 0)$ 走到 $(n, n)$ 走 $2n$ 步，每次可以向左或向右一步，且始终不越过对角线($y\ge x$)的路径数量

这些题目的结果都是卡特兰数$G(n)$，原因是它们的输入都是 $n$，且具有相同的“前缀约束”：比如合法的括号字符串的前缀满足“$左括号数量\ge 右括号数量$”，入栈出栈顺序满足“$入栈数量\ge 出栈数量$”，Dyck路径满足“$x\ge y$”。且最终到不等号两边都等于 $n$。还有一个卡特兰数的例子是，A和B的票数最终都是 $n$，且投票过程中 $A的票数 \ge B的票数$，求所有可能的投票过程数量。

这种性质使得我们可以把它转化为递归的形式：如果不等号第一次取等的前缀长度是 $i$ ，那么就得到了两个子问题：从0到 $i$ 的结果数量是 $G(i-1)$，从 $i$ 到 $n$ 的数量是 $G(n-i)$，于是枚举不同的 $i$ 可以得到递归的式子：

这样就得到了卡特兰数的递归公式，可以求出：

还有一道hot100题目：96. 不同的二叉搜索树也和卡特兰数有关。但是它的“前缀约束”就没有前面的例子直观：从中序遍历考虑，DFS中序遍历会访问每个顶点两次，出发一次，返回一次，DFS过程中“$出发次数\ge 返回次数$”。由于DFS本质也是栈的顺序，所以和前面栈的例子完全等价，但二叉树的例子有非常直接的递归结构能直接得到卡特兰数公式。

蓄水池抽样

流式数据如何随机的采样 $k$ 个样本？蓄水池抽样给出了一个非常简单的算法，每次抽样复杂度都是$O(1)$：

class Sampler:
    def __init__(self, k):
        self.k = k
        self.n = 0
        self.reservoir = []
    
    def update(self, x):
        """
        每产生一个流式样本x就调用一次
        """
        self.n += 1;
        if len(self.reservoir) < self.k:
            self.reservoir.append(x)
            return

        i = random.randint(0, self.n)
        if i < k:  # 以k/n的概率决定是否替换
            self.reservoir[i] = x
    
    def sample(self):
        """
        返回采样的k个样本
        """
        return self.reservoir

可以证明 $n\ge k$ 时采样到到第 $j\ge k$ 个样本的概率是 $\frac{k}{n}$。因为第 $j$ 个样本被采样意味着它加入蓄水池（概率是 $\frac{k}{j}$），且后续一直不被替换出去（概率是 $\frac{j}{j+1}\frac{j+1}{j+2}\cdots\frac{n-1}{n}=\frac{j}{n}$）。二者相乘就得到了概率 $\frac{k}{n}$。