算法思维的6个层次

登录以参加训练计划

一只羊的思维总结

志宏说算法

算法思维6个层次

一、概述

算法题的解题思路主要涉及三个方面：编程、数据结构和算法思维。
编程和数据结构相对简单，也是程序员日常工作的一部分，因此程序员一般都能熟练掌握。
算法思维灵活多变，程序员的工作生活也很少触及，市面上也缺乏系统而全面的学习资料，因此很多程序员对其相对陌生，面试也常常挂在了这里。

因此本课程解题思路的重点是算法思维，需要学员具备一定的编程和数据结构的基础。

二、算法思维层次

面试算法题的解题思路可以简单总结为以下几个层次：

L0：编程模拟

部分算法题不仅描述了想要的结果，还清楚地描述了求得结果的具体步骤。
对于这类题目，根据题目的要求编写代码即可，不涉及复杂的算法思维。（这部分简单理解即可，实际高级别考试都是考思维题为主）
题目示例：

L1：暴力穷举

绝大多数算法题都只描述了想要的结果，并没有描述求得结果的具体步骤，因此需要程序员自己来设计具体步骤。
一个听起来容易实施起来却并不容易、听起来很笨实际上却很有效的算法思维，就是：暴力穷举。

有些暴力穷举显而易见，我们可以枚举出所有可能性，再从中找出最优结果：

有些暴力穷举比较隐晦，需要做合理的“子问题拆分”，再穷举所有子问题，再根据子问题的解得到父问题的解。
关于如何做子问题拆分，可以参考动态规划模板体系中的《最优子结构全景图》。

穷举过程中有时可加入一些策略，虽然整体的搜索空间没有减少，但优先搜索了概率更大的分支，也是一种优化手段，参考“启发式搜索”。

暴力穷举法虽然看起来性能不高，但却是其他算法有效的基础，在互联网大厂的面试中举足轻重。

L2：快速跳过不必要的分支（剪枝）

穷举所有可能性虽然能够得到正确的结果，但时间复杂度较高。
如果数据存在某些特征或题目给出某些条件，则可根据规则跳过某些不必要的分支，从而降低时间复杂度。

L3：预处理

对数据的有效预处理，也可以降低算法的时空复杂度。

L4：子问题去重

一些算法是通过将大问题拆分为多个小问题来解决的，这些小问题又进一步拆分为更小的小问题来解决。
在小问题的不断拆分过程中，会出现很多重复子问题，对这些重复子问题的有效去重，可有效降低时间复杂度，相当于用空间换时间。

  • 记忆化搜索
    在计算大问题时，先递归地将依赖的小问题计算完，然后再根据小问题的最优解推导出大问题的最优解。
    计算过程中用记忆化表保存小问题的计算结果，下次再递归到这个小问题时，直接从记忆化表取结果，避免重复计算。
    980. 不同路径 III
    329. 矩阵中的最长递增路径
  • 动态规划DP
    从小到大计算<=目标问题的所有问题，并用dp数组存储这些问题的解，直到得到目标问题的解。
    1027. 最长等差数列
    198. 打家劫舍

关于记忆化搜索和动态规划的更多介绍，参考《理解动态规划》。

L5：数学

一些算法题是可以通过数学方法降低时空复杂度，甚至直接给出答案的。

三、总结

随着算法层次的不断提升，算法时间复杂度在不断下降。
L0表示仅考察编程不涉及算法，L1表示搜索整个空间，L2/L3/L4通过算法思维降低搜索空间，L5通过数学方法降低搜索为空间。

对于准备参加互联网大厂算法面试的程序员而言，更应该关注哪个层次的算法呢？是最高效的L5数学吗？
我认为恰恰相反，程序员更应该关注L0和L1，因为这决定了能否在面试中将题做出来，在能做出来的前提下，再借助L2/L3/L4的思想不断优化算法的时空复杂度。

至于L5数学方法，这是数学家应该研究的东西，程序员不可能也没必要记住太多数学公式，刷题过程中根据碰到的具体例题适量补充一些即可。

章节 1. L0 模拟

开放

题目 尝试 AC 难度
1   A+B 输入输出练习I 0 0 (无)
 
参加人数
1
创建人
  1. 任务列表
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 11ms
  4. Powered by Hydro v5.0.0-beta.8 Community