算法和数据结构（golang语言实现）

算法和数据结构（golang语言实现）

第1节 选择、冒泡、插入、复杂度

选择排序

选择排序 时间复杂度为O(N^2) 额外空间复杂度O(1）

过程：

arr[0～N-1]范围上，找到最小值所在的位置，然后把最小值交换到0位置。

arr[1～N-1]范围上，找到最小值所在的位置，然后把最小值交换到1位置。

arr[2～N-1]范围上，找到最小值所在的位置，然后把最小值交换到2位置。

…

arr[N-2～N-1]范围上，找到最小值位置，然后把最小值交换到N-2位置

选择排序的时间复杂度为O(N^2)，将马上解释！

D:\Workspace\Go\src\projects\demo\main.go

package main

import (
	"log"
)

func main() {
	arr := []int{10, 3, 0, -9, 2, 100, -22, 54, 23, 7}
	log.Println(arr)
	selectionSort(arr)
	log.Println(arr)
}

func selectionSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	// 长度 >= 2
	n := len(arr)
	for i := 0; i < n-1; i++ {
		// i ~ n-1范围上，找到最小值
		// 最小值，和i位置的数交换
		// 不是值，位置
		minIndex := i
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		swap(arr, i, minIndex)
	}
}

func swap(arr []int, i int, j int) {
	tmp := arr[i]
	arr[i] = arr[j]
	arr[j] = tmp
}

PS D:\Workspace\Go\src\projects\demo> go run main.go     
2023/06/06 17:25:26 [10 3 0 -9 2 100 -22 54 23 7]
2023/06/06 17:25:26 [-22 -9 0 2 3 7 10 23 54 100]

冒泡排序

冒泡排序 时间复杂度为O(N^2) 额外空间复杂度O(1）

过程：

在arr[0～N-1]范围上：

arr[0]和arr[1]，谁大谁来到1位置；

arr[1]和arr[2]，谁大谁来到2位置；

…

arr[N-2]和arr[N-1]，谁大谁来到N-1位置；

在arr[0～N-2]范围上，重复上面的过程，最后一步是arr[N-3]和arr[N-2]，谁大谁来到N-2位置

在arr[0～N-3]范围上，重复上面的过程，最后一步是arr[N-4]和arr[N-3]，谁大谁来到N-3位置

…

最后在arr[0～1]范围上，重复上面的过程，但最后一步是arr[0]和arr[1]，谁大谁来到1位置

D:\Workspace\Go\src\projects\demo\main.go

package main

import (
	"log"
)

func main() {
	arr := []int{10, 3, 0, -9, 2, 100, -22, 54, 23, 7}
	log.Println(arr)
	bubbleSort(arr)
	log.Println(arr)
}

func bubbleSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	// 长度 >= 2
	n := len(arr)
	for end := n - 1; end > 0; end-- {
		for i := 0; i < end; i++ {
			if arr[i] < arr[i+1] {
				swap(arr, i, i+1)
			}
		}
	}
}

func swap(arr []int, i int, j int) {
	tmp := arr[i]
	arr[i] = arr[j]
	arr[j] = tmp
}

PS D:\Workspace\Go\src\projects\demo> go run main.go     
2023/06/06 17:31:56 [10 3 0 -9 2 100 -22 54 23 7]
2023/06/06 17:31:56 [100 54 23 10 7 3 2 0 -9 -22]

插入排序

插入排序 时间复杂度为O(N^2) 额外空间复杂度O(1）

过程：

想让arr[0~0]上有序，这个范围只有一个数，当然是有序的。

想让arr[0~1]上有序，所以从arr[1]开始往前看，如果arr[1]<arr[0]，就交换。否则什么也不做。

…

想让arr[0~i]上有序，所以从arr[i]开始往前看，arr[i]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。

最后一步，想让arr[0~N-1]上有序， arr[N-1]这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。

D:\Workspace\Go\src\projects\demo\main.go

package main

import "log"

func main() {
	arr := []int{10, 3, 0, -9, 2, 100, -22, 54, 23, 7}
	log.Println(arr)
	insertSort(arr)
	log.Println(arr)
}

func insertSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	n := len(arr)
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0 && arr[j] > arr[j+1]; j-- {
			swap(arr, j, j+1)
		}
	}
}

func swap(arr []int, i int, j int) {
	tmp := arr[i]
	arr[i] = arr[j]
	arr[j] = tmp
}

PS D:\Workspace\Go\src\projects\demo> go run main.go
2023/06/11 10:37:44 [10 3 0 -9 2 100 -22 54 23 7]
2023/06/11 10:37:44 [-22 -9 0 2 3 7 10 23 54 100]

复杂度

时间复杂度 常数时间的操作

如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间。

这样的操作为常数时间的操作。

• 常见的位运算（>>、>>>、<<、|、&、^等）

• 常见的算术运算（+、-、*、/、% 等）

• 赋值、比较、自增、自减操作等

• 数组寻址操作

总之，执行时间固定的操作都是常数时间的操作。

反之，执行时间不固定的操作，都不是常数时间的操作。

时间复杂度

粗略来说：

时间复杂度是算法流程的常数操作总量与样本数量之间的表达式关系，该表达式只看最高阶的部分

最好、平均、最差三种时间复杂度评价方式，

注意：我们只关注最差的时间复杂度，也就是O( )

如何确定算法流程的总操作数量与样本数量之间的表达式关系？

1，想象该算法流程所处理的数据状况，要按照最差情况来。

2，把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。

3，如果数据量为N，看看基本动作的数量和N是什么关系。

时间复杂度

我们以刚才的选择、冒泡、插入排序举例

等差数列求和公式为：S(n) = n*a1 + n*(n-1)*d/2

S(n) = n*a1 + (n^2)*d/2 - n*d/2

S(n) = (d/2) * (n^2) + (a1 - d/2) * n + 0

三个排序，总的常数操作数量 = a*(n^2) + b*n + c (a、b、c都是常数)

当完成了表达式的建立，只要把最高阶项留下即可。

低阶项都去掉！所有系数也去掉！

记为：O(忽略掉系数的高阶项)

时间复杂度都为O(N^2)

插入排序 优于 选择排序和冒泡排序

他们时间复杂度都是O(N^2)

但是插入排序的常数时间更好，举例子说明

3、4、3、2、5

注意！

1，算法的过程，和具体的语言是无关的。

2，想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉！也就是说，虽然你知道了时间复杂度的定义，但是让你分析一个算法流程，你可能还是不会去分析，因为你对算法流程不熟悉。能分析时间复杂度，一定是建立在对流程熟悉的基础上！这里面技巧很多。我们后面的课会大量分析各种流程的时间复杂度。

3，一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。

时间复杂度的意义

抹掉了好多东西，只剩下了一个最高阶项啊…

那这个东西有什么意义呢？

时间复杂度的意义在于：

当我们要处理的样本量很大很大时，我们会发现低阶项是什么不是最重要的；

每一项的系数是什么，不是最重要的；

真正重要的就是最高阶项是什么！

这就是时间复杂度的意义：

它是衡量算法流程的复杂程度的一种指标，该指标只与数据量有关，与过程之外的优化无关

这就相当于解决问题的流程设计有了一种宏观上的评价尺度，而不会在微小问题里迷失

常见的时间复杂度

排名从好到差：

O(1)、O(logN)、O(N)、O(N*logN)   

O(N^2)、O(N^3)、O(N^K)

O(2^N)、O(3^N)、O(K^N)

O(N!)

评价算法的核心指标

1) 时间复杂度（算法流程决定）

2) 额外空间复杂度（算法流程决定）

3）常数项时间（实现细节决定）

额外空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。

作为输入参数的空间，不算额外空间。

作为输出结果的空间，也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算。

但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。

如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

算法流程的常数项

我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的。

难道同样时间复杂度的流程，在实际运行时候就一样的好吗？

当然不是。

时间复杂度只是一个很宏观的指标。

如果两个时间复杂度一样的算法，

你还要去在具体的运行时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。

算法流程的常数项的比拼方式

放弃理论分析，生成随机数据直接测。实测！

为什么不去理论分析？

不是不能纯分析，而是没必要。

因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。

比如：

位运算的常数时间小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址。

所以如果纯理论分析，往往会需要非常多的分析过程。

都已经到了具体细节的程度，莫不如交给实验数据好了。

何为最优解？

1）在时间复杂度的指标上，一定要尽可能的低

2）满足了时间复杂度最低这个指标之后，使用最少的空间

叫问题的最优解

一般说起最优解都是忽略掉常数项这个因素的，

因为这个因素只决定了实现层次的优化和考虑，

而和怎么解决整个问题的思想无关。

第2节 前缀和、二分、异或运算

前缀和数组

假设有一个数组arr，

用户总是频繁的查询arr中范围的累加和

你如何组织数据，

能让这种查询变得每次都特别快捷？

package main

import "log"

func main() {
	arr := []int{2, 3, 1, 5, -2}
	log.Print(arr)
	sum := preSumArray(arr)

	l := 1
	r := 3
	log.Print("数组范围[", l, "...", r, "]上累加和:", getSum(sum, l, r))

	l = 0
	r = 2
	log.Print("数组范围[", l, "...", r, "]上累加和:", getSum(sum, l, r))

	l = 0
	r = 3
	log.Print("数组范围[", l, "...", r, "]上累加和:", getSum(sum, l, r))

	l = 0
	r = 4
	log.Print("数组范围[", l, "...", r, "]上累加和:", getSum(sum, l, r))
}

func preSumArray(arr []int) []int {
	n := len(arr)
	sum := make([]int, n)
	// 0 ~ 0
	sum[0] = arr[0]
	for i := 1; i < n; i++ {
		// 0 ~ i范围上的前缀和, sum[i]
		// 0 ~ i-1范围上的前缀和 + arr[i] -> 0 ~ i范围上的前缀和
		sum[i] = sum[i-1] + arr[i]
	}
	return sum
}

// 原始数组arr[l..r]范围上的累加和返回
// 其实是利用前缀和数组sum加工得到！
func getSum(sum []int, l int, r int) int {
	// arr[l...r]范围上的累加和
	// arr[0..3] sum[3]
	if l == 0 {
		return sum[r]
	} else {
		// l != 0
		// arr[3..10]范围上的累加和
		// 0...10 - 0...2
		// sum[10] - sum[2]
		return sum[r] - sum[l-1]
	}
}

PS D:\Workspace\Go\src\projects\demo> go run main.go
2023/06/12 22:40:49 [2 3 1 5 -2]
2023/06/12 22:40:49 数组范围[1...3]上累加和:9
2023/06/12 22:40:49 数组范围[0...2]上累加和:6
2023/06/12 22:40:49 数组范围[0...3]上累加和:11
2023/06/12 22:40:49 数组范围[0...4]上累加和:9

二分常见问题

有序数组中找到num

有序数组中找到>=num最左的位置

有序数组中找到<=num最右的位置

时间复杂度为log N，这是什么意思呢？

认识异或运算

异或运算：相同为0，不同为1

同或运算：相同以1，不同为0

能长时间记住的概率接近0%

所以，异或运算就记成无进位相加！

认识异或运算

异或运算的性质

1. 0^N == N      N^N == 0

2. 异或运算满足交换律和结合率，同一批数字，不管以什么顺序异或，结果不变

上面的两个性质用无进位相加来理解就非常的容易

认识异或运算

如何不用额外变量交换两个数 

怎么把一个int类型的数，提取出最右侧的1来

认识异或运算

一个数组中有一种数出现了奇数次，

其他数都出现了偶数次，

怎么找到并打印这种数 

认识异或运算

一个数组中有两种数出现了奇数次，

其他数都出现了偶数次，

怎么找到并打印这两种数 

第3节 哈希表、有序表、对数器、比较器

哈希表

1) 哈希表在使用层面上可以理解为一种集合结构

2) 如果只有key，没有伴随数据value，可以使用hashset结构

3) 如果既有key，又有伴随数据value，可以使用hashmap结构

4) 有无伴随数据，是hashmap和hashset唯一的区别，实际结构是一回事 

5) 使用哈希表增、删、改、查的操作，可以认为时间复杂度为 O(1)，但是常数时间比较大

下面我们演示

使用哈希表解决一个题目

题目：

给定一个数组 nums 和一个目标值 k，

找到累加和等于 k 的最长连续子数组长度。

如果不存在任意一个符合要求的子数组，则返回 0。

解法：

利用哈希表建立前缀和记录

key : 某个前缀和

value : 这个前缀和最早出现的位置

(0…j)(j+1……..i)

i

有序表

1) 有序表在使用层面上可以理解为一种集合结构

2) 如果只有key，没有伴随数据value，可以使用treeset结构

3) 如果既有key，又有伴随数据value，可以使用treemap结构

4) 有无伴随数据，是treeset和treemap唯一的区别，底层的实际结构是一回事

5) 有序表把key按照顺序组织起来，而哈希表完全不组织

6) 目前go的库里没有现成可供使用的有序表，我找了一个很好的实现，给大家演示

7) 在课上的有序表底层是红黑树实现的，但是可以实现有序表的结构很多

8) 红黑树、avl树、sb树和跳表，等都属于有序表结构，只是底层具体实现不同

9) 不管是什么底层具体实现，只要是有序表，增、删、改、查都是log N的复杂度

哈希表和有序表

哈希表在使用时，增删改查时间复杂度都是O(1)

有序表在使用时，比哈希表功能多，时间复杂度都是O(logN)

对数器

你在网上找到了某个公司的面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..

你和朋友交流面试题，你想了好久，感觉自己会做，但是你找不到在线测试，你好心烦..

你在网上做笔试，但是前几个测试用例都过了，突然一个巨大无比数据量来了，结果你的代码报错了，如此大的数据量根本看不出哪错了，你好心烦…

对数器

1，你想要测的方法g

2，实现复杂度不好但是容易实现的方法f

3，实现一个随机样本产生器（长度，值，都随机）

4，把方法a和方法b跑相同的随机样本，看看得到的结果是否一样

5，如果有一个随机样本使得比对结果不一致，打印出错的样本，

6，因为你可以控制出错样本的长度，所以可以找一个容易debug的例子出来

7，进行人工干预，改对方法g和方法f

8，当样本数量很多时比对测试依然正确，可以确定方法g已经正确。 

我们来演示一下

对数器

对数器非常重要

1）自己验证程序正确性的重要技巧

2）验证贪心策略的重要手段

3）coding练习中，debug提高的利器

4）面试过程中，不至于茫然的途径

一定要掌握！

比较器

1）可以定制排序方法的排序策略

2）可以定制有序结构的组织策略

我们来演示一下

第4节 递归、Master公式、归并排序、小和问题

递归

• 怎么从思想上理解递归

• 大事化小的思想，但是大和小问题拥有同样的结构

• 怎么从实际实现的角度出发理解递归

• 系统栈

递归最简单的例子

求数组arr[L..R]中的最大值，怎么用递归方法实现。

1）将[L..R]范围分成左右两半。左：[L..Mid]  右[Mid+1..R]

2）左部分求最大值，右部分求最大值

3） [L..R]范围上的最大值，是max{左部分最大值，右部分最大值}

注意：2）是个递归过程，当范围上只有一个数，就可以不用再递归了

新手需要常常画递归决策图

对于新手来说，把调用的过程画出结构图是必须的，这有利于分析递归

递归并不是玄学，递归底层是利用系统栈来实现的

任何递归函数都一定可以改成非递归

Master公式

形如

T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数)

的递归函数，可以直接通过Master公式来确定时间复杂度

如果 log(b,a) < d，复杂度为O(N^d)

如果 log(b,a) > d，复杂度为O(N^log(b,a))

如果 log(b,a) == d，复杂度为O(N^d  * logN)

Master公式只能用在子过程都是等规模的递归问题，并且都按比例减小

子过程不是等规模的递归问题，分析起来比较复杂，这里不做阐述

归并排序

1）整体是递归，左边排好序+右边排好序+merge让整体有序

2）让其整体有序的过程里用了排外序方法

3）利用master公式来求解时间复杂度

4）当然可以用非递归实现

归并排序复杂度

T(N) = 2*T(N/2) + O(N^1)

根据master可知时间复杂度为O(N*logN)

merge过程需要辅助数组，所以额外空间复杂度为O(N)

归并排序的实质是把比较行为变成了有序信息并传递，比O(N^2)的排序快

小和问题

在一个数组中，一个数左边比它小的数的总和，叫数的小和，

所有数的小和累加起来，叫数组小和，返回数组小和。

例子： [ 1, 3, 4, 2, 5 ] 

1左边比1小的数：没有 -> 0

3左边比3小的数：1 -> 1

4左边比4小的数：1、3 -> 4

2左边比2小的数：1 -> 1

5左边比5小的数：1、3、4、 2 -> 10

所以数组小和 = 1+1+3+1+1+3+4+2 = 16 

第5节 partition过程、快速排序、寻找第K大的数

partition过程(经典)

• 给定一个数组arr和一个整数num

• 小于等于num的数放在数组的左边

• 大于num的数放在数组的右边

  要求额外空间复杂度O(1)，时间复杂度O(N)

荷兰国旗问题

• 给定一个数组arr，和一个整数num，请把：

• 小于num的数放在数组的左边

• 等于num的数放在数组的中间

• 大于num的数放在数组的右边

  要求额外空间复杂度O(1)，时间复杂度O(N) 

快速排序

在arr[L..R]范围上，进行快速排序的过程：

1）如果L…R范围上只有一个数字，返回

2）随机选一个位置，把这个位置的数字和R位置的数字做交换

3）用arr[R]做划分值，对该范围做partition

<= arr[R]的数在左部分，保证左部分，最后一个位置的数，一定是划分值。它固定了！

>arr[R]的数在右部分

4）分别对固定位置的左边、和右部分，重复上面的过程

快速排序(改进)

当arr中有大量重复出现的数字，可以做如下改进：

在arr[L..R]范围上，进行快速排序的过程：

1）如果L…R范围上只有一个数字，返回

2）随机选一个位置，把这个位置的数字和R位置的数字做交换

3）用arr[R]做划分值，对该范围做荷兰国旗划分

<arr[R]的数在左部分，

==arr[R]的数在中间，这部分不用再移动了，排好序的话这些数一定在这些位置

>arr[R]的数在右部分

4）分别左部分和右部分，重复上面的过程

快速排序 复杂度

时间复杂度O(N * logN)

额外空间复杂度O(logN)

怎么来的？

直接记住！

和快速排序过程有关的题目

给你一个整数数组 nums 和一个正数 k

