【记录】算法 - C/C++版

基础

输入输出

【输入输出格式 - 算法笔记P19】

输入输出使用scanf和printf。（因为scanf和printf的运行速度比cin和cout快）

异或

相异为1，相同为0。
N^0=N，NN=0。
满足交换律和结合律。

// 数组中有一个数只出现奇数次，其余都出现偶数次。请找出这个数。 
// leetcode-136 
// 时间复杂度O(n)，空间复杂度O(1)
int findNum(vector<int>& nums){
	int res = 0;
	for(int n : nums){
		res ^= n;
	}
	return res;
}
// 数组中有两个数只出现奇数次，其余都出现偶数次。请找出这两个数。 
// leetcode-260 
// 时间复杂度O(n)，空间复杂度O(1)
vector<int> findNums(vector<int>& nums){
	int eor = 0;
	for(int n : nums){
		eor ^= n;
	}
	// eor=a^b，且不等于0。
	// eor&（eor的补码）找出eor二进制表示中为1的最低位。
	// 判断eor是不是INT_MIN，如果等于INT_MIN，取反会溢出。
	int right = eor == INT_MIN ? eor : eor & (-eor);
	int one = 0; // 得到a或b。
	for(int n : nums){
		// 根据right位的不同分类异或。
		if(n & right){
			one ^= n;
		}
	}
	vector<int> res;
	res.push_back(one);
	res.push_back(one^eor);
	return res;
}
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

交换

