算法

LincZero大约 7 分钟

算法

算法
- 位运算
  - 二进制及其基本位运算科普
  - ……
- 对数器
- 比较器
- 排序
  - 选择排序
  - 冒泡排序
  - 插入排序
  - 归并排序
  - 快速排序
  - 堆排序
  - 计数排序
  - 基数排序
  - 排序大总结 & 避坑指南
- 二分及其扩展
递归到动态规划
- 递归行为
  - Master公式
  - 汉诺塔问题
  - 生成全子序列
  - 生成全排列
  - 很多题目的对数器方法都是递归
- 动态规划
  - 从左往右尝试模型
  - 区间范围尝试模型
  - 样本对应尝试模型
  - 业务限制尝试模型
- 贪心
数据结构
- 链表
- 队列
- 栈
- 哈希表的使用
- 有序表的使用
- 堆
  - 堆的原理和实现
  - 最大线段重合问题
  - 合并K个有序链表
- 加强堆
- 前缀树
- 二叉树
- 并查集
- 图
- 哈夫曼树

指标

复杂度

复杂度制表，及符号

$O(...)$ ，最差复杂度（读大欧，或big欧）
$\Theta(...)$ ，平均复杂度
$\Omega(...)$ ，最优复杂度
一般仅需要看最差，平均和最好很少看

选最大多项式，如：

看：O(n^2)
比较：O(n^2)
交换：O(n)
总的时间复杂度：O(an^2+bn+c) = O(n^2)

特别地：

数组寻址，常数操作
链表寻位置，则不是常熟操作，复杂度是n
常数操作与N操作最明显的区别：会不会随数据量的增大而增大

同算法复杂度如何判断优劣？

很难去拼常数项，哪怕知道常数操作的数量，也常数操作之间的时间也会不同。只能去实验
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。

稳定性

概念：

注意这里的稳定性，不是指不同数据状态下复杂度不同。

指值相同的元素在排完之后，能否保证原来的相对次序不变。

例如对：[2,1,2,1,3,2,3,2]，排序后是否能保证同样是1或2，在排序后位置不变

作用：

基础类型的数组没有用，主要用于非基础类型。

例如：学生有班级号和年龄两个信息，我可以分别弄一个班级和年龄的比较器，有稳定性的排序算法在两次排序后就能先排年龄再排班级。再例如学生有语文、数学、英语成绩，那么就可以依次排序得到成绩最好的学生。

判断：

见前面的表格，几乎是跨多个数字交换就做不到，堆也做不到

位运算

交换

有个好玩的点，可以用异或来交换（弹幕好像说，CSAPP里说现在这种写法性能没什么优势了）
异或，也是无进位相加（可以用这个来理解：为什么异或满足交换率和结合率），加法器也是异或实现，除了与或非外，这个最重要最好用了应该。

这三行跑完就交换了：

a = a^b;	// a = a原^b原，b=b原
b = a^b;	// a = a原^b原，b = a原^b原^b原 = a原^0 = a原，这里使用了交换率或结合率
a = a^b;	// a = a原^b原^a原 = b原，b = a原

注意有个致命缺点，这里有个前提，a和b的值可以相当，但不能是同一个内存，否则自己和自己异或会变成0

题（找两出现奇数次的数）

限制时间复杂度O(n)，空间复杂度O(1)
一个数组中，有一个数出现了奇数次，其他都是偶数次，怎么找出来？
- 全部异或，最后出来的数就是了
一个数组中，有两个数出现了奇数次，其他都是偶数次，怎么找出来？
- 这个一时间没想出来
- 答案：先得到A^B，因为A!=B，所以一定有一位不等于0。假设第8位是1，则表示A和B第8位不同，一个是1一个是0。此时将第8位是1的数组全部异或一遍，就得到了A或B了！强啊！
- 代码实现里的一个细节技巧：int rightOne = eor & (~eor+1); 位运算，提取最右侧的零。有点类似于补码转化那种想法，但有些不同
```
eor == 		0x1010111100;
~eor == 	0x0101000011;
~eor+1 ==	0x0101000100;
eor & (~eor+1) == 0x0000000100;
```

二分

二分查找， $O(\log_2N)$

技巧：

$mid = \frac{L+R}2$ 可能溢出，可以写成 $mid = L+\frac{R-L}2 = L+(R-L)>>1$ 。但现代编译器都会把除法优化成移位，爱咋写咋写

题（局部最小，无序二分）

局部最小定义：n[i-1] < n[i] < n[i+1]，无需数组，相邻数一定不相等。问：是否最好情况能少于O(n)
答案：少于O(n)，那应该是 $O(\log_2N)$ $O (lo g_{2} N)$ 了，应该是二分的思路。无序二分
- 例如 0->1 下降，n-2 -> n-1 上升，那么中间必然存在局部最小！
- 有点像罗尔定理、拉格朗日中值定理
总结如何想出这种答案？甩掉一半原问题与二分问题相同就能二分

对数器

非常好用，可以不依赖线上测试平台就验证算法的准确性

对数器的概念和使用

有一个你想要测的方法a
实现复杂度不好但是容易实现的方法b
实现一个随机样本产生器
把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。
如果有一个随机样本使得比对结果不一致，打印样本进行人工千预，改对方法a或者方法b
当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

比较器

类似于Cpp重载运算符，或者是Cpp模板里的比较器，Java也有比较器。Cpp也有叫仿函数的

用于比较自定义结构体或类

例如：

Arrays.sort(students, new IdAscendingComparator());
Arrays.sort(students, new AgeAscendingComparator());

约定：

返回负数时，参数1在前
返回正数时，参数2在前
返回零时，顺序无所谓

使用场景：

比较器的实质就是重载比较运算符
比较器可以很好的应用在特殊标准的排序上
比较器可以很好的应用在根据特殊标准排序的结构上

从递归到动态规划

递归

递归行为复杂度估算 —— master公式

一个递归情景：用递归找数组中的最大值，系统是怎么做的？

master公式：

T(N)= a*T(\frac Nb)+O(N^d)\\ 母问题=调用子问题的次数*子问题的规模是父问题的多少分之一+除子问题外的部分的复杂度\\ \\ \begin{cases} & 1.~log_ba>d & 复杂度为O(N^{\log_ba}) \\ & 2.~log_ba=d & 复杂度为O(N^d*\log(N)) \\ & 3.~log_ba<d & 复杂度为O(N^d) \end{cases}

例如在 “递归找数组中的最大值” 的例子中：

a=2, b=2, d=0\\ T(N)=2*T(\frac N2)+O(1)

如果我不二分而是三分，也符合：

a=3, b=3, d=0\\ T(N)=3*T(\frac N3)+O(1)

此处不证，《算法导论》有相等时的证明（P53）

再算一个归并排序：

a=2，b=2，d=1，与上同理，结果复杂度就是 $O(N\log N)$

双指针

滑动窗口，比较步进同向双指针
- 例如找最长不重复字符子串
归并排序的双指针，比较步进同向双指针
- 例如两个容器的两个指针各自遍历
无环单链表判断相交双指针，同速步进同路径双指针
扩张窗口，荷兰过期的双指针/三指针，遍历指针 + 比较步进内向双指针
- 例如一个指针正常遍历，另一个指针往后压缩空间/两个指针往中间压缩空间
快慢指针，快慢步进同向双指针 (例如快指针2步慢指针一步，也是双指针的一种，快慢指针有时不同的定制)
- 例如不知道长度的链表找中间位置