请你返回第k大的数

排序了之后，第k大的数。排序：O（N*logN）

要求：时间复杂度O（N）

注意：

借用了快排的过程，

但是和快排有明显区别，时间复杂度O(N)

依然直接记住！

第6节 堆结构、堆排序、堆相关的题目

堆结构

1）堆结构就是用数组实现的完全二叉树结构

2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

4）堆结构的heapInsert与heapify操作

5）堆结构的增大和减少 （heapSize++、heapSize- -）

6）优先级队列结构，就是堆结构 

各种操作都是O(logN)

堆排序

1，先让整个数组都变成大根堆结构，建立堆的过程

2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，

再去调整堆，一直周而复始，时间复杂度为O(N*logN) 

3，堆的大小减小成0之后，排序完成 

时间复杂度O(N * logN)

堆相关题目

给你一个整数数组 nums 和一个整数 k ，

请你返回其中出现频率前 k 高的元素（唯一）。

你可以按 任意顺序 返回答案。

介绍一下Golang库中怎么方便的使用堆

第7节 链表、栈、队列

单链表定义和翻转

type ListNode struct {
   Val  int
   Next *ListNode
}

双链表定义和翻转

type ListNode struct {
    Val  int
    Next *ListNode
    Last *ListNode
}

完成翻转操作

完成翻转操作

栈

先进后出

用数组实现栈

用链表实现栈

队列

先进先出

用数组实现队列

用链表实现队列

队列面试题

用环形数组实现队列（面试题）

双端队列

头、尾都可以进出

用链表实现双端队列

含有getMin功能的栈

完成栈常规的操作

加上：得到栈中最小值的功能

要求所有操作，时间复杂度都是O(1)

第8节 链表相关的经典题目

题目1

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

https://leetcode.cn/problems/add-two-numbers

题目2

编写一个函数，检查输入的链表是否是回文的。

https://leetcode.cn/problems/palindrome-linked-list-lcci/

题目3

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

https://leetcode.cn/problems/merge-k-sorted-lists/

题目4

给你两个单链表的头节点 headA 和 headB ，

请你找出并返回两个单链表相交的起始节点。

如果两个链表不存在相交节点，返回 null 。

https://leetcode.cn/problems/intersection-of-two-linked-lists/

题目5

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。

如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

https://leetcode.cn/problems/linked-list-cycle-ii/

题目6

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

https://leetcode.cn/problems/reverse-nodes-in-k-group/

第9节 常见的暴力递归

暴力递归

暴力递归就是尝试 

1，把问题转化为规模缩小了的同类问题的子问题

2，有明确的不需要继续进行递归的条件(base case)

3，有当得到了子问题的结果之后的决策过程

4，不记录每一个子问题的解

熟悉什么叫尝试

题目1

给定一个不含重复数字的数组

请返回所有的子集

题目2

给定一个不含重复数字的数组

请返回所有的排列

题目3

打印n层汉诺塔问题的所有运动轨迹

题目4

给你一个栈，请你逆序这个栈，

不能申请额外的数据结构，

只能使用递归函数。 如何实现? 

题目5

栈只提供push、pop、isEmpty三个方法

请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大

只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数

除此之外不能使用任何的容器，任何容器都不许，连数组也不行

也不能自己定义任何结构体

就是只用：

1) 栈提供的push、pop、isEmpty三个方法

2) 简单返回值的递归函数

题目6

给定一个正整数N，

表示有N份青草统一堆放在仓库里，

有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草

不管是牛还是羊，每一轮能吃的草量必须是：1，4，16，64…(4的某次方)

谁最先把草吃完，谁获胜，

假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定。

根据唯一的参数N，返回谁会赢

第10节 二叉树结构与常见题目（上）

二叉树结构描述

type TreeNode struct {
   Val   int
   Left  *TreeNode
   Right *TreeNode
}

二叉树的先序、中序、后序遍历

先序：任何子树的处理顺序都是，先头节点、再左子树、然后右子树

中序：任何子树的处理顺序都是，先左子树、再头节点、然后右子树

后序：任何子树的处理顺序都是，先左子树、再右子树、然后头节点

题目1

二叉树三种遍历的实现

题目2

判断二叉树是不是搜索二叉树

题目3

二叉树的宽度遍历（按层遍历）

题目4

判断二叉树是不是完全二叉树

题目5

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。

判断该树中是否存在 根节点到叶子节点 的路径，

这条路径上所有节点值相加等于目标和 targetSum 。

如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

题目6

二叉树的按先序方式序列化和反序列化

题目7

二叉树的按层序列化和反序列化

第11节 二叉树结构与常见题目（下）

二叉树的递归套路

1）假设以X节点为头，假设可以向X左树和X右树要任何信息

2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）

3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息

4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S

5）递归函数都返回S，每一棵子树都这么要求

6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息S

可以解决面试中绝大多数的二叉树问题尤其是树型dp问题

本质是利用递归遍历二叉树的便利性

题目1

返回二叉树的最大深度

题目2

判断二叉树是否是平衡二叉树

题目3

小偷又发现了一个新的可行窃的地区。

这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。

一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。

如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

https://leetcode.cn/problems/house-robber-iii

题目4

给定一棵二叉树，你需要计算它的直径长度。

一棵二叉树的直径长度是任意两个结点路径长度中的最大值。

这条路径可能穿过也可能不穿过根结点。

https://leetcode.cn/problems/diameter-of-binary-tree/

题目5

已知一棵完全二叉树

求完全二叉树的节点个数

要求时间复杂度小于O(N)

可以达到O((logN) ^ 2)

题目6

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，

并返回该子树的大小。其中，最大指的是子树节点数最多的。

二叉搜索树（BST）中的所有节点都具备以下属性：

左子树的值小于其父（根）节点的值。

右子树的值大于其父（根）节点的值。

注意：子树必须包含其所有后代。

https://leetcode.cn/problems/largest-bst-subtree

第12节 前缀树实现及其相关题目

前缀树（trie）

1）单个字符串中，字符从前到后的加到一棵多叉树上

2）字符放在路上，节点上有专属的数据项（常见的是pass和end值）

3）所有样本都这样添加，如果没有路就新建，如有路就复用

4）沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1

可以完成前缀相关的查询

前缀树路的实现方式

1）路用固定数组实现

2）路用哈希表实现

https://leetcode.cn/problems/implement-trie-ii-prefix-tree/

前缀树删除

1）先查询s是否在前缀树里

2）沿途pass-1，最后节点end-1

3）如果某个节点的下一个节点pass已经为0，要把下一个节点和整棵树断连

题目1

在英语中，有一个叫做 词根(root) 的概念，

它可以跟着其他一些词组成另一个较长的单词

我们称这个词为 继承词(successor)。

例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

需要输出替换之后的句子。

https://leetcode.cn/problems/UhWRSj

题目2

给你一个非负数组 nums ，

返回 nums[i] 异或 nums[j] 的最大运算结果，

其中 0 ≤ i ≤ j < n 。

输入：nums = [3,10,5,25,2,8]

输出：28

解释：最大运算结果是 5 异或 25 = 28.

https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array

第13节 并查集详解及其相关题目

并查集(UnionFind)

• 1）有若干个样本a、b、c、d…在并查集中一开始认为每个样本都在单独的集合里

• 2）用户可以在任何时候调用如下两个方法：

       boolean isSameSet(x, y) : 查询样本x和样本y是否属于一个集合

       void union(x, y) : 把x和y各自所在集合的所有样本合并成一个大集合

3） isSameSet和union方法的时间复杂度越低越好

并查集(UnionFind)

1）每个节点都有一条往上指的指针

2）节点a往上找到的头节点，叫做a所在集合的代表节点

3）查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个

4）把x和y各自所在集合的所有点合并成一个大集合：

只需要小集合的代表点挂在大集合的代表点的下方即可

并查集(UnionFind) 重要优化

1）节点往上找代表点的过程，把沿途的链变成扁平的

2）小集合挂在大集合的下面

如果方法调用很频繁，那么单次调用的代价为O(1)，两个方法都如此

证明不需要管！因为非常难，发明这个结构的人：Bernard A. Galler、Michael J. Fischer

用了25年时间证明1964~1989

结构如此简单，证明如此复杂，只需要记住结论

题目1

并查集实现代码讲解

题目2

有 n 个城市，其中一些彼此相连，另一些没有相连。

如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，

那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，

其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，

而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

链接：https://leetcode.cn/problems/number-of-provinces

题目3

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

链接：https://leetcode.cn/problems/number-of-islands

递归解法

并查集解法

题目4

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。

你可以从一个平台游向四周相邻的任意一个平台，

但是前提是此时水位必须同时淹没这两个平台。

假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。

当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。

返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间 。

链接：https://leetcode.cn/problems/swim-in-rising-water

题目5

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ，

其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。

https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column

第14节 常见贪心算法与实战技巧

贪心算法

1）最自然智慧的算法

2）用一种局部最功利的标准，总是做出在当前看来是最好的选择

3）难点在于证明局部最功利的标准可以得到全局最优解

4）对于贪心算法的学习主要以增加阅历和经验为主

贪心算法实战技巧

1）实现一个不依靠贪心策略的解法X，可以用最暴力的尝试

2）脑补出贪心策略A、贪心策略B、贪心策略C...

3）用解法X和对数器，用实验的方式得知哪个贪心策略正确 

4）不要去纠结贪心策略的证明 

题目1

arr是一个可能包含重复元素的整数数组，

我们将这个数组分割成几个“块”，

并将这些块分别进行排序。

之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

https://leetcode.cn/problems/max-chunks-to-make-sorted-ii

题目2

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，

其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，

并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

https://leetcode.cn/problems/course-schedule-iii

题目3

一个整数区间 [a, b]  ( a < b ) 代表着从 a 到 b 的所有连续整数，包括 a 和 b。

给你一组整数区间intervals，

请找到一个最小的集合 S，

使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。

输出这个最小集合S的大小。

https://leetcode.cn/problems/set-intersection-size-at-least-two

题目4

森林中有未知数量的兔子。

提问其中若干只兔子 "还有多少只兔子与你（指被提问的兔子）颜色相同?" ，

将答案收集到一个整数数组 answers 中，其中 answers[i] 是第 i 只兔子的回答。

给你数组 answers ，返回森林中兔子的最少数量。

https://leetcode.cn/problems/rabbits-in-forest

题目5

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，

力扣 希望在 IPO 之前开展一些项目以增加其资本。

由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。

帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，

和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，

且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，

以 最大化最终资本 ，并输出最终可获得的最多资本。

链接：https://leetcode.cn/problems/ipo

题目6

你有一些长度为正整数的棍子。

这些长度以数组 sticks 的形式给出， sticks[i] 是 第i个 木棍的长度。

你可以通过支付 x + y 的成本将任意两个长度为 x 和 y 的棍子连接成一个棍子。

你必须连接所有的棍子，直到剩下一个棍子。

返回以这种方式将所有给定的棍子连接成一个棍子的 最小成本 。

https://leetcode.cn/problems/minimum-cost-to-connect-sticks

题目7

给定一组非负整数 nums，

重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

https://leetcode.cn/problems/largest-number

第15节 图及其常见算法

图的概念和表达

概念：

1）由点的集合和边的集合构成

2）虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达

3）边上可能带有权值

表达：

1) 邻接矩阵

2) 邻接表

更多时候采用的是邻接表

既可以表示有向图、也可以表示无向图(一种特殊的有向图)

有无权值对于图的表达来说并不是特别重要，简单改写即可

题目1

建图的方式

给你点的数量n，所有点的编号都在0~n-1

给你所有的边，请建立好图

1）不带权值的情况

2）带权值的情况

图的宽度优先遍历

宽度优先遍历

1，利用队列实现

2，从源节点开始依次按照宽度进队列，然后依次弹出

3，每弹出一个点，把该节点所有，没有进过队列的邻接点，放入队列

4，直到队列变空

图的深度优先遍历

深度优先遍历

1，常常利用递归实现

2，来到当前节点，如果已经访问，就返回；如果没有访问，就标记为已访问

3，继续去当前节点的邻接表里，访问每个邻接点

4，直到能找到的所有节点都已经访问

题目2

有一个具有 n个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）

图中的边用一个二维整数数组 edges 表示，

其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。

每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 start 开始，到顶点 end 结束的 有效路径 。

给你数组 edges 和整数 n、start和end，

如果从 start 到 end 存在 有效路径 ，则返回 true，否则返回 false 。

https://leetcode.cn/problems/find-if-path-exists-in-graph/

图的拓扑排序

1）在图中找到所有入度为0的点输出

2）把所有入度为0的点在图中删掉，同时消掉边的影响

3）继续找入度为0的点输出，周而复始

4）图的所有点都被删除后，依次输出的顺序就是拓扑排序

要求：有向图且其中没有环

应用：事件安排、编译顺序、检查环

题目3

现在你总共有 n 门课需要选，编号为 0 到 n - 1。

给你一个数组 prerequisites ，

其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 1 ，你需要先完成课程 0 ，我们用一个匹配来表示：[1,0] 。

返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回 任意一种 就可以了。

如果不可能完成所有课程，返回 一个空数组 。

最小生成树算法之Kruskal

1）总是从权值最小的边开始考虑，依次考察权值依次变大的边

2）当前的边要么进入最小生成树的集合，要么丢弃

3）如果当前的边进入最小生成树的集合中不会形成环，就要当前边

4）如果当前的边进入最小生成树的集合中会形成环，就不要当前边

5）考察完所有边之后，最小生成树的集合也得到了

最小生成树算法之Prim

1）可以从任意节点出发来寻找最小生成树

2）某个点加入到被选取的点中后，解锁这个点出发的所有新的边

3）在所有解锁的边中选最小的边，然后看看这个边会不会形成环

4）如果会，不要当前边，继续考察剩下解锁的边中最小的边，重复3）

5）如果不会，要当前边，将该边的指向点加入到被选取的点中，重复2）

6）当所有点都被选取，最小生成树就得到了

题目4

想象一下你是个城市基建规划者，地图上有 n 座城市，它们按以 1 到 n 的次序编号。

给你整数 n 和一个数组 conections，

其中 connections[i] = [xi, yi, costi] 

表示将城市 xi 和城市 yi 连接所要的costi（连接是双向的）。

返回连接所有城市的最低成本，每对城市之间至少有一条路径。

如果无法连接所有 n 个城市，返回 -1

该 最小成本 应该是所用全部连接成本的总和。

单源最短路径：Dijkstra算法

1）Dijkstra算法必须指定一个源点s，且所有边权值没有负数

2）生成一个s到各个点的最小距离表map，把(s, 0)记录放入小根堆

3）从小根堆里弹出记录（y，w），表示当前从s到y，最小距离是w

4）如果y是之前算过的点，重复步骤3）；

5）如果y是之前没算过的点，记录map[y] = w；

y的邻接点假设为{a,b,c}，

如果a没最小距离的记录，把(a, w + y到a的代价)放入小根堆；否则跳过

如果b没最小距离的记录，把(b, w + y到b的代价)放入小根堆；否则跳过

如果c没最小距离的记录，把(c, w + y到c的代价)放入小根堆；否则跳过

总之，y的所有邻接点，全按照上面处理后，重复步骤3）

6）小根堆空了，过程停止

题目5

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，

其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。

需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

第16节 窗口最值更新结构和单调栈

滑动窗口

滑动窗口是一种想象出来的数据结构：

1）滑动窗口有左边界L和有边界R

2）在数组或者字符串或者一个序列上，记为S，窗口就是S[L..R]这一部分

3）L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口

4）L和R都只能往右滑

滑动内最大值或最小值的更新结构

窗口不管L还是R滑动之后，都会让窗口呈现新状况，

如何能够更快的得到窗口当前状况下的最大值和最小值？

最好平均下来复杂度能做到O(1)

利用单调双端队列！

题目1

假设一个固定大小为W的窗口，依次划过arr，

返回每一次滑出状况的最大值

例如，arr = [4,3,5,4,3,3,6,7], W = 3

返回：[5,5,5,4,6,7]

题目2

给定一个整型数组arr，和一个整数limit

某个arr中的子数组sub，如果想达标，必须满足：

sub中最大值 – sub中最小值 <= limit，

返回arr中达标子数组的数量

单调栈

一种特别设计的栈结构，为了解决如下的问题：

给定一个可能含有重复值的数组arr，求每一个i位置的数：

arr[i]的左侧离i最近并且小于arr[i]的数在哪？

怎么能让得到信息的过程尽量快，那么到底怎么设计呢？

题目3

给定一个只包含正数的数组arr，arr中任何一个子数组sub，

一定都可以算出(sub累加和 )* (sub中的最小值)是什么，子数组的指标！

那么所有子数组中，这个指标最大是多少？

题目4

给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]

这样的坡的宽度为 j - i。

找出 A 中的坡的最大宽度，如果不存在，返回 0

第17节 差分、首尾双指针、LRU、LIS

差分结构及其题目

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi]

意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数

链接：https://leetcode.cn/problems/corporate-flight-bookings

首尾双指针技巧及其题目1

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，

每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

链接：https://leetcode.cn/problems/boats-to-save-people

首尾双指针技巧及其题目2

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，

在这种情况下，可以接 6 个单位的雨水

链接：https://leetcode.cn/problems/trapping-rain-water

LRU内存替换结构

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；

如果不存在，则向缓存中插入该组 key-value 。

如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

链接：https://leetcode.cn/problems/lru-cache

最长递增子序列的长度

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

链接：https://leetcode.cn/problems/longest-increasing-subsequence

第18节 从暴力递归到动态规划（上）

暴力递归和动态规划的关系

某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划

任何动态规划问题，都一定对应着某一个有重复过程的暴力递归

暴力递归到动态规划的套路

1） 写出一个可变参数都是简单类型的暴力尝试

2）找到哪些参数的变化会影响返回值，对每一个列出变化范围

3）参数间的所有的组合数量，意味着表大小

4）记忆化搜索的方法就是傻缓存，非常容易得到

5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解

题目1

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。

如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

链接：https://leetcode.cn/problems/coin-change-2

题目2

给定一个包含非负整数的 m x n 网格 grid ，

请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

链接：https://leetcode.cn/problems/minimum-path-sum

题目3

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；

每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。

每回合，玩家从行的 开始 或 结束 处取走整堆石头。

这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，

当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

链接：https://leetcode.cn/problems/stone-game

题目4

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，

这些数字存在数组 nums 中。

现在要求你戳破所有的气球。

戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 

这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。

如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

链接：https://leetcode.cn/problems/burst-balloons

