养成算法思维

LloydFinch 6/30/2021 算法思想

有句话说得好:"算法是内功，语言是外功"，通俗的说，算法好的人，不在乎用什么招式(语言)，因为不管什么招式，没有强大的内功，都是渣，譬如慕容复之于游坦之，学了那么多，还是渣，因为内功不行。反观游坦之，屁招式不会，但因为内功强大(运气真好)，能硬杠萧峰，真是"six six six"，这就是"无招胜有招"。语言就是个api工具，真正强大的还是算法，比如刘慈欣，他不管用什么语言，都能写出来"三体"，我缺的是语言吗，No，我缺的是他那种能想出来"三体"的思维，这才是真正重要的，话不絮烦，看正文:

# 常见算法思想

常见算法思想总结如下:

分治，贪心，回溯，动态规划

# 1 分治

将问题划分为k个较小规模的子问题，对k个问题分别求解，如果子问题不够小，则继续分解，然后将子问题合并，"自底向上"求出原问题的解。

分治很简单，就两点: 1 拆分， 2 合并。有点像数学中的"分类讨论思想"，常见的是"二分查找" (opens new window)，来看代码:

public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int mid = 0;
    while (left <= right) {
        mid = (left + right) >> 1; //中间的
        if (nums[mid] == target) return mid; //找到了，返回
        if (nums[mid] > target) right = mid - 1; //大了，去左边找
        if (nums[mid] < target) left = mid + 1; //小了，去右边找
    }
    return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12

代码很简单，就像在一个由高到低的队伍里找175cm的人，先找中间，低了就肯定在后面，高了肯定在前面，这样把队伍切成一段一段的，找到了再合并起来，就是典型的"分治"。分治的用法很多，比如Android的组件化，快速排序，还有国家的行政组成，无一不是，关键在于"拆分"，所以，如果遇到"大"问题，"复杂"问题，应该要有首先想到"分治"的思想。

# 2 贪心

根据当前信息找出"最好的"，简言之就是"鼠目寸光"。

贪心一般用来得到问题的"近似解"，结果往往不是最好的，但是是"接近最好的"。

比如"背包问题": 你有一个能装20斤物体的背包，现在商场有18斤(价值3000)，12斤(价值2000)，8斤(价值1500)的东西，你要怎么装，才能获利最大，答案肯定是12斤的和8斤的，因为一目了然，但是如果物体很多呢，有一万件物体呢，现在让我们扩大问题的规模，背包能装10000斤，商场有9999斤(价值5万)，8888斤(价值4万)，2000斤(价值3万)...... 2斤(价值2000)，现在你要怎么挑选呢，因为东西太多了，看不过来，耗时耗力，所以不管了，直接挑选9999斤那个完事，这就是"贪心"的体现，只找目前"最好"的，虽然有点"鼠目寸光"，但是省事，在问题不能解决，或者难以解决的时候，找到最"近似解"，也不乏是一种好的措施。

开发中也应该有"贪心"的思想，产品提的需求太"奇葩"，无法实现？不急，稍微改下，改成"近似"的。bug找不到？不急，先"曲线救国"，曲线都没发曲线？没事，先try-catch掉吧。但是不能完全依赖"贪心"，能解决问题从而拿到"最优解"还是要解决，总而言之: "贪心只是在无法解决问题时候的一种绕弯思路，可以利用，但不能依赖"。

