常见数据结构和算法实现(排序/查找/数组/链表/栈/队列/树/递归/海量数据处理/图/位图/Java版数据结构)_数据结构全解(链,数组,栈,树,图)与算法分析(排序,查找,递归,分治,动态规划

常见数据结构和算法实现(排序/查找/数组/链表/栈/队列/树/递归/海量数据处理/图/位图/Java版数据结构)

数据结构和算法作为程序员的基本功，一定得稳扎稳打的学习，我们常见的框架底层就是各类数据结构，例如跳表之于redis、B+树之于mysql、倒排索引之于ES，熟悉了底层数据结构，对框架有了更深层次的理解，在后续程序设计过程中就更能得心应手。掌握常见数据结构和算法的重要性显而易见，本文主要讲解了几种常见的数据结构及基础的排序和查找算法，最后对高频算法笔试面试题做了总结。本文会持续补充，希望对大家日常学习或找工作有所帮忙。

1、什么是数据结构？(研究应用程序中数据之间逻辑关系、存储方式及其操作的学问就是数据结构)

• 程序中数据大致有四种基本逻辑结构：集合(同属一个集合)/线性关系(一对一)/树形结构(一对多)/图状结构或网状结构(多对多)
• 物理存储结构：顺序存储结构/非顺序结构(链式存储/散列结构)
• 算法的设计取决于逻辑结构；算法的实现依赖于存储结构

---

2、为什么学习数据结构和算法？

有3点比较重要 (王争)

• 1、直接好处是能够有写出性能更优的代码；数据结构：存储；算法：计算；
  • 算法是程序的灵魂，优秀的程序可以在海量数据计算时，依然保持高速计算。
• 2、算法，是一种解决问题的思路和方法，有机会应用到生活和事业的其他方面；
• 3、长期来看，大脑思考能力是个人最重要的核心竞争力，而算法是为数不多的能够有效训练大脑思考能力的途径之一。

推荐的书籍及教程
《大话数据结构 程杰》入门
《算法图解》
《数据结构与算法分析：Java语言描述》(大学课本 伪代码)
《剑指offer》 使用的C++语言来实现的，现在我不怎么使用了
《程序员代码面试指南:IT名企算法与数据结构题目最优解》左程云，现在正在看的书
《编程珠玑》(对大数据量处理的算法)
《编程之美》(超级难)
《算法导论》(很厚很无聊)
《算法第四版》(推荐 本书没有动态规划)
《数据结构与算法 极客时间》 王争google
《算法帝国》
《数学之美》
《算法之美》(闲暇阅读) https://github.com/wangzheng0822/algo
《计算机程序设计艺术》面试必刷的宝典
《图解Java数据结构》韩顺平
《数据结构与算法之美》王争

倘若是在日常开发中，算法的基本逻辑，优缺点、适用场景是更为重要的。

如果是考察技术基础，考核的范围应该是算法的基本逻辑，优缺点、适用场景，因为这些技术点在后续具体应用中选择合适的算法来解决问题的时候很有用；如果是考察思维能力，考核的方式应该是给一个具体的算法应用题，来看看面试者的分析和思考过程，例如一道业务上曾经用到的“如何快速计算你好友的好友和你的共同好友数”。

---

3、有哪些常见的数据结构？

由于日常开发使用java居多，因此使用JDK提供的Java版各类数据结构更加符合实际需求。

---

4、说一下几种常见的排序算法和分别的复杂度，java提供的默认排序算法(数组排序)

4.1、排序算法

排序算法指标

• 选择排序(原理：将待排序的元素分为已排序（初始为空）和未排序两组，依次将未排序的元素中值最小的元素放入已排序的组中)

public static void selectSort(int[] a) {
	int temp,flag = 0;
	int n = a.length;
	for (int i = 0; i < n; i++) {
		temp = a[i]; //第一个数据给temp a[i]为已排序区间的末尾
		flag = i;
		for (int j = i + 1; j < n; j++) {
			if (a[j] < temp) {
				temp = a[j]; // 值
				flag = j; // 位置
			}
		}
		if (flag != i) {
			// 最小数据与第一个数据进行交换
			a[flag] = a[i];
			a[i] = temp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 插入排序 n^2 空间O(1) 稳定(每次将一个待排序的元素，按其关键字的大小插入到前面已经排好序的子文件的适当位置) 经常使用

public static void insertSort(int[] a) {
	if (a != null) {
		for (int i = 1; i < a.length; i++) {
			// 寻找插入的位置
			int temp = a[i], j = i;
			if (a[j - 1] > temp) {
				while (j >= 1 && a[j - 1] > temp) {
					a[j] = a[j - 1];//依次后移
					j--;
				}
			}
			a[j] = temp;//插入合适的位置
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

冒泡 n^2 稳定(相邻两元素进行比较，如有需要则进行交换)(两个for循环 一轮比较9次，二轮比较8次)

public class 冒泡排序 {
	// 冒泡排序，a表示数组，n表示数组大小
	public void bubbleSort(int[] a, int n) {
		if (n <= 1)
			return;
		for (int i = 0; i < n; ++i) {
			boolean flag = false;// 提前退出冒泡循环的标志位
			for (int j = 0; j < n - i - 1; ++j) {
				if (a[j] > a[j + 1]) { // 交换
					int tmp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tmp;
					flag = true; // 表示有数据交换
				}
			}
			if (!flag)
				break; // 没有数据交换，提前退出
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 希尔 nlgn~n^2 (将整个待排元素序列分割成若干个子序列，分别进行直接插入排序，待整个序列的元素基本有序，在对全体元素进行一次直接插入排序)
• 快排 nlgn 空间复杂度O(lgn) 不稳定 基于分割交换排序的原则，这种类型的算法占用空间较小，他将待排序列表分成三个主要部分：小于基准的元素，基准元素，大于基准的元素
  • (思想：通过一次划分：将待排元素分为左右两个子序列，左侧均小于基准元素排序码，右侧均大于等于基准元素排序码，反复递归，直至每一个序列只有一个元素为止)
  • 快排的优化方法，在选择基准元素时，可以(1、三数取中法(首/尾/中间各取一个数据作为分区点，取中间数作为分区点) 2、随机法)

public static void sort(int array[], int low, int high) {
	int index;
	if (low >= high) {
		return;
	}
	int i = low;
	int j = high;
	//基准点
	index = array[i];
	while (i < j) {
		//由小到大排列   好吧，通过代码知道了扫描的顺序，从右开始向左扫描，若是交换了元素，从左往右扫描，然后依次进行
		while (i < j && array[j] >= index) {
			j--; //从右向左扫描
		}
		if (i < j) {//说明上述array[j]<index,while循环跳出，该值放置在基准左侧
			array[i++] = array[j];
		}
		while (i < j && array[i] < index) {
			i++; //从左向右扫描
		}
		if (i < j) {//说明上述array[i]>index,while循环跳出，该值放置在基准右侧
			array[j--] = array[i];
		}
	}
	//最后把基准元素放上去
	array[i] = index;
	sort(array, low, i - 1);
	sort(array, i + 1, high);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

编程题：用快排思想在O(n)内查找第K大元素？比如，4，2，5，12，3 这样一组数据，第3大元素就是4。

思路：选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot，对数组A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]，如果p+1=K，那A[p]就是要求解的元素；如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间，我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找

public class 查找无序数组的第K大的数 {
	public static int kthSmallest(int[] arr, int k){
		if (arr == null || arr.length < k) {
			return -1;
		}
		int partition = partition(arr, 0, arr.length - 1);
		//经过一轮分区
		while(partition + 1 != k){
			if(partition + 1 < k){//说明第K大元素出现在A[p+1…n-1]区间
				partition = partition(arr, partition + 1, arr.length - 1);
			}else{//说明第K大元素出现在A[1…p-1]区间
				partition = partition(arr, 0, partition - 1);
			}
		}
		return arr[partition];//一次成功
	}
	private static int partition(int[] arr, int p, int r){
		int pivot = arr[r];
		int i = p;
		for(int j = p; j <= r-1; j++){
			// 这里要是 <= ，不然会出现死循环，比如查找数组 [1,1,2] 的第二小的元素   这操作真的秀
			if(arr[j] < pivot){//放基准元素左侧
				swap(arr, i, j);
				i++;
			}
		}
		swap(arr, i, r);
		return i;
	}
	private static void swap(int[] arr, int i, int j){
		if(i == j){
			return;
		}
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}//时间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

补充：倘若是现在开发“查找第K大元素” 这个需求，我会将这批数据放进List集合里面，然后使用Collections.sort()方法按大小排序好，然后get第K个元素。

• 堆排 nlgn 不稳定
  可以看做是选择排序的改进，基于比较的排序算法，他将其输入划分为未排序和排序的区域，通过不断消除最小元素并将其移动到排序区域来收缩未排序区域。
• 归并 nlgn 稳定 jdK1.7之前集合工具包默认使用的排序算法 1.7使用的是TimSort排序方法，还没有研究过 （可分为二路归并/多路归并）
  使用分治思想，将复杂问题分解为较小的子问题，直到分解的足够小，可以轻松解决问题为止。（将两个有序表合并成一个有序表） 由大到小排列

//使用分治的思想
public static void MergeSort(int array[], int p, int r) {
	if (p < r) {
		int q = (p + r)/2;
		MergeSort(array, p, q);
		MergeSort(array, q + 1, r);
		Merge(array, p, q, r);
	}
}
//Merge的作用：将已经有序的A[p…q]和A[q+1…r]合并成一个有序的数组，并且放入A[p…r]。
public static void Merge(int array[], int p, int q, int r) {
	int i, j, k, n1, n2;
	n1 = q - p + 1;
	n2 = r - q;
	int[] L = new int[n1];
	int[] R = new int[n2];
	for(i = 0, k = p; i < n1; i++, k++){
		L[i] = array[k];
	}
	for(i = 0, k = q + 1; i < n2; i++, k++){
		R[i] = array[k];
	}
	//相当于合并两条有序的链表  由大到小排列
	for(k = p, i = 0, j = 0; i < n1 && j < n2; k++){
		if (L[i] > R[j]) {
			array[k] = L[i];
			i++;
		} else {
			array[k] = R[j];
			j++;
		}
	}
	if(i < n1){
		for (j = i; j < n1; j++, k++){
			array[k] = L[j];
		}
	}
	if(j < n2){
		for (i = j; i < n2; i++, k++){
			array[k] = R[i];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

• 基数排序 O(n) 空间复杂度O(rd) 稳定(基数排序必须依赖于另外的排序方法 实质是多关键字排序)
  是通过比较数字将其分配到不同的“桶里”来排序元素的。他是线性排序算法之一。
  解决方案：1、最高位优先法MSD 2、最低位优先法LSD

• 桶排序 O(n) 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序
  适用场景：外部排序中(磁盘中，内存有限，无法将数据全部加载到内存中)

• 计数排序(桶排序的一种特殊形式：每个桶中的数据相同)

• 排序方法的选择？ n代表数据量
  1、n较小，可以采用直接插入或直接选择排序
  2、若文件初始状态基本有序，应选用直接插入、冒泡或随机的快速排序
  3、n较大，采用复杂度为O(nlgn)的方法：快排/堆排/归并
  4、在实际的软件开发中，为什么我们更倾向于使用插入排序而不是冒泡排序算法？
  从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，所以在对相同数组进行排序时，冒泡排序的运行时间理论上要长于插入排序。

• 利用快排思想实现在O(n)内查找第K大的元素？

快排核心思想就是分治和分区，选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot(基准元素)，对数组A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。如果p+1=K，那A[p]就是要求解的元素；如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间，我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找。同理，如果K<p+1，那我们就在A[0…p-1]区间查找

为什么这个算法的时间复杂度为O(n)？
第一次分区查找，我们需要对大小为n的数组执行分区操作，需要遍历n个元素。第二次分区查找，我们只需要对大小为n/2的数组执行分区操作，需要遍历n/2个元素。
依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为1。如果把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。这是一个等比数列求和，最后的和等于2n-1。所以，上述解决思路的时间复杂度就为O(n)。

如果数据存储在链表中，这三种排序算法还能工作吗？
一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；
插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；
选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。

4.2、排序工具类Arrays？如何实现一个通用的、高性能的排序函数？(Java语言采用堆排序实现排序函数，C语言使用快速排序实现排序函数)

• Arrays拥有一组static方法(equals():比较两个array是否相等/fill():将值填入array中/sort():用来对array进行排序/binarySearch():在排好序的array中寻找元素/system.arraycopy():array的复制)
• Jdk7中Arrays.sort()和Collections.sort()排序方法使用注意: jdk1.6中的arrays.sort（）和 collections.sort（）使用的是MergeSort； jdk1.7中内部实现转换成了TimSort方法，
• 对对象间比较的实现
  1、有两个参数，第一个是比较的数据，第二个是比较的规则，如果comparator为空，则使用comparableTimSort的sort实现
  2、传入的待排序数组若小于MIN_MERGE（Java实现中为32）则从数组开始处找到一组连接升序或严格降序（找到后翻转）的数
  BinarySort：使用二分查找的方法将后续的数插入之前的已排序数组
  3、开始真正的TimSort过程（选取minRun大小，之后待排序数组将被分成以minRun大小为区块的一块块子数组）
  Timsort的思想：找到已经排好序的数据子序列，然后对剩余部分排序，最后合并起来
• java提供的默认排序算法
  1、对于基础数据类型，目前使用的是所谓双轴快速排序（Dual-Pivot QuickSort），是一种改进的快速排序算法，早期版本是相对传统的快速排序；
  2、而对于对象数据类型，目前则是使用TimSort，思想上也是一种归并(Merge)和二分插入排序（binary Sort）结合的优化排序算法。
  思路是查找数据集中已经排好序的分区（这里叫run 连续升或降的序列），然后合并这些分区来达到排序的目的。

• Java8引入了并行排序算法(直接使用parallelSort方法)，这是为了充分利用现代多核处理器的计算能力，底层实现基于fork-join框架,当处理的数据集比较小的时候，差距不明显，甚至还表现差一点；但是,当数据集增长到数万或百万以上时,提高就非常大了，具体还是取决于处理器和系统环境.
• fork-join框架的适用场景：计算密集型，而非IO密集型，踩过坑

---

4.3、常见的查找算法？

• 1、二分查找法(考虑好边界条件，不要被面试官抓住漏洞)(使用Arrays工具类的binarySearch方法)
  思路：先确定数组的中间位置，然后将要查询的值与数组中间位置的值进行比较，若小于数组中间值，则要查找的值应位于该中间值之前，依次类推；
  算法： 1、如果关键字小于中央元素，只需继续在数组的前半部分进行搜索；2、如果关键字与中央元素相等，则搜索结束，找到匹配元素；3、如果关键字大于中央元素，只需继续在数组的后半部分进行搜索
  限制：用于顺序链表或排序后的链表
  注意事项：1、循环退出条件low<=high;2、mid的取值(low+(high-low)>>1)因为相比除法运算来说，计算机处理位运算要快得多;3、low和high的更新low=mid+1,high=mid-1
  时间复杂度：O(lgn)

public int bsearch(int[] a, int n, int value) {
	int low = 0;
	int high = n - 1;
	while (low <= high) {
		int mid = (low + high) / 2;//或者int mid = low+((high-low)>>1)；
		if (a[mid] == value) {
			return mid;
		} else if (a[mid] < value) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 2、4种常见的二分查找变形问题
  第一种：查找第一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
	int low = 0;
	int high = n - 1;
	while (low <= high) {
		int mid = low + ((high - low) >> 1);
		if (a[mid] > value) {
			high = mid - 1;
		} else if (a[mid] < value) {
			low = mid + 1;
		} else {
			if ((mid == 0) || (a[mid - 1] != value)) 
				return mid;  //mid不是第一个数或mid左边的数不是
			else high = mid - 1;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二种：查找最后一个值等于给定值的元素

public int bsearch(int[] a, int n, int value) {
	int low = 0;
	int high = n - 1;
	while (low <= high) {
		int mid = low + ((high - low) >> 1);
		if (a[mid] > value) {
			high = mid - 1;
		} else if (a[mid] < value) {
			low = mid + 1;
		} else {
			if ((mid == n - 1) || (a[mid + 1] != value))
				return mid;
			else
				low = mid + 1;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第三种：查找第一个大于等于给定值的元素

public int bsearch(int[] a, int n, int value) {
	int low = 0;
	int high = n - 1;
	while (low <= high) {
		int mid = low + ((high - low) >> 1);
		if (a[mid] >= value) {
			if ((mid == 0) || (a[mid - 1] < value))
				return mid;
			else
				high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第四种：查找最后一个小于等于给定值的元素

public int bsearch7(int[] a, int n, int value) {
	int low = 0;
	int high = n - 1;
	while (low <= high) {
		int mid = low + ((high - low) >> 1);
		if (a[mid] > value) {
			high = mid - 1;
		} else {
			if ((mid == n - 1) || (a[mid + 1] > value))
				return mid;
			else
				low = mid + 1;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 3、如果有序数组是一个循环有序数组，比如4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？

 public int search(int[] nums, int target) {
	if (nums.length == 1 && nums[0] == target)
		return 0;
	int left = 0;
	int right = nums.length - 1;
	int mid = 0;
	while (left < right) {
		mid = (left + right) >> 1;
		if (nums[left] == target)
			return left;
		if (nums[right] == target)
			return right;
		if (nums[mid] == target)
			return mid;
		if (nums[mid] > nums[left]) { // 第一种情况
			if (target > nums[mid]) {
				left = mid + 1;   //在mid到左侧最大值区间
			} else {//target小于中间值
				if (target > nums[left]) {
					right = mid - 1;
				} else {
					left = mid + 1;  //在右侧区间
				}
			}
		} else { // 第二种情况   mid小于最左值
			if (target > nums[mid]) {//两种情况：1、在mid右侧  2、在左侧
				if (target < nums[right]) {
					left = mid + 1; //1、在mid右侧 
				} else {
					right = mid - 1; //2、在左侧
				}
			} else {  //在右侧的左边区域
				right = mid - 1;
			}
		}

	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

• 4、x的平方根 LeetCode69 实现int sqrt(int x)函数。计算并返回x的平方根，其中x是非负整数,由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去

• 方法1：java自带API

public int mySqrt(int x) {
	return (int)Math.sqrt(x);
}
1
2
3

• 方法2：二分搜索

int mySqrt(int x) {
	//注：在中间过程计算平方的时候可能出现溢出，所以用long long。
	long i=0;
    long j=x/2+1;//对于一个非负数n，它的平方根不会大于（n/2+1）
	while(i<=j)
	{
		long mid=(i+j)/2;
	    long res=mid*mid;
		if(res==x) return mid;
		else if(res<x) i=mid+1;
		else j=mid-1;
	}
	return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法3：牛顿迭代法 求c的算术平方根就是求f(x)=x^2-c的正根 迭代公式：xn+1=1/2(xn+c/xn)

int mySqrt(int x) {
	if (x == 0) return 0;
	double last=0;
	double res=1;
	while(res!=last)
	{
		last=res;
		res=(res+x/res)/2;
	}
	return int(res);
}
1
2
3
4
5
6
7
8
9
10
11

---

4.4、复杂度分析

常见的时间复杂度？（表示的是一个算法执行效率与数据规模增长的变化趋势）

空间复杂度：(表示算法的存储空间与数据规模之间的增长关系)
常见的空间复杂度就是O(1)、O(n)、O(n2)

• 平均时间复杂度(加权平均时间复杂度)：加了概率
• 均摊时间复杂度：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。
• 算法的最好情况和最坏情况？
  最好情况：算法执行最佳的数据排列。如：二分搜索时，目标值正好位于搜索的数据中心，时间复杂度为0；
  最差情况：给定算法的最差输入。如：快速排序中，如果选择的关键值是列表中最大或最小值，最差情况就会发生，时间复杂度会变成O(n^2)

---

4.5、如何高效地判断无序数组中是否包含某特定值？

// 方法1：使用list  (**最常使用**)
public static boolean useList(String[] arr, String targetValue) {
   return Arrays.asList(arr).contains(targetValue);
}
		
// 方法2：使用Set  低效
>public static boolean useSet(String[] arr, String targetValue) {
	Set<String> set = new HashSet<String>(Arrays.asList(arr));
	return set.contains(targetValue);
}

// 方法3：使用一个简单循环  最高效
>public static boolean useLoop(String[] arr, String targetValue) {
	for(String s: arr){
		if(s.equals(targetValue))
			return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 方法4：Arrays.binarySearch()方法：数组必须是有序的(有序数组时，使用列表或树可达到O(lgn),使用hashset可达到O(1))

---

4.6、查找算法实战？

• 1、我们要给电商交易系统中的“订单”排序。订单有两个属性(下单时间，订单金额) 需求是按金额从小到大对订单数据排序。对金额相等的订单，按下单时间从早到晚排序
  稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变
  思路：先按下单时间给订单排序，排完序之后，使用稳定排序算法，按订单金额重新排序(稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变)

• 2、O(n)时间复杂度内求无序数组中的第K大元素？(利用分区的思想) 代码放在eclipse中
  我们选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot，对数组A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。
  如果p+1=K，那A[p]就是要求解的元素；如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间，我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找。同理，如果K<p+1，那我们就在A[0…p-1]区间查找。

• 3、现在你有10个接口访问日志文件，每个日志文件大小约300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件，合并为1个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有1GB，你有什么好的解决思路
  answer：先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O(n)，空间复杂度是O（1）,几乎不占用内存。

4.7、哪些数据结构有序？ 纳尼，好奇怪的问题

5、数组部分面试题

定义：是多个相同类型数据按一定顺序排列的集合，bi

• 1、实现一个支持动态扩容的数组
• 2、实现一个大小固定的有序数组，支持动态增删改操作 实际开发中我们使用ArrayList，更高效
• 3、实现两个有序数组合并为一个有序数组
• 4、数组操作常见问题(数组脚标越界异常(ArrayIndexOutOfBoundsException)/空指针异常(NullPointerException))
• leetcode15:三数求和
  给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组
  思路：首先对数据进行排序，然后确定第一个数，使用for循环，后两个数使用两指针，依次尝试，如果值大于0-num[i],右指针左移；如果值小于0-num[i],左指针右移。

class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);//由小到大
		List<List<Integer>> ls = new ArrayList<>();
		for (int i = 0; i < nums.length - 2; i++) {
			if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {  // 跳过可能重复的答案
 
				int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
				while (l < r) {
					if (nums[l] + nums[r] == sum) {
						ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
						while (l < r && nums[l] == nums[l + 1]) l++;
						while (l < r && nums[r] == nums[r - 1]) r--;
						l++;
						r--;
					} else if (nums[l] + nums[r] < sum) {
						while (l < r && nums[l] == nums[l + 1]) l++;   // 跳过重复值
						l++;
					} else {
						while (l < r && nums[r] == nums[r - 1]) r--;
						r--;
					}
				}
			}
		}
		return ls;
	}
}//时间复杂度是O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

• leetcode169:求众数 给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于?n/2?的元素
  先决条件：给定的数组总是存在众数
  思路：1、利用摩尔投票法 2、利用java的api

public int majorityElement(int[] nums){
	int count = 1;
	int maj = nums[0];
	for (int i = 1; i < nums.length; i++){
		if (maj == nums[i])
			count++;
		else {
			count--;
			if (count == 0) {//说明maj所代表的数不能超过一半
				maj = nums[i + 1];
			}
		}
	}//时间复杂度O(n)
	return maj;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 第二种解法：使用java的api，排序

public int majorityElement(int[] nums){
	Arrays.sort(nums);//时间复杂度O(nlgn)
	return nums[nums.length / 2];
}
1
2
3
4

• LeetCode41：求缺失的第一个正数
  给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

class Solution {
	public int firstMissingPositive(int[] nums) {
		//先排序，然后分两种情况 ：有1  和  没有1 （负数略过）
		//1.没有1，则输出1
		//2.有1 则判断下一个数和前一个数是否相等、差1或者差好几个数，相等继续，差1继续，否则退出
		boolean flag = false;
		int i;
		Arrays.sort(nums);
		for(i=0;i<nums.length;i++)
		{
			if(nums[i]<0)
				continue;//负数略过
			if(nums[i]==1)
				flag=true;
			if(i+1<nums.length && nums[i]==nums[i+1])
				continue;
			if(i+1==nums.length || nums[i]+1!=nums[i+1])
					break;
		}
		if(flag==true)
			return nums[i]+1;
		if(flag==false)
			return 1;
		return 0;
	}
}//时间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Demo 五子棋程序中，有存盘退出和续上盘的功能，因为该二维数组中的很多值默认为0，因此记录了很多没有意义的数据 --》稀疏

---

6、链表部分面试题

6.1、单链表：next指针 (尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点)

public class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
	}
}
1
2
3
4
5
6
7

循环链表：循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表(比如著名的约瑟夫问题)

ListNode p = null;//在单链表的基础之上，链尾指向链头
q =p;
for (int i = 2; i <= N; i++) {
	p = p.getNext();
	p.setVal(i);
}
p.setNext(q);//构建循环链表
1
2
3
4
5
6
7

在遍历循环链表时得特别小心，否则将会无限地遍历链表，因为循环链表每一个结点都有一个后继结点
双向链表：(需要额外的两个空间来存储后继结点next和前驱结点的地址prev)

public class ListNode {
	int value;
	ListNode prev;
	ListNode next;
	ListNode(int key, int val) {
		this.key = key;
		this.value = val;
	}
}
1
2
3
4
5
6
7
8
9

使用技巧：
1、理解指针或引用的含义：是存储所指对象的内存地址(将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针)
2、警惕指针丢失和内存泄漏 java不需考虑(使用jvm自动管理内存)
3、利用哨兵简化实现难度：如果我们引入哨兵结点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点(插入排序、归并排序、动态规划)
删除最后一个结点和删除其他节点,插入第一个结点和插入其他节点可以统一为相同的代码逻辑。
哨兵的好处：它可以减少特殊情况的判断，比如判空，判越界，因为空可越界可认为是小概率情况，如实每次执行代码都走一遍，大多数情况下是多于的。
比如给一个哨兵节点，以及将key赋值给末尾元素，让数组遍历不用判断越界也可以因为相等停下来。
4、重点留意便捷条件处理：(如果链表为空时，代码是否能正常工作？如果链表只包含一个结点时，代码是否能正常工作？代码逻辑在处理头结点和尾结点的时候，是否能正常工作？)
5、举例画图，辅助思考：(举例法和画图法)

---

6.2、描述一下链式存储结构

• 可以用任意一组存储单元来存储单链表中的数据结构（可以不连续），存储每个元素的值a，还必须存储后集结点的信息，这两个信息组成结点。

---

6.3、倒排一个LinkedList（即链表的反转）

开发中使用集合工具包，Collecionts.reverse(List<?> list)
原理：i m n相邻，调整指针的指向，调整m的指向，指向结点i，链表会断开，需要在调整之前把n保存起来 代码P236

public class 链表反转 {
//单链表的反转 调整指针的指向，在调整next指针之前，需要保存前一个值 反转后链表的头结点为原始链表的尾节点，即next为空指针的节点
	public void reverseIteratively(Node head) {
		Node pReversedHead = head;
		Node pNode = head;
		Node pPrev = null;
		while (pNode != null) {
			Node pNext = pNode.next;
			if (pNext == null) {
				pReversedHead = pNode;//pNode此时为最后一个结点 反转后链表的头结点为原始链表的尾节点
			}
			pNode.next = pPrev;
			pPrev = pNode;
			pNode = pNext;
		}
		head = pReversedHead;
}		
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

6.4、判断一个单链表中是否有环？ 阿里 LeetCode141

• 思路1：蛮力法
  若链表中出现多个结点的后继指针重复，就表明存在环。从第一个结点开始，令其为当前节点，然后看看链表中其他节点的后继指针是否指向当前结点，如果存在，说明链表中存在环。
  缺点：如果不能确定链表的表尾，算法将会出现死循环。

*思路2：使用散列表(时间复杂度O(n)，空间复杂度O(n))
从表头节点开始，逐一遍历链表中的每个结点；
对于每个结点，检查该结点的地址是否存在于散列表中；
如果存在，则表明当前访问的结点已经被访问过，出现此情况的原因是给定的链表中存在环；
如果散列表中没有当前节点的地址，那么把该地址插入散列表中；
重复上述过程，直至到达表尾或找到环。

• 思路3：如果一个单链表中有环，用一个指针去遍历，永远不会结束，所以可以用两个指针，一个指针一次走一步，另一个指针一次走两步，如果存在环，则这两个指针会在环内相遇，时间复杂度为O(n) indeed（无论环的个数是奇数还是偶）被称为Floyd算法

public static  boolean checkCircle(Node list){
	if (list == null) {
		return false;
	}
	Node fast = list.next;
	Node slow = list;
	while (fast != null && fast.next !=null) {
		fast = fast.next.next;
		slow = slow.next;
		if (slow ==fast) {
			return true;
		}
	}        
	return false;
}//时间复杂度O(n) 空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对floyd算法的补充：如果两个指针每次分别移动2个结点和3个结点，而不是移动一个和2个结点，算法仍然有效吗？
可以，算法的复杂度可能增加

---

6.5、判定给定的链表是否已NULL结束，如果链表中存在环，返回环的长度？

思路：在找到链表中的环后，保持slowPtr指针不变，fastPtr指针则继续移动，每次移动fastPtr指针时，计数器变量加1，直至再一次回到slowPtr指针所在的位置，即为环的长度。

public class 检测环的长度 {
	int FindLoopLength(ListNode head){
		ListNode slowPtr =head,fastPtr =head;
		boolean loopExists = false;
		int counter = 0;
		if (head == null) {
			return 0;
		}
		while (fastPtr.next != null && fastPtr.next.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
			if (slowPtr == fastPtr) {
				loopExists =true;
				break;
			}
		}
		if (loopExists) {
			fastPtr =fastPtr.next;
			while (slowPtr != fastPtr) {
				fastPtr =fastPtr.next;
				counter++;
			}
			return counter;
		}
		return 0;  //链表中不存在环
	}
}	//时间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

补充：此思路可以引申为 求循环小数的开始位置(小数点之后的位数)和循环长度

---

6.6、快慢指针能解决的问题？ 阿里

• 1、已知单链表的头指针，查找到倒数第K个节点，然后删除这个节点
  思路1：快慢指针法：
  我们定义一个快指针P和慢指针Q,先让P指针走到K个节点位置，然后Q指针从头指针开始和P一起移动，当P移动到尾部的时候，那么此时Q节点所在的位置就是倒数第K个节点

public static Node deleteLastKth(Node list,int k){
	Node fast =list;
	int i =1;
	while (fast !=null && i<k) {
		fast =fast.next;
		++i;//第一个指针先走k步
	}
	if (fast ==null) {
		return list;
	}
	Node slow =list;
	Node prev =null;
	while (fast.next !=null) {
		fast = fast.next;
		prev =slow;  //prev为倒数第k个数
		slow =slow.next;
	}
	if (prev ==null) {
		list = list.next;
	}else {
		prev.next =prev.next.next;
	}
	return list;
}//时间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路2：蛮力法(时间复杂度最高)
从链表的第一个结点开始，统计当前节点后面的结点个数。如果后面的节点个数小于k-1，算法结束；如果大于k-1，则移动到下一个结点，重复该过程
思路3：散列表O(m) 为了减少链表遍历的次数
散列表的条目是<结点的位置，结点地址>，在遍历链表时，可以得到链表的长度，令M表示链表的长度，这样求链表的导师胡第n个结点的问题转变为求链表正数
第M-n+1个结点。返回散列表中主键为M-n+1的值即可。时间复杂度O(m)，空间复杂度O(m)：创建一个大小为M的散列表。

• 2、已知单链表的头结点，查找到链表的中间节点(只允许扫描一次)
  一个快指针P和慢指针Q,P和Q同时从头指针出发，快指针P每次移动两步，慢指针每次移动一步，当快指针P到尾部的时候，慢指针Q所在的位置就是中间节点的位置

public class 找到链表的中间节结点 {
	ListNode FindMiddle(ListNode head) {
		ListNode ptr1x, ptr2x;
		ptr1x = ptr2x = head;
		int i = 0;
		//不断循环，直至第一个指针到达表尾
		while (ptr1x.getNext() !=null) {
			if (i == 0) {
				ptr1x =ptr1x.getNext();//只移动第一个指针
				i = 1;
			}
			else if (i== 1) {
				ptr1x = ptr1x.getNext();
				ptr2x = ptr2x.getNext();
				i =0;
			}
		}        
		return ptr2x;//返回ptr2x的值，即为中间结点
	}
}//时间复杂度O(n)  空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

6.7、实现两个有序的链表合并为一个有序链表(双重遍历) LeetCode23 合并k个排序链表

思路：使用分治的思想，两两归并

class Solution {
	 public ListNode mergeKLists(ListNode[] lists) {

		if (lists.length == 0)
			return null;
		if (lists.length == 1)
			return lists[0];
		if (lists.length == 2) {
			return mergeTwoLists(lists[0], lists[1]);
		}
		int mid = lists.length/2;
		ListNode[] l1 = new ListNode[mid];
		for(int i = 0; i < mid; i++){
			l1[i] = lists[i];
		}
		ListNode[] l2 = new ListNode[lists.length-mid];
		for(int i = mid,j=0; i < lists.length; i++,j++){
			l2[j] = lists[i];
		}
		return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

	}
	//两个有序链表合并为一个新的有序链表  递归的方法
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) return l2;
		if (l2 == null) return l1;

		ListNode head = null;
		if (l1.val <= l2.val){
			head = l1;
			head.next = mergeTwoLists(l1.next, l2);
		} else {
			head = l2;
			head.next = mergeTwoLists(l1, l2.next);
		}
		return head;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

6.8、在有序链表中插入一个结点

		public class 在有序链表中插入一个结点 {
			ListNode InsertSortedList(ListNode head, ListNode newNode){
				ListNode current =head;
				ListNode temp = null;
				if (head ==null) {
					return newNode;
				}
				//遍历链表，直至找到比新节点中数据值更大的节点
				while (current != null && current.val < newNode.val) {
					temp = current;//temp为current的上一个节点
					current = current.next; //current为比newNode值大的数
				}
				//在该结点前插入新节点
				newNode.setNext(current);
				temp.setNext(newNode);
				return null;  
			}   
		}//时间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

6.9、求两个单向链表的合并点，合并后成为一个单向链表。假设链表list1和链表list2在相交前的节点数量分别为n和m，n/m大小不确定，求两个链表的合并点。

方法1：蛮力法
把第一个链表中的每一个结点指针与第二个链表中的每一个结点指针比较，当结点相等时，即为相交结点。时间复杂度为O(mn)
方法2：散列表
选择结点较少的链表(若链表长度未知，那么随便选择一个链表)，将其所有结点的指针值保存在散列表中；遍历另一个链表，对于该链表中的每一个结点，检查散列表
中是否已经保存了其结点指针。如果两个链表存在合并点，那么必定会在散列表中找到记录。时间复杂度O(m)+O(n)；空间复杂度O(m)或O(n)
方法3：两个栈
创建两个栈，然后遍历两个链表，分别把所有结点存入第一个和第二个栈，两个栈包含了对应链表的结点地址，比较两个栈的栈顶元素，如果相等，则弹出两个栈
的栈顶元素并保存在临时变量中，继续上述操作，直至两个栈的栈顶元素不相等，此时即找到了两个链表的合并点。时间复杂度O(m+n),空间复杂度O(m+n)
方法4：时间复杂度超低的解法
获取两个链表L1/L2的长度，O(max(m,n))；计算两个长度的差d，从较长链表的表头开始，移动d步，然后两个链表同时移动，直至出现两个后继指针相等的情况。

			public class 求两个链表的合并点 {
				ListNode FindIntersectingNode(ListNode list1, ListNode list2){
					int L1=0,L2=0,diff=0;//L1为第一个链表的长度，L2为第二个链表的长度，diff为两链表的差值
					ListNode head1=list1,head2=list2;
					while (head1 !=null) {
						L1++;
						head1 = head1.getNext();
					}
					while (head2 !=null) {
						L2++;
						head2 = head2.getNext();
					}
					if (L1<L2) {
						head1 = list2;
						head2 = list1;
						diff = L2-L1;
					}
					else  {
						head1 = list1;
						head2 = list2;
						diff = L1-L2;
					}
					for (int i = 0; i < diff; i++) {
						head1 = head1.getNext();
					}
					while (head1 != null && head2 != null) {
						if (head1 == head2) {
						   return head1;
						}
						head1= head1.getNext();
						head2 = head2.getNext();
					}
					return null;
				}
			}//时间复杂度O(max(m,n)) 空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

6.10、如何判断一个字符串(链表)是否是回文字符串的问题(字符串是通过单链表来存储)(上海自来水来自海上)

1）前提：字符串以单个字符的形式存储在单链表中。
2）遍历链表，判断字符个数是否为奇数，若为偶数，则不是。
3）将链表中的字符倒序存储一份在另一个链表中。
4）同步遍历2个链表，比较对应的字符是否相等，若相等，则是水仙花字串，否则，不是。
思路2：使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等
时间复杂度O(n) 空间复杂度O(1)

---

6.11、O(1)时间内删除单链表中某一个节点

把后一个元素赋值给待删除节点，这样也就相当于是删除了当前元素
1. 如果待删除节点不是最后一个节点，就用他的next节点的value覆盖它的value，然后删掉它的next节点
2、如果是最后一个节点，顺序遍历o（n）

---

6.12、如何逐对逆置链表？初始1->2->3->4->X,逐对转置后，为2->1->4->3->X。

//递归版本
ListNode ReversePairRecursive(ListNode head){
	ListNode temp;
	if (head ==null || head.next == null) {
		return head;  //当前链表为空或只有一个元素
	}else {
		//逆置第一对
		temp = head.next;
		head.next = temp.next;//第一个结点的下一个为第三个结点
		temp.next = head;//第一个结点变为第二个
		head =temp;//第二个结点变第一个
		head.next.next=ReversePairRecursive(head.next.next);
		return head;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

6.13、约瑟夫环(N个人想选出一个领头人，他们排成一个环，沿着环每数到第M个人就排除该人，并从下一个人开始重新数，求最后留在环中的人)

		/**
		 * @param N 人数
		 * @param M 需要排除的人序号
		 * @return 最后留下来的人
		 */
		ListNode GetJosephusPosition(int N, int M){
			ListNode p = null,q;
			//建立一个包含所有人的循环链表
			p.setVal(1);
			q =p;
			for (int i = 2; i <= N; i++) {
				p = p.getNext();
				p.setVal(i);
			}
			p.setNext(q);//构建循环链表
			for (int count = N; count >1; --count) {
				for (int i = 0; i < M-1; i++) {
					p = p.getNext();
				}
				p.setNext(p.getNext().getNext());//删除选手
			}
			return p;//最后留下的勇者
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7、栈(一种特殊的线性表，只能固定在一端进行插入、删除操作 可分为顺序栈结构和链式栈结构)

7.1、栈的特性

递归的本质 栈
1、递归是函数里调用自身
2、必须有一个明确的递归出口
3、在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出
递归的基本思想：
1、是把规模较大的一个问题，分解成规模较小的多个子问题去解决
2、先解决子问题，再基于子问题来解决当前问题
递归和内存：每次递归调用都在内存中生成一个新的函数副本(仅仅是一些相关的变量)，一旦函数结束(即返回某些数据)，改返回函数的副本就从内存中删除。
递归一般用于解决三类问题：
1、数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）
2、问题解法按递归实现。（动态规划/分治/回溯）归并排序和快速排序用到了递归的思想
3、数据的结构形式是按递归定义的。（二叉树的/先/中/后序遍历，图的深度/广度优先搜索）

7.2、栈的使用场景 美团

• 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
  • JVM中的栈帧
• 处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中
• 表达式的转换和求值
• 二叉树的遍历
• 图的深度优先搜索
• 浏览器的前进、后退功能
• 字符串反转

1、栈在表达式求值中的应用：(一个保存操作符的栈，另一个是保存运算符的栈)
我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较(栈顶元素优先级高就取出运算符，从操作数栈取两个操作数，结果压入操作数栈)

• LeetCode150 逆波兰表示式求值(后缀表达式)(逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序)

public int evalRPN(String[] tokens) {
	Stack<Integer> stack = new Stack<>();
	for (int i = 0; i < tokens.length; i++) {
		String str = tokens[i];
		if (str.length() == 1) {
			char ch = str.charAt(0);
			if (ch - '0' >= 0 && ch - '0' <= 9) {
				Integer a = Integer.valueOf(str);
				stack.push(a);
			} else {//如果是运算符
				if (stack.size() < 2)
					return 0;
				int num2 = stack.pop();
				int num1 = stack.pop();
				switch (ch) {
				case '+':
					stack.push(num1 + num2);
					break;
				case '-':
					stack.push(num1 - num2);
					break;
				case '*':
					stack.push(num1 * num2);
					break;
				case '/':
					stack.push(num1 / num2);
					break;
				}
			}
		} else {
			int n = Integer.valueOf(str);
			stack.push(n);
		}
	}
	return stack.pop();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

栈在括号匹配中的应用：(我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号)

• LeetCode20：有效的括号 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效

		public class 有效的括号 {
			public boolean isValid(String s) {
				Stack<Character> stack = new Stack<>();
				char[] chars = s.toCharArray();
				for (char aChar : chars) {
					if (stack.size() == 0) {
						stack.push(aChar);
					} else if (isSym(stack.peek(), aChar)) {
						stack.pop();
					} else {
						stack.push(aChar);
					}
				}
				return stack.size() == 0;
			}
			//括号是否能匹配成功
			private boolean isSym(char c1, char c2) {
				return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

变体1：给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度 例如：输入: "(()"输出: 2 输入: “)()())” 输出: 4
对于这种括号匹配问题，一般都是使用栈，我们先找到所有可以匹配的索引号，然后找出最长连续数列！O(nlogn)

public class 最长有效括号 {
	public int longestValidParentheses(String s) {
		if (s == null || s.length() == 0) return 0;
		Deque<Integer> stack = new ArrayDeque<>();
		stack.push(-1);
		//System.out.println(stack);
		int res = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') 
				stack.push(i);
			else {
				stack.pop();
				if (stack.isEmpty()) 
					stack.push(i);
				else {
					res = Math.max(res, i - stack.peek());
				}
			}
		}
		return res;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路2：动态规划

public int longestValidParentheses(String s) {
	if (s == null || s.length() == 0) return 0;
	int[] dp = new int[s.length()];//状态转移表   下标表示对应考察元素     返回值表示最长有效括弧
	int res = 0;
	for (int i = 0; i < s.length(); i++) {
		if (i > 0 && s.charAt(i) == ')') {
			if (s.charAt(i - 1) == '(') {
				dp[i] = (i - 2 >= 0 ? dp[i - 2] + 2 : 2);
			} else if (s.charAt(i - 1) == ')' && i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
				dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
			}
		}
		res = Math.max(res, dp[i]);
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

编程题5：如何实现浏览器的前进、后退功能？
我们使用两个栈，X和Y，我们把首次浏览的页面依次压入栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次放入栈Y.当我们点击前进按钮时，
我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，那就说明没有页面可以继续后退浏览了。当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。
递归需要满足的三个条件：1、一个问题的解可以分解为几个问题的解；2、这个问题与分解后的子问题，除了数据规模不同，求解思路完全一样；3、存在递归终止条件
首先是定义ListNode，最基础的数据结构(包含int value，指向下一个结点点的指针)，然后有结点构成栈(包含pop/push/print/clear等功能)，最后实现浏览器功能()

public class 用栈实现浏览器的前进后退 {
	private String currentPage;
	//使用两个栈，X和Y
	private LinkedListBasedStack backStack;			//LinkedListBasedStack为基于链表实现的栈，功能有入栈/出栈/获取栈顶元素/打印栈中元素
	private LinkedListBasedStack forwardStack;
	//构造函数
	public 用栈实现浏览器的前进后退() {
		this.backStack = new LinkedListBasedStack();//第一个栈  打开新页面时入栈，页面前进时入栈  后退时出栈
		this.forwardStack = new LinkedListBasedStack();//第二个栈  前进时出栈  后退时入栈
	}
	public void open(String url) {
		if (this.currentPage != null) {
			this.backStack.push(this.currentPage);//入栈 第一个栈
			this.forwardStack.clear();
		}
		showUrl(url, "Open");
	}
	public boolean canGoBack() {
		return this.backStack.size() > 0;
	}
	public boolean canGoForward() {
		return this.forwardStack.size() > 0;
	}
	//后退功能
	public String goBack() {
		if (this.canGoBack()) {
			this.forwardStack.push(this.currentPage);//第二个栈入栈
			String backUrl = this.backStack.pop();//第一个栈出栈
			showUrl(backUrl, "Back");
			return backUrl;
		}
		System.out.println("* Cannot go back, no pages behind.");
		return null;
	}
	//前进功能
	public String goForward() {
		if (this.canGoForward()) {
			this.backStack.push(this.currentPage);//第一个栈入栈
			String forwardUrl = this.forwardStack.pop();//第二个栈出栈
			showUrl(forwardUrl, "Foward");
			return forwardUrl;
		}
		System.out.println("** Cannot go forward, no pages ahead.");
		return null;
	}
	public void showUrl(String url, String prefix) {
		this.currentPage = url;
		System.out.println(prefix + " page == " + url);
	}
	public void checkCurrentPage() {
		System.out.println("Current page is: " + this.currentPage);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

编程题3：用数组实现一个顺序栈

public class 用数组实现栈 {
	private String[] items; // 数组
	private int count; // 栈中元素个数
	private int n; // 栈的大小
	// 初始化数组，申请一个大小为n的数组空间
	public 用数组实现栈(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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

编程题4：用链表实现一个链式栈

public class 用链表实现栈 {
		private ListNode top = null;
		//入栈
		public void push(int value) {
			ListNode newNode = new ListNode(value, null);
			//判断是否栈空
			if (top == null) {
				top = newNode;
			} else {
				newNode.next = top;
				top = newNode;
			}
		}
		//出栈
		public int pop() {
			if (top == null)
				return -1;
			int value = top.data;
			top = top.next;
			return value;
		}
		public void printAll() {
			ListNode p = top;
			while (p != null) {
				System.out.print(p.data + " ");
				p = p.next;
			}
			System.out.println();
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

---

8、队列部分知识点(关键点：确定队空/队满的判定条件)

8.1、具有某种特性的队列：循环队列、阻塞队列、并发队列(在片底层的系统、框架、中间件开发中，起着重要的作用，如高性能队列Disruptor、Linux环形缓存，用到了循环并发队列

java concurrent并发包利用ArrayBlockingQueue来实现公平锁等)
分类：顺序队列和链式队列(用数组实现的队列和链表实现的队列) 基于链表实现的无界队列(可能会导致过多的请求排队，响应时间较长)，基于数组实现的有界队列(大小有限)

8.2、队列使用场景 美团

• 排队请求；
• 数据库连接池；
• 高性能队列Disruptor

8.3、高性能队列Disruptor(内存消息队列) kafka

Disruptor(线程之间用于消息传递的队列)(应用apache Storm/canal/log4j2) 性能比常用的内存消息队列ArrayblockingQueue要高出一个数量级，它还因此获得过Oracle官方的Duke大奖
1、Disruptor详解？
基于循环队列保证数据被消费的顺序性。(实现了一个最简单的“生产者-消费者模型”)在这个模型中，“生产者”生产数据，并且将数据放到一个中心存储容器中。之后，“消费者”从中心存储容器中，取出数据消费。而存储数据的中心存储容器，是用什么样的数据结构来实现的呢？(1、基于链表实现的链式队列；2、基于数组实现的顺序队列(循环队列))
基于循环队列的生产者/消费者模型：思路(当队列满了之后，生产者就轮询等待，当队列空了后，消费者就轮训等待)

public class Queue {
	private Long[] data;//基于数据实现
	private int size = 0, head = 0, tail = 0;
	public Queue(int size) {
		this.data = new Long[size];
		this.size = size;
	}
	public boolean add(Long element) {
		if ((tail + 1) % size == head) return false;//循环队列满了
		data[tail] = element;
		tail = (tail + 1) % size;
		return true;
	}
	public Long poll() {
		if (head == tail) return null;//循环队列为空
		long ret = data[head];
		head = (head + 1) % size;
		return ret;
	}
}
public class Producer {
	private Queue queue;
	public Producer(Queue queue) {
		this.queue = queue;
	}
	public void produce(Long data) throws InterruptedException {
		while (!queue.add(data)) {
			Thread.sleep(100);//说明添加失败，队列为满，等待消费
		}
	}
}
public class Consumer {
	private Queue queue;
	public Consumer(Queue queue) {
		this.queue = queue;
	}
	public void comsume() throws InterruptedException {
		while (true) {
			Long data = queue.poll();
			if (data == null) {
				Thread.sleep(100);
			} else {
				// TODO:...消费数据的业务逻辑...
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

上述代码存在的问题：多线程下，多个生产者写入的数据可能会互相覆盖，多个消费者可能会读取重复的数据
解决方法：1、加锁(同一时间只允许一个线程执行add()函数，相当于并行改成了串行)，可以使用CAS乐观锁机制减少加锁的粒度。
基于无锁的并发“生产者-消费者模型”

• 对于生产者来说，它往队列中添加数据之前，先申请可用空闲存储单元，并且是批量地申请连续的n个（n≥1）存储单元。后续往队列中添加元素，就可以不用加锁了；
• 对于消费者来说，处理的过程跟生产者是类似的。它先去申请一批连续可读的存储单元，当申请到这批存储单元之后，后续的读取操作就可以不用加锁了。
  源码中，Disruptor采用的是RingBuffer和AvailableBuffer这两个结构
  需要注意的地方：生产者A申请到一组连续的存储单元，假设下标是3到6的存储单元，生产者B紧跟着申请到下标是7到9的存储单元，那么3-6没有完全写入数据之前，7-9的数据是无法读取的，这是Disruptor实现思路的一个弊端。实际上，不管架构设计还是产品设计，往往越简单的设计思路，越能更好地解决问题。
  4、实现一个消息队列系统

编程题1：用数组实现一个顺序队列

public class 用数组实现的队列 {
	// 数组：items，数组大小：n
	private String[] items;
	private int n = 0;
	// head表示队头下标，tail表示队尾下标
	private int head = 0;
	private int tail = 0;
	// 申请一个大小为capacity的数组
	public 用数组实现的队列(int capacity) {
		items = new String[capacity];
		n = capacity;
	}
	// 入队
	public boolean enqueue1(String item) {
		// 如果tail == n 表示队列已经满了
		if (tail == n)
			return false;
		items[tail] = item;
		++tail;
		return true;
	}
	//入队操作，将item放入队尾      并更新head/tail的索引 可以动态扩容的队列
	public boolean enqueue2(String item) {
		// tail == n表示队列末尾没有空间了
		if (tail == n) {
			//tail ==n && head==0，表示整个队列都占满了
			if (head == 0)
				return false;// 表示整个队列都占满了
			// 数据搬移
			for (int i = head; i < tail; ++i) {
				items[i - head] = items[i];
			}
			//搬移完之后重新更新head和tail
			tail -= head;
			head = 0;
		}
		items[tail] = item;
		++tail;
		return true;
	}
	// 出队
	public String dequeue() {
		// 如果head == tail 表示队列为空
		if (head == tail)
			return null;
		// 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
		String ret = items[head];
		++head;
		return ret;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

编程题2：用链表实现一个链式队列

public class 基于链表实现的队列 {
	// 队列的队首和队尾
	private ListNode head = null;
	private ListNode tail = null;
	// 入队
	public void enqueue(String value) {
		if (tail == null) {
			//新建的队列
			ListNode newNode = new ListNode(value, null);
			head = newNode;
			tail = newNode;
		} else {
			tail.next = new ListNode(value, null);
			tail = tail.next;
		}
	}
	// 出队
	public String dequeue() {
		if (head == null)
			return null;
		String value = head.data;
		head = head.next;
		if (head == null) {
			tail = null;
		}
		return value;
	}
	public void printAll() {
		ListNode p = head;
		while (p != null) {
			System.out.print(p.data + " ");
			p = p.next;
		}
		System.out.println();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

编程题3：实现一个循环队列(最关键的是，确定好队空和队满的判定条件)（我使用数组实现）
队列为空的判断条件仍然是head == tail，当队满时，(tail+1)%n=head，循环队列会浪费一个数组的存储空间。

public class 循环队列 {
	//数组：items，数组大小：n
	private String[] items;
	private int n = 0;
	// head表示队头下标，tail表示队尾下标
	private int head = 0;
	private int tail = 0;
	// 申请一个大小为capacity的数组
	public 循环队列(int capacity) {
		items = new String[capacity];
		n = capacity;
	}
	// 入队
	public boolean enqueue(String item) {
		// 队列满了
		if ((tail + 1) % n == head)
			return false;
		items[tail] = item;
		tail = (tail + 1) % n;
		return true;
	}
	// 出队
	public String dequeue(){
		// 如果head == tail 表示队列为空
		if (head == tail)
			return null;
		String ret = items[head];
		head = (head + 1) % n;
		return ret;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

编程题4：实现一个双端队列 java中有工具包Deque

public class 自己动手实现双端队列 {
	private Object[] data;
	private int head = 0;
	private int tail = 0;
	public 自己动手实现双端队列(int k) {
		data = new Object[k];
	}
	public boolean insertFront(int value) {
		if(isFull()){
			return false;
		}
		head= decr(head);
		data[head] = value;
		return true;
	}
	public boolean insertLast(int value) {
		if(isFull()){
			return false;
		}
		data[tail] = value;
		tail = incr(tail);
		return true;
	}
	public boolean deleteFront() {
		if(isEmpty()){
			return false;
		}
		data[head] = null;
		head = incr(head);
		return true;
	}
	public boolean deleteLast() {
		if(isEmpty()){
			return false;
		}
		tail = decr(tail);
		data[tail] = null;
		return true;
	}
	public int getFront() {
		if(isEmpty()){
			return -1;
		}
		return (int)data[head];
	}
	public int getRear() {
		if(isEmpty()){
			return -1;
		}
		return (int) data[decr(tail)];
	}
	public boolean isEmpty() {
		return head == tail && data[head] == null && data[tail] == null;
	}
	public boolean isFull() {
		return tail== head && data[head] != null && data[tail] != null;
	}
	//前进一步
	private int incr(int index){
		return ++index % data.length;
	}
	//后退一步
	private int decr(int index){
		return (--index + data.length) % data.length;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

编程题5：滑动窗口最大值

public int[] maxSlidingWindow(int[] nums, int k){
	if(nums==null||nums.length<2) 
		return nums;
	//双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数按从大到小排序
	LinkedList<Integer> list = new LinkedList();
	// 结果数组
	int[] result = new int[nums.length-k+1];
	for(int i=0;i<nums.length;i++){
		//保证从大到小 如果前面数小 弹出
		while(!list.isEmpty()&&nums[list.peekLast()]<=nums[i]){
			list.pollLast();
		}
		//添加当前值对应的数组下标
		list.addLast(i);
		//初始化窗口 等到窗口长度为k时 下次移动在删除过期数值
		if(list.peek()<=i-k){
			list.poll();   
		} 
		//窗口长度为k时 再保存当前窗口中最大值
		if(i-k+1>=0){
			result[i-k+1] = nums[list.peek()];
		}
	}
	return result;
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 编程题6：两个栈实现队列
  思路：用栈a栈b模拟队列q，a为插入栈，b为弹出栈，栈a提供入队功能，栈b提供出队功能。入队时，入栈a即可，出队时，分两种情况：
  *1、栈b不为空，直接弹出栈b的数据 *2、栈b为空，则依次弹出栈a的数据，放入栈b中，再弹出栈b的数据。

public class 两个栈实现队列<E> {
	Stack<E> s1 = new Stack<E>();//E为链表或数组
	Stack<E> s2 = new Stack<E>();
	public synchronized void put(E e) {
		s1.push(e);
	}
	public synchronized E pop() {
		if (s2.isEmpty()) {
			while (!s1.isEmpty()) {
				s2.push(s1.pop());
			}
		}
		return s2.pop();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

编程题7：使用两个队列实现栈
思路：确保有一个队列总是空的， 入栈：在任何一个非空队列中插入元素，检查队列q1是否为空，如果q1为空，那么对q2执行入队操作；
出栈：如果队列q1非空，那么从q1移n-1个元素到q2中，然后对q1中的最后一个元素执行出队操作并返回该元素。

public class 使用队列实现栈<E> {
	Queue<E> queue1 = new LinkedBlockingQueue<E>();//E为链表或数组;
	Queue<E> queue2 = new LinkedBlockingQueue<E>();;
	public void push(E data) {
		if (queue1.isEmpty()) {
			queue2.add(data);
		} else {
			queue1.add(data);
		}
	}
	public E Pop(){
		int i,size;
		if (queue2.isEmpty()) {
			size = queue1.size();
			i=0;
			while (i < size-1) {
				queue2.add(queue1.remove());
				i++;
			}
			return queue1.remove();
		}else {
			size = queue2.size();
			i=0;
			while (i < size-1) {
				queue1.add(queue2.remove());
				i++;
			}
			return queue2.remove();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

8.4、写一个生产者-消费者队列 政采云问到了 ***非常好的题目 通过arrayblockingqueue的put/take+callable实现，详见后面的阻塞队列

• 1、可以通过阻塞队列实现 2、也可以通过wait-notify来实现 3、通过无锁的内存高性能队列Disruptor实现“生产者-消费者模型”
• 后续补充具体例子

---

9、递归方法

递归的使用场景
1、查询类目树

使用递归时应该注意的问题？
1、警惕堆栈溢出：(如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险) 解决方案：递归调用超过一定的深度后，就停止队规，返回错误(由于递归深度无法事先知道，这种方案不实用)

• 在递归调用类目树时遇到过，由于程序不当，造成了树一直被递归调用，从而导致堆栈溢出

2、递归代码的重复计算问题：某一个子问题被重复计算了多次。解决方案：通过一个数据结构(散列表)保存已经求结果的f(k),先看子问题是否被求解过，若是，直接从散列表中取值返回。

public int f(int n){
	if(n==1) return 1;
	if(n==2) return 2;
	//hasSolvedList可以理解为一个Map，key是n，value是f(n)
	hasSolvedList.containsKey(n){
		return hasSolvedList.get(n);
	}
	int ret =f(n-1)+f(n-2);
	hasSolvedList.put(n,ret);
	return ret;
}//王争这道题没写好，他的本意是记忆化递归
1
2
3
4
5
6
7
8
9
10
11

3、空间复杂度，比较大，为O(n)
3、递归代码改写为非递归代码：f(x) =f(x-1)+1 ->

	int f(int n){
		int ret = 1;
		for (int i = 2; i <= n; ++i) {
			ret = ret + 1;
		}
		return ret;
	}
	f(n) = f(n-1)+f(n-2) ->
	int f(int n){
		if (n == 1) return 1;
		if (n == 2) return 2;
		int ret = 0;int pre = 2;int prepre = 1;
		for (int i = 3; i <= n; ++i) {
			ret = pre + prepre;
			prepre = pre;
			pre = ret;
		}
		return ret;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4、如何调试递归？调试递归:1.打印日志发现，递归值。2.结合条件断点进行调试

编程题2：如何找到“最终推荐人”？在数据库表中，我们可以记录两行数据，其中actor_id表示用户id，referrer_id表示推荐人id

long findRootReferrerId(long actorId) {
	Long referrerId = select referrer_id from [table] where actor_id = actorId;
	if (referrerId == null) return actorId;
	return findRootReferrerId(referrerId);
}
1
2
3
4
5

可能出现的问题：1、递归很深会出现堆栈溢出的问题 2、若数据库中存在脏数据，可能会出现无限循环的问题 （如何来检测环的存在呢？）

• 检测环可以构造一个set集合或者散列表(下面都叫散列表)。每次获取到上层推荐人就去散列表里先查，没有查到的话就加入，如果存在则表示存在环了。当然，每一次查询都是一个自己的散列表，不能共用。
• 检测环的第二种方法：双指针法(从起点开始分别以2x,1x速度出发两个指针,当遇到null停止,相遇点为null时说明没有环,如果相遇点不为null,说明有环)
  编程1；实现斐波那契数列求值f(n)=f(n-1)+f(n-2) or 假如这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这n个台阶有多少种走法？
  递推公式：f(n)=f(n-1)+f(n-2) 递归终止条件：f(1)=1,f(2)=2
  最终的递归代码是这样的：

int f(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	return f(n-1) + f(n-2);
}
1
2
3
4
5

编程题2：汉诺塔(思想：将原柱最上面的n-1个圆盘移动到辅助柱；将第n个圆盘从原柱移到目的柱；将辅助柱的n-1个圆盘移动到目的柱)

void TowersOfHanoi(int n,char frompeg,char topeg,char auxpeg){
	/*如果仅有一个圆盘，直接移动，然后返回*/
	if(n==1){
		syso("Move disk 1 from peg"+frompeg+"to peg"+topeg);
		return;
	}
	/*利用c作为辅助，将A柱最上面的n-1个圆盘移动到B柱*/
	TowersOfHanoi(n-1, frompeg, topeg,auxpeg)；
	/*将余下的圆盘从A柱移动C柱*/
	syso("Move disk 1 from peg"+frompeg+"to peg"+topeg);
	/*利用A柱作为辅助，将B柱上的n-1个圆盘移到C柱*/
	TowersOfHanoi(n-1, auxpeg,topeg,frompeg)；
}
1
2
3
4
5
6
7
8
9
10
11
12
13

编程3；实现求阶乘n!

int Fact(int n){
	//基本情形：当参数为0或1时，返回1
	if (n==1) {
		return 1;
	}else if (n == 0) {
		return 1;
	}else {
		return n*Fact(n-1);
	}
}
1
2
3
4
5
6
7
8
9
10

编程4；实现一组数据集合的全排列

		public class 实现一组数据集合的全排列 {
			public void printAllSort(int[] arr) {
				if (arr == null || arr.length == 0) {
					return;
				}
				if (arr.length == 1) {
					System.out.println(arr[0]);
				}
				List<List<Integer>> result = _printAllSort(arr);
				int count=0;
				for (List list : result) {
					count++;
					System.out.println(list+" 第"+count+"种");
				}
			}
			private List<List<Integer>> _printAllSort(int[] tmpArr) {
				// 结束条件
				List<List<Integer>> result = new ArrayList<>();
				if (tmpArr.length == 2) {
					List<Integer> subList = new ArrayList<>();
					List<Integer> subList2 = new ArrayList<>();
					subList.add(tmpArr[0]);
					subList.add(tmpArr[1]);
					subList2.add(tmpArr[1]);
					subList2.add(tmpArr[0]);
					result.add(subList);
					result.add(subList2);
					return result;
				}
				// 当前层处理
				for (int i = 0; i < tmpArr.length; i++) {
					// 顺序拿出一个参数，其余交给下一层处理
					int tmp = tmpArr[i];
					int[] arr = new int[tmpArr.length - 1];
					int offset = 0;
					for (int j = 0; j < tmpArr.length; j++) {
						if (i != j) {
							arr[offset] = tmpArr[j];
							offset++;
						}
					}
					List<List<Integer>> nextLevelResult = _printAllSort(arr);
					// 处理下一层结果（当前值加到结果的前面、后面）
					for (List<Integer> nextList : nextLevelResult) {
						List<Integer> appendList = new ArrayList<>();
						appendList.add(tmp);
						appendList.addAll(nextList);
						result.add(appendList);
					}
				}
				return result;
			}
		}//[1, 2, 3, 4] 第1种  [1, 2, 4, 3] 第2种  [1, 3, 2, 4] 第3种  [1, 3, 4, 2] 第4种  [1, 4, 2, 3] 第5种  [1, 4, 3, 2] 第6种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

编程5；爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

//方法1：暴力法 使用递归
public int climbStairs(int n) {
	return climb_Stairs(0, n);
}
public int climb_Stairs(int i, int n) {
	if (i > n) {
		return 0;
	}
	if (i == n) {
		return 1;
	}
	return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
}//时间复杂度：O(2^n)
1
2
3
4
5
6
7
8
9
10
11
12
13

方法2：记忆化递归 每一步的结果存储在 memomemo 数组之中，每当函数再次被调用，我们就直接从 memomemo 数组返回结果

public class 记忆化递归 {
	public int climbStairs(int n) {
		int memo[] = new int[n + 1];
		return climb_Stairs(0, n, memo);
	}
	public int climb_Stairs(int i, int n, int memo[]) {
		if (i > n) {
			return 0;
		}
		if (i == n) {
			return 1;
		}
		if (memo[i] > 0) {
			return memo[i];
		}
		memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
		return memo[i];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法3：动态规划 第i阶可以由以下两种方法得到：在第(i-1)阶后向上爬一阶。在第(i-2)阶后向上爬 2 阶。状态转移公式：dp[i]=dp[i?1]+dp[i?2]

public class 动态规划求解爬楼梯 {
	public int climbStairs(int n) {
		if (n == 1) {
			return 1;
		}
		int[] dp = new int[n + 1];
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		return dp[n];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

10、散列表相关知识点(HashMap/LinkedHashMap)

10.1、什么是hash算法，他们用于什么？

hash算法是一个hash函数，他使用任意长度的字符串，并将其减少为唯一的固定长度字符串。他用于密码有效性、消息和数据完整性以及许多其他加密系统。

• 加密算法原理：加密是将明文转换成“密文”的过程。要转换文本，算法使用一系列被称为“键”的位来进行计算。密钥越大，创建密文的潜在模式越多。大多数加密算法使用长度约为64到128位的固定输入块，而有些则使用流方法。
• 常用的加密算法：3-way blowfish cast cmea gost des/triple des idea loki crc MD5
• 哈希算法的应用：安全加密(MD5/SHA)、数据校验、唯一标识、散列函数，负载均衡、数据分片、分布式存储 **
• 安全加密：第一是很难根据哈希值反向推导出原始数据，第二是散列冲突的概率很小。
• 唯一标识：图片的唯一id(我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中)
• 数据校验:我们通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。哈希算法特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。
• 散列函数：对于冲突的要求低很多(即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决),更看重的是散列的平均性和哈希算法的执行效率。

• 在分布式系统中的应用：

• 负载均衡：(利用哈希算法替代映射表)通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。

数据分片：(通过哈希算法对处理的海浪数据进行分片，多机分布式处理，突破单机资源限制)
1、如何统计“搜索关键词”出现的次数？(难点：搜索日志很大，没办法放到一台机器的内存中；第二：如果只用一台机器处理数据，时间耗费很长)
我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度(n台机器，从搜索记录的日志文件中，依次独处每个搜索关键词，并且通过哈希函数计算hash值，然后再跟n取模
最终得到的值，就是应该被分配到的机器编号)(MapReduce的基本设计思想)
2、如何快速判断图片是否在图库中？我们同样可以对数据进行分片，然后采用多机处理。我们准备n台机器，让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯
一标识，然后与机器个数n求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。
当我们要判断一个图片是否在图库中的时候，我们通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数n求余取模。假设得到的值是k，那就去编号k的机器构建的散列表中查找。

分布式存储：(利用一致性哈希算法，解决缓存等分布式系统的扩容/缩容导致数据大量搬移的问题)
假设我们有k个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成m个小区间（m远大于k），每个机器负责m/k个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

散列表：散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。
当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标。

散列函数：1. 散列函数计算得到的散列值是一个非负整数；2. 如果key1 = key2，那hash(key1) == hash(key2)；3. 如果key1 ≠ key2，那hash(key1) ≠ hash(key2)(这一点即使是MD5/CRC算法也无法完全避免散列冲突)

• 应用：判断单词是否拼写错误(使用Trie树更好)；redis的字典是使用链式法来解决散列冲突的，并且使用了渐进式rehash方式进行hash表的弹性扩容

Q:区块链使用的是哪种哈希算法？是为了什么问题而使用的呢？
A:区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体(区块头保存着自己区块体和上一个区块头 的哈希值),因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。区块链使用的是SHA256哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。

---

10.2、hash函数是怎么实现的？

1、散列算法 hash(key)&(capitity-1) //在插入或查找时,计算Key被映射到桶的位置。 当capacity为2的整数倍是该公式才成立。相当于对key的hash值对表厂取模，基于hashmap是2的幂次方特性，这种位运算速度更快。
2、hash的高16bit和低16bit做了一个异或
3、（n-1）&hash 得到下标
4、使用&代替取模，实现了均匀的散列，但效率要高很多，与运算比取模的效率高，由于计算机组成原理
代码：

int hash(Object key){
	int h = key.hashCode();
	return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
}	
public int hashCode(){
	int var1 = this.hash;
	if(var1 == 0 && this.value.length > 0){
		char[] var2 = this.value;
		for(int var3 = 0; var3 < this.value.length; ++var3) {
			var1 = 31 * var1 + var2[var3];
		}
		this.hash = var1;
	}
	return var1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

10.3、hash冲突解决方案：(开放定址法/链表法)

使用链地址法，先找到下标i，KEY值找Entry对象，新值存放在数组中，旧值在新值的链表上，将存放在数组中的Entry设置为新值的next

• 开放定址法
  散列表的冲突处理？散列表的冲突处理主要分为闭散列法和开散列法；常用：线性探测法、链地址法 20181230补
  1、闭散列法(开放寻址法) 不开辟额外的存储空间 (当数据量比较小、装载因子小的时候，适合采用开放寻址法)

特点
1、不开辟额外的存储空间，还是在原先hash表的空间范围之内
2、当插入元素发生了散列冲突，就逐个查找下一个空的散列地址供插入，直到查找失败

方法
1、线性探测法：将散列表看作是一个循环向量，若初始地址是f(key)=d，则依照顺序d、d+1、d+2…的顺序取查找，即f(key)=(f(key)+1)mod N;(ThreadLocalMap使用的线性探测法)
2、二次探测法：基本思路和线性探测法一致，只是搜索的步长和方向更加的多样，会交替以两个方向，步长为搜索次数的平方来查找 **
3、 双重散列法：通常双重散列法是开放地址中最好的方法，其通过提供hash()和rehash()两个函数，前者产生冲突的时候，定制化后者rehash()重新寻址

2、开散列法(链地址法) 寻找额外的存储空间(基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略)

1、特点
1、一般通过将冲突的元素组织在链表中，采用链表遍历的方式查找
2、解决方法直观,实现起来简单,尤其在删除元素的时候此处只是简单的链表操作
3、开散列法可以存储超过散列表容量个数的元素

2、方法
1、链地址法：相同散列值的记录放到同一个链表中，他们在同一个Bucket中（java中LinkedHashMap采用此方法）
优化方案：将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。
2、公共溢出法：将所有的冲突都放到一个公共的溢出表中去，适用于冲突情况很小的时候

---

10.4、面试题

• 1、假设我们有10万条URL访问日志，如何按照访问次数给URL排序
  遍历10万条数据，以URL为key，访问次数为value，存入散列表，同时记录访问次数的最大值K，时间复杂度O(N)，如果K不是很大，可以使用桶排序，时间复杂度O(N)。如果k非常大(10万)，就使用快速排序，复杂度O(NlgN)
• 2、有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串？
  以第一个字符串数组构建散列表，key为字符串，value为出现次数。再遍历第二个字符串数组，以字符串为key在散列表中查找，如果value大于零，说明存在相同字符串。时间复杂度O(N)。
• 3、如何避免低效扩容？
  当装载因子已经到达阈值，需要先进行扩容，再插入数据，这种操作很低效。解决方案：将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
  当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。
• 5、如何通过哈希算法生成短网址？（王争的第56讲 http://t.cn是短网址服务的域名）
  MurmurHash算法。现在它已经广泛应用到Redis、MemCache、Cassandra、HBase、Lucene等众多著名的软件中。
• 6、编程实现一个基于链表法解决冲突问题的散列表

public class HashTable {
	private int tSize;
	private int count;
}
public class HashTableNode {
	private int blockCount;
	private ListNode startNode;//维护的线性表
}
public class 基于散列表解决冲突的散列表 {
	public final static int LOADFACTOR = 20;
	public static HashTable createHashTable(int size) {
		HashTable h = new HashTable();
		//count默认设置为0；
		h.settSize(size / LOADFACTOR);
		for (int i = 0; i < h.gettSize(); i++) {
			h.getTable()[i].setStartNode(null);
		}
		return h;
	}
	public static int hashSearch(HashTable h, int data) {
		ListNode temp;
		temp = h.getTable()[Hash(data, h.gettSize())].getStartNode();
		while (temp != null) {
			if (temp.getVal() ==data) {
			   return 1; 
			}
			temp = temp.getNext();
		}
		return 0;
	}
	//散列函数
	public static int Hash(int data, int gettSize) {
		int h = data; /* data.hashCode(); */
		return (h ^ (h >>> 16)) & (gettSize - 1); // capicity表示散列表的大小
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

7、编程实现一个LRU缓存淘汰算法 (使用散列表+链表组合实现缓存淘汰算法)LinkedHashMap(思路牛逼)(双向链表+散列表)(使用双向链表支持按照插入的顺序遍历数据，支持按照访问顺序遍历数据)

一个缓存（cache）系统主要包含下面这几个操作：往缓存中添加一个数据；从缓存中删除一个数据；在缓存中查找一个数据。
①使用双向链表存储数据，链表中每个节点存储数据（data）、前驱指针（prev）、后继指针（next）和hnext指针（解决散列冲突的链表指针）。
②散列表通过链表法解决散列冲突，所以每个节点都会在两条链中。一条链是双向链表，另一条链是散列表中的拉链。前驱和后继指针是为了将节点串在双向链表中，hnext指针是为了将节点串在散列表的拉链中。(牛逼)

• 往缓存中查找一个数据：在散列表中查找数据的时间复杂度为O(1)，找到后，将其移动到双向链表的尾部
• 删除数据：在O(1)时间复杂度里找到要删除的结点，双向链表可以通过前驱指针O(1)时间复杂度获取前驱结点
• 添加一个数据：先看这个数据是否已经在缓存中。如果已经在其中，需要将其移动到双向链表的尾部；如果不在其中，还要看缓存有没有满。如果满了，则将双向链表头部的结点删除，然后再将数据放到链表的尾部；如果没有满，就直接将数据放到链表的尾部。

public class LRU缓存淘汰算法{
	private ListNode head; //最近最少使用，类似列队的头，出队
	private ListNode tail; //最近最多使用，类似队列的尾，入队
	private Map<Integer, ListNode> cache;
	private int capacity;
	public LRU缓存淘汰算法(int capacity){
		this.cache = new HashMap<>();
		this.capacity = capacity;
	}
	public int get(int key) {
		ListNode node = cache.get(key);
		if (node == null) {
			return -1;
		} else {
			moveNode(node);//把该数据移动到链表尾部
			return node.value;
		}
	}
	public void put(int key, int value) {
		ListNode node = cache.get(key);
		if(node != null){
			node.value = value;
			moveNode(node);//把该数据移动到链表尾部
		} else{//缓存满了，移除链表的头结点
			removeHead();
			addNode(new ListNode(key, value));
		}
		cache.put(key, node);
	}
	private void removeHead() {
		if (cache.size() == capacity) {
			ListNode tempNode = head;
			cache.remove(head.key);
			head = head.next;
			tempNode.next = null;
			if (head != null)
				head.prev = null;
		}
	}
	private void addNode(ListNode node) {
		if (head == null)
			head = tail = node;
		else
			addNodeToTail(node);
	}
	private void addNodeToTail(ListNode node) {
		node.prev = tail;
		tail.next = node;
		tail = node;
	}
	//移动数据到链表尾部 分类讨论：第一种要移动的结点是头结点；第二种直接为尾节点，无需处理；第三种为链表中的结点
	private void moveNode(ListNode node){
		if (head == node && node != tail){
			head = node.next;
			head.prev = null;
			node.next = null;
			addNodeToTail(node);
		} else if (tail == node){
		} else {
			node.prev.next = node.next;
			node.next.prev = node.prev;
			node.next = null;
			addNodeToTail(node);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

java中有现成的工具可以使用

• LinkedHashMap维护了插入的先后顺序【FIFO】，适合LRU算法做缓存（最近最少使用）(在项目中被用到过)

 LinkedHashMap<Long, String> unchecked = new LinkedHashMap<Long, String >(20, .75F, true) {
     @Override
     protected boolean removeEldestEntry(Map.Entry<Long, String> eldest){
         //什么时候执行LRU操作
         return this.size() > 20;
     }
 };
1
2
3
4
5
6
7

---

11、字符串处理算法总结：

理解常用字符串匹配算法的原理、实现、设计意图和应用场景，搞清楚能解决什么问题。

11.1、用Java写一个递归遍历目录下面的所有文件

思路：利用File类中的一个listFiles将该文件路径下所有的文件全部列出来，然后通过循环遍历

public static void showDirectory(File file){		   
	File[] files = file.listFiles();		   
	for(File a:files){	
		System.out.println(a.getAbsolutePath());  
		if(a.isDirectory()){	
			showDirectory(a);
		}
	}
}
1
2
3
4
5
6
7
8
9

11.2、给定一个txt文件，如何得到某字符串出现的次数

File file = new File("E://test.txt");
InputStream is = new FileInputStream(file);
byte b[] = new byte[1024];
int a = is.read(b);
String str[] = new String(b,0,a).split("");
int count = 0;
for(int i = 0;i<str.length;i++){
	if("a".equals(str[i]))
		count++;
}
System.out.println(count);
1
2
3
4
5
6
7
8
9
10
11

11.3、实现一个字符集，只包含a～z这26个英文字母的Trie树（也称为字典树/键树）

• 暂时在项目中找不到使用场景。

public class TrieNode {
	public char data;
	public TrieNode[] children = new TrieNode[26];
	public boolean isEndingChar = false;
	public TrieNode(char data) {
		this.data = data;
	}
}
public class Trie树 {
	private TrieNode root = new TrieNode('/'); //存储无意义字符
	// 往Trie树中插入一个字符串
	public void insert(char[] text) {
		TrieNode p = root;
		for (int i = 0; i < text.length; ++i) {
			int index = text[i] - 'a';
			if (p.children[index] == null) {
				TrieNode newNode = new TrieNode(text[i]);
				p.children[index] = newNode;
			}
			p = p.children[index];
		}
		p.isEndingChar = true;
	}
	// 在Trie树中查找一个字符串
	public boolean find(char[] pattern){
		TrieNode p = root;
		for (int i = 0; i < pattern.length; ++i){
			int index = pattern[i] - 'a';
			if (p.children[index] == null){
				return false; // 不存在pattern
			}
			p = p.children[index];
		}
		if (p.isEndingChar == false)
			return false; // 不能完全匹配，只能匹配前缀
		else
			return true; // 找到pattern
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

11.4、实现朴素的字符串匹配算法(暴力匹配算法/BF算法)

• 思路：我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串 我们把主串的长度记作n，模式串的长度记作m。因为我们是在主串中查找模式串，所以n>m
• 我们在主串中，检查起始位置分别是0、1、2…n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。

JDK提供的Utils方法：

// 时间复杂度：O(n*m)
public static bool contains(String a) {
	String aa = 'jd.com';
	if(a.contains(aa)) {
		return true;
	}
	return false;
}
1
2
3
4
5
6
7
8

// 暴力匹配算法 时间复杂度是O(n*m)
public static int bF(String a, String b) {
	int m = a.length(), n = b.length(), k;
	char[] a1 = a.toCharArray();//主串
	char[] b1 = b.toCharArray();//模式串
	for(int i = 0; i <= m - n; i++){
		k = 0;
		for(int j = 0; j < n; j++){//n为模式串的长度
			if(a1[i + j] == b1[j]){
				k++;//k的值表示匹配的长度
			}else
				break;
		}
		if(k == n){
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

思路：我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了，效率取决于哈希算法的设计方法。

public static int rK(String a, String b){
	int m = a.length(), n = b.length(), s, j;
	int[] hash = new int[m - n + 1];//主串可以分解为子串的个数
	int[] table = new int[26];
	char[] a1 = a.toCharArray();
	char[] b1 = b.toCharArray();
	s = 1;
	//将26的次方存储在一个表里，取的时候直接用,虽然溢出，但没啥问题
	for (j = 0; j < 26; j++) {
		table[j] = s;
		s *= 26;
	}
	for (int i = 0; i <= m - n; i++) {//主串
		s = 0;
		for (j = 0; j < n; j++) {
			s += (a1[i + j] - 'a') * table[n - 1 - j];//table为倒序
		}
		hash[i] = s;
	}
	s = 0;
	for (j = 0; j < n; j++) {//模式串
		s += (b1[j] - 'a') * table[n - 1 - j];
	}
	for (j = 0; j < m - n + 1; j++) {//两者的hash值比较
		if (hash[j] == s) {
			return j;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// sunday算法 时间复杂度 O(n)
 /**
 * 判断子串中是否存在末尾下一个位置对应的父串的字符
 * 每次从后往前匹配，为了不遗漏可能的匹配，应该是跳到使得子串中最右一个字符与父串中的该字符对应，
 * 这样跳过的距离最小，且是安全的。
 */
private static int contains(char[] sonArray, char ch) {
    for (int i = sonArray.length - 1; i >= 0; i--) {
        if (sonArray[i] == ch) {
            return i;
        }
    }
    return -1;
}

private static int search(String source, String target) {
    //这里转为char数组要更方便些
    char[] fatherArray = source.toCharArray();
    char[] sonArray = target.toCharArray();

    int fatherLength = fatherArray.length;
    int sonLength = sonArray.length;
    int i = 0, j = 0;
    //+ j是可能会出现最后一次移动father剩余长度与son长度不一致的情况
    while (i <= fatherLength - sonLength + j) {
        if (fatherArray[i] != sonArray[j]) {
            //如果父串与子串当前字符不相等
            if (i == fatherLength - sonLength + j) {
                //这里说明子串已经是在和父串中最后可能想等的字符比较过了，并且后面也没有可比较的了，所以返回
                return -1;
            }

            //如果父串的中间部分与子串匹配，且结果不相等
            //就从子串最后面开始，找出子串最后一位的下一位对应父串的字符在子串中是否存在
            int pos = contains(sonArray, fatherArray[i - j + sonLength]);
            if (pos == -1) {
                //不存在则直接跳到再下一位，子串从头开始
                i = i - j + sonLength + 1;
                j = 0;
            } else {
                //存在则将这个字符与子串最右边与它相同的字符对其,并再次从头开始比较
                i = i + sonLength - pos - j;
                j = 0;
            }

        } else {
            //如果父串与子串当前字符相等
            if (j == sonLength - 1) {
                //如果比较到了子串的最后一位，说明已经存在
                return i - j;
            } else {
                //不是子串最后一位，则进行下一个字符的对比
                i++;
                j++;
            }
        }
    }
    return -1;
}
// 测试
public static void main(String[] args) {
	   String source = "http://www.cg.yixiubao.tv.com?itemId=1111";
	   String target = "cg.yixiubao.tv";
	   System.out.println(search(source, target));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

算法思想：编程中一定会出现的问题：变种非常多(反转/反转单词/子串/最长子串/最长子序列)

• 1、用固定支付替换字符串中的空格
  使用stringbuffer的append（）
• 2、验证是否是回文串
  只考虑字母和数字字符，先用isletterOrDigit来跳过其他字符，第一个字符与最后一个字符依次比较，然后I++，J–
• 3、数组的最长公共前缀
  先用数组的sort方法升序排列，找出数组第一个字符串和最后一个的长度，按小的计算，比较字符串的元素，若相等就
  保存在Stringbuffer中
• 4、最长回文串 区分大小写
  字符出现次数为双+一个只出现一次的字符，遍历数组，字符在hashset中就移除，count++，否则，添加进去

5、反转字符串，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题 输入：[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]

public void reverseString(char[] s){
	int l = 0;
	int r = s.length-1;
	int mid = (s.length)/2;
	while(l != mid ){
		char temp = s[l];
		s[l] = s[r];
		s[r] = temp;
		l++;
		r--;
	}
}//时间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12

StringTokenizer详解：(允许应用程序将字符串分解为标记)
1、int countTokens() 计算在生成异常之前可以调用此 tokenizer 的 nextToken 方法的次数；
2、boolean hasMoreElements() 返回与 hasMoreTokens 方法相同的值；
3、String nextToken(String delim) 返回此 string tokenizer 的字符串中的下一个标记。
下面是一个使用 tokenizer 的实例。代码如下：

StringTokenizer st = new StringTokenizer("this is a test");
while (st.hasMoreTokens()) {
	System.out.println(st.nextToken());
}
1
2
3
4

输出以下字符串： this is a test
StringTokenizer出于兼容性的原因而被保留，建议使用String的split方法或java.util.regex包。建议

String[] result = "this is a test".split("\\s");
for (int x=0; x<result.length; x++)
	System.out.println(result[x]);
1
2
3

输出以下字符串： this is a test

6、 翻转字符串里的单词 输入: “the sky is blue” 输出: “blue is sky the”

public String reverseWords(String s) {
	String[] strArr = s.split("\\s+"); //正则匹配空格
	StringBuilder sb = new StringBuilder();
	for(int i=strArr.length-1;i>=0;i--){ //倒序遍历，添加空格
		sb.append(strArr[i]);
		sb.append(" ");
	}
	return sb.toString().trim();//去除首尾多余空格，toString返回
}
1
2
3
4
5
6
7
8
9

7、字符串转换整数 请你来实现一个 atoi 函数，使其能将字符串转换成整数
该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数
例如：输入: " -42" 输出: -42 第一个非空白字符为 ‘-’, 它是一个负号
输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字

public int myAtoi(String str) {
	int i = 0;
	int len = str.length();
	boolean flag = true;//使用flag指定数值正负
	while (i < len && str.charAt(i) == ' ') {
		i++;
	}
	if (i < len) {
		if (i == len || !Character.isDigit(str.charAt(i))) {
			if (str.charAt(i) == '+') {
				i++;
			} else if (str.charAt(i) == '-') {
				flag = false;
				i++;
			} else {
				return 0;
			}
		}
	} else {
		return 0;
	}
	StringBuilder sb = new StringBuilder();
	if (i < len && Character.isDigit(str.charAt(i))) {
		while (i < len && Character.isDigit(str.charAt(i))) {
			sb.append(str.charAt(i));
			i++;
		}
	} else
		return 0;
	String string = sb.toString();
	int parseInt = 0;
	try {
		parseInt = Integer.parseInt(string);
	} catch (Exception e) {
		if (flag == true) {
			parseInt = Integer.MAX_VALUE;
		} else {
			parseInt = Integer.MIN_VALUE;
		}
	}
	if (flag == true)
		return parseInt;
	else
		return -parseInt;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

12、树部分面试题

12.1、如何遍历一棵二叉树？

二叉树是n个有限元素的集合，由根元素以及左右子数组成。集合可以为空。

• 概念：结点的度，结点所拥有的子树的个数称为度。
  叶节点，度为o的结点。
  分支节点，即非叶子结点
• 路径：n1，n2，，，nk的长度为路径
• 层数：根结点层数为1，其余的结点++双亲
• 深度：最大层数
• 满二叉树：所有叶子结点在同一层
• 完全二叉树：叶子结点只能出现在最下层和次下层。
• 性质： 非空二叉树第i层最多2{i-1}个结点
  深度为k，最多2{k}-1个结点，最少k个结点
  非空二叉树，度为0的节点数比度为2的节点数多1，n0=n2+1；
  n个结点的完全二叉树的深度为lgn+1
• 存储：1、基于指针或者应用的二叉链式存储法；2、基于数组的顺序存储法(适合完全二叉树)
  链式存储法：每个结点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针
  顺序存储法：节点X存储在数据中下标为i的位置，下标为2i的位置存储的是左子节点，下标为2i+1的位置存储的是右子节点。
• 遍历：使用队列来实现对二叉树的层序遍历，思路：根结点放入队列，每次从队列中取出一个结点，打印值。若这个值有子结点，子结点入队尾，直至队列为空。 代码P305（是一种广度优先的遍历算法）
  递归实现：中序遍历，先序遍历，后序遍历(表示的是节点与它的左右子树节点遍历打印的先后顺序) 时间复杂度O(n)
  非递归中序遍历：首先要移动到结点的左子树，完成左子树的遍历后，再将结点出栈进行

void InOrderNonRecursive(TreeNode root){
	if (root == null) {
		return;
	}
	Stack s = new Stack();
	while(true){
		while (root !=null) {
			s.push(root);
			root = root.left;
		}
		if (s.isEmpty()) {
			break;
		}
		root = (TreeNode) s.pop();
		System.out.println(root.val);
		root = root.right;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

非递归先序遍历：需要使用一个栈来记录当前节点，以便在完成左子树遍历后能返回到右子树中进行遍历；
* 在遍历左子树之前，把当前节点保存在栈中，直至遍历完左子树，将该元素出栈，然后找到右子树进行遍历。

void PreOderNonRecursive(TreeNode root){
	if (root == null) {
		return;
	}
	Stack s= new Stack();//使用栈保存将要遍历的结点
	while(true){
		while (root !=null) {
			System.out.println(root.val);
			s.push(root);
			root = root.left;
		}
		if (s.isEmpty()) {
			break;
		}
		root = (TreeNode) s.pop();
		root = root.right;
	}
}
递归后序遍历：
void PostOrder(TreeNode root){
	if (root!= null) {
		PostOrder(root.left);
		PostOrder(root.right);
		System.out.println(root.val);
	}
}
层序遍历：
void LevelOrder(TreeNode root){
	TreeNode temp;
	Queue q= new ArrayBlockingQueue(0);
	if (root == null) 
		return;
	q.add(root);
	while (!q.isEmpty()) {
		temp = (TreeNode) q.remove();
		System.out.println(temp.val);
		if (temp.left != null) {
			q.add(temp.left);
		}
		if (temp.left != null) {
			q.add(temp.right);
		}
	}
	q.clear();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

12.2、二叉查找树(二叉搜索树)(Mysql索引的底层)

二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作
1、查找操作：我们先去根节点，如果它等于我们要查找的数据，就返回；如果比根节点小，就在左子树中递归查找；如果比根节点值大，就在右子树中递归查找。

public class BinarySearchTree {
	private Node tree;
	public Node find(int data) {
		Node p = tree;
		while (p != null) {
			if (data < p.data) p = p.left;
			else if (data > p.data) p = p.right;
			else return p;
		}
		return null;
	}
	public static class Node {
		private int data;
		private Node left;
		private Node right;
		public Node(int data) {
			this.data = data;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2、插入操作 得先比较，从根节点开始

public void insert(int data) {
	if (tree == null) {
		tree = new Node(data);
		return;
	}
	Node p = tree;
	while (p != null) {
		if (data > p.data) {
			if (p.right == null) {
				p.right = new Node(data);
				return;
			}
			p = p.right;
		} else { // data < p.data
			if (p.left == null) {
				p.left = new Node(data);
			return;
			}
			p = p.left;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3、二叉查找树的删除操作(1、如果要删除的节点没有子节点，我们只需要直接将父节点中指向要删除节点的指针置为null；2、要删除的节点有一个子节点，我们只需要更新父节点，指向要删除节点的指针
3、要删除的节点有两个子节点，找到这个节点的右子树中的最小节点，替换到要删除的节点上)

public void delete(int data) {
	Node p = tree; // p指向要删除的节点，初始化指向根节点
	Node pp = null; // pp记录的是p的父节点
	while(p != null && p.data != data) {
		pp = p;
		if (data > p.data) p = p.right;
		else p = p.left;
	}
	if (p == null) return; // 没有找到
	//要删除的节点有两个子节点
	if (p.left != null && p.right != null) {//查找右子树中最小节点
		Node minP = p.right;
		Node minPP = p; // minPP表示minP的父节点
		while (minP.left != null) {
			minPP = minP;
			minP = minP.left;
		}
		p.data = minP.data; // 将minP的数据替换到p中
		p = minP; // 下面就变成了删除minP了
		pp = minPP;
	}
	//删除节点是叶子节点或者仅有一个子节点
	Node child; // p的子节点
	if (p.left != null) child = p.left;
	else if (p.right != null) child = p.right;
	else child = null;
	if (pp == null) tree = child; // 删除的是根节点
	else if (pp.left == p) pp.left = child;
	else pp.right = child;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

二叉查找树的执行效率：若是根节点的左右子树季度不平衡，已经退化到了链表，查找的时间复杂度为O(n)；平衡二叉查找树的时间复杂度O(lgn)

---

12.3、红黑树的应用场景(TreeMap 红黑树：一种近似平衡的二叉查找树：二叉树中任意一个节点的左右子树的高度相差不能大于1。包括完全二叉树、满二叉树) 红黑树一定得掌握

• 红黑树的由来
  红黑树是于1972年发明的，当时称为对称二叉B树，1978年得到优化，正式命名为红黑树。它的主要特征是在每个节点上增加一个属性来表示节点的颜色，可以是红色，也可以是黑色。红黑树和 AVL 树类似，都是在进行插入和删除元素时，通过特定的旋转来保持自身平衡的， 从而获得较高的查找性能。与AVL树相比，红黑树并不追求所有递归子树的高度差不超过1， 而是保证从根节点到叶子节点的最长路径不超过最短路径的2 倍，所以它的最坏运行时间也是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除操作后的自平衡调整。当然 ， 红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件，如下

• 红黑树的特点
  1、每个节点要么是红色，要么是黑色;
  2、根节点必须是黑色;
  3、红色节点不能连续(红色节点的孩子和父亲都不能是红色);
  4、对于每个节点，从该点至叶子的任何路径，都含有相同个数的黑色节点;
  5、确保节点的左右子树的高度差，不会超过二者中较低那个的一倍;

• 应用场景：搜索，插入删除次数多(为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的)
  1、map和set都是用红黑树实现的
  2、linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
  3、epoll在内核中的实现，用红黑树管理事件块
  4、nginx中，用红黑树管理timer
  5、Java的TreeMap实现
  AVL树适合用于插入删除次数比较少，但查找多的情况

• 关于动态数据结构：链表/栈/队列/哈希表（链表适合遍历的场景，插入和删除操作方便；栈和队列可以算一种特殊的链表，分别使用先进后出和先进先出的场景；哈希表适合插入和删除比较少，查找比较多的场景；红黑树对数据要求有序，对数据增删改查都有一定要求的时候）

• 散列表/跳表/红黑树性能对比：
  1、散列表：插入删除查找都是O(1)，是最常用的，缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于不需要顺序遍历、数据更新不那么频繁的；
  2、跳表：插入删除查找都是O(lgn)，能顺序遍历，缺点是空间复杂度O(n)，适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便；
  3、红黑树：插入删除查找都是O(lgn)，中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。

---

12.4、数据结构 堆

• 满足条件：1、堆是一个完全二叉树；2、堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值
  堆都支持哪些操作以及如何存储一个堆(通过数组来存储)
• 缺点：对于一组已经有序的数据来说，经过建堆后，数据反而变得更无序了
• 堆排序的过程：1、建立初始堆(把数组中的元素的序列看成是一颗完全二叉树，对该二叉树进行调整，使之成为堆) 根节点的索引是1
  2、堆排序(把根元素与最右子节点交换，然后再次构建堆，再与倒数第二集结点交换，然后再构建堆) 生成由小到大排列的数组
  时间复杂度：假设有n个数据，需要进行n-1次建堆，每次建堆本身耗时lgn，则其时间效率为O(nlgn) 空间复杂度O(1)
  建堆操作：

private static void buildHeap(int[] a, int n) {
	for (int i = n/2; i >= 1; --i) {
		heapify(a, n, i);
	}
}
private static void heapify(int[] a, int n, int i) {
	while (true) {
		int maxPos = i;
		if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
		if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
		if (maxPos == i) break;
		swap(a, i, maxPos);
		i = maxPos;
	}
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

	排序操作：	//n表示数据的个数，数组a中的数据从下标1到n的位置。
1

public static void sort(int[] a, int n) {
	buildHeap(a, n);
	int k = n;
	while (k > 1) {
		swap(a, 1, k);
		--k;
		heapify(a, k, 1);
	}
}
1
2
3
4
5
6
7
8
9

为什么快速排序要比堆排序性能好？
1、堆排序数据访问的方式没有快速排序友好(开拍是顺序访问；堆排序是跳着访问，对cpu缓存不友好)
2、同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序
应用：1、优先级队列；2、topK；3、流里面的中位数；

---

12.5、AC自动机：如何用多模式串匹配实现敏感词过滤功能？(使用Trie树)

字符串匹配算法：单模式串匹配算法(BF算法、RK算法、BM算法、KMP算法)，多模式串匹配算法(Trie树 最长前缀匹配)
AC自动机算法包含两个部分，第一部分是将多个模式串构建成AC自动机，第二部分是在AC自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成Trie树，另一个是在Trie树上构建失败指针
适用场景：

• 单模式串匹配：
  BF(直接匹配算法 简单场景，主串和模式串都不太长, O(mn) 效率最低)
  KP(字符集范围不要太大且模式串不要太长，否则hash值可能冲突，O(n))
  naive-BM(模式串最好不要太长（因为预处理较重）,比如IDE编辑器里的查找场景；预处理O(mm),匹配O(n),实现较复杂，需要较多额外空间)
  KMP(适合所有场景，整体实现起来也比BM简单，O(n+m)，仅需一个next数组的O(n)额外空间；但统计意义下似乎BM更快)
  还有一种比BM/KMP更快，且实现+理解起来都更容易的Sunday算法
• 多模式串匹配：
  naive-Trie(适合多模式串公共前缀较多的匹配(O(n*k)) 或者 根据公共前缀进行查找(O(k))的场景，比如搜索框的自动补全提示 root不存储字符)
  AC自动机(适合大量文本中多模式串的精确匹配查找, 查找的复杂度可以到O(n))**
  定义：AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上

public class AcNode {
	public char data; 
	public AcNode[] children = new AcNode[26]; //字符集只包含a~z这26个字符
	public boolean isEndingChar = false; //结尾字符为true
	public int length = -1; //当isEndingChar=true时，记录模式串长度
	public AcNode fail; //失败指针  相当于KMP中失效函数next数组
	public AcNode(char data) {
		this.data = data;
	}
}
1
2
3
4
5
6
7
8
9
10

12.6 B树和B+树的区别(为什么 MongoDB 索引选择B树，而 Mysql 选择B+树)?

一个是数据的保存位置，

• B树的数据每个节点既保存索引，又保存数据；B+树的数据只会落在叶子节点

一个是相邻节点的指向

• 增加了相邻节点的指向指针

上述两种特性造成的现象为：
1、B+树查询时间复杂度固定是logn，B树查询复杂度最好是 O(1)。
2、B+树相邻接点的指针可以大大增加区间访问性，可使用在范围查询等，而B树每个节点 key 和 data 在一起，无法区间查找。
3、B+树更适合外部存储，也就是磁盘存储。由于父级节点无 data 域，每个节点能索引的范围更大更精确
4、注意这个区别相当重要，B树每个节点即保存数据又保存索引，所以磁盘IO的次数很少，B+树只有叶子节点保存，磁盘IO多，但是区间访问比较好。

MongoDB

• MongoDB 是文档型的数据库，是一种 nosql，它使用类 Json 格式保存数据。比如之前我们的表可能有用户表、订单表、购物车表等等，还要建立他们之间的外键关联关系。但是类Json就不一样了。
• MongoDB使用B树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql。
  

Mysql

• Mysql作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。

---

13、海量数据的处理思路问题

13.1、大数据量的问题：

10w个id，怎么去100亿个id里找数据，怎么做能更快，分库分表？

---

13.2、有10G大小的文件，每行记录一条运单信息，机器大小是500M，求出出现次数最多的前1000条运单号，给出思路。

典型的Top K算法(分治思想)
1、先对这批海量数据预处理，在O(N)的时间内用Hash表完成分组(相同单号被分配到Hash桶中的同一条链表中) %20 20个文件，每个文件500M 堆的大小取决于机器的内存值500M;
2、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK
3、对每个堆中的TOPk，计算出前k个数（归并排序）

13.3、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

方案1：可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M
遍历文件b，采取和a相同的hash函数将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,…,a999vsb999）中，
不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可
求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

13.4、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

方案1：用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存内存，还可以接受。
然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素

13.5、怎么在海量数据中找出重复次数最多的一个？

方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求100w个数中找出最大的100个数
用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)

13.6、如果你所在的省有50万考生，如何通过成绩快速排序得出名次呢？

13.7、假设我们有10万个手机号码，希望将这10万个手机号码从小到大排序，你有什么比较快速的排序方法呢？

13.8、假设我们有1000万个整型数据，每个数据占8个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这1000万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过100MB，你会怎么做呢？

13.9、如何在海量数据中快速查找某个数据？(索引)(在计算机组成中称为寻址)

MySQL底层依赖的是B+树这种数据结构，Redis这样的Key-Value数据库中的索引，又是怎么实现的呢？底层依赖的又是什么数据结构呢？

• 索引存储位置：在内存还是硬盘
• 单值查找还是区间查找？
  单关键词查找还是多关键词组合查找？对于结构化数据的查询需求(MYSQL)，针对多个关键词的组合，建立索引；对于非结构数据的查询需求(搜索引擎)，以针对单个关键词构建索引，然后通过集合操作，比如求并集、求交集等，计算出多个关键词组合的查询结果。
  索引的维护成本。因为在原始数据动态增删改的同时，也需要动态的更新索引。
• 构建索引常用的数据结构？
  对动态数据建立索引：散列表、红黑树、跳表、B+树；位图、布隆过滤器可以作为辅助索引；有序数组可以用来对静态数据构建索引。
• 散列表：一些键值数据库，比如Redis、Memcache，就是使用散列表来构建索引的，增删改查的性能非常好，时间复杂度为O(1)，这类索引，一般都构建在内存中；
• 红黑树：作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是O(logn)，也非常适合用来构建内存索引。Ext文件系统中，对磁盘块的索引，使用的是红黑树；
• B+树：比起红黑树来说，更加适合构建存储在磁盘中的索引，B+树是一个多叉树，所以，对相同个数的数据构建索引，B+树的高度要低于红黑树。当借助索引查询数据的时候，
  读取B+树索引，需要的磁盘IO次数非常更少，关系型数据库的索引：如Mysql、oracle，使用的是B+树建立索引
• 跳表：支持快速添加、删除、查找数据。而且通过灵活调整索引结点个数和数据个数之间的比例，可以很好地平衡索引对内存的消耗及其查询效率。Redis中的有序集合，就是用跳表来构建的
  布隆过滤器：对于判定存在的数据，有可能并不存在，但是对于判定不存在的数据，那肯定就不存在。内存占用非常少
  有序数组：如果数据是静态的，也就是不会有插入、删除、更新操作，那我们可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据
• 你知道基础系统、中间件、开源软件等系统中，有哪些用到了索引吗？这些系统的索引是如何实现的呢？
  1、区块链拿以太坊来说，存储用的leveldb，数据存储用的数据结构是帕特利夏树，是一种高级的trie树，很好的做了数据的压缩；
  2、消息中间件像kafka这种，会去做持久化，每个partition都会有很多数据，会有大量数据存储在磁盘中，所以每个partition也会有个索引，方便去做快速访问。
  3、ES中的倒排索引用了trie树(一种专门处理字符串匹配的数据结构),对每个需要索引的key维护了一个trie树,用于定位到这个key在文件中的位置,然后直接用有序列表直接去访问对应的documents
  trie树(两个操作：一个将字符串插入到Trie树的过程。另一个是在Trie树中查询一个字符串)

Q:Trie树：如何实现搜索引擎的搜索关键词提示功能？(为了方便快速输入，当你在搜索引擎的搜索框中，输入要搜索的文字的某一部分的时候，搜索引擎就会自动弹出下拉框，里面是各种关键词提示)
A:‘字典树’。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题.
Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起（感觉有点像霍夫曼编码：左0右1）
时间复杂度：O(k) k为字符串长度
应用场景：自动输入补全，比如输入法自动补全功能、IDE代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等
Q:Trie树应用场合对数据要求比较苛刻，比如字符串的字符集不能太大，前缀重合比较多等。如果现在给你一个很大的字符串集合，比如包含1万条记录，如何
通过编程量化分析这组字符串集合是否比较适合用Trie树解决呢？也就是如何统计字符串的字符集大小，以及前缀重合的程度呢？
A:依次读取每个字符串的字符构建 Trie 树，用散列表来存储每一个节点。每一层树的所有散列表的元素用一个链表串联起来，求某一长度的前缀重合，在对应树层级上遍历该层链表，
求链表长度，除以字符集大小，值越小前缀重合率越高。遍历所有树层级的链表，存入散列表，最后散列表包含元素的个数，就代表字符集的大小

如何存储一个Trie树？

public class Trie {
	private TrieNode root = new TrieNode('/'); //存储无意义字符
	//往Trie树中插入一个字符串
	public void insert(char[] text) {
		TrieNode p = root;
		for (int i = 0; i < text.length; ++i) {
			int index = text[i] - 'a';
			if (p.children[index] == null) {
				TrieNode newNode = new TrieNode(text[i]);
				p.children[index] = newNode;
			}
			p = p.children[index];
		}
		p.isEndingChar = true;
	}
	//在Trie树中查找一个字符串
	public boolean find(char[] pattern) {
		TrieNode p = root;
		for(int i = 0; i < pattern.length; ++i) {
			int index = pattern[i] - 'a';
			if (p.children[index] == null) {
				return false; //不存在pattern
			}
			p = p.children[index];
		}
		if(p.isEndingChar == false) 
			return false; //不能完全匹配，只是前缀
		else 
			return true; //找到pattern
	}
	public class TrieNode {
		public char data;
		public TrieNode[] children = new TrieNode[26];
		public boolean isEndingChar = false;
		public TrieNode(char data) {
			this.data = data;
		}
	}
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

13.10、并行计算：利用并行处理提高算法的执行效率(分治的思想)

算法无法再继续优化的情况下，如何来进一步提高执行效率呢？可以使用一种简单但好用的优化方法，那就是并行计算。

• 1、并行排序 对时间复杂度为O(nlgn)的三种排序算法：归并/快排/堆排进行并行化处理
  如：归并排序时，将8G的数据先划分为16个小的数据集合，然后多线程处理，最后将这16个有序集合合并；快速排序中，先扫描一遍数据，遭到数据所处的范围区间，
  同样划分为16个小区间，并行进行排序，等到16个线程都执行借宿之后，得到的数据就是有序数据了。
• 2、并行查找 散列表，给动态数据构建索引，在数据不断加入的时候，散列表的装载因子就会越来越大。为了保证散列表性能不下降，我们就需要对散列表进行动态扩容，
  可以将数据随机分割成k份（比如16份），每份中的数据只有原来的1/k，然后我们针对这k个小数据集合分别构建散列表，增加存储空间的利用率。

---

14、图的应用

14.1、如何存储微博、微信等社交网络中的好友关系？

• 微博：有向图(入度代表粉丝数，出度代表关注数)
  社交关系存储方法：邻接表(存储用户关注关系)+逆邻接表(存储被关注信息)

• 需求：判断用户A是否关注了用户B；判断用户A是否是用户B的粉丝；用户A关注用户B；用户A取消关注用户B；
  根据用户名称的首字母排序，分页获取用户的粉丝列表；根据用户名称的首字母排序，分页获取用户的关注列表。

• 如何迅速判断俩用户之间的关注关系？
  因为需要按首字母排序，获取粉丝列表或关注列表，在邻接表右边使用跳表是最合适的(跳表存储的数据有序)。这是因为，跳表插入、删除、查找都非常高效，时间复杂度是O(logn)，空间复杂度上稍高，是O(n)
  如何解决数据量大的问题？
  可以通过哈希算法等数据分片方式，将邻接表存储在不同的机器上。例如：在机器1上存储顶点1，2，3的邻接表，在机器2上，存储顶点4，5的邻接表，当要查询顶点与顶点关系的时候，我们就利用同样的哈希算法，先定位顶点所在的机器，然后再在相应的机器上查找。
  持久化存储关系？
  使用数据库

• 微信：无向图(好友间建立一条边)

• QQ：带权图(每条边都有一个权重，可以通过权重表示QQ好友间的亲密度)

14.2、如何在内存中存储图这种数据结构？

• 邻接矩阵：依赖一个二维数组，A[i][j]=w表示可达，w表示权重 (我们的扫雷游戏就是使用的这种有向图数据结构，带权值(0表示没有操作，1表示地雷，-1表示插上了红旗)下次可以做成PPT
  缺点：对于无向图来说，浪费了一半的空间；对于稀疏矩阵，绝大多数的存储空间都被浪费了
  优点：基于矩阵，在获取两顶点的关系时，就非常高效；第二是方便计算，如求最短路径
• 邻接表：每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点
  优点：节省空间
  缺点：在邻接表中查询两个顶点间的关系效率较低，改进措施(邻接表右侧的链表可以使用二叉树/红黑树/跳表来表示，跳表最适合)

14.3、图的其他领域应用？

Gradle这个编译工具，内部组织task的方式用的是有向图；
Android framework层提供了一个CoordinatorLayout，其内部协调子view的联动，也是用的图；
互联网上网页之间通过超链接连接成一张有向图；
城市乃至全国交通网络是一张加权图；

14.4、如何找出社交网络中的三度好友关系？(深度优先和广度优先搜索算法)(存储使用邻接表)(无向图)

• BFS:广度优先搜索：时间复杂度O(V+E) V为顶点个数，E为边的个数(对于一个连通图来说,E肯定要大于等于V-1，所以，广度优先搜索的时间复杂度也可以简写为O(E)。)
  广度优先搜索的空间消耗主要在几个辅助变量visited数组、queue队列、prev数组上.所以空间复杂度是O(V)。
• DFS:深度优先搜索(深度优先搜索找出来的路径，并不是顶点s到顶点t的最短路径) 时间复杂度是O(E) 空间复杂度是O(V)
  借助 栈来实现 辅助变量visited数组和prev数组
• 社交网络中的三度好友关系?
  非常适合于图的广度优先搜索算法来解决，因为它是层层往外推进的。首先，遍历与起始顶点最近的一层顶点，也就是用户的一度好友，然后再遍历与用户距离的边数为2的顶点，也就是二度好友关系，以及与用户距离的边数为3的顶点，也就是三度好友关系。
  适用场合：状态空间不大，也就是图不大的搜索，属于基本的搜索算法(高级搜搜算法有A*/IDA*)

14.5、如何确定代码源文件的编译依赖关系？(拓扑排序 有向无环图)

问题阐述：一个完整的项目往往会包含很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。比如，A.cpp依赖B.cpp，那在编译的时候，编译器需要先编译B.cpp，才能编译A.cpp。我们可以把源文件与源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。
算法解析：

//数据结构：有向无环图，使用邻接表来存储
public class Graph {
	private int v; // 顶点的个数
	private LinkedList<Integer> adj[]; // 邻接表存放顶点
	public Graph(int v) {
		this.v = v;
		adj = new LinkedList[v];
		for (int i=0; i<v; ++i) {
			adj[i] = new LinkedList<>();
		}
	}
	public void addEdge(int s, int t) { // s先于t，边s->t
		adj[s].add(t);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

两种实现方式：Kahn和DFS
1、Kahn基于贪心算法，思路是如果s需要先于t执行，那就添加一条s指向t的边，如果某个顶点入度为0， 也就表示，没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行。
我们先从图中，找出一个入度为0的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减1）
我们循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。

public void topoSortByKahn(){
	int[] inDegree = new int[v]; // 统计每个顶点的入度
	for (int i = 0; i < v; ++i){
		for (int j = 0; j < adj[i].size(); ++j){
			int w = adj[i].get(j); // i->w   w为  ->w，即被指向的顶点，有某个点或几个点只指向他人，而不会被指向
			inDegree[w]++;
		}
	}
	LinkedList<Integer> queue = new LinkedList<>();
	for (int i = 0; i < v; ++i){
		if (inDegree[i] == 0) queue.add(i);//某个顶点的入度是0，将此顶点加入队列
	}
	while (!queue.isEmpty()){
		int i = queue.remove();
		System.out.print("->" + i);
		for (int j = 0; j < adj[i].size(); ++j){
			int k = adj[i].get(j);
			inDegree[k]--;	//删除顶点，即此顶点可达的顶点入度都减1
			if (inDegree[k] == 0) queue.add(k);//此时，又有一个/多个顶点的入度为0，加入到队列中
		}
	}
}//时间复杂度就是O(V+E)（V表示顶点个数，E表示边的个数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.DFS算法 时间复杂度也是O(V+E)。

public void topoSortByDFS(){
	//先构建逆邻接表，边s->t表示，s依赖于t，t先于s
	LinkedList<Integer> inverseAdj[] = new LinkedList[v];
	for(int i=0; i<v; ++i) {//申请空间
		inverseAdj[i] = new LinkedList<>();
	}
	for(int i=0; i<v; ++i) {//通过邻接表生成逆邻接表  为什么这么转换
		for (int j = 0; j < adj[i].size(); ++j) {
			int w = adj[i].get(j); // i->w
			inverseAdj[w].add(i); // w->i
		}
	}
	boolean[] visited = new boolean[v];
	for(int i=0; i<v; ++i) {//深度优先遍历图   
		if (visited[i] == false) {
			visited[i] = true;
			dfs(i, inverseAdj, visited);
		}
	}
}
private void dfs(int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited){
	for (int i = 0; i < inverseAdj[vertex].size(); ++i){
		int w = inverseAdj[vertex].get(i);
		if (visited[w] == true) continue;
		visited[w] = true;
		dfs(w, inverseAdj, visited);
	}//先把vertex这个顶点可达的所有顶点都打印出来之后，再打印它自己
	System.out.print("->" + vertex);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3、拓扑排序的应用：需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。
实现拓扑排序的Kahn算法能检测图中环的存在，若果最后输出的顶点个数少于图中顶点个数，说明图中还有入度不是0的顶点，那就说明，图中存在环。
这就是环的检测问题：(只需要记录已经访问过的用户ID，当用户ID第二次被访问的时候，就说明存在环)

HashSet<Integer> hashTable = new HashSet<>(); // 保存已经访问过的actorId
long findRootReferrerId(long actorId) {
	if (hashTable.contains(actorId)) { // 存在环
		return;
	}
	hashTable.add(actorId);
	Long referrerId = select referrer_id from [table] where actor_id = actorId;
	if (referrerId == null) return actorId;
		return findRootReferrerId(referrerId);
}
1
2
3
4
5
6
7
8
9
10

如果想知道数据库中所有用户之间的推荐关系，有没有存在环的情况，需要使用拓扑排序算法，我们把用户之间的推荐关系，从数据库中加载到内存中，然后构建成有向图的数据结构，再利用拓扑排序，就可以快速检测出是否存在环。

14.6、最短路径算法 (Dijkstra/A*)

建模：将地图抽象成具体的数据结构-图，把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。
数据结构如下：

public class Graph { //有向有权图的邻接表表示
	private LinkedList<Edge> adj[]; //邻接表
	private int v; //顶点个数
	public Graph(int v) {
		this.v = v;
		this.adj = new LinkedList[v];
		for (int i = 0; i < v; ++i) {
			this.adj[i] = new LinkedList<>();
		}
	}
	public void addEdge(int s, int t, int w) { //添加一条边
		this.adj[s].add(new Edge(s, t, w));
	}
	private class Edge {
		public int sid; //边的起始顶点编号
		public int tid; //边的终止顶点编号
		public int w; 	//权重
		public Edge(int sid, int tid, int w) {
			this.sid = sid;
			this.tid = tid;
			this.w = w;
		}
	}
	//下面这个类是为了dijkstra实现用的
	private class Vertex {
		public int id; //顶点编号ID
		public int dist; //从起始顶点到这个顶点的距离
		public Vertex(int id,int dist) {
			this.id = id;
			this.dist = dist;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

最短路径算法实现Dijkstra 时间复杂度是O(E*logV) E为所有边的个数，V表示顶点的个数
思想：1、采用贪婪法：总是选取最接近源点的顶点；2、使用优先队列并按照到s的距离来存储未被访问过的顶点；3、不能用于权值为负的情况。
具体而言：Dijkstra通过回溯穷举所有从s到达t的不同路径，在此基础上，利用动态规划的思想，对回溯搜索进行了剪枝，只保留起点到某个顶点的最短路径，继续往外扩展搜索，能得到最优解。

// 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
private class PriorityQueue { // 根据vertex.dist构建小顶堆
private Vertex[] nodes;
private int count;
public PriorityQueue(int v) {
	this.nodes = new Vertex[v+1];
	this.count = v;
}
public Vertex poll() { // TODO: 留给读者实现... }
public void add(Vertex vertex) { // TODO: 留给读者实现...}
// 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)。
public void update(Vertex vertex) { // TODO: 留给读者实现...}
public boolean isEmpty() { // TODO: 留给读者实现...}
}
public void dijkstra(int s, int t) { // 从顶点s到顶点t的最短路径
	int[] predecessor = new int[this.v]; //用来还原最短路径，用于它记录每个顶点的前驱顶点
	Vertex[] vertexes = new Vertex[this.v]; //记录从起始顶点到每个顶点的距离（dist），我们更新了某个顶点的dist值之后，如果这个顶点已经在优先级队列中，就不要再将它重复添加进去了
	for (int i = 0; i < this.v; ++i) {
		vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
	}
	PriorityQueue queue = new PriorityQueue(this.v);// 小顶堆
	boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
	vertexes[s].dist = 0;
	queue.add(vertexes[s]);
	inqueue[s] = true;
	while (!queue.isEmpty()) {
		Vertex minVertex= queue.poll(); // 取堆顶元素并删除
		if (minVertex.id == t) break; // 最短路径产生了
		for (int i = 0; i < adj[minVertex.id].size(); ++i) {
			Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
			Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
			if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist
				nextVertex.dist = minVertex.dist + e.w;
				predecessor[nextVertex.id] = minVertex.id;
				if (inqueue[nextVertex.id] == true) {
					queue.update(nextVertex); // 更新队列中的dist值
				} else {
					queue.add(nextVertex);
					inqueue[nextVertex.id] = true;
				}
			}
		}
	}
	// 输出最短路径
	System.out.print(s);
	print(s, t, predecessor);
}
private void print(int s, int t, int[] predecessor) {
	if (s == t) return;
	print(s, predecessor[t], predecessor);
	System.out.print("->" + t);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

实际的应用中，相比Dijkstra算法，地图软件更多的是A*启发式搜索算法

• 实例2：在计算最短时间的出行路线中，如何获得通过某条路的时间呢？
  与时间相关的变量：1、路径长度；2、路况；3、拥堵情况；4、红绿灯个数，获取这些因素后就可以建立一个回归模型(如线性回归)来评估时间
  情况3是数据是动态的，可以通过与交通部门合作获得路段拥堵情况，联合其他导航软件获得该路段的在线人数

• 实例3：今天讲的出行路线问题，我假设的是开车出行，那如果是公交出行呢？如果混合地铁、公交、步行，又该如何规划路线呢？
  混合公交、地铁和步行时，地铁时刻表是固定的，容易估算。公交虽然没那么准时，大致时间是可以估计的，步行时间受路拥堵状况小，基本与道路长度成正比，也容易估算。总之，公交、地铁、步行，时间估算会比开车更容易，也更准确些。

• 实例4：翻译系统。只能针对单个词来做翻译。如果要翻译一整个句子，我们需要将句子拆成一个一个的单词，再丢给翻译系统。针对每个单词，翻译系统会返回一组可选的翻译列表，并且针对每个翻译打一个分，表示这个翻译的可信程度。我们希望计算出得分最高的前K个翻译结果。
  解答：使用Dijkstra最短路径算法

14.7、A*搜索算法(实现游戏中的寻路功能)

1、与Dijkstra算法的比较：Dijkstra类似BFS算法，它每次找到跟起点最近的顶点，往外扩展
2、曼哈顿距离：两点之间横纵坐标的距离之和，计算过程只涉及加减法，符号位反转，比欧几里得距离高效
int hManhattan(Vertex v1, Vertex v2) { //Vertex表示顶点，后面有定义
return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
} //启发函数
3、A*算法是对Dijkstra算法的简单改进

private class Vertex {
	public int id; //顶点编号ID
	public int dist; //从起始顶点，到这个顶点的距离，也就是g(i)
	public int f; //新增：f(i)=g(i)+h(i)
	public int x, y; //新增：顶点在地图中的坐标（x, y）
	public Vertex(int id, int x, int y) {
		this.id = id;
		this.x = x;
		this.y = y;
		this.f = Integer.MAX_VALUE;
		this.dist = Integer.MAX_VALUE;
	}
}
//Graph类的成员变量，在构造函数中初始化
Vertex[] vertexes = new Vertex[this.v];
//新增一个方法，添加顶点的坐标
public void addVetex(int id, int x, int y) {
	vertexes[id] = new Vertex(id,x,y)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

与Dijkstra算法的三点区别：
1、优先级队列构建的方式不同。A算法是根据f值（也就是刚刚讲到的f(i)=g(i)+h(i)）来构建优先级队列，而Dijkstra算法是根据dist值（也就是刚刚讲到的g(i)）来构建优先级队列；
2、A算法在更新顶点dist值的时候，会同步更新f值；
3、循环结束的条件也不一样。Dijkstra算法是在终点出队列的时候才结束，A算法是一旦遍历到终点就结束。
(A每次从f值最小的顶点出队列，一旦搜索到重点就不再继续考察其他顶点和路线，也就不可能找出最短路径)

public void astar(int s, int t) { //从顶点s到顶点t的路径
	int[] predecessor = new int[this.v]; //用来还原路径
	//按照vertex的f值构建的小顶堆，而不是按照dist
	PriorityQueue queue = new PriorityQueue(this.v);
	boolean[] inqueue = new boolean[this.v]; //标记是否进入过队列
	vertexes[s].dist = 0;
	vertexes[s].f = 0;
	queue.add(vertexes[s]);
	inqueue[s] = true;
	while (!queue.isEmpty()) {
		Vertex minVertex = queue.poll(); //取堆顶元素并删除
		for (int i = 0; i < adj[minVertex.id].size(); ++i) {
			Edge e = adj[minVertex.id].get(i); //取出一条minVetex相连的边
			Vertex nextVertex = vertexes[e.tid]; //minVertex-->nextVertex
			if (minVertex.dist + e.w < nextVertex.dist) { //更新next的dist,f
				nextVertex.dist = minVertex.dist + e.w;
				nextVertex.f= nextVertex.dist+hManhattan(nextVertex, vertexes[t]);//关键之处，使用f(i)=g(i)+h(i)）来构建优先级队列
				predecessor[nextVertex.id] = minVertex.id;//用于还原路径
				if (inqueue[nextVertex.id] == true) {
					queue.update(nextVertex);
				} else {
					queue.add(nextVertex);//入队
					inqueue[nextVertex.id] = true;
				}
			}
			if (nextVertex.id == t) break; //只要到达顶点t，就可以结束while了，no，这个地方王争搞错了
		}
	}
	//输出路径
	System.out.print(s);
	print(s, t, predecessor); // print函数请参看Dijkstra算法的实现
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

总结：A算法属于一种启发式搜索算法，还有一些其他的同类型算法：IDA算法、蚁群算法、模拟退火算法等
启发式搜索算法利用估价函数，避免“跑偏”，贪心地朝着最有可能到达终点的方向前进，这种算法找出的路线，并不是最短路线，但是启发式搜索算法能很好地平衡路线质量和执行效率，
它在实际的软件开发中的应用更加广泛。
补充1：break的作用域

break 跳出最近的｛｝包裹的代码，如果有标记，就跳出标记的｛｝
上述代码更正为：
if(nextVertex.id==t){
	queue.clear();
	break;
}
1
2
3
4
5
6

---

15、位图(bitmap)与推荐算法

• 利用欧几里得公式计算俩用户听歌喜好的距离
• 头条的新闻推送，淘宝的猜你喜欢
• bitmap(位图)与布隆过滤器

bitmap的数据结构：

public class BitMap {
	private char[] bytes;
	private int nbits;
	public BitMap(int nbits) {
		this.nbits = nbits;
		this.bytes = new char[nbits/8+1];
	}
	public void set(int k) {
		if (k > nbits) return;
		int byteIndex = k / 8;
		int bitIndex = k % 8;
		bytes[byteIndex] |= (1 << bitIndex);
	}
	public boolean get(int k) {
		if (k > nbits) return false;
		int byteIndex = k / 8;
		int bitIndex = k % 8;
		return (bytes[byteIndex] & (1 << bitIndex)) != 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

好处：如果用散列表存储着1千万的数据，数据时32位的整型数，也就是需要4字节的存储空间，那总共至少需要40MB的存储空间，如果我们通过位图的话，数字范围在1到1亿之间，
只需要1亿个二进制位，也就是12MB左右的存储空间即可。

15.1、什么是布隆过滤器，其实现原理是？（java.util的BitSet类，实现类位图） False positive指的是？（蚂蚁问到）

布隆过滤器是由一个很长的二进制向量(位图)加一系列随机映射函数(例如hash函数)组成。它可以用于检索一个元素是否在一个集合中。
例如：我们把hash函数设计成f(x)=x%n,其中，x表示数字，n表示位图的大小(1亿)，也就是，对数字跟位图的大小进行取模求余。
hash函数的特殊设计：一个hash函数可能会存在冲突，那使用多个hash函数一块儿定义一个数据，我们把这K个数字作为位图中的下标，降低冲突的概率。当要查询某个数字是否存在的时候，我们用同样的K个哈希函数，对这个数字求哈希值，如果都是true，则说明，这个数字存在。(带来了新的缺点：容易误判)优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误判(即判断一个元素存在，可能被误判，而判断这个元素不存在，则一定不存在)和删除困难
数据结构采用了bitmap 位图 解决缓存击穿的问题，有一个拦截机制，能迅速判断请求是否有效，他的内部维护了一系列合法有效的key，若是请求的元素在这个集合当中，说明请求有效。
false-positive (误检率)
布隆过滤器有一定的误检率，即判断一个元素存在，可能被误判(例如布隆过滤器中只存在A和E，但是对B进行过滤时，刚好被定位到了A的上半部分和E的下半部分，被误判为存在)

• 应用：
  1、ip地址的布隆过滤器(比如统计一个大型网站的每天的UV数) 网页爬虫的url去重
  2、redis中的防止缓存穿透(使用bloomFilter来减轻系统负担)
  3、比特币(spv客户端访问full比特币客户端时，使用布隆过滤器进行拦截，减轻系统负担)
  4、分布式系统MapReduce中，使用布隆过滤器判断某个子任务是否存在某台机器上
  例子1：我们用布隆过滤器来记录已经爬取过的网页链接，假设需要判重的网页有10亿，那我们可以用一个10倍大小的位图来存储，也就是100亿个二进制位，换算成字节，
  那就是大约1.2GB。之前我们用散列表判重，需要至少100GB的空间。相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多。
  例子2：假设我们有1亿个整数，数据范围是从1到10亿，如何快速并且省内存地给这1亿个数据从小到大排序？
  传统的做法：1亿个整数，存储需要400M空间，排序时间复杂度最优 N×log(N)
  使用位图算法：数字范围是1到10亿，用位图存储125M就够了，然后将1亿个数字依次添加到位图中，然后再将位图按下标从小到大输出值为1的下标，排序就完成了，时间复杂度为 N

15.2、概率统计：如何利用朴素贝叶斯算法过滤垃圾短信？

• 1.基于黑名单的过滤器
  ①布隆过滤器:如果我们要存储500万个手机号码，我们把位图大小设置为10倍数据大小，也就是5000万，那也只需要使用5000万个二进制位（5000万bits），换算成字节，
  也就是不到7MB的存储空间。比起散列表的解决方案，内存的消耗减少了很多。
  ②我们可以把黑名单存储在服务器端上，把过滤和拦截的核心工作，交给服务器端来做。手机端只负责将要检查的号码发送给服务器端，服务器端通过查黑名单，
  判断这个号码是否应该被拦截，并将结果返回给手机端。网络传输的速度较慢(硬性要求：必须联网处理)
• 2.基于规则的过滤器
  前提：有大量的样本数据（比如1000万条短信），并且每条短信都做好了标记，它是垃圾短信还是非垃圾短信
• 3.基于概率统计的过滤器
  解决了基于规则的过滤器容易被绕过的缺陷。基于概率统计的基础理论是朴素贝叶斯算法(将一个未知概率的求解，分解成其他三个已知概率的求解)
• 总结：可以结合上述3点共同判断一条短信是否为垃圾短信
  评论中的观点：机器学习尤其是NLP方向的很多算法可用于anti-spam(反垃圾邮件)，判别式模型(logistic regression)效果通常好于生成式模式(naive-bayes),对于电话号码数字，正则或定时拉黑名单比ML模型简单可靠。

15.3、推荐系统

这里是引用

原则：找到跟你口味偏好相似的用户，把他们爱听的歌曲推荐给你；找出跟你喜爱的歌曲特征相似的歌曲，把这些歌曲推荐给你
1.基于相似用户做推荐(基于用户建模的协同过滤算法推荐)
计算多维向量(用户对各首歌曲的喜爱程度作为向量)之间的距离，使用欧几里得计算公式
2.基于相似歌曲做推荐
针对每首歌曲，将每个用户的打分作为向量

• 弱点：
  1、稀疏性问题：当用户评价项目数少于中项目数时，就很容易造成评价矩阵相当稀疏，导致算法难以找到一个用户的偏好相似邻居。
  2、冷启动问题：基于用户协同过滤是建立在有大量用户对某个产品的评价上的，由于在新产品开始阶段没有人购买，也没有对其进行评价，那么在开始阶段也将无法对其进行推荐
  3、算法扩展性问题。随着物品数尤其是用户数的剧烈增加，最近邻居算法的计算量也相应增加，所以不太适合数据量大的情况使用，所以推荐系统性能也会大大受影响
  4、特殊用户问题。

---

16、断点续传思路和算法

在http头文件里面保存了content和content-type标签，用于记录传输文件的字节段。