题目5

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。

如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：

它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（

也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

链接：https://leetcode.cn/problems/longest-common-subsequence

第19节 从暴力递归到动态规划（下）

经典动态规划问题

上一节我们学了从暴力递归到动态规划

本节课我们来学几道动态规划经典题目

这些题目依然可以从暴力递归改过来

不过因为太过经典，所以我们直接讲述经典实现

题目1

子数组最大累加和问题

https://leetcode.cn/problems/maximum-subarray/

题目2

数组中不能选择相邻数字的子序列最大累加和问题

https://leetcode.cn/problems/house-robber/

题目3

最长无重复子串问题

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

题目4

编辑距离问题

https://leetcode.cn/problems/edit-distance/

题目5

全是1的最大正方形问题

https://leetcode.cn/problems/maximal-square/

第20节 用二分答案的思路解题

二分答案法

发现了答案本身和问题之间的单调性关系

就可以根据答案的范围逐渐二分得到最佳的答案

题目1

完成旅途的最少时间

https://leetcode.cn/problems/minimum-time-to-complete-trips/

题目2

爱吃香蕉的珂珂

https://leetcode.cn/problems/koko-eating-bananas/

题目3

分割数组的最大值尽量小

https://leetcode.cn/problems/split-array-largest-sum/

Go程序员面试算法宝典

1.1 如何实现链表的逆序

• 题目描述：
  给定一个带头结点的单链表，请将其逆序。
  例如，原来为head->1->2->3->4->5->6->7，逆序后为head->7->6->5->4->3->2->1。

// 链表定义
type LNode struct {
    Data interface{}
    Next *LNode
}

// 创建链表
func CreateNode(node *LNode, max int) {
    cur := node
    for i := 1; i < max; i++ {
        cur.Next = &LNode{}
        cur.Next.Data = i
        cur = cur.Next
    }
}

// 打印链表的方法
func PrintNode(info string, node *LNode) {
    fmt.Print(info)
    for cur := node.Next;cur != nil; cur = cur.Next {
        fmt.Print(cur.Data, " ")
    }
    fmt.Println()
}

分析与解答：由于单链表与数组不同，单链表中每个结点的地址都存储在其前驱结点的指针域中，因此，对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。在对链表的操作过程中，需要特别注意在修改结点指针域的时候，记录下后继结点的地址，否则会丢失后继结点。方法一：就地逆序主要思路为：在遍历链表的时候，修改当前结点指针域的指向，让其指向它的前驱结点。为此需要用一个指针变量来保存前驱结点的地址。此外，为了在调整当前结点指针域的指向后还能找到后继结点，还需要另外一个指针变量来保存后继结点的地址，在所有的结点都被保存好以后就可以直接完成指针的逆序了。除此之外，还需要特别注意对链表首尾结点的特殊处理。具体实现方式如下图所示。

在上图中，假设当前已经遍历到cur结点，由于它所有的前驱结点都已经完成了逆序操作，因此，只需要使cur.next=pre即可完成逆序操作，在此之前为了能够记录当前结点的后继结点的地址，需要用一个额外的指针next来保存后继结点的信息，通过上图（1）～（4）四步把实线的指针调整为虚线的指针就可以完成当前结点的逆序；当前结点完成逆序后，通过向后移动指针来对后续的结点用同样的方法进行逆序操作。 

方法一：就地逆序

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

// 带头结点的逆序
func Reverse(head *LNode) { // 传入参数head头结点
	// 如果链表不存在或者链表为空(只有一个头结点)，直接返回
	// head == nil || head.Next == nil
	// node = head 头结点
	if head == nil || head.Next == nil {
		return
	}
	var pre *LNode // 定义前驱结点，默认值为nil
	var cur *LNode // 定义当前结点，默认值为nil
	// next指针(头结点的Next指针变量)
	next := head.Next
	// for循环next，直到next走到链表最后一个结点
    // next是当前遍历的结点
	for next != nil {
		// 先保存next的后继结点信息
		cur = next.Next
		// 再修改next指针域的指向，进行逆序操作
		next.Next = pre
		// 旧的next成了新的前驱结点
		pre = next
		// 旧的cur成了新的next，用于继续执行
		next = cur
	}
	// 头指针指向pre
	head.Next = pre
}

func main() {
	//声明头结点
	head := &LNode{}
	fmt.Println("就地逆序")
	CreateNode(head, 8)
	PrintNode("逆序前：", head)
	Reverse(head)
	PrintNode("逆序后：", head)
}

这个代码里next和cur是不是写反了

// 带头结点的逆序
func Reverse(head *LNode) { // 传入参数head头结点
	// 如果链表不存在或者链表为空(只有一个头结点)，直接返回
	// head == nil || head.Next == nil
	// node = head 头结点
	if head == nil || head.Next == nil {
		return
	}
	var pre *LNode  // 定义前驱结点，默认值为nil
	var next *LNode // 定义后继结点，默认值为nil
	// 当前结点从1开始(头结点的Next指针变量)
	cur := head.Next
	for cur != nil {
		// 先保存cur的后继结点信息
		next = cur.Next
		// 再修改cur指针域的指向，进行逆序操作
		cur.Next = pre
		// 旧的cur成了新的前驱结点
		pre = cur
		// 旧的next成了新的cur，用于继续执行
		cur = next
	}
	// 头指针指向pre
	head.Next = pre
}

• 程序的运行结果为

方法二：递归法

要逆序 1->2->3->4->5->6->7 ，则要先逆 2->3->4->5->6->7 ，
要逆序 2->3->4->5->6->7 ，则要先逆 3->4->5->6->7 ，
要逆序 3->4->5->6->7，则要先逆 4->5->6->7 ，
要逆序 4->5->6->7 ，则要先逆 5->6->7 ，
要逆序 5->6->7 ，则要先逆 6->7 ，
……

func RecursiveReverseChild(node *LNode) *LNode {
	if node == nil || node.Next == nil {
		return node
	}
	newHead := RecursiveReverseChild(node.Next)
	node.Next.Next = node
	node.Next = nil
	return newHead
}

// 带头结点的逆序
func RecursiveReverse(node *LNode) { // 传入参数head头结点
	// 先逆序除第一个结点以外的子链表
	firstNode := node.Next
	// 递归调用
	// 逆序子链表
	newHead := RecursiveReverseChild(firstNode)
	node.Next = newHead
}

• 算法性能
  时间复杂度：O(n)，因为需要对链表进行一次遍历，n为链表长度。
  优点：思路比较直观，容易理解，不需要保存前驱结点的地址；
  缺点：算法实现难度较大，且由于递归需要不断调用自己，需要额外的压栈与弹栈操作，因此相比方法一性能有所下降。

方法三：插入法

func InsertReverse(node *LNode) {
	if node == nil || node.Next == nil {
		return
	}
	var cur *LNode  // 当前结点
	var next *LNode // 后继结点
	// 从结点2开始
	cur = node.Next.Next
	node.Next.Next = nil // 设置链表第一个结点为尾结点

	// 把遍历到的结点插入到头结点的后面
	for cur != nil {
		next = cur.Next
		cur.Next = node.Next
		// 插入到头结点的后面
		node.Next = cur
		cur = next
	}
}

首先要创建不带头结点的单链表

package main

import (
	"fmt"
	// . "github.com/isdamir/gotype" // 引入定义的数据结构
)

// LNode 链表定义
type LNode struct {
	Data interface{}
	Next *LNode
}

// CreateNode 创建不带头结点的单链表
func CreateNode(node *LNode, max int) {
	cur := node
	cur.Data = 1
	for i := 2; i < max; i++ {
		cur.Next = &LNode{}
		cur.Next.Data = i
		// fmt.Println("cur:", cur)
		cur = cur.Next
	}
}

// PrintNode 打印不带头结点的单链表
func PrintNode(node *LNode) {
	for cur := node; cur != nil; cur = cur.Next {
		// fmt.Print(cur.Data, "")
		fmt.Println("cur_node", cur)
	}
	fmt.Println()
}

func main() {
	head := &LNode{}
	CreateNode(head, 8)
	PrintNode(head)

}

运行结果：创建的不带头结点的单链表

cur_node &{1 0xc000004090}
cur_node &{2 0xc0000040a8}
cur_node &{3 0xc0000040c0}
cur_node &{4 0xc0000040d8}
cur_node &{5 0xc0000040f0}
cur_node &{6 0xc000004108}
cur_node &{7 <nil>}

对不带头结点的单链表进行逆序-递归法

package main

import (
	"fmt"
	// . "github.com/isdamir/gotype" // 引入定义的数据结构
)

// LNode 链表定义
type LNode struct {
	Data interface{}
	Next *LNode
}

// CreateNode 创建不带头结点的单链表
func CreateNode(node *LNode, max int) {
	cur := node
	cur.Data = 1
	for i := 2; i < max; i++ {
		cur.Next = &LNode{}
		cur.Next.Data = i
		// fmt.Println("cur:", cur)
		cur = cur.Next
	}
}

// PrintNode 打印不带头结点的单链表
func PrintNode(info string, node *LNode) {
	fmt.Print(info)
	for cur := node; cur != nil; cur = cur.Next {
		fmt.Print(cur.Data, " ")
		// fmt.Println("cur_node", cur)
	}
	fmt.Println()
}

func RecursiveReverseChild(node *LNode) *LNode {
	if node == nil || node.Next == nil {
		return node
	}
	newHead := RecursiveReverseChild(node.Next)
	node.Next.Next = node
	node.Next = nil
	return newHead
}
func main() {
	head := &LNode{}
	CreateNode(head, 8)
	fmt.Println("对不带头结点的单链表进行逆序-递归法")
	PrintNode("逆序前：", head)

	newHead := RecursiveReverseChild(head)
	PrintNode("逆序后：", newHead)
}

（2）从尾到头输出链表。

• 方法一：就地逆序+顺序输出
  首先对链表进行逆序，然后再顺序输出逆序后的链表。
  缺点：改变了链表原来的结构。
• 方法二：逆序+顺序输出
  每当遍历到一个结点时，申请一块新的存储空间来存储这个结点的数据域，同时把新结点插入到新链表的头结点后。
  缺点：需要申请额外的存储空间。
• 方法三：递归输出

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

// RecursivePrint 从尾到头输出链表-递归
func RecursivePrint(node *LNode) {
	if node == nil {
		return
	}
	RecursivePrint(node.Next)
	fmt.Print(node.Data, " ")
}

func main() {
	head := &LNode{}
	CreateNode(head, 8)
	fmt.Println("从尾到头输出链表")
	PrintNode("顺序输出：", head)
	fmt.Println("逆序输出：")
	RecursivePrint(head.Next)

}

1.2 从无序链表中移除重复项

• 题目描述：
  给定一个没有排序的链表，去掉其重复项，并保留原顺序。
  例如，链表 1->3->1->5->5->7，去掉重复项后为 1->3->5->7。

方法一：顺序删除

• 思路
  通过双重循环直接在链表上进行删除操作。
  外层循环用一个指针从第一个结点开始遍历整个链表，
  内层循环用另一个指针遍历其余结点，将与外层循环遍历到的指针所指结点的数据域相同的结点删除。

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func CreateNodeT(node *LNode) {
	CreateNode(node, 7)
	node.Next.Next.Data = 3
	node.Next.Next.Next.Data = 1
	node.Next.Next.Next.Next.Data = 5
	node.Next.Next.Next.Next.Next.Data = 7
}

// RemoveDup 顺序删除
func RemoveDup(head *LNode) {
	if head == nil || head.Next == nil {
		return
	}
	outerCur := head.Next // 用于外层循环，指向链表第一个结点
	var innerCur *LNode   // 用于内层循环遍历outerCur后面的结点
	var innerPre *LNode   // innerCur的前驱结点
	for ; outerCur != nil; outerCur = outerCur.Next {
		for innerCur, innerPre = outerCur.Next, outerCur; innerCur != nil; {
			if outerCur.Data == innerCur.Data {
				innerPre.Next = innerCur.Next
				innerCur = innerCur.Next
			} else {
				innerPre = innerCur
				innerCur = innerCur.Next
			}
		}
	}
}

func main() {
	head := &LNode{}
	fmt.Println("删除重复结点")
	CreateNodeT(head)
	fmt.Println("----顺序删除---")
	PrintNode("删除重复结点前：", head)
	RemoveDup(head)
	PrintNode("删除重复结点后：", head)
	CreateNodeT(head)
}

• 算法性能
  时间复杂度：O(n^2) ，因为采用双重循环对链表进行遍历，n为链表长度。
  空间复杂度：O(1)，使用了常量个额外的指针变量。

方法二：递归法

• 思路
  对于结点cur，首先递归地删除以cur.Next为首的子链表中重复的结点，
  接着从以cur.Next为首的子链表中找出与cur有着相同数据域的结点并删除。

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func CreateNodeT(node *LNode) {
	CreateNode(node, 7)
	node.Next.Next.Data = 3
	node.Next.Next.Next.Data = 1
	node.Next.Next.Next.Next.Data = 5
	node.Next.Next.Next.Next.Next.Data = 7
}

// removeDupRecursionChild 递归法删除重复结点
func removeDupRecursionChild(head *LNode) *LNode {
	if head == nil || head.Next == nil {
		return head
	}
	var pointer *LNode
	cur := head
	// 对以head.Next为首的子链表删除重复的结点
	head.Next = removeDupRecursionChild(head.Next)
	pointer = head.Next
	// 找出以head.Next为首的子链表中与head结点相同的结点并删除
	for pointer != nil {
		if head.Data == pointer.Data {
			cur.Next = pointer.Next
			pointer = cur.Next
		} else {
			pointer = pointer.Next
			cur = cur.Next
		}
	}
	return head
}

func RemoveDupRecursion(head *LNode) {
	if head == nil {
		return
	}
	head.Next = removeDupRecursionChild(head.Next)
}
func main() {
	head := &LNode{}
	fmt.Println("删除重复结点-递归法")
	CreateNodeT(head)

	PrintNode("删除重复结点前：", head)
	RemoveDupRecursion(head)
	PrintNode("删除重复结点后：", head)

}

• 算法性能
  时间复杂度：O(n^2) ，该方法与方法一类似，本质上需要对链表进行双重遍历，n为链表长度。
  由于递归法会增加许多额外的函数调用，因此，理论上该方法效率比方法一低。

方法三：空间换时间
思路
建立一个HashSet， HashSet中的内容为已经遍历过的结点内容，并将其初始化为空；
从头开始遍历链表中的所有结点，存在以下两种可能性：
如果结点内容已经在HashSet中，则删除此结点，继续向后遍历 ；
如果结点内容不在HashSet中，则保留此结点，将此结点内容添加到HashSet中，继续向后遍历。
 

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func CreateNodeT(node *LNode) {
	CreateNode(node, 7)
	node.Next.Next.Data = 3
	node.Next.Next.Next.Data = 1
	node.Next.Next.Next.Next.Data = 5
	node.Next.Next.Next.Next.Next.Data = 7
}

func removeDuplicateNodes(head *LNode) *LNode {
	if head == nil {
		return head
	}
	hashSet := make(map[interface{}]bool)
	cur := head
	for cur.Next != nil {
		if hashSet[cur.Next.Data] {
			// 删除重复结点
			cur.Next = cur.Next.Next
		} else {
			// 记录保存结点
			hashSet[cur.Next.Data] = true
			cur = cur.Next
		}
	}
	return head
}

func main() {
	head := &LNode{}
	fmt.Println("删除重复结点-空间换时间")
	CreateNodeT(head)

	PrintNode("删除重复结点前：", head)
	removeDuplicateNodes(head)
	PrintNode("删除重复结点后：", head)

}

算法性能
时间复杂度：O(n) ，因为采用for循环对链表进行遍历，n为链表长度。
空间复杂度：O(n)，使用了辅助空间hashSet。

引申练习：从有序链表中移除重复项
有序链表：链表中的各个结点按照结点数据域中的数据递增/递减有序连接。

上述介绍的从无序链表中移除重复项的方法，也适用于链表有序的情况，但是以上方法没有充分利用到链表有序这个条件，因此，算法的性能肯定不是最优的。
对于有序链表，由于链表具有有序性，因此，不需要对链表进行两次遍历。（如112334，543321，重复项只会挨在一起）

思路：
用cur指向链表第一个结点，此时需要分为以下两种情况讨论：
如果 cur.Data == cur.Next.Data，那么删除cur.Next结点；
如果 cur.Data != cur.Next.Data，那么cur=cur.Next，继续遍历其余结点。

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func CreateNodeT(node *LNode) {
	CreateNode(node, 7)
	node.Next.Next.Data = 1
	node.Next.Next.Next.Data = 2
	node.Next.Next.Next.Next.Data = 3
	node.Next.Next.Next.Next.Next.Data = 3
	node.Next.Next.Next.Next.Next.Next.Data = 3
}

func RemoveDup(head *LNode) {
	if head == nil {
		return
	}

	cur := head.Next
	for cur.Next != nil {
		if cur.Data == cur.Next.Data {
			// 删除重复结点
			cur.Next = cur.Next.Next
		} else {
			// 继续遍历其余结点
			cur = cur.Next
		}
	}
}

func main() {
	head := &LNode{}
	fmt.Println("删除重复结点-顺序删除")
	CreateNodeT(head)

	PrintNode("删除重复结点前：", head)
	RemoveDup(head)
	PrintNode("删除重复结点后：", head)
}

1.3 计算两个单链表所代表的数之和
题目描述
给定两个单链表，链表的每个结点代表一位数，计算两个数的和。
例如，输入链表（3->1->5）和链表（5->9->2），输出 8->0->8，即513+295=808，注意个位数在链表头。
方法一：整数相加法
思路
分别遍历两个链表，求出两个链表所代表的整数的值，然后把这两个整数进行相加，最后把它们的和用链表的形式表示出来。
优点：计算简单
缺点：当链表所代表的的数很大的时候（超过long int的表示范围），就无法使用该方法了。
方法二：链表相加法
思路
对链表中的结点直接进行相加操作，把相加的和存储到新的链表中对应的结点中，同时还要记录结点相加后的进位。

该方法需要注意的问题：

每组结点相加后需要记录其是否有进位；
如果两个链表的长度不同（长度分别为L1和L2，且L1<L2），当对链表的第L1位计算完成之后，只需要考虑链表L2剩余的结点的值（需要考虑进位）；
对链表所有结点都完成计算后，还需要考虑此时是否还有进位，如果有进位，则需要增加新的结点，此结点的数据域为1。

package main

