2020-07-02

递归控制

如何证明递归函数正确执行？

• 数学归纳法中的数学/自然语言<-->程序语言

递归书写方法

• 严格定义递归函数作用，包括参数，返回值，Side-effct
• 先一般，后特殊
• 每次调用必须缩小问题规模
• 每次问题规模缩小程度必须为1

链表创建

Head -->1-->2-->3-->4-->5-->null

为何面试喜欢问链表（单向）

• 容易理解
• 代码难写
• 通过链表本身考察代码的能力

链表反转

列出所有组合（side effect）

• combinations([1, 2, 3, 4], 2):
• [1, 2]、[1、3]、[1、4]、[2、3]、[2、4]、[3、4]

递归缺点：

• 函数调用开销
• stack overflow
• 问题规模：n million 栈大小

循环控制

递归 --> 非递归

• 一般化的方法仍需要使用栈
• 代码复杂，不根本解决问题

Node CreateLinkedList(List<Integer> values)

循环不变式（loop invariant）

• 是一句断言定义各变量所满足的条件
• Var a, b；
• While(){ }

循环书写方法

• 定义循环不变式，并在循环体每次结束后保持循环不变式
• 先一般，后特殊
• 每次必须向前推进循环不变式中涉及的变量值
• 每次推进的规模必须为1

链表反转

链表中delete_if

1. 去重
2. 头节点没有previous怎么办？
   1. 特殊处理
   2. 增加虚拟头节点

边界控制

例如：二分查找

在二序数组中查找元素k，返回k所在下标

binarySearch([1, 2, 10, 15, 100], 15) == 3

二分查找思路：

• 规定要查找的值k可能在的数组arr内下标区间a, b
• 计算区间a，b的中间点m
• 若k<arr[m]，将区间缩小为a, m。继续二分查找
• 若k>arr[m]，将区间缩小为m, b。继续二分查找

数据结构

树 -- 重点与难点

在白板上写程序：白板、纸笔、Word文档、记事本

修改不便；缩进不便；对齐困难

心里不抵触； 先思考后写； 不要惧怕修改/重写

回顾

列表：

• 数组--随机访问
• 链表
• 队列、栈-- 访问有讲究

树：

• 二叉树
• 搜索树
• 堆/优先队列

栈/队列/优先队列

Map<K, V> / Set<K>

• HashMap / HashSet --> K.hashCode()
• TreeMap / TreeSet -- > K implements Comparable

图：

• 无向图
• 有向图
• 有向无环图
• 图的算法--复杂，面试一般不出算法题
• 深度优先遍历
• 广度优先遍历
• 拓扑排序
• 最短路径/最小生成树

数学归纳法 -- 用在编码上

用于证明断言对所有自然数成立

1. 证明对于N=1成立
2. 证明N>1时：如果对于N-1成立，那么对于N成立

数学归纳法法则：

求证：1+2+3+4+...+n=n(n+1)/2

• 1 = 1*2/2
• 如果1+2+3+...+(n-1) = (n-1)n/2
• 那么1+2+3+...+n = 1+2+3+...+(n-1)+n=(n-1)n/2+n = (n(n-1)+2n)/2=n(n+1)/2

int sum(int n){
  if (n == 1)
    return 1;
  return sum(n-1)+n;
}