03 | 复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？
大 O 时间复杂度
大 O 时间复杂度表示法：T(n) = O(n)； T(n) = O(n2)。
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
空间复杂度分析
- 类比时间复杂度，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
- 分析的就是存储空间，也是用的大O来表示，分析的方式和时间的是一样的，只是看储存空间。
小结
常见的复杂度并不多，从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)。
04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度
- 最好情况时间复杂度（best case time complexity）: 在最理想的情况下，执行这段代码的时间复杂度
- 最坏情况时间复杂度（worst case time complexity）: 在最糟糕的情况下，执行这段代码的时间复杂度
- 平均情况时间复杂度（average case time complexity）: 需要加入概率论，计算还不是特别明白
- 均摊时间复杂度（amortized time complexity）: 太复杂，看不懂的，后面来吧
05 | 数组：为什么很多编程语言中数组都从0开始编号？
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表
非线性表
为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：
a[k]_address = base_address + k * type_size
但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：
a[k]_address = base_address + (k-1)*type_size
对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。
数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。
06 | 链表（上）：如何实现LRU缓存淘汰算法?
常用缓存策略
- FIFO: First In，First Out，先进先出策略
- LFU: Least Frequently Used，最少使用策略
- LRU: Least Recently Used，最近最少使用策略
数组和链表内存分布
单链表
单向的，最后地址为null。
循环链表
循环链表是一种特殊的单链表。它跟单链表的区别就是尾节点指向了头节点。主要解决约瑟夫问题类的问题。
双向链表
- 删除节点的时间复杂度为O(1)，但是空间会多出的1倍。
- 这是用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。
双向循环链表
链表 VS 数组性能大比拼
时间复杂度| 数组 | 链表
---|---|---|---
插入删除 | O(n) | O(1)
随机访问 | O(1) | O(n)
如何基于链表实现 LRU 缓存淘汰算法
我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
- 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
- 如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表的头部；
- 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
07 | 链表（下）：如何轻松写出正确的链表代码？
- 技巧一：理解指针或引用的含义
- 技巧二：警惕指针丢失和内存泄漏
- 技巧三：利用哨兵简化实现难度
处理边界情况，比如头节点和尾节点，哨兵节点概念可以在通用处理代码中，不需要判断这些边界，从而提高性能。
// 在数组a中，查找key，返回key所在的位置
// 其中，n表示数组a的长度
// 我举2个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}
// 这里因为要将a[n-1]的值替换成key，所以要特殊处理这个值
if (a[n-1] == key) {
return n-1;
}
// 把a[n-1]的值临时保存在变量tmp中，以便之后恢复。tmp=6。
// 之所以这样做的目的是：希望find()代码不要改变a数组中的内容
char tmp = a[n-1];
// 把key的值放到a[n-1]中，此时a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;
int i = 0;
// while 循环比起代码一，少了i<n这个比较操作
while (a[i] != key) {
++i;
}
// 恢复a[n-1]原来的值,此时a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;
if (i == n-1) {
// 如果i == n-1说明，在0...n-2之间都没有key，所以返回-1
return -1;
} else {
// 否则，返回i，就是等于key值的元素的下标
return i;
}
}
- 技巧四：重点留意边界条件处理
- 技巧五：举例画图，辅助思考
- 技巧六：多写多练，没有捷径
08 | 栈：如何实现浏览器的前进和后退功能？
如何理解“栈”？
后进者先出，先进者后出，这就是典型的“栈”结构。
实现一个简单的栈
- 空间复杂度为O(n)
- 时间复杂度为O(1)
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回false，入栈失败。
if (count == n) return false;
// 将item放到下标为count的位置，并且count加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回null
if (count == 0) return null;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
String tmp = items[count-1];
--count;
return tmp;
}
}
栈在函数调用中的应用
函数调用是栈使用的一个经典场景
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
调用栈：
栈在表达式求值中的应用
另一个常见的应用场景，编译器如何利用栈来实现表达式求值。
实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
3+5*8-6 这个表达式的计算过程画成了一张如下图:
栈在括号匹配中的应用
除了用栈来实现表达式求值，我们还可以借助栈来检查表达式中的括号是否匹配。
我们同样简化一下背景。我们假设表达式中只包含三种括号，圆括号 ()、方括号[]和花括号{}，并且它们可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。那我现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？
这里也可以用栈来解决。我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。
如何实现浏览器的前进、后退功能？
其实，用两个栈就可以非常完美地解决这个问题。
我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。
- 看了a,b,c三个页面
- 从c页面回到a页面
- 又从a页面前进到b页面
- 在b页面打开了一个新的d页面
小结
- 栈是一种操作受限的数据结构，只支持入栈和出栈操作。
- 后进先出是它最大的特点。
- 栈既可以通过数组实现，也可以通过链表来实现。
- 不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。