import (
	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func Add(h1 *LNode, h2 *LNode) *LNode {
	if h1 == nil || h1.Next == nil {
		return h2
	}
	if h2 == nil || h2.Next == nil {
		return h1
	}
	c := 0                 // 记录进位
	sum := 0               // 记录两个结点相加的值
	p1 := h1.Next          // 遍历h1
	p2 := h2.Next          // 遍历h2
	resultHead := &LNode{} // 相加后链表头结点
	p := resultHead        // 指向链表resultHead最后一个结点

	for p1 != nil && p2 != nil {
		p.Next = &LNode{} // 指向新创建的存储相加和的结点
		sum = p1.Data.(int) + p2.Data.(int) + c
		p.Next.Data = sum % 10
		c = sum / 10 // 进位
		p = p.Next
		p1 = p1.Next
		p2 = p2.Next
	}
	// 链表h2比h1长，接下来只需要考虑h2剩余结点的值
	if p1 == nil {
		for p2 != nil {
			p.Next = &LNode{} // 指向新创建的存储相加和的结点
			sum = p2.Data.(int) + c
			p.Next.Data = sum % 10 // 两结点相加和
			c = sum / 10           // 进位
			p = p.Next
			p2 = p2.Next
		}
	}
	// 链表h1比h2长，接下来只需要考虑h1剩余结点的值
	if p2 == nil {
		for p1 != nil {
			p.Next = &LNode{} // 指向新创建的存储相加和的结点
			sum = p1.Data.(int) + c
			p.Next.Data = sum % 10 // 两结点相加和
			c = sum / 10           // 进位
			p = p.Next
			p1 = p1.Next
		}
	}
	if c == 1 {
		p.Next = &LNode{}
		p.Next.Data = 1
	}
	return resultHead
}
func CreateNodeT(l1 *LNode, l2 *LNode) {
	cur := l1
	for i := 1; i < 7; i++ {
		cur.Next = &LNode{}
		cur.Next.Data = i + 2
		cur = cur.Next
	}
	cur = l2
	for i := 9; i > 4; i-- {
		cur.Next = &LNode{}
		cur.Next.Data = i
		cur = cur.Next
	}
}

func RemoveDup(head *LNode) {
	if head == nil {
		return
	}

	cur := head.Next
	for cur.Next != nil {
		if cur.Data == cur.Next.Data {
			// 删除重复结点
			cur.Next = cur.Next.Next
		} else {
			// 继续遍历其余结点
			cur = cur.Next
		}
	}
}

func main() {
	head1 := &LNode{}
	head2 := &LNode{}
	CreateNodeT(head1, head2)

	PrintNode("Head1：", head1)
	PrintNode("Head2：", head2)
	PrintNode("相加后：", Add(head1, head2))
}

• 算法性能
  时间复杂度：O(n) ，因为需要对两个链表都进行遍历，n为较长的链表的长度。
  空间复杂度：O(n)，因为计算结果保存在一个新的链表中。

1.4 对链表进行重新排序

• 题目描述
  给定链表 L0->L1->L2…Ln-1->Ln，将链表重新排序为 L0->Ln->L1->Ln-1->L2->Ln-2…
  要求：①在原来链表的基础上进行排序，即不能申请新的结点； ②只能修改结点的next域，不能修改数据域。

  思路

  首先找到链表的中间结点；
  对链表的后半部分子链表进行逆序；
  把链表的前半部分子链表与后半部分的子链表进行合并，合并的思路为 分别从两个链表各取一个结点进行合并。

package main

import (
	. "github.com/isdamir/gotype" //引入定义的数据结构
)

// findMinddleNode 找出链表的中心结点，把链表从中间断成两个子链表
func findMinddleNode(head *LNode) *LNode {
	if head == nil || head.Next == nil {
		return head
	}
	fast := head // 遍历链表的每次向前走两步
	slow := head // 遍历链表的每次向前走一步
	slowPre := head
	for fast != nil && fast.Next != nil {
		slowPre = slow
		slow = slow.Next
		fast = fast.Next.Next
	}
	slowPre.Next = nil
	return slow
}

// reverse 逆序不带头结点的单链表
func reverse(head *LNode) *LNode {
	if head == nil || head.Next == nil {
		return head
	}
	var pre *LNode
	var next *LNode
	for head != nil {
		next = head.Next
		head.Next = pre
		pre = head
		head = next
	}
	return pre
}

func Recorder(head *LNode) {
	if head == nil || head.Next == nil {
		return
	}
	cur1 := head.Next // 前半部分的链表第一个结点
	mid := findMinddleNode(head.Next)
	cur2 := reverse(mid) // 后半部分链表逆序后的第一个结点
	var tmp *LNode
	for cur1.Next != nil {
		tmp = cur1.Next
		cur1.Next = cur2
		cur1 = tmp
		tmp = cur2.Next
		cur2.Next = cur1
		cur2 = tmp
	}
	cur1.Next = cur2
}
func main() {
	head := &LNode{}
	CreateNode(head, 8)
	PrintNode("排序前：", head)
	Recorder(head)
	PrintNode("排序后：", head)
}

算法性能分析：查找链表中间结点的方法的时间复杂度为O(n)，逆序子链表的时间复杂度也为O(n)，合并两个子链表的时间复杂度也为O(n)，因此，整个方法的时间复杂度为O(n)，其中，n表示的是链表的长度。由于这种方法只用了常数个额外指针变量，因此，空间复杂度为O(1)。

引申：如何查找链表的中间结点。分析与解答：主要思路：用两个指针从链表的第一个结点开始同时遍历结点，一个快指针每次走2步，另外一个慢指针每次走1步；当快指针先到链表尾部时，慢指针则恰好到达链表中部。（快指针到链表尾部时，当链表长度为奇数时，慢指针指向的即是链表中间指针，当链表长度为偶数时，慢指针指向的结点和慢指针指向的结点的下一个结点都是链表的中间结点），上面的代码FindMiddleNode就是用来求链表的中间结点的。

1.5 找出单链表中的倒数第k个元素

题目描述：找出单链表中的倒数第k个元素，例如给定单链表：1->2->3->4->5->6->7，则单链表的倒数第k=3个元素为5。

方法一：顺序遍历两遍法主要思路：首先遍历一遍单链表，求出整个单链表的长度n，然后把求倒数第k个元素转换为求顺数第n-k个元素，再去遍历一次单链表就可以得到结果。但是该方法需要对单链表进行两次遍历。

方法二：快慢指针法由于单链表只能从头到尾依次访问链表的各个结点，因此，如果要找链表的倒数第k个元素，也只能从头到尾进行遍历查找，在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k步，然后两个指针同时往前移动。循环直到先行的指针值为null时，另一个指针所指的位置就是所要找的位置。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" //引入定义的数据结构
)

// 快慢指针查找
func FindLastK(head *LNode, k int) *LNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow := head.Next
	fast := head.Next
	i := 0
	for i = 0; i < k && fast != nil; i++ {
		fast = fast.Next
	}
	if i < k {
		return nil
	}
	for fast != nil {
		slow = slow.Next
		fast = fast.Next
	}
	return slow
}
func main() {
	fmt.Println("寻找倒数k")
	head := &LNode{}
	CreateNode(head, 8)
	PrintNode("链表：", head)
	fmt.Println("链表倒数第3个元素为：", FindLastK(head, 3).Data)
}

算法性能分析：这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外，由于只需要常量个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。

引申：如何将单链表向右旋转k个位置？题目描述：给定单链表1->2->3->4->5->6->7，k=3，那么旋转后的单链表变为5->6->7->1->2->3->4。

主要思路：①首先找到链表倒数第k+1个结点slow和尾结点fast（如下图所示）；②把链表断开为两个子链表，其中，后半部分子链表结点的个数为k；③使原链表的尾结点指向链表的第一个结点；④使链表的头结点指向原链表倒数第k个结点。

 实现代码如下：

package main

import (
	. "github.com/isdamir/gotype" //引入定义的数据结构
)

// RotateK 把链表右旋k个位置
func RotateK(head *LNode, k int) {
	if head == nil || head.Next == nil {
		return
	}
	slow := head.Next
	fast := head.Next
	i := 0
	for i = 0; i < k && fast != nil; i++ {
		fast = fast.Next
	}
	if i < k {
		return
	}
	for fast.Next != nil {
		slow = slow.Next
		fast = fast.Next
	}
	tmp := slow
	slow = slow.Next
	tmp.Next = nil
	fast.Next = head.Next
	head.Next = slow
}
func main() {
	head := &LNode{}
	CreateNode(head, 8)
	PrintNode("旋转前：", head)
	RotateK(head, 3)
	PrintNode("旋转后", head)
}

算法性能分析：这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外，由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。

1.6 检测一个较大的单链表是否有环

题目描述：单链表有环指的是单链表中某个结点的next域指向的是链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在？分析与解答：

方法一：蛮力法定义一个Set用来存放结点的引用，并将其初始化为空，从链表的头结点开始向后遍历，每遍历到一个结点就判断Set中是否引用这个结点，如果没有，说明这个结点是第一次访问，还没有形成环，那么将这个引用结点添加到指针Set中去。如果在Set中找到了同样的结点，那么说明这个结点已经被访问过了，于是就形成了环。这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。

方法二：快慢指针遍历法定义两个指针fast（快）与slow（慢），二者的初始值都指向链表头，指针slow每次前进一步，指针fast每次前进两步，两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，如果快指针等于慢指针，就证明这个链表是带环的单向链表，否则，证明这个链表是不带环的循环链表。实现代码见引申部分。

引申：如果链表存在环，那么如何找出环的入口点？分析与解答：当链表有环的时候，如果知道环的入口点，那么在需要遍历链表或释放链表所占的空间的时候方法将会非常简单，下面主要介绍查找链表环入口点的思路。

如果单链表有环，那么按照上述方法二的思路，当走得快的指针fast与走得慢的指针slow相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈（1<=n）。如果slow指针走了s步，则fast指针走了2s步（fast步数还等于s加上在环上多转的n圈），假设环长为r，则满足如下关系表达式：2s=s+nr由此可以得到：s=nr设整个链表长为L，入口环与相遇点距离为x，起点到环入口点的距离为a。则满足如下关系表达式：a+x=nr

a+x=(n-1)r+r=(n-1)r+L-a

a=(n-1)r+(L-a-x)

(L-a-x)为相遇点到环入口点的距离，从链表头到环入口点的距离=(n-1)×环长+相遇点到环入口点的长度，于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" //引入定义的数据结构
)

// 判断单链表是否有环
func IsLoop(head *LNode) *LNode {
	if head == nil || head.Next == nil {
		return head
	}
	slow := head.Next
	fast := head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return slow
		}
	}
	return nil
}

// 找出环的入口点
func FindLoopNode(head *LNode, meetNode *LNode) *LNode {
	first := head.Next
	second := meetNode
	for first != second {
		first = first.Next
		second = second.Next
	}
	return first
}

func main() {
	fmt.Println("查找环")
	head := &LNode{}
	CreateNode(head, 8)
	meetNode := IsLoop(head)
	if meetNode != nil {
		fmt.Println("有环")
		loopNode := FindLoopNode(head, meetNode)
		fmt.Println("环的入口点为：", loopNode.Data)
	} else {
		fmt.Println("无环")
	}
}

运行结果分析：示例代码中给出的链表为：1->2->3->4->5->6->7->3（3实际代表链表第三个结点）。因此，IsLoop函数返回的结果为两个指针相遇的结点，所以，链表有环，通过函数FindLoopNode可以获取到环的入口点为3。算法性能分析：这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。

1.7 把链表相邻元素翻转

题目描述：把链表相邻元素翻转，例如给定链表为1->2->3->4->5->6->7，则翻转后的链表变为2->1->4->3->6->5->7。分析与解答：

方法一：交换值法最容易想到的方法就是交换相邻两个结点的数据域，这种方法由于不需要重新调整链表的结构，因此，比较容易实现，但是这种方法并不是考官所期望的解法。

方法二：就地逆序主要思路：通过调整结点指针域的指向来直接调换相邻的两个结点。如果单链表恰好有偶数个结点，那么只需要将奇偶结点对调即可，如果链表有奇数个结点，那么只需要将除最后一个结点外的其他结点进行奇偶对调即可。为了便于理解，下图给出了其中第一对结点对调的方法。

在上图中，当前遍历到结点cur，通过（1）～（6）6个步骤用虚线的指针来代替实线的指针实现相邻结点的逆序。其中，（1）～（4）实现了前两个结点的逆序操作，（5）和（6）两个步骤向后移动指针，接着可以采用同样的方式实现后面两个相邻结点的逆序操作。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" //引入定义的数据结构
)

func Reverse(head *LNode) {
	if head == nil || head.Next == nil {
		return
	}
	cur := head.Next // 当前遍历结点
	pre := head      // 当前结点的前驱结点
	var next *LNode  // 当前结点的后继结点的后继结点
	for cur != nil && cur.Next != nil {
		next = cur.Next.Next //见图第（1）步
		pre.Next = cur.Next  // 见图第(2)步
		cur.Next.Next = cur  // 见图第（3）步
		cur.Next = next      // 见图第（4）步
		pre = cur            // 见图第（5）步
		cur = next           // 见图第（6）步
	}
}

func main() {
	fmt.Println("相邻元素反转")
	head := &LNode{}
	CreateNode(head, 8)
	PrintNode("顺序输出：", head)
	Reverse(head)
	PrintNode("逆序输出", head)
}

上例中，由于链表有奇数个结点，因此，链表前三对结点相互交换，而最后一个结点保持在原来的位置。算法性能分析：这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。

1.8 把链表以k个结点为一组进行翻转

题目描述：K链表翻转是指把每k个相邻的结点看成一组进行翻转，如果剩余结点不足k个，则保持不变。假设给定链表1->2->3->4->5->6->7和一个数k，如果k的值为2，那么翻转后的链表为2->1->4->3->6->5->7。如果k的值为3，那么翻转后的链表为：3->2->1->6->5->4->7。

分析与解答：主要思路为：首先把前k个结点看成一个子链表，采用前面介绍的方法进行翻转，把翻转后的子链表链接到头结点后面，然后把接下来的k个结点看成另外一个单独的链表进行翻转，把翻转后的子链表链接到上一个已经完成翻转子链表的后面。具体实现方法如下图所示。

在上图中，以k=3为例介绍具体实现的方法：（1）首先设置pre指向头结点，然后让begin指向链表第一个结点，找到从begin开始第k=3个结点end。（2）为了采用本章1.1节中链表翻转的算法，需要使end.next=null，在此之前需要记录下end指向的结点，用pNext来记录。（3）使end.next=null，从而使得从begin到end为一个单独的子链表，可以对这个子链表采用1.1节介绍的方法进行翻转。（4）对以begin为第一个结点，end为尾结点所对应的k=3个结点进行翻转。（5）由于翻转后子链表的第一个结点从begin变为end，因此，执行pre.next=end，把翻转后的子链表链接起来。（6）把链表中剩余的还未完成翻转的子链表链接到已完成翻转的子链表后面（主要是针对剩余的结点的个数小于k的情况）。（7）让pre指针指向已完成翻转的链表的最后一个结点。（8）让begin指针指向下一个需要被翻转的子链表的第一个结点（通过begin=pNext来实现）。接下来可以反复使用（1）～（8）这8个步骤对链表进行翻转。实现代码如下： 

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" //引入定义的数据结构
)

// 对不带头结点的单链表翻转
func reverse(head *LNode) *LNode {
	if head == nil || head.Next == nil {
		return head
	}
	var pre *LNode  // 前驱结点
	var next *LNode // 当前结点
	for head != nil {
		next = head.Next
		head.Next = pre
		pre = head
		head = next
	}
	return pre
}

func ReverseK(head *LNode, k int) {
	if head == nil || head.Next == nil {
		return
	}
	pre := head
	begin := head.Next
	var end *LNode
	var pNext *LNode
	if begin != nil {
		end = begin
		// 对应图中第（1）步找到从begin开始第k个结点
		for i := 1; i < k; i++ {
			if end.Next != nil {
				end = end.Next
			} else {
				return
			}
		}
		pNext = end.Next          //图中第（2）步
		end.Next = nil            // 图中第（3）步
		pre.Next = reverse(begin) // 图中第（4）（5）步
		begin.Next = pNext
		pre = begin   // 图中第（7）步
		begin = pNext // 图中第（8）步
	}
}
func main() {
	fmt.Println("k元素翻转")
	head := &LNode{}
	CreateNode(head, 8)
	PrintNode("顺序输出：", head)
	ReverseK(head, 3)
	PrintNode("逆序输出", head)
}

算法性能分析：这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。

1.9 合并两个有序链表

题目描述：已知两个链表head1和head2 各自有序（例如升序排列），请把它们合并成一个链表，要求合并后的链表依然有序。

分析与解答：分别用指针head1和head2来遍历两个链表，如果当前head1指向的数据小于head2指向的数据，则将head1指向的结点归入合并后的链表中，否则，将head2指向的结点归入合并后的链表中。如果有一个链表遍历结束，则把未结束的链表连接到合并后的链表尾部。下图以一个简单的示例为例介绍合并的具体方法：

由于链表按升序排列，首先通过比较链表第一个结点中元素的大小来确定最终合并后链表的头结点；接下来每次都找两个链表中剩余结点的最小值链接到被合并的链表后面，如上图中的虚线所示。在实现的时候需要注意，要释放head2链表的头结点，实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" //引入定义的数据结构
)

// 合并两个升序排列的单链表
func Merge(head1 *LNode, head2 *LNode) *LNode {
	if head1 == nil || head1.Next == nil {
		return head1
	}
	if head2 == nil || head2.Next == nil {
		return head2
	}
	cur1 := head1.Next // 用来遍历head1
	cur2 := head2.Next // 用来遍历head2
	var head *LNode    // 合并后链表的头结点
	var cur *LNode     // 合并后的链表在尾结点
	if cur1.Data.(int) > cur2.Data.(int) {
		head = head2
		cur = cur2
		cur2 = cur2.Next
	} else {
		head = head1
		cur = cur1
		cur1 = cur1.Next
	}
	// 每次找链表剩余结点的最小值对应的结点连接到合并后链表的尾部
	for cur1 != nil && cur2 != nil {
		if cur1.Data.(int) < cur2.Data.(int) {
			cur.Next = cur1
			cur = cur1
			cur1 = cur1.Next
		} else {
			cur.Next = cur2
			cur = cur2
			cur2 = cur2.Next
		}
	}
	if cur1 != nil {
		cur.Next = cur1
	}
	if cur2 != nil {
		cur.Next = cur2
	}
	return head
}
func main() {
	fmt.Println("合并有序链表")
	head1 := &LNode{}
	head2 := &LNode{}
	CreateNodeT(head1, 1)
	CreateNodeT(head2, 2)
	PrintNode("head1:", head1)
	PrintNode("head2:", head2)
	head := Merge(head1, head2)
	PrintNode("合并后的链表", head)
}

