算法草稿本

卡特兰数

• 应用
  • 入栈出栈顺序：1 -1 1 1 -1 1 … > 0 折线法证明结果为： c(2n, n-1)
  • 递归式满足：fn = f(1)*f(n-1) + f(2)f(n-2)…*f(n-1)*f(1) 可求解得出 fn = c(2n ,n) / n+1
    • 母函数（生成函数）
    • 二项式定理
    • 隔板法
• 公式：fn = c(2n, n) / n+1 = c(2n, n) - c(2n, n-1)
• 例题
  • 三角形问题

树

• 二叉树

• avl树

  • 单旋转
  • 双旋转

• 红黑树

• b树

• 字典树

• 哈希树

• 树状数组

  • 从上往下建树，第一层为2^n,之后为空白处开始加2^n

  • 求和：二进制数每次去掉最后一个1，累加

    • 去掉最后一个1: a = x- (x & (-x))

  • 更新第x个数，则需要更新x对应的二进制数最后一个1代表数加该数

    • 求和结果为: a = x + ( x & (-x))

  • 建树：

    • 从第一个位置开始更新
    • 对1…n 的每个数:

    1 2 3 4 5

    j := i + ( i & -i ) if i < n + 1 { bit[j] += bit[i] }

• 线段树

  • 完全二叉树
  • 叶子节点为数据节点，中间节点为对应范围的最小值\最大值\范围和

• 并查集

  • pre数组存每个点的前置节点
  • 判断一个点与另一个点是否在同一个集只需判断根节点是否相同
  • 连通两个点只需设置其中一个点的根节点的前置节点为另一个点的根节点
  • 路劲压缩，查找根节点时把当前节点的前置节点设置为根节点
  • 食物链问题

图

• prim最小生成树算法
• 多源最短路径
• 单源最短路径

算法

• 大整数相乘
• tim排序
• 移棋子问题
  • 两个组合计算间隔数
  • 所有间隔数转化为nim游戏
    • 所有数字求异或，结果为0比输，不为0有必胜策略设为k
    • 必胜策略为：将任意在k的最高位为1的数与k异或取代改数