有技术的可以做一下这道题 (opens new window)，链接:(https://leetcode-cn.com/problems/word-break-ii/)，理解体会一下贪心的思想。

# 3 回溯

采用穷举法，一步一步向下试探，行不通就回退到上一步，继续试探另一条路，直到找到问题的答案或者试探完毕为止。

回溯的用法也很多，但是一般来说不太常见，比如N皇后问题 (opens new window)，哈密顿回路等，将回溯的思想体现的淋漓尽致，我们来看一个比较简单的问题:全排列 (opens new window)，给定一个数组，比如[1,2,3]，列出他的所有可能的全排列，这个应该没难度，可以直接"穷举":

[1,2,3] [1,3,2]

[2,1,3] [2,3,1]

[3,1,2] [3,2,1]

那么我们是怎么做的呢? 第一次: 我们先随便找一个数字A放到第1位，然后找一个不是A的数字B放到第2位，然后找不是A B的数字C放到第3位，得到ABC。

第二次: 找A放第一位，找B放第2位，只剩下C了，只能放第3位，这样和第一次ABC重复了，好，"回退"，把C放到第2位，B放第3位，得到ACB。

第三次: A放第一位，B放第二位，C第三位，得到ABC，重复了，回退；A第1位，C第2位，B第三位，得到ACB，重复了，回退，B第一位，第二位，C第三位，得到BAC。 ... ... 直到穷举完毕。这个例子体现了回退的思想: "一步一步试探，不行就回退到上一步，直到找到答案或者试探完毕为止"，

# 4 动态规划

将问题分解成若干相互重叠的子问题，对子问题求解并将结果"记录"下来，后续遇到此子问题，直接使用结果，从而避免大量的重复计算。

动态规划是典型的"空间换时间"算法，堪称是最牛逼的算法之一。其实"动态规划"这个名字起的一点都不好，看到这四个字的人几乎都是一脸懵逼，不知所云，所以他的别名叫"记忆化搜索"，不过，我觉得他应该叫"记忆化递归"更合适。我们来看个列子，稍微体会一下"动态规划"的思想，题目很简单:斐波那契数列 (opens new window) 求第n个斐波那契数，斐波那契数很简单，当n=0时候，为0，n=1时为1，n>=2时，就是前两个数字之和，比如:0 1 1 2 3 5 8 13，就是斐波那契数列。用数学函数很简单的表示为:

     = 0 (x=0)   
f(x) = 1 (x=1)
     = f(x-1) + f(x-2) (x>=2)

1
2
3

好，我们代码来实现一下:

public int fibonacci(int n) {
    if(x < 0) throw  new IllegalArgumentException("fuck the argument"); //参数不合法
    if(x == 0) return 0; // f(0)=0
    if(x == 1) return 1; // f(1)=1
    return fibonacci(n-1) + fibonacci(n-2); //否则就是f(x-1)+f(x-2)
}

1
2
3
4
5
6

根据函数，我们很容易的写出代码，但是这段代码有个很大的问题: 太费时间！举个例子，假如现在n是100:
f(100) = f(99) + f(98); //分别计算f(99)和f(98)

f(99) = f(98) + f(97); //分别计算f(98)和f(97)，但是上面已经计算过f(98)了，这里还要计算

f(98) = f(97) + f(96); //分别计算f(97)和f(96)，上面已经计算过f(97)了，这里还要计算

....

f(3) = f(2) + f(1);

f(2) = 1;

f(1) = 1; 我们可以看到，做了很多重复的工作，如下图 fib 很明显，可以看到，时间复杂度是2的n次方；怎么优化呢? 我们可以将计算过的结果"保存"下来，下一次遇到的时候，直接使用，这就是典型的"记忆化"，也是动态规划的核心思想之一，当然，保存的前提是"后面还会遇到"，否则白保存，也就是说，有"重复子问题"，这也是动态规划的条件之一，总之就是"重复子问题"，"记忆化"，我们来看动态规划版本代码:

public static int fib(int n) {
    if (n == 0) return 0;
    int[] fib = new int[n + 1]; //用来保存从0到n的n个斐波那契数
    fib[0] = 0; //f(0)=0
    fib[1] = 1; //f(1)=1
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2]; //f(x) = f(x-1) + f(x-2)
    }
    return fib[n];
}

1
2
3
4
5
6
7
8
9
10

这样以来，我们只有一个for循环，时间复杂度直接就成了O(n)，虽然空间复杂度也是O(n)，但是时间复杂度大大减小，牺牲这点空间还是值得的，各位可以计算一下，n=100的时候，动态规划时间复杂度是100，递归的时间复杂度是2的100次方，这是何其大的一个数字，各位用idea试试，没有几天是运行不出来结果的，leetcode也是直接超时的。动态规划直接将指数级的蛮力，在线性时间内解决了，不可谓不nb!

# 常见算法总结