// 创建链表
func CreateNodeT(node *LNode, start int) {
	cur := node
	for i := start; i < 7; i += 2 {
		cur.Next = &LNode{}
		cur.Next.Data = i
		cur = cur.Next
	}
}

 算法性能分析：以上这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。

1.10 在只给定单链表中某个结点指针的情况下删除该结点

题目描述：假设给定链表1->2->3->4->5->6->7中指向第5个元素的指针，要求把结点5删掉，删除后链表变为1->2->3->4->6->7。

分析与解答：一般而言，要删除单链表中的一个结点p，首先需要找到结点p的前驱结点pre，然后通过pre.next=p.next来实现对结点p的删除。对于本题而言，由于无法获取到结点p的前驱结点，因此，不能采用这种传统的方法。那么如何解决这个问题呢？可以分如下两种情况来分析：（1）如果这个结点是链表的最后一个结点，那么无法删除这个结点。（2）如果这个结点不是链表的最后一个结点，可以通过把其后继结点的数据复制到当前结点中，然后删除后继结点的方法来实现。实现方法如下图所示：

在上图中，第一步首先把结点p的后继结点的数据复制到结点p的数据域中；接着第二步把结点p的后继结点删除。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" //引入定义的数据结构
)

// 给定单链表中某个结点，删除该结点
func RemoveNode(node *LNode) bool {
	if node == nil || node.Next == nil {
		return false
	}
	node.Data = node.Next.Data
	tmp := node.Next
	node.Next = tmp.Next
	return true
}
func main() {
	fmt.Println("删除指定结点")
	head := &LNode{}
	retNode := CreateNodeT(head, 5)
	fmt.Printf("删除结点%[1]v前链表：", retNode.Data)
	PrintNode("", head)
	result := RemoveNode(retNode)
	if result {
		PrintNode("删除该结点后链表：", head)
	}
}

// 创建链表
func CreateNodeT(node *LNode, get int) (retNode *LNode) {
	cur := node
	for i := 1; i < 8; i++ {
		cur.Next = &LNode{}
		cur.Next.Data = i
		cur = cur.Next
		if i == get {
			retNode = cur
		}
	}
	return
}

 算法性能分析：由于这种方法不需要遍历链表，只需要完成一个数据复制与结点删除的操作，因此，时间复杂度为O(1)。由于这种方法只用了常数个额外指针变量，因此，空间复杂度也为O(1)。引申：只给定单链表中某个结点p(非空结点)，如何在p前面插入一个结点？分析与解答：主要思路：首先分配一个新结点q，把结点q插入在结点p后，然后把p的数据域拷贝到结点q的数据域中，最后把结点p的数据域设置为待插入的值。

1.11 判断两个单链表（无环）是否交叉

题目描述：单链表相交指的是两个链表存在完全重合的部分，如下图所示：

在上图中，这两个链表相交于结点5，要求判断两个链表是否相交，如果相交，找出相交处的结点。分析与解答：方法一：Hash法如上图所示，如果两个链表相交，那么它们一定会有公共的结点，由于结点的地址或引用可以作为结点的唯一标识，因此，可以通过判断两个链表中的结点是否有相同的地址或引用来判断链表是否相交。具体可以采用如下方法实现：首先遍历链表head1，把遍历到的所有结点的地址存放到HashSet中；接着遍历链表head2，每遍历到一个结点，就判断这个结点的地址在HashSet中是否存在，如果存在，那么说明两个链表相交并且当前遍历到的结点就是它们的相交点，否则直到链表head2遍历结束，说明这两个单链表不相交。

算法性能分析：由于这种方法需要分别遍历两个链表，因此，算法的时间复杂度为O(n1+n2)，其中，n1与n2分别为两个链表的长度。此外，由于需要申请额外的存储空间来存储链表head1中结点的地址，因此，算法的空间复杂度为O(n1)。

方法二：首尾相接法主要思路：将这两个链表首尾相连（例如把链表head1尾结点链接到head2的头指针），然后检测这个链表是否存在环，如果存在，则两个链表相交，而环入口结点即为相交的结点，如下图所示。具体实现方法以及算法性能分析见1.6节。

 主要思路：如果两个链表相交，那么两个链表从相交点到链表结束都是相同的结点，必然是Y字形（如上图所示），所以，判断两个链表的最后一个结点是不是相同即可。即先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交，这时记下两个链表的长度n1、n2，再遍历一次，长链表结点先出发前进|n1-n2|步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" //引入定义的数据结构
)

func IsIntersect(head1 *LNode, head2 *LNode) *LNode {
	if head1 == nil || head1.Next == nil || head2 == nil || head2.Next == nil {
		return nil
	}
	tmp1 := head1.Next
	tmp2 := head2.Next
	n1 := 0
	n2 := 0
	// 遍历head1,找到尾结点，同时记录head1的长度
	for tmp1.Next != nil {
		tmp1 = tmp1.Next
		n1++
	}
	// 遍历head2，找到尾结点，同时记录head2的长度
	for tmp1.Next != nil {
		tmp2 = tmp2.Next
		n2++
	}
	// head1与head2是有相同的尾结点
	if tmp1 == tmp2 {
		// 长链表先走|n1-n2|步
		if n1 > n2 {
			for n1-n2 > 0 {
				head1 = head1.Next
				n1--
			}
		}
		if n2 > n1 {
			for n2-n1 > 0 {
				head2 = head2.Next
				n2--
			}
		}

		//两个链表同时前进，找出相同的结点
		for head1 != head2 {
			head1 = head1.Next
			head2 = head2.Next
		}
		return head1
	}
	return nil
}
func main() {
	fmt.Println("判断相交链表")
	head1 := &LNode{}
	retNode := CreateNodeT(head1, 5)
	head2 := &LNode{}
	cur := head2
	for i := 1; i < 5; i++ {
		cur.Next = &LNode{}
		cur.Next.Data = i
		cur = cur.Next
	}
	cur.Next = retNode
	interNode := IsIntersect(head1, head2)
	if interNode == nil {
		fmt.Println("这两个链表不相交：")
	} else {
		fmt.Println("这两个链表相交点为：", interNode)
	}
}

// 创建链表
func CreateNodeT(node *LNode, get int) (retNode *LNode) {
	cur := node
	for i := 1; i < 8; i++ {
		cur.Next = &LNode{}
		cur.Next.Data = i
		cur = cur.Next
		if i == get {
			retNode = cur
		}
	}
	return
}

运行结果分析：在上述代码中，由于构造的两个单链表相交于结点5，因此，输出结果中它们的相交结点为5。算法性能分析：假设这两个链表长度分别为n1和n2，重叠的结点的个数为L(0<L<min(n1，n2))，则总共对链表进行遍历的次数为n1+n2+L+n1-L+n2-L=2(n1+n2)-L，因此，算法的时间复杂度为O(n1+n2)；由于这种方法只使用了常数个额外指针变量，因此，空间复杂度为O(1)。

引申：如果单链表有环，如何判断两个链表是否相交？分析与解答：（1）如果一个单链表有环，另外一个没环，那么它们肯定不相交。（2）如果两个单链表都有环并且相交，那么这两个链表一定共享这个环。判断两个有环的链表是否相交的方法为：首先采用本章第1.6节中介绍的方法找到链表head1中环的入口点p1，然后遍历链表head2，判断链表中是否包含结点p1，如果包含，则这两个链表相交，否则不相交。找相交点的方法为：把结点p1看作两个链表的尾结点，这样就可以把问题转换为求两个无环链表相交点的问题，可以采用本节介绍的求相交点的方法来解决这个问题。

1.12 如何展开链接列表

题目描述：给定一个有序链表，其中每个结点也表示一个有序链表，结点包含两个类型的指针：（1）指向主链表中下一个结点的指针（在下面的代码中称为“正确”指针）。（2）指向此结点头的链表（在下面的代码中称之为“down”指针）。所有链表都被排序。请参见以下示例：

 实现一个函数flatten()，该函数用来将链表扁平化成单个链表，扁平化的链表也应该被排序。例如，对于上述输入链表，输出链表应为3->6->8->11->15->21->22->30->31->39->40->45->50。

分析与解答：本题的主要思路为使用归并排序中的合并操作，使用归并的方法把这些链表来逐个归并。具体而言，可以使用递归的方法，递归地合并已经扁平化的链表与当前的链表。在实现的过程可以使用down指针来存储扁平化处理后的链表。实现代码如下：

package main

import (
	"fmt"
)

type LNode struct {
	data  int
	right *LNode
	down  *LNode
}

func (p *LNode) Insert(headRef *LNode, data int) *LNode {
	newNode := &LNode{data: data, down: headRef}
	headRef = newNode
	return headRef
}

// 用来合并两个有序的链表
func merge(a *LNode, b *LNode) *LNode {
	if a == nil {
		return b
	}
	if b == nil {
		return a
	}
	// 把两个链表头中较小的结点赋值给result
	var result *LNode
	if a.data < b.data {
		result = a
		result.down = merge(a.down, b)
	} else {
		result = b
		result.down = merge(a, b.down)
	}
	return result
}

// 把链表扁平化处理
func Flatten(root *LNode) *LNode {
	if root == nil || root.right == nil {
		return root
	}
	// 递归处理root.right链表
	root.right = Flatten(root.right)
	// 把root结点对应的链表与右边的链表合并
	root = merge(root, root.right)
	return root
}
func main() {
	fmt.Println("链表扁平化")
	head := CreateNode()
	head = Flatten(head)
	PrintNode("扁平化链表后：", head)
}

// 创建链表
func CreateNode() *LNode {
	node := &LNode{}
	node = node.Insert(nil, 31)
	node = node.Insert(node, 8)
	node = node.Insert(node, 6)
	node = node.Insert(node, 3)

	node.right = node.Insert(node.right, 21)
	node.right = node.Insert(node.right, 11)

	node.right.right = node.Insert(node.right.right, 50)
	node.right.right = node.Insert(node.right.right, 22)
	node.right.right = node.Insert(node.right.right, 15)

	node.right.right.right = node.Insert(node.right.right.right, 55)
	node.right.right.right = node.Insert(node.right.right.right, 40)
	node.right.right.right = node.Insert(node.right.right.right, 39)
	node.right.right.right = node.Insert(node.right.right.right, 40)

	return node
}

// 打印链表的方法
func PrintNode(info string, node *LNode) {
	fmt.Print(info)
	tmp := node
	for tmp != nil {
		fmt.Print(tmp.data, " ")
		tmp = tmp.down
	}
	fmt.Println()
}

2.1 如何实现栈

题目描述：实现一个栈的数据结构，使其具有以下方法：压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。分析与解答：栈的实现有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。方法一：数组实现在采用数组来实现栈的时候，栈空间是一段连续的空间。实现思路如下图所示。

从上图中可以看出，可以把数组的首元素当作栈底，同时记录栈中元素的个数size，假设数组首地址为arr，从上图可以看出，压栈的操作其实是把待压栈的元素放到数组arr[size]中，然后执行size++操作；同理，弹栈操作其实是取数组arr[size-1]元素，然后执行size--操作。根据这个原理可以非常容易实现栈，示例代码如下：

package main

// golang1.18之前的版本不支持泛型，一般定义interface来处理
// 类型都可以定义为interface{}
import (
	"errors"
	"fmt"
	// 引入定义的数据结构
)

type SliceStack struct {
	arr       []int
	stackSize int
}

func (p *SliceStack) IsEmpty() bool {
	return p.stackSize == 0
}

func (p *SliceStack) Size() int {
	return p.stackSize
}

func (p *SliceStack) Top() int {
	if p.IsEmpty() {
		panic(errors.New("栈已经为空"))
	}
	return p.arr[p.stackSize-1]
}
func (p *SliceStack) Pop() int {
	if p.stackSize > 0 {
		p.stackSize--
		ret := p.arr[p.stackSize]
		p.arr = p.arr[:p.stackSize]
		return ret
	}
	panic(errors.New("栈已经为空"))
}
func (p *SliceStack) Push(t int) {
	p.arr = append(p.arr, t)
	p.stackSize = p.stackSize + 1
}
func main() {
	SliceMode()
}

func SliceMode() {
	defer func() {
		if err := recover(); err != nil {
			fmt.Println(err)
		}
	}()
	fmt.Println("Slice构建栈结构")
	sliceStack := &SliceStack{arr: make([]int, 0)}
	sliceStack.Push(1)
	fmt.Println("栈顶元素为：", sliceStack.Top())
	fmt.Println("栈大小为：", sliceStack.Size())
	sliceStack.Pop()
	fmt.Println("弹栈成功：", sliceStack.Size())
	sliceStack.Pop()
}

 方法二：链表实现在创建链表的时候经常采用一种从头结点插入新结点的方法，可以采用这种方法来实现栈，最好使用带头结点的链表，这样可以保证对每个结点的操作都是相同的，实现思路如下图所示：

在上图中，在进行压栈操作的时候，首先需要创建新的结点，把待压栈的元素放到新结点的数据域中，然后只需要（1）和（2）两步就实现了压栈操作（把新结点加到了链表首部）。同理，在弹栈的时候，只需要进行（3）的操作就可以删除链表的第一个元素，从而实现弹栈操作。实现代码如下：

package main

// golang1.18之前的版本不支持泛型，一般定义interface来处理
// 类型都可以定义为interface{}
import (
	"errors"
	"fmt"

	"github.com/isdamir/gotype"
	// 引入定义的数据结构
)

type LinkedStack struct {
	head *gotype.LNode
}

func (p *LinkedStack) IsEmpty() bool {
	return p.head.Next == nil
}

func (p *LinkedStack) Size() int {
	size := 0
	node := p.head.Next
	for node != nil {
		node = node.Next
		size++
	}
	return size
}

func (p *LinkedStack) Top() int {
	if p.head.Next != nil {
		return p.head.Next.Data.(int)
	}
	panic(errors.New("栈已经为空"))
}
func (p *LinkedStack) Pop() int {
	tmp := p.head.Next
	if tmp != nil {
		p.head.Next = tmp.Next
		return tmp.Data.(int)
	}
	panic(errors.New("栈已经为空"))
}
func (p *LinkedStack) Push(t int) {
	node := &gotype.LNode{Data: t, Next: p.head.Next}
	p.head.Next = node
}
func main() {
	LinkedMode()
}

func LinkedMode() {
	defer func() {
		if err := recover(); err != nil {
			fmt.Println(err)
		}
	}()
	fmt.Println("链表构建栈结构")
	LinkedStack := &LinkedStack{head: &gotype.LNode{}}
	LinkedStack.Push(1)
	fmt.Println("栈顶元素为：", LinkedStack.Top())
	fmt.Println("栈大小为：", LinkedStack.Size())
	LinkedStack.Pop()
	fmt.Println("弹栈成功：", LinkedStack.Size())
	LinkedStack.Pop()
}

 两种方法的对比：采用数组实现栈的优点是：一个元素值占用一个存储空间。它的缺点为：如果初始化申请的存储空间太大，会造成空间的浪费，如果申请的存储空间太小，后期会经常需要扩充存储空间，扩充存储空间是个费时的操作，这样会造成性能的下降。采用链表实现栈的优点是：使用灵活方便，只有在需要的时候才会申请空间。它的缺点为：除了要存储元素外，还需要额外的存储空间存储指针信息。算法性能分析：这两种方法压栈与弹栈的时间复杂度都为O(1)。

2.2 如何实现队列

题目描述：实现一个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。

分析与解答：与实现栈的方法类似，队列的实现也有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。

方法一：数组实现下图给出了一种最简单的实现方式，用front来记录队列首元素的位置，用rear来记录队列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为rear的位置，同时执行rear++，出队列的时候只需要执行front++即可。

代码如下：

package main

import (
	"errors"
	"fmt"
	// 引入定义的数据结构
)

type SliceQueue struct {
	arr   []int
	front int // 队列头
	rear  int // 队列尾
}

// 判断队列是否为空
func (p *SliceQueue) IsEmpty() bool {
	return p.front == p.rear
}

// 返回队列的大小
func (p *SliceQueue) Size() int {
	return p.rear - p.front
}

// 返回队列首元素
func (p *SliceQueue) GetFront() int {
	if p.IsEmpty() {
		panic(errors.New("队列已经为空"))
	}
	return p.arr[p.front]
}

// 返回队列尾元素
func (p *SliceQueue) GetBack() int {
	if p.IsEmpty() {
		panic(errors.New("队列已经为空"))
	}
	return p.arr[p.rear-1]
}

// 删除队列头元素
func (p *SliceQueue) DeQueue() {
	if p.rear > p.front {
		p.rear--
		p.arr = p.arr[1:]
	} else {
		panic(errors.New("队列已经为空"))
	}
}

// 把新元素加入队列尾
func (p *SliceQueue) EnQueue(item int) {
	p.arr = append(p.arr, item)
	p.rear++
}
func main() {
	SliceMode()
}

func SliceMode() {
	defer func() {
		if err := recover(); err != nil {
			fmt.Println(err)
		}
	}()
	fmt.Println("Slice构建队列结构")
	sliceQueue := &SliceQueue{arr: make([]int, 0)}
	sliceQueue.EnQueue(1)
	sliceQueue.EnQueue(2)
	fmt.Println("队列头元素为：", sliceQueue.GetFront())
	fmt.Println("队列尾元素为：", sliceQueue.GetBack())
	fmt.Println("队列大小为：", sliceQueue.Size())
}

以上这种实现方法最大的缺点为：出队列后数组前半部分的空间不能够充分地利用，解决这个问题的方法为把数组看成一个环状的空间（循环队列）。当数组最后一个位置被占用后，可以从数组首位置开始循环利用，具体实现方法可以参考数据结构相关书籍。

方法二：链表实现采用链表实现队列的方法与实现栈的方法类似，分别用两个指针指向队列的首元素与尾元素，如下图所示。用pHead来指向队列的首元素，用pEnd来指向队列的尾元素。

