数据结构

  • 链表
  • 数组(多维)
  • 队列
  • 堆
  • 栈
  • 二叉树

编程思想

迭代(Iteration)

迭代

由远而近地逼近问题的最终解。

  • 定义:将输出做为输入,不断进行处理;像一个不断循环的圆圈。
  • (+) 逻辑清晰,空间利用率高。
  • (-) 有时难以抽象出循环次数,例如汉诺塔问题。
  • 迭代 vs 循环

    • 虽然他们都是描述一个重复操作,但是 循环 侧重于每次操作的 相同之处(做什么操作),而 迭代 侧重于每次操作的不同之处(输入输出的数据)。
  • 迭代 vs 递归
    • 大部分时候递归跟迭代是可以相互替代的。具体来说,迭代比较容易转成递归,但是如果递归要转成迭代,有时候难以抽象出其概括性的子问题,例如汉诺塔问题。如果都可以的话 优先使用迭代(效率持平或更高)。

递归(Recurrence)

迭代

自顶向下,不断缩小问题规模从而最终得到解。

  • 定义:自己调用自己,遇到终止条件时停止;像一颗不断往下探索最终汇总的树。
  • 优劣:
    • (+) 与迭代相比,很多时候可读性更强。
    • (-) 如果没有 尾递归 优化,则会占用大量内存(视问题深度),可能导致 栈溢出。
    • (-) 计算效率低,可能导致一些冗余计算(例如计算斐波那契数列),过多的函数调用也会拖慢计算。
  • 递归三步走:
    1. 想清楚怎么把问题分解成 更小规模的子问题(确定输入、输出);
    2. 确定 递归关系式,注意边界条件;
    3. 确定 递归结束条件,一般是当规模最小的时候。
  • 优化技巧:
    • 可以加入 历史记录 缓存,避免大量冗余运算(参考动态规划)。
    • 尽量保持 尾递归,消除调用栈。

动态规划(Dynamic Programming)

自底向上,不断扩大问题规模从而最终得到解。

  • 定义:利用历史记录(一般是一、二维数组)来避免重复计算。
  • 优劣:
    • 略
  • 动规三步走(类似递归):
    1. 想清楚应该保存什么 历史记录(例如一维、二维数组);
    2. 确定历史记录之间的 动规关系式;
    3. 确定历史记录 初始值。
  • 优化技巧:
    • 只保存接下来用得到的历史记录,而无需保存完整的历史记录。
  • 递归 vs 动态规划
    • 他们的核心思想(即 递推关系式)其实非常类似,但是他们的出发点与实施思路不同。「递归」更多的是考虑自顶而下分解问题,通过不断解决小规模的子问题来最终完成最终解;而「动态规划」的出发点则是考虑利用先前的结果来帮助之后的结果,具体实现更偏向于「正面硬钢递推」。
  • 补充:什么时候适合用动态规划?需要满足两个条件:
    1. 最优子结构:对于多阶段决策问题,如果每一个阶段的最优决策序列的子序列也是最优的,就称为最优子结构。
    2. 无后效性:类似马尔科夫链,某个决策只受上一个决策(即当前状态)的影响,不受更早的决策(即之前的状态)的影响。

强烈推荐搞懂 背包问题,很多算法题都是背包问题的变种。

其他

  • 二分法
  • 分治法
  • 贪心法
  • 搜索

编程技巧

边界条件

  • 注意边界条件
  • 考虑输入为:最小值、最大值、0、空、空容器
  • 考虑循环的开始条件、结束条件
  • 考虑双指针相遇

算法优化

  1. 哈希
    • 能用哈希尽量用哈希,例如在搜索、寻找匹配的时候。
  2. 剪枝
    • 对加速来说,剪枝很重要,可以去掉很多不必要的运算。
  3. 排序
    • 跟数值大小有关的题可以考虑先做个排序,快排的平均时间复杂度是 $O(n \log n)$,通过排序可以去掉大量重复操作,即上面的「剪枝」。

其他

  • 入门算法
    • 各种排序算法
  • 入门数学
  • 入门概率论

  • 算法复杂度计算

  • 编码风格
  • 调试能力
  • 异常处理
  • 编码速度

参考

▲