计算机很傻，并不聪明，它只会重复，它的厉害之处在于算的快，比如计算1+2+3+.....+100，他直接加都比你用等差数列的前n项和公式计算的快，你说气不气，计算机傻的可以，只能识别if-else，while循环，for循环，递归等操作，所以我们知道这个套路的情况下，可以为计算机量身定做几种模版。

# 1 递归

递归是计算机最常用的情景之一，递归是"用来对历史进行回放"，无处不递归，比如我们经常写的函数，就是一个递归的过程，比如:

f1(){f2();}
f2(){f3();}
f3(){}

1
2
3

f1调用f2，f2调用了f3，就是一个递归的过程，因为方法栈就是基于递归实现的，f1入栈，f2入栈，f3入栈，f3出栈，结果给f2，f2出栈，结果给f1，f1出栈，结果直接返回。入:f1() -> f2() -> f3() 出:f1() <- f2() <- f(3) 正好是将"历史回放"，也就是递归的思想，换言之: 栈就是基于递归实现的!!! 我们来看下通用的递归模版:

//level表示递归深度
//param表示此深度对应的参数
public void recursion(int level,int param) {
    //检测终止条件
    if(level > MAX) return; //这里可以返回结果
    //处理当前层逻辑
    handleLogic(level,param); //这里可以改变param
    //深入到下一层
    recursion(level+1,param);
}

1
2
3
4
5
6
7
8
9
10

再来看看我们的斐波那契数递归版本代码

public int fibonacci(int n) {
    //检测终止条件
    if(x < 0) throw  new IllegalArgumentException("fuck the argument"); //参数不合法
    if(x == 0) return 0; // f(0)=0
    if(x == 1) return 1; // f(1)=1

    //这里的当前结果也就是返回值

    //深入下一层
    return fibonacci(n-1) + fibonacci(n-2); //否则就是f(x-1)+f(x-2)
}

1
2
3
4
5
6
7
8
9
10
11

来看下二叉树的先序遍历:

public void preOrder(TreeNode root) {
    //检测终止条件
    if(root == null) return;
    //处理当前层逻辑
    println(root.val);
    //深入下一层
    preOrder(root.left);
    preOrder(root.right);
}

1
2
3
4
5
6
7
8
9

简直完美诠释了递归的思想。

# 2 夹逼

我们高等数数学都学过夹逼准则，此处不再提，直接说思想: 当我们要在一个"已经有序"的序列中找某个目标，不妨直接从最大范围开始，一步一步逼近最终目标，说白了就是"逐步缩小范围"。

我们来看个题目:盛水最多的容器 (opens new window)，简单的理解下(图片来源于leetcode): 图中任意两个条都能和x轴构成一个矩形，找出能构成最大矩形的两个条。简单粗暴的遍历穷举当然可以，但是有另一种更简单的方法，就是"双指针"，也就是夹逼的实现之一，思想如下:

1 定义两个指针left和right，一个指向最左边，一个指向最右边

2 计算他们的面积area，并记录下来

3 如果left < right，就让left右移，否则让right左移，这里很简单，谁小就让谁移动，因为要求最大的。

4 依此类推，直到left==right 看下代码:

public int maxArea(int[] height) {
    //定义左右边界
    int left = 0, right = height.length - 1;
    int temp = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left); //求当前面积
        temp = Math.max(temp, area); //取最大的
        //移动指针
        if (height[left] <= height[right]) left++;
        else right--;
    }
    return temp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

可以看到，我们通过不断移动left和right，使得他们慢慢夹逼，慢慢接近，从而得出了最后结果。我们可以总结个模板:

public int squeeze(int[] arr){
    //定义左右边界
    int left = 0,right = arr.length-1;
    //左右边界不碰撞，就不断接近
    while(left < right){
        //处理当前区间逻辑
        result = handleLogic();
        //移动边界
        if(logic(left) < logic(right) ) left++;
        else right--; 
    }
    //返回结果
    return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

算法掌握好的，绝对可以"fuck sky, fuck ground, fuck air"，BAT，字节，美团等都及其重视的玩意，绝对不会错，这其中，背记no egg use，掌握思想才是王道，多归纳总结就能得心应手。

AndroidUFO

Choose mode