在上图中，刚开始队列中只有元素1、2和3，当新元素4要进队列的时候，只需要上图中（1）和（2）两步，就可以把新结点连接到链表的尾部，同时修改pEnd指针指向新增加的结点。出队列的时候只需要（3）一步，改变pHead指针使其指向pHead->next，此外也需要考虑结点所占空间释放的问题。在入队列与出队列的操作中也需要考虑队列尾空的时候的特殊操作，实现代码如下：

package main

import (
	"errors"
	"fmt"

	"github.com/isdamir/gotype"
	// 引入定义的数据结构
)

type LinkedQueue struct {
	head *gotype.LNode
	end  *gotype.LNode
}

// 判断队列是否为空, 如果为空返回true，否则返回false
func (p *LinkedQueue) IsEmpty() bool {
	return p.head == nil
}

// 获取队列中元素的个数
func (p *LinkedQueue) Size() int {
	size := 0
	node := p.head
	for node != nil {
		node = node.Next
		size++
	}
	return size
}

// 入队列：把元素e加入到队列尾
func (p *LinkedQueue) EnQueue(e int) {
	node := &gotype.LNode{Data: e}
	if p.head == nil {
		p.head = node
		p.end = node
	} else {
		p.end.Next = node
		p.end = node
	}
}

// 出队列，删除队列首元素
func (p *LinkedQueue) DeQueue() {
	if p.head == nil {
		panic(errors.New("队列已经为空"))
	}
	p.head = p.head.Next
	if p.head == nil {
		p.end = nil
	}
}

// 返回队列首元素
func (p *LinkedQueue) GetFront() int {
	if p.head == nil {
		panic(errors.New("队列已经为空"))
	}
	return p.head.Data.(int)
}

// 返回队列尾元素
func (p *LinkedQueue) GetBack() int {
	if p.end == nil {
		panic(errors.New("队列已经为空"))
	}
	return p.end.Data.(int)
}

func main() {
	LinkedMode()
}

func LinkedMode() {
	defer func() {
		if err := recover(); err != nil {
			fmt.Println(err)
		}
	}()
	fmt.Println("Linked构建队列结构")
	linkedQueue := &LinkedQueue{}
	linkedQueue.EnQueue(1)
	linkedQueue.EnQueue(2)
	fmt.Println("队列头元素为：", linkedQueue.GetFront())
	fmt.Println("队列尾元素为：", linkedQueue.GetBack())
	fmt.Println("队列大小为：", linkedQueue.Size())
}

显然用链表来实现队列有更好的灵活性，与数组的实现方法相比，它多了用来存储结点关系的指针空间。此外，也可以用循环链表来实现队列，这样只需要一个指向链表最后一个元素的指针即可，因为通过指向链表尾元素可以非常容易地找到链表的首结点。

2.3 如何翻转栈的所有元素

题目描述：翻转（也称颠倒）栈的所有元素，例如输入栈{1， 2，3， 4， 5}，其中，1处在栈顶，翻转之后的栈为{5，4， 3， 2， 1}，其中，5处在栈顶。分析与解答：最容易想到的办法是申请一个额外的队列，先把栈中的元素依次出栈放到队列里，然后把队列里的元素按照出队列顺序入栈，这样就可以实现栈的翻转，这种方法的缺点是需要申请额外的空间存储队列，因此，空间复杂度较高。下面介绍一种空间复杂度较低的递归的方法。递归程序有两个关键因素需要注意：递归定义和递归终止条件。经过分析后，很容易得到该问题的递归定义和递归终止条件。递归定义：将当前栈的最底元素移到栈顶，其他元素顺次下移一位，然后对不包含栈顶元素的子栈进行同样的操作。终止条件：递归下去，直到栈为空。递归的调用过程如下图所示：

在上图中，对于栈{1， 2， 3， 4， 5}，进行翻转的操作为：首先把栈底元素移动到栈顶得到栈{5， 1， 2， 3，4}，然后对不包含栈顶元素的子栈进行递归调用（对子栈元素进行翻转），子栈{1，2，3，4}翻转的结果为{4，3，2，1}，因此，最终得到翻转后的栈为{5，4，3，2，1}。此外，由于栈的后进先出的特点，使得只能取栈顶的元素，因此，要把栈底的元素移动到栈顶也需要递归调用才能完成，主要思路为：把不包含该栈顶元素的子栈的栈底的元素移动到子栈的栈顶，然后把栈顶的元素与子栈栈顶的元素（其实就是与栈顶相邻的元素）进行交换。

 为了更容易理解递归调用，可以认为在进行递归调用的时候，子栈已经把栈底元素移动到了栈顶，在上图中，为了把栈{1， 2， 3， 4， 5}的栈底元素5移动到栈顶，首先对子栈{2， 3， 4， 5}，进行递归调用，调用的结果为{5， 2， 3， 4}，然后对子栈顶元素5，与栈顶元素1进行交换得到栈{5， 1， 2， 3， 4}，实现了把栈底元素移动到了栈顶。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func moveBottomToTop(s *SliceStack) {
	if s.IsEmpty() {
		return
	}
	top1 := s.Pop() // 弹出栈顶元素
	if !s.IsEmpty() {
		// 递归处理不包含栈顶元素的子栈
		moveBottomToTop(s)
		top2 := s.Pop()
		s.Push(top1)
		s.Push(top2)
	} else {
		s.Push(top1)
	}
}

// 翻转栈顺序
func ReverseStack(s *SliceStack) {
	if s.IsEmpty() {
		return
	}
	// 把栈底元素移动到栈顶
	moveBottomToTop(s)
	top := s.Pop()
	// 递归处理子栈
	ReverseStack(s)
	s.Push(top)
}

func main() {
	stack := CreateStack([]int{5, 4, 3, 2, 1})
	ReverseStack(stack)
	PrintStack("翻转后出栈顺序为：", stack)
}

// 快速创建一个栈
func CreateStack(list []int) *SliceStack {
	stack := NewSliceStack()
	for _, v := range list {
		stack.Push(v)
	}
	return stack
}

// 打印栈
func PrintStack(str string, s *SliceStack) {
	fmt.Print(str)
	for !s.IsEmpty() {
		fmt.Print(s.Pop(), "")
	}
	fmt.Println()
}

算法性能分析：把栈底元素移动到栈顶操作的时间复杂度为O(n)，在翻转操作中对每个子栈都进行了把栈底元素移动到栈顶的操作，因此，翻转算法的时间复杂度为O(n2)。

引申：如何给栈排序？分析与解答：很容易通过对上述方法进行修改得到栈的排序算法。主要思路为：首先对不包含栈顶元素的子栈进行排序，如果栈顶元素大于子栈的栈顶元素，则交换这两个元素。因此，在上述方法中，只需要在交换栈顶元素与子栈顶元素的时候增加一个条件判断即可实现栈的排序，实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func moveBottomToTop(s *SliceStack) {
	if s.IsEmpty() {
		return
	}
	top1 := s.Pop() // 弹出栈顶元素
	if !s.IsEmpty() {
		// 递归处理不包含栈顶元素的子栈
		moveBottomToTop(s)
		top2 := s.Pop()
		s.Push(top1)
		s.Push(top2)
	} else {
		s.Push(top1)
	}
}

// 翻转栈顺序
func ReverseStack(s *SliceStack) {
	if s.IsEmpty() {
		return
	}
	// 把栈底元素移动到栈顶
	moveBottomToTop(s)
	top := s.Pop()
	// 递归处理子栈
	ReverseStack(s)
	s.Push(top)
}
func moveBottomToTopSort(s *SliceStack) {
	if s.IsEmpty() {
		return
	}
	top1 := s.Pop() // 弹出栈顶元素
	if !s.IsEmpty() {
		// 递归处理不包含栈顶元素的子栈
		moveBottomToTop(s)
		top2 := s.Top()
		if top1.(int) > top2.(int) {
			s.Pop()
			s.Push(top1)
			s.Push(top2)
			return
		}
	}
	s.Push(top1)
}

// 对栈排序
func SortStack(s *SliceStack) {
	if s.IsEmpty() {
		return
	}
	// 把栈底元素移动到栈顶
	moveBottomToTopSort(s)
	top := s.Pop()
	SortStack(s)
	s.Push(top)
}
func main() {
	stack := CreateStack([]int{5, 4, 3, 2, 1})
	ReverseStack(stack)
	PrintStack("翻转后出栈顺序为：", stack)
	stack = CreateStack([]int{1, 3, 2})
	SortStack(stack)
	PrintStack("排序后出栈顺序为：", stack)
}

// 快速创建一个栈
func CreateStack(list []int) *SliceStack {
	stack := NewSliceStack()
	for _, v := range list {
		stack.Push(v)
	}
	return stack
}

// 打印栈
func PrintStack(str string, s *SliceStack) {
	fmt.Print(str)
	for !s.IsEmpty() {
		fmt.Print(s.Pop(), "")
	}
	fmt.Println()
}

算法性能分析：这种方法的时间复杂度为O(n2)。

2.4 如何根据入栈序列判断可能的出栈序列

题目描述：输入两个整数序列，其中一个序列表示栈的push（入）顺序，判断另一个序列有没有可能是对应的pop（出）顺序。分析与解答：假如输入的push序列是1、2、3、4、5，那么3、2、5、4、1 就有可能是一个pop序列，但5、3、4、1、2 就不可能是它的一个pop序列。主要思路是使用一个栈来模拟入栈顺序，具体步骤如下：（1）把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素，然后栈顶元素出栈，pop序列移动到第二个元素。（2）如果栈顶继续等于pop序列现在的元素，则继续出栈并pop后移；否则对push序列继续入栈。（3）如果push序列已经全部入栈，但是pop序列未全部遍历，而且栈顶元素不等于当前pop元素，那么这个序列不是一个可能的出栈序列。如果栈为空，而且pop序列也全部被遍历过，则说明这是一个可能的pop序列。下图给出一个合理的pop序列的判断过程。

在上图中，（1）～（3）三步，由于栈顶元素不等于pop序列第一个元素3，因此，1，2，3依次入栈，当3入栈后，栈顶元素等于pop序列的第一个元素3，因此，第（4）步执行3出栈，接下来指向第二个pop序列2，且栈顶元素等于pop序列的当前元素，因此，第（5）步执行2出栈；接着由于栈顶元素4不等于当前pop序列5，因此，接下来（6）和（7）两步分别执行4和5入栈；接着由于栈顶元素5等于pop序列的当前值，因此，第（8）步执行5出栈，接下来（9）和（10）两步栈顶元素都等于当前pop序列的元素，因此，都执行出栈操作。最后由于栈为空，同时pop序列都完成了遍历，因此，{3，2，5，4，1}是一个合理的出栈序列。

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func IsPopSerial(push string, pop string) bool {
	pushLen := len(push)
	popLen := len(pop)
	if pushLen == 0 || popLen == 0 || pushLen != popLen {
		return false
	}
	pushIndex := 0
	popIndex := 0
	pushRune := []rune(push)
	popRune := []rune(pop)
	stack := NewSliceStack()
	for pushIndex < pushLen {
		// 把push序列依次入栈，直到栈顶元素等于pop序列的第一个元素
		stack.Push(pushRune[pushIndex])
		pushIndex++
		// 栈顶元素出栈，pop序列移动到下一个元素
		for !stack.IsEmpty() && stack.Top() == popRune[popIndex] {
			stack.Pop()
			popIndex++
		}
	}
	// 栈为空，且pop序列中元素都被遍历过
	if stack.IsEmpty() && popIndex == popLen {
		return true
	}
	return false
}

func main() {
	push := "12345"
	pop := "32541"
	if IsPopSerial(push, pop) {
		fmt.Println(pop, "是", push, "的一个pop序列")
	} else {
		fmt.Println(pop, "不是", push, "的一个pop序列")
	}
}

 算法性能分析：这种方法在处理一个合理的pop序列的时候需要操作的次数最多，即把push序列进行一次压栈和出栈操作，操作次数为2n，因此，时间复杂度为O(n)，此外，这种方法使用了额外的栈空间，因此，空间复杂度为O(n)。

2.5 如何用O(1)的时间复杂度求栈中最小元素

分析与解答：由于栈具有后进先出的特点，因此，push和pop只需要对栈顶元素进行操作。如果使用上述的实现方式，只能访问到栈顶的元素，无法得到栈中最小的元素。当然，可以用另外一个变量来记录栈底的位置，通过遍历栈中所有的元素找出最小值，但是这种方法的时间复杂度为O(n)，那么如何才能用O(1)的时间复杂度求出栈中最小的元素呢？在算法设计中，经常会采用空间换取时间的方式来提高时间复杂度，也就是说采用额外的存储空间来降低操作的时间复杂度。具体而言，在实现的时候使用两个栈结构，一个栈用来存储数据，另外一个栈用来存储栈的最小元素。实现思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入保存最小元素的栈中；在出栈的时候，如果当前出栈的元素恰好为当前栈中的最小值，则保存最小值的栈顶元素也出栈，使得当前最小值变为当前最小值入栈之前的那个最小值。为了简单起见，可以在栈中保存int类型。实现代码如下：

package main

