算法速查表

请设置文章作者

发布于：Jan 1, 2000

次浏览

算法速查表

• dp, 最短子序列
• dp, 最短编辑距离: 增删改的最小次数
  • 编辑距离
• dp + bottom up, 石子合并
• 二分, leetcode 1802. 有界数组中指定下标处的最大值
  • 边界, new mid(新边界)
• dp, 完全背包问题(物品个数不限)
• 差分
• 给定一个数n, 快速求[0, n]中奇数偶数的个数
• dp, 最短hamilton路径
  • bitmap状态枚举
  • 三角不等式, 起点i,终点j, 枚举relax中间点k
• dp, 291 蒙德里安的梦, 分割问题
  • 先摆横再摆竖, 逐列扩展
  • dp[i][bitmap], 第i列, 突出状态为bitmap的情况下, 的分割情况
  • 先预处理剔除掉非当前列有奇数个0的情况
  • 状态转移: dp[i][s] += dp[i-1][k]
    • 其中k是”形成互补的状态(补满)”
  • 亮点: map of 互补的状态。当前i则可以选的状态有map[i]

===========

• 质数筛

  • 朴素筛法: 2到n枚举, 筛倍数(j += i): $n/2 + n/3 + … + n/n => O(lnn) < O(logn)$
  • 埃氏筛法: 优化朴素筛, 只筛质数的倍数就可以了。复杂度: 质数定理, 1..n中有n/lnn个质数
  • 线性筛法: 同样筛倍数，但只用最小质因子筛: 枚举质数, 是质因子就可以提前break
• 869. 试除法求约数, 主要就是枚举一半, 算另一半, 枚举i那另一约数就是n/i
       • 约数: a能被b整除, 则说b是a的约数

• 快速幂

  • 任何数都可以写成二进制表示, k同理, $a^k = \prod_x a^{2^x}$

• 滑雪

  • dfs + dp

• 树型dp, 没有上司的舞会

  • 状态表示, 以xxx为根的子树
  • 先个根据出入度找根, 自底向上

• 模拟哈希表

  • 开放寻址
  • 链表
• 4656. 技能升级
        • 多路排序
        • 大数据筛
        • 等差数列, 数学, 二分
• 143. 最大异或对
       • trie tree, 链表模拟
       • 算法逻辑

• 单调栈, use case: 求每个数左边最近的比它小的数

  • 思考怎么从暴力过渡到单调栈
  • 暴力for i, for i左边找最小, i是一点点增加的, i的左边也是，可不可以就维护点结构
  • 分析一下发现如果ax > ay且x < y那么ax一定不会用到, 因为后面的i只会越走越右。所以可以把这样的ax全都删掉

• ⭐滑动窗口: 求窗口内最大最小

  • 最大值是可以立刻更新的, 问题是最小值怎么更新
  • 法1: 最小堆
  • 法2: 两个单调队列(单调栈), 虽然是栈, 但还是需要tt来排除脱离窗口的元素的

• 小根堆: 每个点都小于左右孩子

  • 存储: 数组存, 下标从1开始
    • 2x左儿子, 2x+1右儿子
  • 基本操作: 基本操作组合和调整以达到所需效果
    • down(x): 上层节点变大了要下压。x跟最小的孩子换
    • up(x): 下层节点变小了要上提。跟父节点比, 判断是否向上
  • 插: 末尾插入, 不断up() down()
  • 弹: 最后元素和根节点交换, 然后弹出尾, 新根下沉
  • 建: O(n)建堆法, for i in n/2 .. =1 down(i)
    • 证明: 1/2 * 1/2展开分析
  • 删第k: 换到尾后删, 然后up(k) + down(k), 大了往下小了往上, 反证只会执行一个
  • 改k: 改后down + up
  • 复杂度: 插入删除O(logn), 求最小O(1), 排序O(nlogn)

• ⭐786. top k: 快速选择(快排的优化)

  • 复杂度: O(n), 每层都只用管一半, 所以是n + n/2 + n/4 … <= 2n
  • 注意分隔点: sl = j - l + 1; +1是因为top k的k是1 base
  • MSRA面试题

• 归并排序

  • 递归然后合并, 分两半递归, 归并aux数组

• dp, 01背包

• acwing 4795, 安全区域, 公式推理

• acwing 4796, 删除序列, 值域枚举

• 离散化, 802, 稀疏, 但值域大, 通过映射缩小范围

  • 我们想要一个快速的map, 可以使用大数组这样map[key].key = key就很方便, 但因为值域很大, 数组要开很大
  • 而实际情况时点位的比较稀疏的, 所以我们使用vector保存后去重 + 排序
  • 这样我们可以使用map[bfs(key)].key = key

• 803区间合并, 贪心, 类似戳气球, 但是right的更新更频繁

• 快速排序

  • 为什么不能取=, 为什么不能while() {i++}