void swap(vector<int>& nums, int i, int j){
	// 临时变量
	int temp = nums[i];
	num[i] = nums[j];
	nums[j] = temp;
	
	// 加减（定义了加减法的数据结构才能用）
	nums[i] = nums[i] + nums[j];
	nums[j] = nums[i] - nums[j];
	nums[i] = nums[i] - nums[j];
	
	// 异或（地址值i和j必须不同，但地址所存储的值可以一样（会将该地址所存储的值抹为0，相当于自己地址值里的内容跟自己地址值里的内容异或=0））
	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归

master公式

T(N) = a*T(N/b) + O(N^d)
适用于子问题等规模的递归，求解母问题的时间复杂度。
（1）log(b, a) > d => 复杂度为O( N^log(b, a) )
（2）log(b, a) = d => 复杂度为O( N^d * logN)
（3）log(b, a) < d => 复杂度为O( N^d )

随机数

#include 
#include 
...
int main(){
	// 生成随机种子
	srand((unsigned)time(NULL));
	// 生成随机数[0, RAND_MAX]
	cout << rand() << endl;
	// [0, 1]
	cout << rand() % 2 << endl;
	cout << rand() / RAND_MAX << endl;
	// [x, y]
	cout << rand() % (y-x) + x << endl;
	cout << (int)round(1.0 * rand() / RAND_MAX * (y - x) + x) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

排序

基于比较的排序

选择排序

当前指向i位置，每次从i之后的序列中选出最小值，交换i和最小值。
时间复杂度O（n^2）
空间复杂度O（1）
不稳定

void selection(vector<int>& nums){
	if(nums.size() < 2) return;
	// 长度n，下标0～n-1
	// 遍历i～n-2
	for(int i = 0; i < nums.size()-1; i++){
		int min = i;
		// 遍历i+1～n-1
		for(int j = i + 1; j < nums.size(); j++){
			min = nums[j] < nums[min] ? j : min;
		}
		swap(nums, i, min);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

冒泡排序

从前往后，两两比较，大的往后放，每次比较后冒出一个最大的元素。
时间复杂度O（n^2）
空间复杂度O（1）
稳定

void bubbleSort(vector<int>& nums){
	if(nums.size() < 2) return;
	// i放每趟排序后冒出来的元素
	for(int i = nums.size()-1; i > 0; i--){
		// 遍历0～i-1
		for(int j = 0; j < i; j++){
			if(nums[j] > nums[j+1]) swap(nums, j, j+1);
		}
	}
}
1
2
3
4
5
6
7
8
9
10

插入排序

将元素从后往前插入已排序序列中，比较直到前一个元素比元素小结束。
时间复杂度O（n^2）
空间复杂度O（1）
稳定

void insertSort(vector<int>& nums){
	if(nums.size() < 2) return;
	// i指向待插入元素。
	for(int i = 1; i < nums.size(); i++){
		// j指向i前面元素，比较j和j+1。
		for(int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--){
			swap(nums, j, j+1);	
		}
	}
}
1
2
3
4
5
6
7
8
9
10

归并排序

分成左右两序列，使左右序列分别有序；合并左右序列，小的插入result，指针后移。
时间复杂度O(NlogN)
空间复杂度O(N)
稳定

void merge(vector<int>& arr, int L, int mid, int R){
	vector<int> result(R-L+1);
	// 数组版本
	// int result[R-L+1];
	int i = 0;// 指向result数组当前要放入元素的位置
	int p1 = L;// 指向左序列当前遍历到哪里
	int p2 = mid + 1;// 指向右序列当前遍历到哪里
	while(p1 <= M && p2 <= R){
		// 注意是<=（相等时优先把左序列插入）
		result[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}
	// 遍历结束还有元素未插入
	while(p1 <= M){
		result[i++] = arr[p1++];
	}
	while(p2 <= R){
		result[i++] = arr[p2++];
	}
	for(int j = 0; j < i; j++){
		arr[L+j] = result[j];
	}
}
void process(vector<int>& arr, int L, int R){
	if(L == R) return;
	//mid = L + (R-L)/2；为了防止溢出，mid = L + (R-L)/2；位运算更快。
	int mid = L + ((R - L) >> 1);
	process(arr, L, mid);
	process(arr, mid+1, R);
	merge(arr, L, mid, R);
}
void mergeSort(vector<int>& nums){
	if(nums.size() < 2) return;
	process(nums, 0, nums.size()-1);
}


// 应用 
// 小和问题：在一个数组中，遍历每个数，把每个数左边比当前数小的数累加起来，叫做这个数组的小和。
int merge(vector<int>& arr, int L, int mid, int R){
	vector<int> result(R-L+1);
	int i = 0;
	int p1 = L;
	int p2 = mid+1;
	int res = 0;
	while(p1 <= mid && p2 <= R){
		res += arr[p1] < arr[p2] ? (R-p2+1) * arr[p1] : 0;
		// 注意是<（优先让右序列插入，保证p2指向正确、小和正确）
		result[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	}
	while(p1 <= mid){
		result[i++] = arr[p1++];
	}
	while(p2 <= R){
		result[i++] = arr[p2++];
	}
	for(int j = 0; j < i; j++){
		arr[L+j] = result[j];
	}
	return res;
}
int process(vector<int>& arr, int L, int R{
	if(L == R) return 0;
	int mid = L + ((R-L)>>1);
	return process(nums, L, mid)
		+ process(nums, mid+1, R)
		+ merge(nums, L, mid, R);
}
int smallSum(vector<int>& nums){
	if(nums.size() < 2) return 0;
	return process(nums, 0, nums.size()-1);
}
// 逆序对问题：在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请求出逆序对的总数。 
// leetcode-剑指offer51
int merge(vector<int>& nums, int l, int mid, int r){
	vector<int> result(r-l+1);
	int i = 0;
	int p1 = l;
	int p2 = mid+1;
	int res = 0;
	while(p1 <= mid && p2 <= r){
		res += nums[p1] > nums[p2] ? r-p2+1 : 0;
		result[i++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
	}
	while(p1 <= mid){
		result[i++] = nums[p1++];
	}
	while(p2 <= r){
		result[i++] = nums[p2++];
	}
	for(p1 = 0; p1 < i; p1++){
		nums[l+p1] = result[p1];
	}
	return res;
}
int process(vector<int>& nums, int l, int r) {
	if(l == r) return 0;
	int mid = l + ((r-l)>>1);
	return process(nums, l, mid)
		+ process(nums, mid+1, r)
		+ merge(nums, l, mid, r);
}
int reversePairs(vector<int>& nums) {
	if(nums.size() < 2) return 0;
	return process(nums, 0, nums.size()-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
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

快速排序

时间复杂度O(NlogN)
空间复杂度O(logN)
不稳定

// 问题1：给定一个数组arr和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。 
vector<int> divide(vector<int>& arr, int num){
	int i = -1;// 指向<=区的最后一个元素
	int p = 0;
	while(p < arr.size()){
		// <=num, 和i的下一个数交换（插入<=区，<=区右扩）
		if(arr[p] <= num){
			swap(arr, ++i, p);
		}
		// >num，不做处理

		p++;
	}
	return arr;
}

// 荷兰国旗问题：给定一个数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
vector<int> dutchNationalFlag(vector<int> arr, int num){
	int l = -1;
	int b = arr.size();
	int p = 0;
	while(p < arr.size()){
		// 
		if(arr[p] < num){
			swap(arr, p++, ++l);
		}
		// =num，p右移。
		else if(arr[p] == num){
			p++;
		}
		// >num，和j的前一个数交换（>区左扩），p不动（交换后p还未被比较过）
		else{
			swap(arr, p, b);
		}
	}
	return arr;
}

//快排1.0：最后一个数为num，以问题1为partition算法，不断递归。
//快排2.0：最后一个数为num，以荷兰国旗问题为partition算法，不断递归。
//快排3.0：随机一个数为num，以荷兰国旗问题为partition算法，不断递归。
vector<int> partition(vector<int>& nums, int l, int r){
	int i = l - 1;
	int j = r;// r位置是标杆
	int p = l;
	while(p < j){
		if(nums[p] < nums[r]){
			swap(nums, p++, ++i);
		}else if(nums[p] == nums[r]){
			p++;
		}else{
			swap(nums, p, --j);
		}
	}
	// >区的左边界和标杆换位置
	swap(nums, j, r);
	// 返回=区的左右边界
	vector<int> res {i+1, j};
	return res;
	
}
vector<int> process(vector<int>& nums, int l, int r){
	if(l < r){
		// 挑一个随机数和r交换做标杆
		swap(nums, round(1.0*rand()/RAND_MAX*(r-l)+l, r);
		// p[0]是=区的左边界，p[1]是=区的右边界
		vector<int> p = partition(nums, l, r);
		// <区再做快排
		process(nums, l, p[0]-1);
		// >区再做快排
		process(nums, p[1]+1, r);
	}
	return nums;
}
vector<int> quickSort(vector<int>& nums){
	if(nums.size() < 2) return nums;
	return process(nums, 0, nums.size()-1);
}

// 优化：样本数<60使用插入排序；其余使用快排。
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80

堆排序

时间复杂度O(NlogN)
空间复杂度O(1)
不稳定
优先队列结构就是堆结构。

// 完全二叉树中，（结点下标为i），i结点的父结点为(i-1)/2，左孩子2i+1，右孩子2i+2。

// 给了个大根堆，从index位置开始往上调整成大根堆。 
// 不断跟父节点比较，比父节点大上浮。 
// 时间复杂度O(logN)
void heapInsert(vector<int>& arr, int index){
	// 比父亲小 或 我的父亲就是我自己 时跳出循环。
	while(arr[index] > arr[(index-1)/2]){
		swap(arr, index, (index-1)/2);
		index = (index - 1)/2;
	}

}

// 给了个大根堆，从index位置开始往下调整成大根堆。 
// 不断跟子节点较大的比较，比子节点小下沉。 
// 时间复杂度O(logN)
void heapify(vector<int>& arr, int index, int heapSize){
	int lchild = index*2+1;
	while(lchild < heapSize){
		// 左右孩子进行比较
		int bigOne = lchild+1 < heapSize && arr[lchild] < arr[lchild+1] ? lchild+1 : lchild;
		// 左右孩子中较大的和父亲进行比较
		bigOne = arr[bigOne] > arr[index] ? bigOne : index;
		if(bigOne == index) break;
	
		swap(arr, bigOne, index);
		index = bigOne;
		lchild = index * 2 + 1;
	}
}

// 给了个大根堆，把index位置改成某个数num，要求调整成大根堆。 
// num和arr[index]进行比较，如果numarr[index]往上调整。

// 堆排序
void heapSort(vector<int>& arr){
	if(arr.size() < 2) return;
	// 从0位置开始插入, 建立大根堆
	// for(int i = 0; i < arr.size(); i++){
		// heapInsert(arr, i);
	// }

	int heapSize = arr.size();
	// 倒序遍历，向下调整大根堆
	for(int i = arr.size()-1; i >= 0; i--){
		heapify(arr, i, heapSize);
	}

	// 不断把最大的摘下来，放在最后
	swap(arr, 0, --heapSize);
	while(heapSize > 0){
		heapify(arr, 0, heapSize);
		swap(arr, 0, --heapSize);
	}
}

// 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
void sortedArrDistanceLessK(vector<int>& arr, int k){
	priority_queue<int> heap;
	int index = 0;// 指向数组遍历到哪
	// 把数组前k个数放入堆内，调整堆。
	// 求出数组长度和k中的最小值（防止k>>数组长度）
	for(; index < min(arr.size() , k); index++){
		heap.push(arr[index]);
	}
	int i = 0;// 指向结果放到哪
	// 不断把第k+1个数放进堆里，调整堆，弹出堆顶
	for(; index < arr.size(); i++, index++){
		heap.push(arr[index]);
		// 弹出堆顶，放在i位置上
		arr[i] = heap.top();
		heap.pop();
	}
	while(!heap.empty()){
		arr[i++] = heap.top();
		heap.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
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
67
68
69
70
71
72
73
74
75
76
77
78
79

非基于比较的排序

根据数据对象决定排序方法。

计数排序

建立数组，下标即为数字，统计数字出现的频率。

桶排序（基数排序）

不稳定

#include 
const radix = 10;
int getDigit(int x, int d){
	return ((x / pow(10, d-1))%10);
}
void radixSort(vector<int>& arr, int l, int r, int digit){
	int i = j = 0;
	vector<int> bucket(r-l+1);
	for(int d = 1; d <= digit; d++){
		// 原count数组，count[i]表示d位上，i出现的次数。 
		// 现count数组，count[i]等于count[i]前面的数字累加，表示d位上<=i的有几个（每个数字的片加起来）；每个数该放在bucket数组下标=count[i]-1。
		vector<int> count(radix);
		// 统计出现的次数
		for(i = l; i <= r; i++){
			j = getDigit(arr[i], d);
			count[j]++;
		}
		// 累加
		for(i = 1; i < radix; i++){
			count[i] += count[i-1];
		}
		// 从右往左遍历数组（保证先入先出）
		for(i = r; i >= l; i--){
			j = getDigit(arr[i], d);
			bucket[count[j]-1] = arr[i];
			count[j]--;
		}
		for(i = l, j = 0; i <= r; i++, j++){
			arr[i] = bucket[j];
		}
	}
}
// 求最多有几位radix
int maxbits(vector<int>& arr){
	int max = INT_MAX;
	for(int i = 0; i < arr.size(); i ++){
		max = max(max, arr[i]);
	}
	int res = 0;
	while(max != 0){
		res++;
		max /= radix;
	}
	return res;
}
vector<int> radixSortMain(vector<int>& arr){
	if(arr == null || arr.size() < 2) return arr;
	radixSort(arr, 0, arr.size()-1, maxbits(arr));
	return arr;
}
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

数组

二分查找

找某个数

有序数组，找某个数是否存在。
时间复杂度O（logN）

// 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
// leetcode-704
// 1、左闭右闭[left, right]
int search(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size()-1;
	int middle;
	// 问题1：是<=还是<？
	// 答：因为这里是左闭右闭，举特殊例子，当区间[1, 1]时，left=right是有意义的，仍要进行查找，所以是<=。
	while(left <= right){
		middle = left + ((right - left) >> 1);
		if(nums[middle] > target){
			// 更新右边界
			// 问题2：是middle还是middle-1？
			// 答：middle已经判断过了，所以是middle-1
			right = middle - 1;
		}else if(nums[middle] < target){
			// 更新左边界
			left = middle + 1;
		}else{
			return middle;	
		}
	}
	return -1;
}
// 2、左闭右开[left, right)
int search(vector<int>& nums, int target) {
	int left = 0;
	// 左闭右开，右边界不包含
	int right = nums.size();
	int middle;
	// 当left=right，[1, 1)不合法，所以是<
	while(left < right){
		middle = l + (r - l) >> 1;
		if(nums[middle] > target){
			// 更新右边界，右开，将右边界定为middle
			right = middle;
		}else if(nums[middle] < target){
			// 更新左边界，左闭，将左边界定为middle+1（middle已经判断过）
			left = middle + 1;
		}else{
			return middle;
		}
	}
	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
40
41
42
43
44
45
46

找最左侧

有序数组，找>=或者>某个数最左侧的位置。
时间复杂度O（logN）

// 找lower_bound：找>=某个数的第一个位置
// 左闭右开
int lower_bound(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size();
	int middle;
	// left=right夹出唯一位置
	while(left < right){
		middle = left + ((right - left) >> 1);
		if(nums[middle] >= target){
			// 更新右边界：middle左边可能还有>=target的
			right = middle;
		}else{
			// 更新左边界：>=target在middle右边
			left = middle + 1;
		}
	}		
	// 返回夹出来的位置
	return left;
}


// 找upper_bound：找>某个数的第一个位置
// 左闭右开
int upper_bound(vector<int>& nums, int target){
	int left = 0;
	int right = nums.size();
	int middle;
	while(left < right){
		middle = left + ((right - left) >> 1);
		if(nums[middle] > target){
			// 更新右边界：middle左边可能还有>target的
			right = middle;
		}else{
			// 更新左边界：>target在middle右边
			left = middle + 1;
		}
	}
	return left;
}


// leetcode-35（可能不存在）
// 1、暴力解
int searchInsert(vector<int>& nums, int target) {
	for(int i = 0; i < nums.size(); i ++){
		// 一旦发现>=目标值的就返回
		if(nums[i] >= target){
			return i;
		}
	}
	// 否则返回数组长度
	return nums.size();
}
// 2、二分查找（左闭右开）
int searchInsert(vector<int>& nums, int target){
	int l = 0;
	int r = nums.size();
	int m;
	while(l < r){
		m = l + ((r-l) >> 1);
		if(nums[m] >= target){
			r = m;
		}else{
			l = m + 1;
		}
	}
	// 判断target是否存在于数组中
	/*
		1、target存在 => 返回l
		2、target不存在 => 比所有数大 => 返回nums.size()
					   => 夹在中间 =>返回l
	*/
	// 判断l是否比所有数大
	if(l == nums.size()) return nums.size();
	return l;
}


// 找元素的第一个和最后一个位置
// leetcode-34
vector<int> searchRange(vector<int>& nums, int target) {
	if(nums.empty()) return {-1, -1};
	vector<int> res;
	// 左闭右开
	int l = 0;
	int r = nums.size();
	int m;
	// 找<=target的右边界
	while(l < r){
		m = l + ((r-l)>>1);
		if(nums[m] >= target){
			r = m;
		}else{
			l = m + 1;
		}
	}
	// 查找失败先返回
	if(l == nums.size()) return {-1, -1};
	res.push_back(l);
	// 找>=target的右边界
	// 从上一步的r开始找
	l = r;
	r = nums.size();
	while(l < r){
		m = l + ((r-l) >> 1);
		if(nums[m] <= target){
			l = m + 1;
		}else{
			r = m;
		}
	}
	if(l-1 == nums.size()) return {-1, -1};
	res.push_back(l-1);
	if(res[1]>=res[0]){
		return res;
	}else{
		return {-1, -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
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

局部最小值
无序数组，相邻数一定不相等，求局部最小值。

时间复杂度O（n）

二分法的应用

// 算平方根
// leetcode-69
int mySqrt(int x) {
	// 题意相当于找m^2最接近x的最大的数
	// 特殊情况（0、1）返回
	if(x <= 1) return x;
	// 左闭右闭
	int l = 1, r = x / 2 + 1, m;// 当x>1且为整数时，根号x在[1,x/2+1]区间内
	while(l <= r){
		m = l + ((r-l) >> 1);
		if((long long)m*m < x){
			l = m + 1;// 更新右边界
		}else if((long long)m*m > x){
			r = m - 1;// 更新左边界
		}else{
			return m;
		}
	}
	// 如果不是通过m^2=x返回，则返回r
	return r;
}

// 判断是否为完美平方根
// leetcode-367
bool isPerfectSquare(int num) {
	int l = 1, r = num / 2 + 1, m;
	while(l <= r){
		m = l + ((r - l) >> 1);
		if((long long)m*m < num){
			l = m + 1;
		}else if((long long)m*m > num){
			r = m - 1;
		}else{
			return true;
		}
	}
	return false;
}
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

双指针

// leetcode-26

// leetcode-283

// leetcode-844
bool backspaceCompare(string s, string t) {
	int i = -1;// s有效序列
	for(int k = 0; k < s.length(); k++){
		if(s[k] == '#'){
			if(i>-1){//有路可退，退退退！
				i--;
			}
		}else{
			s[++i] = s[k];//让k指向的元素纳入有效序列
		}
	}
	int j = -1;// t有效序列
	for(int p = 0; p < t.length(); p++){
		if(t[p] == '#'){
			if(j > -1){
				j--;
			}
		}else{
			t[++j] = t[p];
		}
	}
	if(i == -1||j == -1){//最后剩余的是空格
		return i == j;
	}
	// substr(开始位置，截取长度)
	return s.substr(0, i+1) == t.substr(0,j+1);
}

// leetcode-977
// 方法1：双指针从中间开始移动（小的先插入）
vector<int> sortedSquares(vector<int>& nums) {
	vector<int> res;
	int i = 0, j = 0; // i负数列，j正数列
	while(j<nums.size() && nums[j]<0){
		j++;//1
	}
	i = j - 1;//0
	while(i >= 0 && j < nums.size()){
		if(abs(nums[i]) <= nums[j]){
			res.push_back(nums[i]*nums[i]);
			i--;
		}else{
			res.push_back(nums[j]*nums[j]);
			j++;
		}
	}
	while(i >= 0){
		res.push_back(nums[i]*nums[i]);
		i--;
	}
	while(j < nums.size()){
		res.push_back(nums[j]*nums[j]);
		j++;
	}
	return res;
}
// 方法2：双指针分别从两端开始移动（大的先插入）
vector<int> sortedSquares(vector<int>& nums) {
	vector<int> res(nums.size());
	int k = res.size()-1;
	for(int i = 0, j = nums.size()-1; i <= j;){
		if(nums[i]*nums[i] >= nums[j]*nums[j]){
			res[k--] = nums[i]*nums[i];
			i++;
		}else{
			res[k--] = nums[j]*nums[j];
			j--;
		}
	}
	return res;
}
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
67
68
69
70
71
72
73
74
75
76

滑动窗口*

// leetcode-209
int minSubArrayLen(int target, vector<int>& nums) {
	int result = INT32_MAX;// 记录最小长度
	int sum = 0;// 记录子序列和
	int i = 0;// 起始位置
	int subLength = 0;// 子序列长度
	// 终止位置
	for(int j = 0; j < nums.size(); j++){
		// 累加
		sum += nums[j];
		while(sum >= target){
			// 更新最小长度
			subLength = j - i + 1;
			result = result < subLength ? result : subLength;
			// 把滑动窗口头摘下来，更新i
			sum -= nums[i++];
		}
	}
	return result == INT32_MAX ? 0 : result;
}

// leetcode-904
int totalFruit(vector<int>& fruits) {
	int result;// 记录最大长度
	unordered_map<int, int> m;// type, count
	int i = 0;// 起始位置
	int len = 0;// 记录子序列最大长度
	// 终止位置
	for(int j = 0; j < fruits.size(); j++){
		// 累加
		m[fruits[j]] ++;
		len ++;
		while(m.size()>2){
			// 把头摘下来
			m[fruits[i]] --;
			if(m[fruits[i]] == 0){
				m.erase(fruits[i]);
			}
			i++;
			len--;
		}
		// 更新最大长度
		result = result < len ? len : result;
	}
	return result;
}
    
// leetcode-76
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

螺旋矩阵*

哈希表

链表

单链表定义

struct ListNode{
	int val;
	ListNode* next;
	// 构造函数
	ListNode(int x): val(x), next(null) {}
}
1
2
3
4
5
6

删除链表元素

// leetcode-203
// 1、分情况讨论
ListNode* removeElements(ListNode* head, int val) {
	// 删除头节点
	while(head != NULL && head->val == val){
		ListNode* tmp = head;
		head = head->next;
		delete tmp;
	}
	// 删除非头节点
	ListNode* curr = head;
	// 注意可能存在删到最后空了
	while(curr != NULL && curr->next != NULL){
		if(curr->next->val == val){
			// 删除curr->next
			ListNode* tmp = curr->next;
			curr->next = curr->next->next;
			delete tmp;
		}else{
			curr = curr->next;
		}
	}
	return head;
}
// 2、添加虚拟节点
ListNode* removeElements(ListNode* head, int val) {
	// 设置一个虚拟头节点
	ListNode* h = new ListNode(0);
	// next指向链表头
	h->next = head;
	ListNode* curr = h;
	while(curr->next != NULL){
		if(curr->next->val == val){
			ListNode* tmp = curr->next;
			curr->next = curr->next->next;
			delete tmp;
		}else{
			curr = curr->next;
		}
	}
	// 删除虚拟头节点
	head = h->next;
	delete h;
	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
39
40
41
42
43
44
45

反转链表

// 反转单链表
// leetcode-206
// 1、指针法
ListNode* reverseList(ListNode* head) {
	ListNode* prev = NULL;
	ListNode* curr = head;
	ListNode* next = head;
	while(curr != NULL){
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}
// 2、递归法
ListNode* reverseList(ListNode* head) {
	// 递归的边界
	if(head == NULL || head->next == NULL){
		return head;
	}
	// last用来指向反转后的头节点
	ListNode* last = reverseList(head->next);
	// 反转
	head->next->next = head;
	head->next = NULL;
	return last;
}


// 反转双链表
ListNode* reverse(ListNode* head){
	ListNode* prev = NULL;
	ListNode* curr = head;
	while(curr != NULL){
		curr->prev = curr->next;
		curr->next = prev;
		prev = curr;
		curr = curr.prev;
	}
	return prev;
}

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

打印两个有序链表的公共部分

// 谁小谁移动，相同打印并移动，有一个越界停。
void printPublic(ListNode* head1, ListNode* head2){
	ListNode* p1 = head1;
	ListNode* p2 = head2;
	while(p1 != NULL && p2 != NULL){
		if(p1->val < p2->val){
			p1 = p1->next;
		}else if(p1->val > p2->val){
			p2 = p2->next;
		}else{
			cout << p1->val << endl;
			p1 = p1->next;
			p2 = p2->next;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

判断回文链表

// leetcode-234
// 1、辅助栈
bool isPalindrome(ListNode* head) {
	stack<int> s;
	ListNode* p = head;
	while(p!=NULL){
		s.push(p->val);
		p = p->next;
	}
	p = head;
	while(p!=NULL){
		if(s.top() != p->val){
			return false;
		}
		s.pop();
		p = p->next;
	}
	return true;
}
// 2、快慢指针
ListNode* reverse(ListNode* head){
	ListNode* prev = NULL;
	ListNode* curr = head;
	ListNode* next = head;
	while(curr!=NULL){
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}
bool isPalindrome(ListNode* head) {
	if(head == NULL || head->next == NULL){
		return true;
	}
	ListNode* slow = head;
	ListNode* fast = head;
	while(fast.next!=NULL && fast->next->next!=NULL){
		// 慢指针一个一个走，快指针走双倍
		// 如果链表长度是奇数，最后slow走到中间，fast走到end
		// 如果链表长度是偶数，最后slow走到中间后一个，fast走到end+1（null）
		slow = slow->next;
		fast = fast->next->next;
	}
	// 链表长度是奇数，slow还要往后走一个(正中间就不比较了)
	if(fast!=NULL){
		slow = slow->next;
	}
	// 分成左右两块开始遍历
	ListNode* left = head;
	ListNode* right = reverse(slow);
	while(right!=NULL){
		if(left->val != right->val){
			return false;
		}
		left = left->next;
		right = right->next;
	}
	return true;
}
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

分割链表

// 定义六个指针变量sH/sT/eH/eT/bH/bT
// 1、分成<，=，>区版本 
ListNode* partition(ListNode* head, int val){
	ListNode* sH = NULL;
	ListNode* sT = NULL;
	ListNode* eH = NULL;
	ListNode* eT = NULL;
	ListNode* bH = NULL;
	ListNode* bT = NULL;
	ListNode* next = NULL;// 记录下一个节点
	while(head != NULL){
		next = head->next;
		// 摘下头节点
		head->next = null;
		// 连接
		if(head->val < val){
			if(sH == NULL){
				sH = head;
				sT = head;
			}else{
				sT->next = head;
				sT = head;
			}
		}else if(head->val == val){
			if(eH == NULL){
				eH = head;
				eT = head;
			}else{
				eT->next = head;
				eT = head;
			}
		}else{
			if(bH == NULL){
				bH = head;
				bT = head;
			}else{
				bT->next = head;
				bT = head;
			}
		}

		head = next;
	}
	// s区非空，连接s区和e区
	if(sT != NULL){
		sT->next = eH;
		// 判断e区是否为空，谁去连接b区
		eT = eT == NULL ? sT : eT;
	}
	// e区非空，连接e区和b区
	// 如果最后选择的去连接b区的不是空
	if(eT != NULL){
		eT->next = bH;
	}
	return sH != NULL ? sH : (eH != NULL ? eH : bH);
}
// 2、分成<，>=区版本
// leetcode-86
ListNode* partition(ListNode* head, int x) {
	ListNode* sH = NULL;
	ListNode* sT = NULL;
	ListNode* eH = NULL;
	ListNode* eT = NULL;
	ListNode* next = NULL;
	while(head != NULL){
		next = head->next;
		head->next = NULL;
		if(head->val < x){
			if(sH == NULL){
				sH = head;
				sT = head;
			}else{
				sT->next = head;
				sT = head;
			}
		}else{
			if(eH == NULL){
				eH = head;
				eT = head;
			}else{
				eT->next = head;
				eT = head;
			}
		}
		head = next;
	}
	if(sT != NULL){
		sT->next = eH;
	}
	return sH != NULL ? sH : eH;
}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

复制带有随机指针的链表

// leetcode-138
// 1、哈希表（需要额外空间）
Node* copyRandomList(Node* head) {
	if(head == NULL) return head;
	unordered_map<Node*, Node*> m;
	Node* curr = head;
	while(curr != NULL){
		// key旧节点，value新节点
		m[curr] = new Node(curr->val);
		curr = curr->next;
	}
	curr = head;
	while(curr != NULL){
		// 遍历旧节点，设置新节点的next和random
		m[curr]->next = m[curr->next];
		m[curr]->random = m[curr->random];
		curr = curr->next;
	}
	return m[head];
}
// 2、骚操作（不需要额外空间）
Node* copyRandomList(Node* head) {
	if(head == NULL) return head;
	Node* curr = head;
	Node* next = NULL;
	// 在老节点后面拷贝出一个新节点
	while(curr != NULL){
		next = curr->next;
		curr->next = new Node(curr->val);
		curr->next->next = next;
		curr = next;
	}
	curr = head;
	// 拷贝新节点的random
	Node* curCopy = NULL;// 分离新旧节点要用，不可省
	while(curr != NULL){
		next = curr->next->next;
		curCopy = curr->next;
		// 修改新节点的random
		curCopy->random = curr->random != NULL ? curr->random->next : NULL;
		curr = next;
	}
	Node* res = head->next;
	curr = head;
	// 分离新旧节点
	while(curr != NULL){
		next = curr->next->next;
		curCopy = curr->next;
		// 修改旧节点的next
		curr->next = next;
		// 修改新节点的next
		curCopy->next = next != NULL ? next->next : NULL;
		curr = next;
	}
	return res;
}
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

链表相交

// 求有环或无环链表相交节点
ListNode* getIntersectNode(ListNode* head1, ListNode* head2){
	if(head1 == NULL || head2 == NULL){
		return NULL;
	}
	ListNode* loop1 = getLoopNode(head1);
	ListNode* loop2 = getLoopNode(head2);
	if(loop1 == NULL && loop2 == NULL){
		return noLoop(head1, head2);
	}
	if(loop1 != NULL && loop2 != NULL){
		return bothLoop(head1, head2);
	}
	// 一个有环链表和一个无环链表是不可能相交的。
	return NULL;
}
// (1)求环的入节点
ListNode* getLoopNode(ListNode* head){
	if(head == NULL || head->next == NULL || head->next->next == NULL){
		return NULL;
	}
	// 如果链表有环，快慢指针会相遇；且快慢指针在环中转的圈数不会大于两圈，因为快指针比慢指针快了一倍。
	ListNode* slow = head->next;
	ListNode* fast = head->next->next;
	while(slow != fast){
		if(fast->next == NULL || fast->next->next == NULL){
			return NULL;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	// 当快慢指针相遇，快指针回到头，快慢指针一起一步一步走，相遇时则为环的入节点。
	fast = head;
	while(slow != fast){
		slow = slow->next;
		fast = fast->next;
	}
	return fast;
}
// (2)求两个无环链表的相交节点
ListNode* noLoop(ListNode* head1, ListNode* head2){
	if(head1 == NULL || head2 == NULL){
		return NULL;
	}
	ListNode* cur1 = head1;
	ListNode* cur2 = head2;
	int n = 0;// 两个链表长度差值
	while(cur1->next != NULL){
		n++;
		cur1 = cur1->next;
	}
	while(cur2->next != NULL){
		n--;
		cur2 = cur2->next;
	}
	// 走到结束不是同一个节点，则没有相交节点
	if(cur1 != cur2){
		return NULL;
	}
	// 让cur1指向长链表头
	cur1 = n>0 ? head1 : head2;
	cur2 = cur1 == head1 ? head2 : head1;
	n = abs(n);
	// 长链表走差值步数，走到和短链表长度相同处
	while(n != 0){
		n--;
		cur1 = cur1->next;
	}
	// 求相交节点
	while(cur1 != cur2){
		cur1 = cur1->next;
		cur2 = cur2->next;
	}
	return cur1;
}
// (3)求两个有环链表的相交节点
ListNode* bothLoop(ListNode* head1, ListNode* loop1, ListNode* head2, ListNode* loop2){
	ListNode* cur1 = NULL;
	ListNode* cur2 = NULL;
	// 入环节点相同，化为求无环链表的相交节点
	if(loop1 == loop2){
		cur1 = head1;
		cur2 = head2;
		int n = 0;
		while(cur1->next != NULL){
			n++;
			cur1 = cur1->next;
		}
		while(cur2->next != NULL){
			n--;
			cur2 = cur2->next;
		}
		cur1 = n>0 ? head1 : head2;
		cur2 = cur1 == head1 ? head2 : head1;
		n = abs(n);
		while(n != 0){
			n--;
			cur1 = cur1->next;
		}
		while(cur1 != cur2){
			cur1 = cur1->next;
			cur2 = cur2->next;
		}
		return cur1;
	}else{
	// 入环节点不同
		cur1 = loop1.next;
		while(cur1 != loop1){
			if(cur1 == loop2){
				return loop1;
			}
			cur1 = cur1->next;
		}
		return NULL;
	}
}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

删除链表的倒数第N个节点

// leetcode-19
ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* vhead = new ListNode(0, head);
	ListNode* slow = vhead;
	ListNode* fast = vhead;
	// 快指针先走n步
	while(n != 0 && fast != nullptr){
		fast = fast->next;
		n--;
	}
	// 快指针再提前走一步（目的：让慢指针指向被删除节点的前一个）
	fast = fast->next;
	while(fast != nullptr){
		slow = slow->next;
		fast = fast->next;
	}
	// 删除
	slow->next = slow->next->next;
	return vhead->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二叉树

二叉树节点定义

struct BTNode{
	int val;
	BTNode* left;
	BTNode* right;
	BTNode(int data): val(data){}
}
1
2
3
4
5
6

各种遍历

// 递归遍历（每个节点遍历3遍）
void recursion(BTNode* head){
	if(!head) return;
	// 1
	// 1
	recursion(head->left);
	// 2
	// 2
	recursion(head->right);
	// 3
	// 3
}
1
2
3
4
5
6
7
8
9
10
11
12

// 递归版
// 先序遍历（在1的时候打印）
void preOrderRecur(BTNode* head){
	if(!head) return;
	cout << head->val << endl;
	preOrderRecur(head->left);
	preOrderRecur(head->right); 
}
// 中序遍历（在2的时候打印）
void inOrderRecur(BTNode* head){
	if(!head) return;
	inOrderRecur(head->left);
	cout << head->val << endl;
	inOrderRecur(head->right);
}
// 后序遍历（在3的时候打印）
void posOrderRecur(BTNode* head){
	if(!head) return;
	posOrderRecur(head->left);
	posOrderRecur(head->right);
	cout << head->val << endl;
}


// 非递归版
// 先序遍历：根左右
void preOrdeUnrecur(BTNode* head){
	if(head){
		stack<BTNode*> s;
		s.push(head);
		while(!s.empty()){
			// 弹出节点，处理
			head = s.top();
			cout << head->val << endl;
			s.pop();
			// 右孩子进栈
			if(head->right){
				s.push(head->right);
			}
			// 左孩子进栈
			if(head->left){
				s.push(head->left);
			}
		}
	}
}
// 中序遍历：左根右
void inOrderUnrecur(BTNode* head){
	if(head){
		stack<BTNode*> s;
		while(!s.empty() || head != nullptr){
			// 根节点的整个左边界进栈
			if(head){
				s.push(head);
				head = head->left;
			}else{
			// 弹出栈顶，处理
				head = s.top();
				cout << head->val << endl;
				s.pop();
			// 走右树
				head = head->right;
			}
		}
	}
}
// 后序遍历：左右根（利用收集栈）
void posOrderUnrecur(BTNode* head){
	if(head){
		stack<BTNode*> s1;
		stack<BTNode*> s2;// 收集栈
		s1.push(head);
		while(!s1.empty()){
			// 弹出节点，压入收集栈
			head = s1.top();
			s2.push(head);
			s1.pop();
			// 左孩子进栈
			if(head->left){
				s1.push(head->left);
			}
			// 右孩子进栈
			if(head->right){
				s1.push(head->right);
			}
		}
		while(!s2.empty()){
			cout << s1.top()->val << endl;
			s1.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
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

// 层序遍历（广度优先）：用队列
void floorTraversing(BTNode* head){
	if(head){
		queue<BTNode*> q;
		q.push(head);
		while(!q.empty()){
			// 队头出队
			BTNode* cur = q.front();
			cout << cur->val << endl;
			q.pop();
			// 左孩子进队
			if(cur->left){
				q.push(cur->left);
			}
			// 右孩子进队
			if(cur->right){
				q.push(cur->right);
			}
		}	
	}
}
// 求二叉树的最大宽度：哈希表
int maxWidth(BTNode* head){
	if(head){
		queue<BTNode*> q;
		unordered_map<BTNode*, int> levelMap;
		q.push(head);
		levelMap[head] = 1;
		int curLevel = 1;// 当前层数
		int curLevelNodes = 0;// 当层节点数
		int max = 0;// 最大宽度
		while(!q.empty()){
			BTNode* cur = q.front();
			q.pop();
			int curNodeLevel = levelMap[cur];
			if(curNodeLevel == curLevel){
				curLevelNodes ++;
			}else{// 该更新了
				max = max(max, curLevelNodes);
				curLevel ++;
				curLevelNodes = 1;
			}
			if(cur->left){
				q.push(cur->left);
				levelMap[cur->left] = curNodeLevel+1;
			}
			if(cur->right){
				q.push(cur->right);
				levelMap[cur->right] = curNodeLevel+1;
			}
		}
		// 更新最后一层
		max = max(max, curLevelNodes);
		return max;
	}
}
// 求二叉树的最大宽度（这里的宽度包括nullptr）：编号
// leetcode-662
int widthOfBinaryTree(TreeNode* root) {
	queue<pair<TreeNode*, long long> > q;
	q.emplace(root, 0);
	int res = 0;
	while(!q.empty()){
		// 队头的编号（最左边节点的编号）
		long long offset = q.front().second;
		// 基于队头和队尾获得当前层的宽度
		res = max(res, (int)(q.back().second - offset + 1));
		// 遍历当前层
		int n = q.size();
		for(int i = 0; i < n; i++){
			// 当层每个节点依次出队列
			auto [cur, curVal] = q.front();
			q.pop();
			// 编号缩小
			curVal -= offset;
			if(cur->left){
				// 有左孩子，设置左孩子的值，进队
				q.emplace(cur->left, curVal * 2);
			}
			if(cur->right){
				// 有右孩子，设置右孩子的值，进队
				q.emplace(cur->right, curVal * 2 + 1);
			}
		}
	}
	return res;
}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

求中序遍历后继节点

// 左根右
TreeNode* getSuccessorNode(TreeNode* node){
	if(node == nullptr) return node;
	// 如果node有右孩子，后继节点为右子树上最左边的节点
	if(node->left != nullptr){
		return getLeftMost(node->right);
	}else{
		// 如果node无右孩子
		TreeNode* parent = node->parent;
		// node为parent的右孩子，后继节点为祖先中第一个为它父亲的左孩子的节点
		while(parent != nullptr && parent->left != node){
			node = parent;
			parent = node->parent;
		}
		return parent;
		// 还有一种情况，如果找不到，则说明node为最右节点，没有后继节点
	}
}
TreeNode* getLeftMost(TreeNode* node){
	if(node == nullptr){
		return node;
	}
	while(node->left != nullptr){
		node = node->left;
	}
	return 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

二叉树的序列化、反序列化

// 按先序
// leetcode-297
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
	if(root == nullptr) return "#_";// 加_是因为val可能是多位数。
	// int转string
	string res = to_string(root->val) + '_';
	res += serialize(root->left);
	res += serialize(root->right);
	return res;
}
// Decodes your encoded data to tree.
queue<string> split(string& str){
	queue<string> res;
	string s;
	for(auto c : str){
		if(c == '_'){
			res.emplace(s);
			s.clear();
		}else{
			s += c;
		}
	}
	return res;
}
TreeNode* process(queue<string>& q){
	if(q.empty()) return nullptr;
	string s = q.front();
	q.pop();
	if(s == "#") return nullptr;
	// string转int
	TreeNode* cur = new TreeNode(stoi(s));
	cur->left = process(q);
	cur->right = process(q);
	return cur;
}
TreeNode* deserialize(string data) {
	queue<string> q = split(data);
	return process(q);
}
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

纸条的折痕

// 二叉树中序遍历就是纸条从左到右的折痕顺序，根节点是凹，左孩子是凹，右孩子是凸。
void printAllFolds(int n){
	printProcess(1, n, true);
}
// i节点层数；总层数；是否为凹
void printProcess(int i, int n, bool down){
	if(i > n) return;
	printProcess(i+1, n, true);
	cout << down?"凹":"凸" << endl;
	printProcess(i+1, n, false);
}
1
2
3
4
5
6
7
8
9
10
11

判断各种树

// 判断搜索二叉树：中序遍历依次升序就是搜索二叉树
// leetcode-98
// 1、递归
long long preVal = LONG_MIN;
bool isValidBST(TreeNode* root) {
	if(root == nullptr) return true;
	if(!isValidBST(root->left)){
		return false;
	}
	if(root->val > preVal){
		preVal = root->val;
	}else{
		return false;
	}
	return isValidBST(root->right);
}
// 2、中序遍历
// 递归版
void process(TreeNode* root, vector<int>& list){// 注意加引用&
	if(root == nullptr) return;
	process(root->left, list);
	list.emplace_back(root->val);
	process(root->right, list);
}
bool isValidBST(TreeNode* root) {
	vector<int> list;
	process(root, list);
	for(int i = 0; i < list.size()-1; i++){
		if(list[i] >= list[i+1]){
			return false;
		}
	}
	return true;
}
// 非递归版
bool isValidBST(TreeNode* root) {
	long long preVal = LONG_MIN;
	stack<TreeNode*> s;
	while(!s.empty() || root != nullptr){
		if(root){
			s.push(root);
			root = root->left;
		}else{
			root = s.top();
			s.pop();
			if(root->val <= preVal){
				return false;
			}else{
				preVal = root->val;
			}
			root = root->right;
		}
	}
	return true;
}

// 判断完全二叉树：层次遍历
bool isCBT(TreeNode* root){
	if(root == nullptr) return true;
	queue<TreeNode*> q;
	bool leaf = false;// 是否遇到第一个左右孩子不双全的节点（开启后，如果接下来遇到的全是叶节点，则为完全二叉树）
	TreeNode* l = nullptr;
	TreeNode* r = nullptr;
	q.push(root);
	while(!q.empty()){
		root = q.top();
		q.pop();
		l = root->left;
		r = root->right;
		// 如果只有右孩 或者 leaf开启但不是叶节点
		if((l == nullptr && r != nullptr)
			|| (leaf && (l != nullptr || r != nullptr))
		){
			return false;
		}
		if(l){
			q.push(l);
		}
		if(r){
			q.push(r);
		}
		// 遇到左右孩子不双全，开启leaf
		if(l == nullptr || r == nullptr){
			leaf = true;
		}
	}
	return true;
}

// 判断满二叉树：用树形dp套路

// 判断平衡二叉树：树形dp套路
// leetcode-110
int process(TreeNode* root){
	if(root == nullptr) return 0;
	int lh = process(root->left);
	int rh = process(root->right);
	// 如果这颗子树是平衡二叉树
	if(lh >= 0
		&& rh >= 0
		&& abs(lh-rh) < 2
	){
		return max(lh, rh) + 1;
	}
	return -1;
}
bool isBalanced(TreeNode* root){
	// >=0返回高度，是平衡二叉树；<0不是平衡二叉树
	return process(root) >= 0;
}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

求公共祖先

// 给定两个二叉树的节点，找到他们的最低公共祖先节点。 
// leetcode-236
// 1、哈希表(超时了)
void process(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& fatherMap){
	if(root == nullptr) return;
	if(root->left){
		fatherMap.emplace(root->left, root);
		process(root->left, fatherMap);
	}
	if(root->right){
		fatherMap.emplace(root->right, root);
		process(root->right, fatherMap);
	}
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
	// 构造fatherMap
	unordered_map<TreeNode*, TreeNode*> fatherMap;
	fatherMap.emplace(root, root);
	process(root, fatherMap);
	
	// 用set记录p往上窜到根节点的路
	unordered_set<TreeNode*> st;
	TreeNode* cur = p;
	// 当自己的爹=自己（根节点）跳出
	while(cur != fatherMap[cur]){
		st.emplace(cur);
		cur = fatherMap[cur];
	}
	st.emplace(root);

	// q向上遍历，检查set是否存在
	cur = q;
	while(st.find(fatherMap[cur]) != st.end()){
		cur = fatherMap[cur];
	}
	return cur;
}
// 2、递归：想不到吧哈哈
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
	// base case
	if(root == nullptr || root == p || root == q){
		return root;
	}
	TreeNode* left = lowestCommonAncestor(root->left, p, q);
	TreeNode* right = lowestCommonAncestor(root->right, p, q);
	// 左右lca都不为空（p、q分别在左右子树）
	if(left != nullptr && right != nullptr){
		return root;	
	}
	// 左右lca存在空（p或q在一边子树）、都为空（p、q不在当前左右子树）
	return left != nullptr ? left : right;
}
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

图

相关阅读:
C++语言之组合、聚合类间关系
 vue获取外网IP、java后端及nginx多次转发获取真实IP
The Sandbox 中的建设者：走进 Sandja Studio
Java使用JavaMail进行邮件的发送和读取
 回归预测 | MATLAB实现BO-GRU贝叶斯优化门控循环单元多输入单输出回归预测
 【算法练习Day29】柠檬水找零&&根据身高重建队列&&用最少数量的箭引爆气球
 java集合
 Rust Wasm 图片转 ASCII 艺术
 Swoole 介绍以及编译安装
 前端Vue入门-day08-vant组件库
原文地址：https://blog.csdn.net/Youkirrr_/article/details/126198162