算法训练营 - 学习笔记 - 第九周

时间真快，算法训练营马上就要结束了。。。最近生活感悟：我发现生活都是在找平衡点，工作与生活、家家庭、个人情感、发展与机遇的平衡点。人不能贪心、不能什么都要。让我联想到《高效能人士的七个习惯》中提到的：“以原则为中心，以人格为基础。”

划重点

1. 人肉递归低效、很累

2. 找到最近最简方法，将其拆解成可重复解决的问题

3. 数学归纳法思维

4. 先见森林，再见树木。

第 17 课 布隆过滤器和 LRU 缓存

高级数据结构，在工业级应用中比较常用。

布隆过滤器

Bloom Filter vs HashTable

一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

优点是空间效率和查询时间都远远超过一般的算法。

缺点是有一定的误识别率和删除困难。

布隆过滤器示意图

只要有一个为 0，那就肯定不存在。如果都是 1，那不一定/可能存在（都被塞满，那后续插入位置就都为 1）。

挡在机器前面的快速缓存罢了。

案例

1. 比特币网络

2. 分布式系统（Map-Reduce) - Hadoop, Search Engine

3. Redis 缓存

4. 垃圾邮件、评论等的过滤

实现

• Size

• Hash Num

LRU Cache(Least Recently Used) 最近最少使用

实现：Hash Table + Double Linked List

CPU Cache: L1, L2, L3 Cache

LRU Cache

两个要素：大小、替换策略

• LFU - Least Frequently Used

• LRU - Least Recently Used

O(1) 查询

O(1) 修改、更新

LeetCode LRU Cache

Python: OrderedDict

Java: LinkedHashMap

第 18 课 排序算法

比较类排序

• 通过比较来决定元素间的相对次序，时间复杂度不能突破 O(nlogn)

• 譬如：传入一个 comparator

• 分为

• 交换排序

• 冒泡排序

• 嵌套循环，每次查看相邻的元素如果逆序，则交换。

• 快速排序*

• 数组取标杆 pivot, 将小元素放在 pivot 左边，大元素放在右侧，然后依次对右边和右边的子数组继续快排；以达到整个序列有序。

• 
  

// quickSort(a, 0, a.length - 1);public static void quickSort(int[] array, int begin, int end) {  if (end <= begin) return;  int pivot = partition(array, begin, end);  quickSort(array, begin, pivot - 1);  quickSort(array, pivot + 1, end);}
static int partition(int[] a, int begin, int end) {  // pivot: 标杆位置，counter: 小于 pivot 的元素的个数  int pivot = end, counter = begin;  for (int i = begin; i < end; i++) {    if (a[i] < a[pivot]) {      int temp = a[counter]; a[counter] = a[i]; a[i] = temp;      counter++;    }  }  int temp = a[pivot]; a[pivot] = a[counter]; a[counter] = temp;  return counter;}

• 插入排序

• 简单插入排序

• 从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到对应位置并插入。

• 希尔排序

• 选择排序

• 简单选择排序

• 每次选择最小值，然后放到待排序数组的起始位置。

• 堆排序(Heap Sort)

• 数组元素依次建立小顶堆

• 依次取堆顶元素，并删除

• 实现

• priority queue

• 归并排序（高级排序）

• 需要额外的内存空间

• 二路归并排序

• 把长度为 n 输入序列分成两个长度为 n/2 的子序列；

• 对这两个子序列分别采用归并排序；

• 将两个排序好的子序列合并成一个最终的排序序列。

public static void mergeSort(int[] array, int left, int right) {  if (right <= left) return;  int mid = (left + right) >> 1; // (left + right) / 2    mergeSort(array, left, mid);  mergeSort(array, mid + 1, right);  merge(array, left, mid, right);}
public static void merge(int[] arr, int left, int mid, int right) {  int[] temp = new int[right - left + 1];  int i = left, j = mid, k = 0;    // 3 segments  while (i <= mid && j <= right) {    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];  }    while (i <= mid) temp[k++] = arr[i++];  while (j <= right) temp[k++] = arr[j++];    for (int p = 0; p < temp.length; p++) {    arr[left + p] = temp[p];  }  // System.arraycopy(a, start1, b, start2, length)}

• 多路归并排序

• 高级排序比较

• 归并：先排序左右子数组，然后合并两个有序子数组

• 快排：先调配出左右子数组，然后对于左右子数组进行排序

非比较类排序

• 不通过比较来决定元素间的相对次序，可以突破基于比较排序的时间下界，以线性时间运行，因此也成为线性时间非比较类排序。

• 分为

• 计数排序(Counting Sort)

• 桶排序(Bucket Sort)

• 基数排序(Radix Sort)

实战解析

1. 有效的字母异位词

2. 合并区间

3. 翻转对，逆序对

第 19 课 高级动态规划

递归、分治、回溯、动态规划

1. 动态规划和分治没有本质上的区别

2. 动态递推形式

难点

1. DP 状态的定义

2. 状态转移方程怎么写

实战例题

1. 爬楼梯

2. 不同路径

3. f(x,y) = f(x-1, y) + f(x, y-1)

4. 打家劫舍

5. 最小路径和

6. 股票买卖

7. 一道题团灭

8. 编辑距离

高级动态规划题目详解

复杂度来源

1. 状态拥有更多维度

2. 状态方程更加复杂

本质：内功、逻辑思维、数学