数据结构

• 1 分钟阅读

我好想好好学习啊.

ai 的出现好像让许多许多事情，变得似乎没那么有价值和意义，
包括这里的，从知识总结到这里的做数据结构和算法题 ai 做的比我都好的多。
但，我还是突然好想好好学习啊…

base

base-structure

  • linear
    • array
      • 连续内存位置，偏移
    • linked list
      • 指针或别的链接连接
    • stack, queue
      • 可以通过上面两类实现，可以看作上面两个东西被限定了操作方式的东西，相比上面可能是种更具体的结构
  • non-linear
    • tree
    • graph
    • heap
    • 它们，相比 linear，同样可以被遍历访问，但没有唯一的顺序了。实现，同样都有连续储存和链接两种实现。
      • dfs, bfs
      • dfs 可以使用 栈（stack） 为遍历中节点的暂存容器来实现；这与用 队列（queue） 实现的 bfs 形成高度对应。
  • hash table

算法x

  • 分析，时空复杂度
  • 设计

递归与分治

递归是种具体的编程技巧，分治是种解决问题的范式。

  1. 递归

递归要想的就是，结束条件和自我调用。

func(传入数值) {
  if (终止条件) return 最小子问题解;
  return func(缩小规模);
}
  1. 分治
  • 问题可缩小解决：基准情况（Base Case）简单。
  • 最优子结构：问题可分解为相同子问题，且解可合并。
  • 子问题独立：分解出的子问题互不重叠，各自独立。

dynamic programming

  • 动态规划可以处理的问题通常是最优化问题，在一堆方案里找一个最 xxx 的结果之类的。
  • 找到一个合适的结构，无后效性的最优子结构: 一个问题的最优解，可以从其子问题的最优解中直接、简单地构造出来，而无需考虑其他非最优的子解或更早的历史。然后围绕这个结构写状态转移。
  • 有一条，渐进式的路：暴力 dfs 搜索 => 加 memo 记忆化搜索 => 递归改迭代，动态规划。
    • 关于寻找最优子结构，加 memo 其实也是在做相同的事，之所以可以这么干，是同一个子问题无论被谁调用，其最优解都是唯一且相同的。
  • 动态规划也许和很多都会相关
    • 算法范式上，最优子结构在说分治，寻找最优解是贪心，遍历着找全局最优解是搜索。
    • 而动态规划里，局部最优不是全局最优，所以简单贪心不够用；有大量可以剪枝的重复计算，子问题并不独立，简单分治不够用。
    • 递归与迭代。

三个性质,动态规划的适用性三角：

  1. 最优子结构是灵魂（能不能分解）。
  2. 重叠子问题是动力（值不值得优化）。
  3. 无后效性是工具（状态该怎么存）。

在解决具体问题时：

  1. 当你苦思冥想状态转移方程时，你在运用最优子结构。
  2. 当你决定用数组 Memo或 DP Table时，你在应对重叠子问题。
  3. 当你发现状态必须增加维度（如记录访问历史）时，通常是在努力满足无后效性。

base-… programming?

计算机程序可以被分为数据与算法，数据结构可以看作数据，而算法…是处理使用数据的程序段。
面向对象里对象的属性和方法，函数式编程里的闭包和函数，也许都可以看作组织这两者的更具体有规律的方式。
即使在什么都没有的 C 里，也会有将一些东西抽象成数据，用表驱动编程去替代冗长的 if else 这种做法。

一些具体的

虽然这种东西一般会优先考虑看看社区有没有实现好的经过广泛测试验证了的，但，有时候还是会想看看。

interval tree

区间树，我在一个虚拟表格里看到了这个东西，那时候它在维护计算一堆物体有多少在可视范围内，或者说，碰撞检测很多会用它。

myers diff algorithm

这是一种计算两个文本串差异的算法。
最长公共子串 也许算一个相关问题，它可以用动态规划做， myers 的算法也会用到。
关于什么是好的(最优目标)文本差异:

  1. 变动尽量少
  2. 先删除再添加
  3. 变动尽量成块

a-technique-for-drawing-directed-graphs

…