现实生活中的算法问题

“找女朋友”问题的37%法则，参考链接
Priority Queue 一个任务的密度 = 重要程度/完成时间，每天将任务放进优先队列进行排序，再开始干
Kelly Formula 凯利公式
Game Theory 博弈论

代码模板

递归：
- 递归的终止条件：“盗梦空间的陀螺”
- 当前层的数据操作
- drilldown，下钻操作
- reverse，恢复现场
DFS递归写法与BFS
二分查找
- left，right与mid，为防越界mid=left+(right-left)/2
- 左右边界的调整
DP
- 状态定义，一般是数组
- 初始状态定义与状态的转移推导
- 最优解的位置，一般是数组开头或结尾
位运算
- X & 1 == 1 OR == 0 判断奇偶 (X % 2 == 1)
- X = X & (X-1) => 清零最低位的 1
- X & -X => 得到最低位的 1

答疑——不同编程语言的语法问题

Python: x, y = 1, 2 Versus Java or C++: x=1; y=2;

Python: x, y = y, x Versus Java or C++: int tmp = x; x = y; y = tmp;

Python版链表逆置：

def reverseList(self, head):
    cur, prev = head，None
    while cur:
        cur.next, prev,cur = prev,cur, cur.next
    return prev

Python版链表交换相邻元素：

def swapPairs (self, head ) :
    result = ListNode(0)#dummy node
    pre, pre.next = result,head

    while pre.next and pre.next.next:
        a = pre.next
        b = a.next
        pre.next, b.next, a.next = b, a, b.next
        pre = a
    return result.next

练习和切题

持续练习 + 精深练习（刻意练习）

除了“做熟悉和会做的题目 ”之外，去刻意练习自己不熟悉的算法和数据结构。
不要为了切题而切题
做过的题目后续要返回再复习

LeetCode上的各种榜单和Topic组合

面试答题四件套

Clarification（询问题目细节、边界条件、可能的极端错误情况）
Possible Solution（所有可能的解法都和面试官沟通一遍）
- Compare Time & Space Complexity（时间复杂度&空间复杂度）
- Optimal Solution（最优解）
Coding（写代码）
Test Cases（测试用例）

切题姿势

环境准备
- KeyBoard Setup
- Items + Oh_my_zsh
- IDE(Pycharm/IntelliJ/WebStorm)
- Editor(VSCode/Atom/Vim/Sublime)
读懂题目，与面试官确认好（数据范围、极端条件等）
列举可能的实现路线
初步写一个简单的main()函数或_init_方法，能够实现简单的测试（返回值）

针对各种路线，分别予以实现，以解决三角形路径最小值为例：

递归解法：
- 列出递归的模板：terminator、process、drill down、reverse
- 写好terminator、drill down，此问题终止条件是到了最后一行即最后一个子数组，drill down是往下探测下一行左右两个节点
- 填充process 和 reverse。此问题proess就是记录节点的值，因此reverse可以不要。一开始不知道怎么做，可以先做一些埋点，把变量输出来。比如在递归的时候把到达的节点打出来，形成一条路径，便于理解

暴力递归代码：

private int _dfs(List<List<Integer>> triangle,int i, int j,String
path, int sum){
//terminator
if (i triangle.size()-1){
   path += triangle.get(i).get(j)+"#";
   sum+= triangle.get(i).get(j);
   System.out.println(path+" with sum: " + sum);
   minSum=sum>=minSum?minSum:sum//minSum是全局变量值，记录路径最小值
   return sum;
}
//process
path += triangle.get(i).get(j)+→>;
sum += triangle.get(i).get(j);

// drill down
_dfs(triangle,i:i + 1, j, path, sum);
_dfs(triangle, i:i + 1，j:j + 1, path,sum);

//clear states(reverse)
// NOTE: no need to clear up the state `path`
return sum;
}
public int minimumTotal(List<List<Integer>> triangle){
if(triangle.size() =0 || triangle.get(0).size()==0){
   return 0;
}    
return _dfs(triangle,0,0,"",0);
}

DP解法：
- 考虑状态定义的方式，一般是一维或二维数组，如果是一维数组，求最值，则可以省去数组的定义，累积到数组首/尾，也可以用一个变量存储。
- 写出递推循环。此问题是行从尾到首，列从尾到首的二重循环。DP一般都是从终止状态到起始状态的倒退。
- 填充循环，即对数据的处理。首先写出DP方程

DP代码：

public int minimumTotal(List<List<Integer>> triangle){
if (triangle.size() ==0 |l triangle.get(0).size() == 0){
   return 0;
}
for(int i = triangle.size()-2; i >= 0; --i)
for(int j = triangle.get(i).size() - 1; j >= 0;--j){
   //DP formula
   int min = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1));
   min += triangle.get(i).get(j);
   triangle.get(i).set(j, min);
}
return triangle.get(0).get(0);

设计一些测试用例，测试一下，考虑边界等特殊情况

上面三角形路径的例子，测试部分（主函数）如下所示：

public class Solution{
    public static void main(String[] args){
        Solution sol = new Solution();
        int result = sol.minimumTotal(Arrays.asList(
        Arrays.asList(   2),
        Arrays.asList(  3,4),
        Arrays.asList( 6,5,7),
        Arrays.asList(4,1,8,3)));
        System.out.println(result);
    }
}

最后：沟通和交流很重要

面试官不应被看成监考老师，而是未来工作的同事，应当进行充分的沟通。

番外篇：回到起点——Fibnacci数列

Fibnacci数列第n项求解的几种方法，前面都已经学过了。目前为止，介绍到的求解方法，时间复杂度最优的是O(logN)。

在番外篇中，覃超老师讲解了另一种思路：矩阵求解，下面是具体过程：

|f(n)  |    |1  1|   |f(n-1)|
          =        *         
|f(n-1)|    |1  0|   |f(n-2)|

根据此公式，若将其递推下去，那么有：

|f(n)  |    |1  1|   |1  1|        | 1 |
          =        *        * …… *      
|f(n-1)|    |1  0|   |1  0|        | 1 |

其中，记行列式A=

|1 1|
|1 0|

的数量共有n-1个，那么f(n)的求解就转化为行列式A的幂A^n-1，而根据前面的知识，power(x,n)的最佳时间复杂度为O(logK)。这样，我们就将Fibnacci数列第n项求解的时间复杂度降到了O(logN)。

结束语

算法和数据结构是内功，重在平时的练习。将典型的代码模板背下来并练习不下五遍，定能“下笔如有神”

总结回顾