Basic

主方法¶

$T(n)=aT(n/b)+f(n)$

$a \ge 1$ 和 $b>1$ 是常数， $f(n)$ 是一个函数， $T(n)$ 是定义在非负整数上的递归式

若对某个常数 $\epsilon >0$ ，有 $f(n)=O(n^{log_ba-\epsilon})$ ，则 $T(n)=\Theta(n^{log_ba})$ ，即如果 $n^{log_ba}$ 大于 $f(n)$ ，复杂度由 $n^{log_ba}$ 主导
若 $f(n)=\Theta(n^{log_ba})$ ，则 $T(n)=\Theta(n^{log_ba}lgn)$ ，即两者相等，复杂度是这个项后加 $lgn$
若对某个常数 $\epsilon>0$ ，有 $f(n)=\Omega(n^{log_ba+\epsilon})$ ，且对某个常数 $c<1$ 和所有足够大的 $n$ 有 $af(n/b)\le cf(n)$ ，则 $T(n)=\Theta(f(n))$ ，即 $f(n)$ 大于 $n^{log_ba}$ ，由 $f(n)$ 主导

有的递归式不适用于主方法，如 $T(n)=4T(n/2)+n^2lgn$ ， $log_ba=2$ ，若 $g(n)=2\Omega ()$

树¶

遍历

前序遍历 (pre-order traversal) - 根->左->右
中序遍历 (in-order traversal) - 左->根->右
后序遍历 (post-order traversal) - 左->右->根

二分搜索树

左节点小于根节点，右节点大于根节点，没有值相等的节点

二分查找¶

LowerBound

返回大于等于target的最小秩 -> l

int binarySearchLowerBound(vector<int> v, int target) {
    int l = 0, r = v.size() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if(target <= v[m]) r = m - 1;
        else l = m + 1;
    }
    return l;
}

UpperBound

返回小于等于target的最大秩 -> r

int binarySearchUpperBound(vector<int> v, int target) {
    int l = 0, r = v.size() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if(target >= v[m]) l = m + 1;
        else r = m - 1;
    }
    return r;
}

对于{1, 3, 3, 4, 5, 5, 5, 6, 6}，从0-7搜索结果如下

	0	1	2	3	4	5	6	7
LowerBound	0	0	1	1	3	4	7	9
UpperBound	-1	0	0	2	3	6	8	8

理解

对于LowerBound，将r限制到比target更小的区域，然后只会进入l的条件，逐渐增加到刚好超过r，就是大于等于target的最小秩元素

对于UpperBound，相反理解即可，将l限制在比target大的区域，然后让r小于l

题目

33. Search in Rotated Sorted Array

34. Find First and Last Position of Element in Sorted Array

35. Search Insert Position

格雷码¶

格雷码是贝尔实验室发明的一种对数字进行编码的方式，使得相邻数字只有一位不同

数字	二进制	格雷码
1	001	001
2	010	011
3	011	010
4	100	110
5	101	111
6	110	101
7	111	100

格雷码可以以这种方式来产生

Take the Gray code 0, 1. Write it forwards, then backwards: 0, 1, 1, 0. Then prepend 0s to the first half and 1s to the second half: 00, 01, 11, 10. Continuing, write 00, 01, 11, 10, 10, 11, 01, 00 to obtain: 000, 001, 011, 010, 110, 111, 101, 100, ... (OEIS A014550). Each iteration therefore doubles the number of codes.

更方便的计算方法如下

整数i的格雷码 Gray(i)=i xor (i >> 1)

从格雷码到二进制可以这样计算，二进制第i位是二进制第i+1位和格雷码第i位的异或结果，刚开始假设最左边数字是0，如下例

number 7
gray code 1 0 0
binary code 1 1 1
2 bit: 0^1=1
1 bit: 1^0=1
0 bit: 1^0=1