import (
	"fmt"
	"math"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

type MinStack struct {
	// 用来存储栈中元素
	elemStack *SliceStack
	// 栈顶永远存储elemStack中最小的值
	minStack *SliceStack
}

func (p *MinStack) Push(data int) {
	p.elemStack.Push(data)
	// 更新保存最小元素的栈
	if p.minStack.IsEmpty() {
		p.minStack.Push(data)
	} else {
		if data <= p.minStack.Top().(int) {
			p.minStack.Push(data)
		}
	}
}

func (p *MinStack) Pop() int {
	topData := p.elemStack.Pop().(int)
	if topData == p.Min() {
		p.minStack.Pop()
	}
	return topData
}

func (p *MinStack) Min() int {
	if p.minStack.IsEmpty() {
		return math.MaxInt32
	} else {
		return p.minStack.Top().(int)
	}
}

func main() {
	stack := &MinStack{elemStack: &SliceStack{}, minStack: &SliceStack{}}
	stack.Push(5)
	fmt.Println("栈中最小值：", stack.Min())
	stack.Push(6)
	fmt.Println("栈中最小值：", stack.Min())
	stack.Push(2)
	fmt.Println("栈中最小值：", stack.Min())
	stack.Pop()
	fmt.Println("栈中最小值：", stack.Min())
}

算法性能分析：这种方法申请了额外的一个栈空间来保存栈中最小的元素，从而达到了用O(1)的时间复杂度求栈中最小元素的目的，但是付出的代价是空间复杂度为O(n)。

2.6 如何用两个栈模拟队列操作

分析与解答：题目要求用两个栈来模拟队列，假设使用栈A与栈B模拟队列Q，A为插入栈，B为弹出栈，以实现队列Q。再假设A和B都为空，可以认为栈A提供入队列的功能，栈B提供出队列的功能。要入队列，入栈A即可，而出队列则需要分两种情况考虑：（1）如果栈B不为空，则直接弹出栈B的数据。（2）如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈B的数据。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

type StackQueue struct {
	aStack *SliceStack
	bStack *SliceStack
}

func (p *StackQueue) Push(data int) {
	p.aStack.Push(data)
}

func (p *StackQueue) Pop() int {
	if p.bStack.IsEmpty() {
		for !p.aStack.IsEmpty() {
			p.bStack.Push(p.aStack.Pop())
		}
	}
	return p.bStack.Pop().(int)
}

func main() {
	stack := &StackQueue{aStack: &SliceStack{}, bStack: &SliceStack{}}
	stack.Push(1)
	stack.Push(2)
	fmt.Println("队列首元素为：", stack.Pop())
	fmt.Println("队列首元素为：", stack.Pop())
}

算法性能分析：这种方法入队操作的时间复杂度为O(1)，出队列操作的时间复杂度则依赖于入队与出队执行的频率。总体来讲，出队列操作的时间复杂度为O(1)，当然会有个别操作需要耗费更多的时间（因为需要从两个栈之间移动数据）。

2.7 如何设计一个排序系统

题目描述：请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户。分析与解答：本题不仅要实现队列常见的入队列与出队列的功能，而且还需要实现队列中任意一个元素都可以随时出队列，且出队列后需要更新队列用户位置的变化。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

// 用于定义对象
type User struct {
	id   int
	name string
	seq  int
}

type LoginQueue struct {
	queue *SliceQueue
}

// 进入队列尾部
func (p *LoginQueue) EnQueue(u *User) {
	p.queue.EnQueue(u)
	u.seq = p.queue.Size()
}

// 出队列
func (p *LoginQueue) DeQueue() {
	p.queue.DeQueue()
	p.UpdateSeq()
}

// 队列中的人随机离开
func (p *LoginQueue) DeQueueUser(u *User) {
	p.queue.Remove(u)
	p.UpdateSeq()
}

func (p *LoginQueue) UpdateSeq() {
	i := 1
	for _, v := range p.queue.List() {
		u := v.(*User)
		u.seq = i
		i++
	}
}
func (p *LoginQueue) PrintQueue() {
	for _, v := range p.queue.List() {
		fmt.Println(v.(*User))
	}
}
func main() {
	u1 := &User{id: 1, name: "user1"}
	u2 := &User{id: 2, name: "user2"}
	u3 := &User{id: 3, name: "user3"}
	u4 := &User{id: 4, name: "user4"}
	loginQueue := &LoginQueue{queue: NewSliceQueue()}
	loginQueue.EnQueue(u1)
	loginQueue.EnQueue(u2)
	loginQueue.EnQueue(u3)
	loginQueue.EnQueue(u4)
	loginQueue.DeQueue()       // 队首元素u1出队列
	loginQueue.DeQueueUser(u3) // 队列中间的元素u3出队列
	loginQueue.PrintQueue()

}

2.8 如何实现LRU缓存方案

题目描述LRU是Least Recently Used的缩写，它的意思是“最近最少使用”，LRU缓存就是使用这种原理实现，简单地说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉。常用于页面置换算法，是为虚拟页式存储管理中常用的算法。下面介绍如何实现LRU缓存方案。分析与解答：我们可以使用两个数据结构实现一个LRU缓存。（1）使用双向链表实现的队列，队列的最大的容量为缓存的大小。在使用的过程中，把最近使用的页面移动到队列首，最近没有使用的页面将被放在队列尾的位置。（2）使用一个哈希表，把页号作为键，把缓存在队列中的结点的地址作为值。当引用一个页面时，所需的页面在内存中，我们需要把这个页对应的结点移动到队列的前面。如果所需的页面不在内存中，我们将它存储在内存中。简单地说，就是将一个新结点添加到队列的前面，并在哈希表中更新相应的结点地址。如果队列是满的，那么就从队列尾部移除一个结点，并将新结点添加到队列的前面。实现代码如下：

package main

// Queue和Set都直接实现，Set实现了线程安全，Queue不是安全的线程
import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

type LRU struct {
	cacheSize int
	queue     *SliceQueue
	hashSet   *Set
}

// 判断缓存队列是否已满
func (p *LRU) IsQueueFull() bool {
	return p.queue.Size() == p.cacheSize
}

// 把页号为pageNum的页也缓存到队列中，同时也添加到Hash表中
func (p *LRU) EnQueue(pageNum int) {
	// 如果队列满了，需要删除队尾的缓存的页
	if p.IsQueueFull() {
		p.hashSet.Remove(p.queue.PopBack())
	}
	p.queue.EnQueueFirst(pageNum)
	// 把新缓存的结点同时添加到hash表中
	p.hashSet.Add(pageNum)
}

// 当访问某一个page的时候会调用这个函数，对于访问的page有两种情况
// 1. 如果page在缓存队列中，直接把这个结点移动到队首
// 2. 如果page不在缓存队列中，把这个page缓存到队首
func (p *LRU) AccessPage(pageNum int) {
	// page不在缓存队列中，把它缓存到队首
	if !p.hashSet.Contains(pageNum) {
		p.EnQueue(pageNum)
	} else if pageNum != p.queue.GetFront() { // page已经在缓存队列中了，移动到队首
		p.queue.Remove(pageNum)
		p.queue.EnQueueFirst(pageNum)

	}
}

func (p *LRU) PrintQueue() {
	for !p.queue.IsEmpty() {
		fmt.Print(p.queue.DeQueue(), " ")
	}
	fmt.Println()
}
func main() {
	// 假设缓存大小为3
	lru := &LRU{cacheSize: 3, queue: NewSliceQueue(), hashSet: NewSet()}
	lru.AccessPage(1)
	lru.AccessPage(2)
	lru.AccessPage(3)
	lru.AccessPage(1)
	lru.AccessPage(6)
	lru.AccessPage(7)
	// 通过上面的访问序列后，缓存的信息为
	lru.PrintQueue()
}

2.9 如何从给定的车票中找出旅程路线

题目描述：给定一趟旅途旅程中所有的车票信息，根据这个车票信息找出这趟旅程的路线。例如：给定下面的车票：（“西安”到“成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）。那么可以得到旅程路线为：北京->上海，上海->大连，大连->西安，西安->成都。假定给定的车票不会有环，也就是说有一个城市只作为终点而不会作为起点。分析与解答：对于这种题目，一般而言可以使用拓扑排序进行解答。根据车票信息构建一个图，然后找出这张图的拓扑排序序列，这个序列就是旅程的路线。但这种方法的效率不高，它的时间复杂度为O(n)。这里重点介绍另外一种更加简单的方法：hash法。主要的思路为根据车票信息构建一个map，然后从这个map中找到整个旅程的起点，接着就可以从起点出发依次找到下一站，进而知道终点。具体的实现思路为：（1）根据车票的出发地与目的地构建map。Tickets={（“西安”到“成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）}

（2）构建Tickets的逆向map如下（将旅程的起始点反向）：ReverseTickets={（“成都”到“西安”），（“上海”到“北京”），（“西安”到“大连”）， （“大连”到“上海”）}

（3）遍历Tickets，对于遍历到的key值，判断这个值是否在ReverseTickets中的key中存在，如果不存在，那么说明遍历到的Tickets中的key值就是旅途的起点。例如：“北京”在ReverseTickets的key中不存在，因此“北京”就是旅途的起点。实现代码如下：

package main

import (
	"fmt"
)

func PrintResult(input map[string]string) {
	// 用来存储把input的键与值调换后的信息
	reverseInput := map[string]string{}
	for k, v := range input {
		reverseInput[v] = k
	}
	// 找到起点
	start := ""
	for k, _ := range input {
		if _, ok := reverseInput[k]; !ok {
			start = k
			break
		}
	}
	if start == "" {
		fmt.Println("输入不合理")
	} else {
		// 从起点出发按照顺序遍历路径
		to := input[start]
		fmt.Print(start, "->", to)
		to = input[to]
		for to != "" {
			fmt.Print(",", start, "->", to)
			start = to
			to = input[to]
		}
		fmt.Println()
	}
}
func main() {
	input := map[string]string{"西安": "成都", "北京": "上海", "大连": "西安", "上海": "大连"}
	PrintResult(input)
}

算法性能分析：这种方法的时间复杂度为O(n)，空间复杂度也为O(n)。

2.10 如何从数组中找出满足a+b=c+d的两个数对

题目描述：给定一个数组，找出数组中是否有两个数对(a， b)和(c，d)，使得a+b=c+d，其中，a、b、c和d是不同的元素。如果有多个答案，打印任意一个即可。例如给定数组：{3， 4， 7， 10， 20， 9， 8}，可以找到两个数对 (3，8) 和(4， 7)，使得3+8=4+7。分析与解答：最简单的方法就是使用四重遍历，对所有可能的数对判断是否满足题目要求，如果满足则打印出来，但是这种方法的时间复杂度为O(n4)，很显然不满足要求。下面介绍另外一种方法--hash法，算法的主要思路为：以数对为单位进行遍历，在遍历过程中，把数对和数对的值存储在哈希表中（键为数对的和，值为数对），当遍历到一个键值对，如果它的和在哈希表中已经存在，那么就找到了满足条件的键值对。下面使用Map为例给出实现代码：

package main

import (
	"fmt"
)

type Pair struct {
	first  int
	second int
}

func FindPairs(arr []int) bool {
	// 键为数对的和，值为数对
	sumPair := map[int]*Pair{}
	n := len(arr)
	// 遍历数组中所有可能的数对
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			// 如果这个数对的和在map中没有，则放入map中
			sum := arr[i] + arr[j]
			if _, ok := sumPair[sum]; !ok {
				sumPair[sum] = &Pair{i, j}
			} else { // map中已经存在与sum相同的数对了，找出来并打印出来
				// 找出已经遍历过的并存储在map中和sum的数对
				p := sumPair[sum]
				fmt.Printf("(%v,%v),(%v,%v)", arr[p.first], arr[p.second], arr[i], arr[j])
				fmt.Println()
				return true
			}
		}
	}
	return false
}
func main() {
	arr := []int{3, 4, 7, 10, 20, 9, 8}
	FindPairs(arr)
}

算法性能分析：这种方法的时间复杂度为O(n2)。因为使用了双重循环，而Map的插入与查找操作实际的时间复杂度为O(1)。

第3章 二叉树3.1 二叉树基础知识二叉树（Binary Tree）也称为二分树、二元树、对分树等，它是n(n≥0)个有限元素的集合，该集合或者为空或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称为一个结点。二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。以下是一些常见的二叉树的基本概念：（1）结点的度。结点所拥有的子树的个数称为该结点的度。（2）叶子结点。度为0的结点称为叶子结点，或者称为终端结点。（3）分支结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶子结点外，其余的都是分支结点。（4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（5）路径、路径长度。如果一棵树的一串结点n1，n2，…，nk有如下关系：结点ni是ni+1的父结点（1≤i<k），就把n1，n2，…，nk称为一条由n1～nk的路径。这条路径的长度是k-1。（6）祖先、子孙。在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。（7）结点的层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。（8）树的深度。树中所有结点的最大层数称为树的深度。（9）树的度。树中各结点度的最大值称为该树的度，叶子结点的度为0。（10）满二叉树。在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称为满二叉树。（11）完全二叉树。一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。二叉树的基本性质如下：性质1：一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。性质2：一棵深度为k的二叉树中，最多具有2k-1个结点，最少有k个结点。性质3：对于一棵非空的二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个，即如果叶子结点数为n0，度数为2的结点数为n2，则有n0=n2+1。证明：用n0表示度为0（叶子结点）的结点总数，用n1表示度为1的结点总数，n2表示度为2的结点总数，n表示整个完全二叉树的结点总数。则n=n0+n1+n2，根据二叉树和树的性质，可知n=n1+2*n2+1（所有结点的度数之和+1=结点总数），根据两个等式可知n0+n1+n2=n1+2*n2+1，所以，n2=n0-1，即n0=n2+1。所以，答案为1。性质4：具有n个结点的完全二叉树的深度为‘log2 n’+1。证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2k-1-1<n≤2k-1或2k-1≤n<2k ，三遍同时取对数，于是有k-1≤log2n<k ，因为k是整数，所以，k=「log2 n」+1。性质5：对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：①如果i>1，则序号为i的结点的双亲结点的序号为i/2（其中“/”表示整除）；如果i=1，则序号为i的结点是根结点，无双亲结点。②如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。③如果2i+1≤n，则序号为i的结点的右孩子结点的序号为2i+1；如果2i+1>n，则序号为i的结点无右孩子。此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为(i-1)/2，左孩子的编号为2i+1，右孩子的编号为2i+2。例题1：一棵完全二叉树上有1001个结点，其中叶子结点的个数是多少？分析：二叉树的公式：n=n0+n1+n2=n0+n1+(n0-1)=2*n0+n1-1。而在完全二叉树中， n1只能取0或1。若n1=1，则2*n0=1001，可推出n0为小数，不符合题意；若n1=0，则2*n0-1=1001，则n0=501。所以，答案为501。例题2：如果根的层次为1，具有61个结点的完全二叉树的高度为多少？分析：根据二叉树的性质，具有n个结点的完全二叉树的深度为 +1，因此，含有61个结点的完全二叉树的高度为 +1，即应该为6层。所以，答案为6。例题3：在具有100个结点的树中，其边的数目为多少？分析：在一棵树中，除了根结点之外，每一个结点都有一条入边，因此，总边数应该是100-1，即99条。所以，答案为99。二叉树有顺序存储和链式存储两种存储结构，本章涉及的算法都采用的是链式存储结构，本章示例代码用到的二叉树的结构如下：

type BNode struct {
	Data interface{}
	LeftChild *BNode
	RightChild *BNode
}

3.2 如何把一个有序整数数组放到二叉树中

分析与解答：如果要把一个有序的整数数组放到二叉树中，那么所构造出来的二叉树必定也是一棵有序的二叉树。鉴于此，实现思路为：取数组的中间元素作为根结点，将数组分成左右两部分，对数组的两部分用递归的方法分别构建左右子树。如下图所示。

如上图所示，首先取数组的中间结点6作为二叉树的根结点，把数组分成左右两部分，然后对于数组的左右两部分子数组分别运用同样的方法进行二叉树的构建，例如，对于左半部分子数组，取中间结点3作为树的根结点，再把孩子数组分成左右两部分。依此类推，就可以完成二叉树的构建，实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

func arrayToTree(arr []int, start int, end int) *BNode {
	var root *BNode
	if end >= start {
		root = NewBNode()
		mid := (start + end + 1) / 2
		// 树的根结点为数组中间的元素
		root.Data = arr[mid]
		// 递归的用左半部分数组构造root的左子树
		root.LeftChild = arrayToTree(arr, start, mid-1)
		// 递归的用右半部分数组构造root的右子树
		root.LeftChild = arrayToTree(arr, mid+1, end)
	}
	return root
}
func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println("数组：", data)
	root := arrayToTree(data, 0, len(data)-1)
	fmt.Println("转换成树的中序遍历为：")
	PrintTreeMidOrder(root)
	fmt.Println()

}

算法性能分析：由于这种方法只遍历了一次数组，因此，算法的时间复杂度为O(n)，其中，N表示的是数组长度。

3.3 如何从顶部开始逐层打印二叉树结点数据

题目描述：给定一棵二叉树，要求逐层打印二叉树结点的数据，例如有如下二叉树：

 对这棵二叉树层序遍历的结果为1，2，3，4，5，6，7。分析与解答：为了实现对二叉树的层序遍历，就要求在遍历一个结点的同时记录下它的孩子结点的信息，然后按照这个记录的顺序来访问结点的数据，在实现的时候可以采用队列来存储当前遍历到的结点的孩子结点，从而实现二叉树的层序遍历，遍历过程如下图所示。

 在上图中，图（1）首先把根结点1放到队列里面，然后开始遍历。图（2）队列首元素（结点1）出队列，同时它的孩子结点2和结点3进队列；图（3）接着出队列的结点为2，同时把它的孩子结点4和结点5放到队列里，依此类推就可以实现对二叉树的层序遍历。

实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

// 方法功能：用层序遍历的方式打印出二叉树结点的内容
// 输出参数：root:二叉树根结点
func PrintTreeLayer(root *BNode) {
	if root == nil {
		return
	}
	var p *BNode
	queue := NewSliceQueue()
	// 树根结点进队列
	queue.EnQueue(root)
	for queue.Size() > 0 {
		p = queue.DeQueue().(*BNode)
		// 访问当前结点
		fmt.Print(p.Data, "")
		// 如果这个结点的左孩子不为空则入队列
		if p.LeftChild != nil {
			queue.EnQueue(p.LeftChild)
		}
		// 如果这个结点的右孩子不为空则入队列
		if p.RightChild != nil {
			queue.EnQueue(p.RightChild)
		}
	}
}
func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println("数组：", data)
	root := ArrayToTree(data, 0, len(data)-1)
	fmt.Println("树的层序遍历结果为：")
	PrintTreeLayer(root)
	fmt.Println()

}

PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
数组： [1 2 3 4 5 6 7 8 9 10]
树的层序遍历结果为：
6 3 9 2 5 8 10 1 4 7

算法性能分析：在二叉树的层序遍历过程中，对树中的各个结点只进行了一次访问，因此，时间复杂度为O(n)，此外，这种方法还使用了队列来保存遍历的中间结点，所使用队列的大小取决于二叉树中每一层中结点个数的最大值。具有N个结点的完全二叉树的深度为h=log2n+1。而深度为h的这一层最多的结点个数为2h-1=n/2。也就是说队列中可能的最多的结点个数为n/2。因此，这种算法的空间复杂度为O(n)。引申：用空间复杂度为O(1)的算法来实现层序遍历。上面介绍的算法的空间复杂度为O(n)，显然不满足要求。通常情况下，提高空间复杂度都是要以牺牲时间复杂度作为代价的。对于本题而言，主要的算法思路为：不使用队列来存储每一层遍历到的结点，而是每次都会从根结点开始遍历。把遍历二叉树的第k层的结点，转换为遍历二叉树根结点的左右子树的第k-1层结点。算法如下：

func printAtLevel(root *BNode, level int) int {
	if root == nil || level < 0 {
		return 0
	} else if level == 0 {
		fmt.Println(root.Data)
		return 1
	} else {
		// 把打印根节点level层的结点转换为求解根结点的孩子结点的level-1层的结点
		return printAtLevel(root.LeftChild, level-1) + printAtLevel(root.RightChild, level-1)
	}
}

通过上述算法，可以首先求解出二叉树的高度h，然后调用上面的函数h次就可以打印出每一层的结点。

3.4 如何求一棵二叉树的最大子树和

题目描述：给定一棵二叉树，它的每个结点都是正整数或负整数，如何找到一棵子树，使得它所有结点的和最大？分析与解答：要求一棵二叉树的最大子树和，最容易想到的办法就是针对每棵子树，求出这棵子树中所有结点的和，然后从中找出最大值。恰好二叉树的后序遍历就能做到这一点。在对二叉树进行后序遍历的过程中，如果当前遍历的结点的值与其左右子树和的值相加的结果大于最大值，则更新最大值。如下图所示：

 在上面这个图中，首先遍历结点-1，这个子树的最大值为-1，同理，当遍历到结点9时，子树的最大值为9，当遍历到结点3的时候，这个结点与其左右孩子结点值的和（3-1+9=11）大于最大值（9）。因此，此时最大的子树为以3为根结点的子树，依此类推直到遍历完整棵树为止。实现代码如下：

package main

import (
	"fmt"
	"math"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

var maxSum = math.MinInt64

// 求最大子树
func FindMaxSubTree(root *BNode, maxRoot *BNode) int {
	if root == nil {
		return 0
	}
	// 求root左子树所有结点的和
	lmax := FindMaxSubTree(root.LeftChild, maxRoot)
	// 求root左子树所有结点的和
	rmax := FindMaxSubTree(root.RightChild, maxRoot)
	sum := lmax + rmax + root.Data.(int)
	// 以root为根的子树的和大于前面求出的最大值
	if sum > maxSum {
		maxSum = sum
		maxRoot.Data = root.Data
	}
	// 返回以root为根结点的子树的所有结点的和
	return sum
}
func CreateTree() *BNode {
	root := &BNode{}
	node1 := &BNode{}
	node2 := &BNode{}
	node3 := &BNode{}
	node4 := &BNode{}
	root.Data = 6
	node1.Data = 3
	node2.Data = -7
	node3.Data = -1
	node4.Data = 9
	root.LeftChild = node1
	root.RightChild = node2
	node1.LeftChild = node3
	node1.RightChild = node4
	return root

}
func main() {
	// 构造二叉树
	root := CreateTree()
	// 最大子树的根结点
	maxRoot := &BNode{}
	FindMaxSubTree(root, maxRoot)
	fmt.Println("最大子树和为：", maxSum)
	fmt.Println("对应子树的根结点为：", maxRoot.Data)
}

程序的运行结果为

PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
最大子树和为： 11
对应子树的根结点为： 3

算法性能分析：这种方法与二叉树的后序遍历有相同的时间复杂度，即为O(n)，其中，N为二叉树的结点个数。

3.5 如何判断两棵二叉树是否相等

题目描述：两棵二叉树相等是指这两棵二叉树有着相同的结构，并且在相同位置上的结点有相同的值。如何判断两棵二叉树是否相等？分析与解答：如果两棵二叉树root1、root2相等，那么root1与root2结点的值相同，同时它们的左右孩子也有着相同的结构，并且对应位置上结点的值相等，即root1.data==root2.data，并且root1的左子树与root2的左子树相等，root1的右子树与root2的右子树相等。根据这个条件，可以非常容易地写出判断两棵二叉树是否相等的递归算法。实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

// 判断两棵树是否相等
// 参数：root1与root2分别为两颗二叉树的根结点
// 返回值：true:如果两棵树相等则返回true，否则返回false
func IsEqual(root1 *BNode, root2 *BNode) bool {
	if root1 == nil && root2 == nil {
		return true
	}
	if root1 == nil && root2 != nil {
		return false
	}
	if root1 != nil && root2 == nil {
		return false
	}
	if root1.Data == root2.Data {
		return IsEqual(root1.LeftChild, root2.LeftChild) && IsEqual(root1.RightChild, root2.RightChild)
	}
	return false
}

func CreateTree() *BNode {
	root := &BNode{}
	node1 := &BNode{}
	node2 := &BNode{}
	node3 := &BNode{}
	node4 := &BNode{}
	root.Data = 6
	node1.Data = 3
	node2.Data = -7
	node3.Data = -1
	node4.Data = 9
	root.LeftChild = node1
	root.RightChild = node2
	node1.LeftChild = node3
	node1.RightChild = node4
	return root

}
func main() {
	// 构造二叉树
	root1 := CreateTree()
	root2 := CreateTree()

	if IsEqual(root1, root2) {
		fmt.Println("这两颗树相等")
	} else {
		fmt.Println("这两棵树不相等")
	}
}

程序的运行结果为

PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
这两颗树相等

算法性能分析：这种方法对两棵树只进行了一次遍历，因此，时间复杂度为O(n)。此外，这种方法没有申请额外的存储空间。

3.6 如何把二叉树转换为双向链表

题目描述：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整结点的指向。例如：

分析与解答：由于转换后的双向链表中结点的顺序与二叉树的中序遍历的顺序相同，因此，可以对二叉树的中序遍历算法进行修改，通过在中序遍历的过程中修改结点的指向来转换成一个排序的双向链表。实现思路如下图所示：假设当前遍历的结点为root，root的左子树已经被转换为双向链表（如下图（1）所示），使用两个变量pHead与pEnd分别指向链表的头结点与尾结点。那么在遍历root结点的时候，只需要将root结点的lchild指向pEnd，把pEnd的rchild（右）指向root；此时root结点就被加入到双向链表里了，因此，root变成了双向链表的尾结点。对于所有的结点都可以通过同样的方法来修改结点的指向。因此，可以采用递归的方法来求解，在求解的时候需要特别注意递归的结束条件以及边界情况（例如双向链表为空的时候）。

实现代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype" // 引入定义的数据结构
)

