little-bee-client

Why

大多数人都有过这样的体会：刷过一系列算法题，并且对常见的解题思路已经了然于胸，可一段时间后，以前的算法题再次变得很陌生。

这一方面是因为很多算法的解题思路巧妙但不直观，另一方面也是因为平时的编码工作并不经常涉及这些巧妙的算法。

为了快速回忆起遗忘的常见算法，这篇“蜂博客”罗列了常见算法的核心思想。

为什么选择”LeetCode”为例子阐述算法？

“LeetCode”是一个比较完善的在线题库，有以下几个优势：

• “LeetCode”框架设置了输入，用户不需要自己编写输入逻辑，可以集中思考算法逻辑。
• 网络中资源丰富，可以找到各种语言的不同解题思路。
• 题目描述简洁清晰，可以快速理解题目的意思。

What

常用的算法有哪些？

• 暴力解法
• 深度递归解法
• 动态规划解法
• 回溯递归解法

常见的数据结构有哪些？

• 数组
• 字符串
• 链表
• 树

How

常用的算法是如何实现的？

• 暴力解法
  暴力解法是最直观的解题思路，但是效率一般不如其他的方法。暴力解法的主体思想是将问题解法的可能性进行分类枚举，并用大量循环结构解出问题的解。本人建议，对于陌生的算法题，可先用暴力解法得出问题的答案，再思考是否有其他更高效的解法。

• 深度递归解法
  树的深度遍历包括：前序遍历、中序遍历和后序遍历。三种遍历都可以通过递归，将大问题化解成小问题，并以边界条件终止。深度递归解法类似深度遍历，利用递归将问题拆解，找到终止逻辑，并通过递归缩小问题范围（如同深度遍历，每次递归处理的树都是上次递归的子树）。

• 动态规划解法
  动态规划是利用小问题的结果，推导出大问题的结果。过程类似数学归纳法。动态规划一般利用一个数组（一维数组或者二维数组）记录每个小问题的结果，利用循环一步一步解出最后的大问题结果。
  • 动态规划与深度递归的不同点：
    深度递归解法是从大问题入手，找出可以递归的小问题和终止条件。而动态规划是从小问题入手，从小问题的结果，推导出大问题的结果。
    以求“费布拉切数列”f(n)问题为例。动态规划解法会依次求出f(1)到f(n-1)的所有值，再推导出f(n)的值。而深度递归解法并不会记录f(1)到f(n-1)的值，而是 利用递归直接求出f(n)的值。
• 回溯递归解法
  回溯递归就像走迷宫，走遍所有路径，如果路径错误，就退回上一步，记录所有可行结果。如：“39.Combination-Sum”和“40.Combination-Sum-II”，为了获取所有可能结果，利用循环加递归，不断枚举可能路径，并通过一个全局变量，记录可行的结果。如果需要缩小枚举范围（如”40.Combination-Sum-II”中对重复数据的处理），可添加额外的检查，终止此路径的递归调用。

常见的数据有哪些操作？

• 数组
  对数组最常见的操作是排序，算法的C++实现可参考GitHub。
  • 暴力解法
    排序的暴力解法包括：选择排序，冒泡排序，插入排序等。暴力解法的时间复杂度都是：O(n^2)。其中，冒泡排序和选择排序的最优时间是O(n)。
    • 选择排序是最直观的算法，即每次遍历都选出未排序数据中的最小值，并放到已排序数据的末尾。
    • 冒泡排序每次遍历也会在已排序数列中增加一个数据，但是不同于选择排序，冒泡排序每次比较都会试图更改数据排列顺序。这个特点就可以优化最优时间。如果一次遍历没有出现数据排列顺序的变化，就表明数据已经排好序，可结束算法。
    • 插入排序类似扑克牌整理过程。每次遍历都会从未排序的数据中任意选择一个，插入到已经排序的数据中。如果是已经排序好的数据，不需要插入的动作，只需要一次比较的动作。因此，最优时间是O(n)。
  • 递归解法
    排序的递归解法包括：快速排序，归并排序，堆排序。递归解法的时间复杂度都是：O(nlogn)。
    • 快速排序将数组根据某个数进行分类，一组数据都小于这个数，另一组数据都大于这个数。这样就可以缩小数据规模，从而利用递归，达到排序的效果。一次分组过程如下，以{49 38 65 97}初始数据为例子，选取49为比较数字，经过一次归并后，得到两组数据{38} 49 {97 65}。继续为此两组数据进行分组，直到分组中的数据只有一个。采用左右逼近比较的方法，进行一次分组。
    • 归并排序将两组已经排序好的数组，归并成一组排序数据。类似树的后序遍历，在递归后得到两组排序好的数据，在归并过程中按顺序比较数据大小，组合成一组数据，需注意边界情况。
    • 堆排序是三者中最复杂的算法。需要建立二叉树数组模型，并利用递归建立最大堆（所有父节点的值大于其两个子节点的值）。最大堆的根节点就是所有数据中的最大值。取出最大值后，又需要调整剩余数据构建新的最大堆。以此类推，直到最大堆中没有数据。

• 字符串
  对字符串的底层数据结构和数组是一样的，常见的操作如：寻找回文子串，逆序等。大部分问题可以先从暴力解法入手（一般是多层循环），再考虑是否可以优化（如：动态规划，KMP等）。

• 链表
  对链表的常见操作是顺序变化（如：逆序，排序）。
  • 单向链表
    单向链表最大的特点是只能单向遍历，如果需要从后往前拿数据，就会比较麻烦。常见的做法是结合栈的特点达到从后往前遍历链表。例如“143.Reorder-List”中，就通过Stack完成了对单向链表的重组操作。需要注意的是，在对链表操作中，会存在数据个数单双数两种情况，可以先分两种情况考虑，再看看能不能合并。
• 树
  对树的常见操作有：树的遍历（如：广度优先，深度优先）。
  • 深度遍历
    深度遍历分：前序遍历、中序遍历、后序遍历。可用递归方法很方便地实现。也可以结合栈的特点，通过迭代实现。
  • 广度遍历
    广度遍历可用递归的方法完成。也可以结合队列的特点，通过迭代实现。