// 方法功能：把二叉树转换为双向列表
// 输入参数：root:二叉树根结点
var pHead *BNode
var pEnd *BNode

func InOrderBSTree(root *BNode) {
	if root == nil {
		return
	}
	// 转换root的左子树
	InOrderBSTree(root.LeftChild)
	// 使当前结点的左孩子指向双向链表中最后一个结点
	root.LeftChild = pEnd
	// 双向列表为空，当前遍历的结点为双向链表的头结点
	if pEnd == nil {
		pHead = root
	} else { // 使双向链表中的最后一个结点的右孩子指向当前结点
		pEnd.RightChild = root
	}
	pEnd = root // 将当前结点设为双向链表中最后一个结点
	// 转换root的右子树
	InOrderBSTree(root.RightChild)
}
func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7}
	fmt.Println("数组：", data)
	root := ArrayToTree(data, 0, len(data)-1)
	InOrderBSTree(root)
	fmt.Print("转换后双向链表正向遍历：")
	for cur := pHead; cur != nil; cur = cur.RightChild {
		fmt.Print(cur.Data, "")
	}
	fmt.Println()
	fmt.Print("转换后双向链表逆向遍历：")
	for cur := pEnd; cur != nil; cur = cur.LeftChild {
		fmt.Print(cur.Data, "")
	}
	fmt.Println()
}

程序的运行结果为

PS D:\Workspace\Go\src\projects\gin-demo> go run test.go
数组： [1 2 3 4 5 6 7]
转换后双向链表正向遍历：1234567
转换后双向链表逆向遍历：7654321

算法性能分析：这种方法与二叉树的中序遍历有着相同的时间复杂度O(n)。此外，这种方法只用了两个额外的变量pHead与pEnd来记录双向链表的首尾结点，因此，空间复杂度为O(1)。

3.7 如何判断一个数组是否是二元查找树后序遍历的序列

题目描述：输入一个整数数组，判断该数组是否是某二元查找树的后序遍历的结果。如果是，那么返回true，否则返回false。例如数组{1，3，2，5，7，6，4}就是下图中二叉树的后序遍历序列。

分析与解答：二元查找树的特点是：对于任意一个结点，它的左子树上所有结点的值都小于这个结点的值，它的右子树上所有结点的值都大于这个结点的值。根据它的这个特点以及二元查找树后序遍历的特点，可以看出，这个序列的最后一个元素一定是树的根结点（上图中的结点4），然后在数组中找到第一个大于根结点4的值5，那么结点5之前的序列（1，3，2）对应的结点一定位于结点4的左子树上，结点5（包含这个结点）后面的序列一定位于结点4的右子树上（也就是说结点5后面的所有值都应该大于或等于4）。对于结点4的左子树遍历的序列{1，3，2}以及右子树的遍历序列{5，7，6}可以采用同样的方法来分析，因此，可以通过递归方法来实现，实现代码如下：

package main

import "fmt"

// 方法功能：判断一个数组是否是二元查找树的后续遍历序列
// 输入参数：arr:数组
// 返回值：true:是，否则返回false
func IsAfterOrder(arr []int, start int, end int) bool {
	if arr == nil {
		return false
	}
	// 数组的最后一个结点必定是根结点
	root := arr[end]
	var i, j int
	// 找到第一个大于root的值，那么前面所有的结点都位于root的左子树上
	for i = start; i < end; i++ {
		if arr[i] > root {
			break
		}
	}
	// 如果序列是后续遍历的序列，那么从i开始的所有值都应该大于根结点root的值
	for j = i; j < end; j++ {
		if arr[j] < root {
			return false
		}
	}
	leftIsAfterOrder := true
	rightIsAfterOrder := true
	// 判断小于root值的序列是否是某一二元查找树的后续遍历
	if i > start {
		leftIsAfterOrder = IsAfterOrder(arr, start, i-1)
	}
	// 判断大于root值的序列是否是某一二元查找树的后续遍历
	if j < end {
		rightIsAfterOrder = IsAfterOrder(arr, i, end)
	}
	return leftIsAfterOrder && rightIsAfterOrder
}

func main() {
	data := []int{1, 3, 2, 5, 7, 6, 4}
	fmt.Println("数组：", data)
	result := IsAfterOrder(data, 0, len(data)-1)
	if result {
		fmt.Println("是某一二元查找树的后续遍历序列")
	}
}

程序的运行结果为

PS D:\Workspace\Go\src\projects\demo> go run main.go
数组： [1 3 2 5 7 6 4]
是某一二元查找树的后续遍历序列

算法性能分析：这种方法对数组只进行了一次遍历，因此，时间复杂度O(n)。

3.8 如何找出排序二叉树上任意两个结点的最近共同父结点

难度系数：★★★☆☆

被考查系数：★★★★☆

题目描述：对于一棵给定的排序二叉树，求两个结点的共同父结点，例如在下图中，结点1和结点5的共同父结点为3。

分析与解答：方法一：路径对比法对于一棵二叉树的两个结点，如果知道了从根结点到这两个结点的路径，就可以很容易地找出它们最近的公共父结点。因此，可以首先分别找出从根结点到这两个结点的路径（例如上图中从根结点到结点1的路径为6->3->2->1，从根结点到结点5的路径为6->3->5）；然后遍历这两条路径，只要是相等的结点都是它们的父结点，找到最后一个相等的结点即为离它们最近的共同父结点，在这个例子中，结点3就是它们共同的父结点。为了便于理解，这里仍然使用3.2节中构造的二叉树的方法。示例代码如下：

package main

import (
	"fmt"

	. "github.com/isdamir/gotype"
)

//方法功能:获取二叉树从根结点 root 到node 结点的路径
//输入参数:root:根结点;node:二叉树中的某个结点;s:用来存储路径的栈
//返回值:node在root 的子树上，或node==root 时返回 true，否则返回 false
func GetPathFromRoot(root *BNode, node *BNode, s *SliceStack) bool {
	if root == nil {
		return false
	}
	// fmt.Println("a", root.Data.(int), node.Data.(int))
	if root.Data.(int) == node.Data.(int) {
		s.Push(root)
		return true
	}
	//如果node结点在 root 结点的左子树或右子树上
	//那么root 就是 node 的祖先结点，把它加到栈里
	if GetPathFromRoot(root.LeftChild, node, s) || GetPathFromRoot(root.RightChild, node, s) {
		s.Push(root)
		return true
	}
	return false
}

//方法功能:查找二叉树中两个结点最近的共同父结点
//输入参数:root:根结点;nodel与 node2 为二叉树中两个结点
//返回值:nodel与node2 最近的共同父结点
func FindParentNode(root, node1, node2 *BNode) *BNode {
	stack1 := NewSliceStack() // 保存从root到node1的路径
	stack2 := NewSliceStack() // 保存从root到node2的路径
	// 获取从root到node1的路径
	GetPathFromRoot(root, node1, stack1)
	// 获取从root到node2的路径
	GetPathFromRoot(root, node2, stack2)

	var commonParent *BNode
	for t1, t2 := stack1.Pop().(*BNode), stack2.Pop().(*BNode); t1 != nil && t2 != nil && t1.Data.(int) == t2.Data.(int); {
		commonParent = t1
		t1 = stack1.Pop().(*BNode)
		t2 = stack2.Pop().(*BNode)
	}
	return commonParent
}

func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println("数组：", data)
	root := ArrayToTree(data, 0, len(data)-1)
	node1 := root.LeftChild.LeftChild.LeftChild
	node2 := root.LeftChild.RightChild
	result := FindParentNode(root, node1, node2)
	if result != nil {
		fmt.Println(node1.Data, "与", node2.Data, "的最近公共父结点为", result.Data)
	} else {
		fmt.Println("没有公共父结点")
	}
}

 程序的运行结果为

PS D:\Workspace\Go\src\projects\demo> go run main.go
数组： [1 2 3 4 5 6 7 8 9 10]
1 与 5 的最近公共父结点为 3

算法性能分析：当获取二叉树从根结点root到node结点的路径时，最坏的情况就是把树中所有结点都遍历了一遍，这个操作的时间复杂度为O(n)，再分别找出从根结点到两个结点的路径后，找它们最近的公共父结点的时间复杂度也为O(n)，因此，这种方法的时间复杂度为O(n)。此外，这种方法用栈保存了从根结点到特定结点的路径，在最坏的情况下，这个路径包含了树中所有的结点，因此，空间复杂度也为O(n)。很显然，这种方法还不够理想。下面介绍另外一种能降低空间复杂度的方法。

方法二：结点编号法根据3.1节中介绍的性质5，可以把二叉树看成是一棵完全二叉树（不管实际的二叉树是否为完全二叉树，二叉树中的结点都可以按照完全二叉树中对结点编号的方式进行编号），下图为对二叉树中的结点按照完全二叉树中结点的编号方式进行编号后的结果，结点右边的数字为其对应的编号。

根据3.1节性质5可以知道，一个编号为n的结点，它的父亲结点的编号为n/2。假如要求node1与node2的最近的共同父结点，首先把这棵树看成是一棵完全二叉树（不管结点是否存在），分别求得这两个结点的编号n1，n2。然后每次找出n1与n2中较大的值除以2，直到n1==n2为止，此时n1或n2的值对应结点的编号就是它们最近的共同父结点的编号，接着可以根据这个编号信息找到对应的结点。具体方法为：通过观察二叉树中结点的编号可以发现：首先把根结点root看成1，求root的左孩子编号的方法为把root对应的编号看成二进制，然后向左移一位，末尾补0，如果是root的右孩子，则末尾补1，因此，通过结点位置的二进制码就可以确定这个结点。例如结点3的编号为2（二进制10），它的左孩子的求解方法为：10向左移一位末尾补0，可以得到二进制100（十进制4），位置为4的结点的值为2。从这个特性可以得出通过结点位置信息获取结点的方法，例如要求位置4的结点，4的二进制码为100，由于1代表根结点，接下来的一个0代表是左子树root.lchild，最后一个0也表示左子树root.lchild.lchild，通过这种方法非常容易根据结点的编号找到对应的结点。实现代码如下：

package main

import (
	"fmt"
	"math"

	. "github.com/isdamir/gotype"
)

//方法功能:获取二叉树从根结点 root 到node 结点的编号
//输入参数:root:根结点;node:待查找结点;number：node结点在二叉树中的编号
//返回值:true：找到该结点的位置，否则返回 false
func getNumber(root *BNode, node *BNode, number int) (bool, int) {
	if root == nil {
		return false, number
	}

	if root.Data == node.Data {
		return true, number
	}
	num := 2 * number
	//node 结点在 root 的左子树中，左子树编号为当前结点编号的2倍
	if b, num := getNumber(root.LeftChild, node, num); b {
		return true, num
	} else {
		//node 结点在 root 的右子树中，右子树编号为当前结点编号的2倍加1
		num = 2*number + 1
		return getNumber(root.RightChild, node, num)
	}
}

func getNodeFromNum(root *BNode, number int) *BNode {
	if root == nil || number < 0 {
		return nil
	} else if number == 1 {
		return root
	}
	// 结点编号对应二进制的位数(最高位一定为1，由于根结点代表 1)
	ll := (uint)(math.Log(float64(number)) / math.Log(2.0))
	// 去掉根结点表示的1
	number -= 1 << ll
	for ; ll > 0; ll-- {
		//如果这一位二进制的值为 1，那么编号为 number 的结点必定在当前结点的右子树上
		if ((1 << (ll - 1)) & number) == 1 {
			root = root.RightChild
		} else {
			root = root.LeftChild
		}
	}
	return root
}

// 查找二叉树中两个结点最近的共同父结点、
func FindParentNodeNum(root, node1, node2 *BNode) *BNode {
	num1 := 1
	num2 := 1
	_, num1 = getNumber(root, node1, num1)
	_, num2 = getNumber(root, node2, num2)
	//找出编号为num1和num2的共同父结点
	for num1 != num2 {
		if num1 > num2 {
			num1 /= 2
		} else {
			num2 /= 2
		}
	}
	// numl就是它们最近的公共父结点的编号，通过结点编号找到对应的结点
	return getNodeFromNum(root, num1)
}
func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println("数组：", data)
	root := ArrayToTree(data, 0, len(data)-1)
	node1 := root.LeftChild.LeftChild.LeftChild
	node2 := root.LeftChild.RightChild
	result := FindParentNodeNum(root, node1, node2)
	if result != nil {
		fmt.Println(node1.Data, "与", node2.Data, "的最近公共父结点为", result.Data)
	} else {
		fmt.Println("没有公共父结点")
	}
}

算法性能分析：这种方法的时间复杂度也为O(n)，与方法一相比，在求解的过程中只用了个别的几个变量，因此，空间复杂度为O(1)。方法三：后序遍历法很多与二叉树相关的问题都可以通过对二叉树的遍历方法进行改装而求解。对于本题而言，可以通过对二叉树的后序遍历进行改编而得到。具体思路为：查找结点node1与结点node2的最近共同父结点可以转换为找到一个结点node，使得node1与node2分别位于结点node的左子树或右子树中。例如在前图中，结点1与结点5的最近共同父结点为结点3，因为结点1位于结点3的左子树上，而结点5位于结点3的右子树上。实现代码如下：

把方法一中的FindParentNode替换为本方法的FindParentNode方法可以得到同样的输出结果。算法性能分析：这种方法与二叉树的后序遍历方法有着相同的时间复杂度为O(n)。引申：如何计算二叉树中两个结点的距离？

【出自腾讯面试题】题目描述：在没有给出父结点的条件下，计算二叉树中两个结点的距离。两个结点之间的距离是从一个结点到达另一个结点所需的最小的边数。例如：给出下面的二叉树：

Dist(4，5)=2，Dist(4，6)=4。分析与解答：对于给定的二叉树root，只要能找到两个结点n1与n2最近的公共父结点parent，那么就可以通过下面的公式计算出这两个结点的距离：Dist(n1， n2)=Dist(root， n1)+Dist(root，n2)-2*Dist(root， parent)

3.9 如何复制二叉树

难度系数：★★★☆☆被考查系数：★★★★☆题目描述：给定一个二叉树根结点，复制该树，返回新建树的根结点。分析与解答：用给定的二叉树的根结点root来构造新的二叉树的方法为：首先创建新的结点dupTree，然后根据root结点来构造dupTree结点（dupTree.data=root.data），最后分别用root的左右子树来构造dupTree的左右子树。根据这个思路可以实现二叉树的复制，使用递归方式实现的代码如下： 

package main

import (
	"fmt"

	. "github.com/isdamir/gotype"
)

func DupTree(root *BNode) *BNode {
	if root == nil {
		return nil
	}
	// 二叉树根结点
	dupTree := NewBNode()
	dupTree.Data = root.Data
	// 复制左子树
	dupTree.LeftChild = DupTree(root.LeftChild)
	// 复制左子树
	dupTree.RightChild = DupTree(root.RightChild)
	return dupTree
}
func main() {
	data := []int{-1, 3, 9, 6, -7}
	fmt.Println("数组:", data)
	root := ArrayToTree(data, 0, len(data)-1)
	dupRoot := DupTree(root)
	fmt.Print("原始二叉树中序遍历:")
	PrintTreeMidOrder(root)
	fmt.Println()
	fmt.Print("新的二叉树中序遍历:")
	PrintTreeMidOrder(dupRoot)
	fmt.Println()
}

程序的运行结果为

PS D:\Workspace\Go\src\projects\demo> go run main.go
数组: [-1 3 9 6 -7]
原始二叉树中序遍历:-1 3 9 6 -7 
新的二叉树中序遍历:-1 3 9 6 -7

算法性能分析：这种方法对给定的二叉树进行了一次遍历，因此，时间复杂度为O(n)，此外，这种方法需要申请N个额外的存储空间来存储新的二叉树。

3.10 如何在二叉树中找出与输入整数相等的所有路径

难度系数：★★★★☆被考查系数：★★★★☆题目描述：从树的根结点开始往下访问一直到叶子结点经过的所有结点形成一条路径。找出所有的这些路径，使其满足这条路径上所有结点数据的和等于给定的整数。例如：给定如下二叉树与整数8，满足条件的路径为6->3->-1(6+3-1=8)。

 

分析与解答：可以通过对二叉树的遍历找出所有的路径，然后判断各条路径上所有结点的值的和是否与给定的整数相等，如果相等，则打印出这条路径。具体实现方法可以通过对二叉树进行先序遍历来实现，实现思路为：对二叉树进行先序遍历，把遍历的路径记录下来，当遍历到叶子结点时，判断当前的路径上所有结点数据的和是否等于给定的整数，如果相等则输出路径信息，示例代码如下：