gcd

最大公约数

辗转相除法

while循环版

这里可以证明(a,b)=(b,r),证明见高数。

1
2
3
4
5
6
7
8
9
inline int gcd(int a,int b) {//a,b可以为0
    int r;
    while(b>0) {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

三目运算版：

1
2
3
inline int gcd(int a,int b) {//a,b可以为0
    return b>0 ? gcd(b,a%b):a;
}

lcm

两个整数的最小公倍数与最大公因数之间有如下的关系：

lcm(a,b)=∣a⋅b∣/gcd(a,b)

1
2
3
inline int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

快速幂

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
#include<iostream>
#include<cstdio>
#include<cmath>
const int mod=998244353;
using namespace std;
int a[101],b[101],m[101];
typedef long long ll;

ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a % mod;
    else
    {
        ll temp = qpow(a, n / 2) % mod;
        return temp * temp % mod;
    }
}
int main()
{
	int n;
	scanf("%lld",&n);
	while(n--){
		long long a,b,k,x;
		scanf("%lld %lld %lld",&a,&b,&k);
		x=k/2;
		x=qpow(2,x);
		if(k%2==0)
		printf("%lld %lld\n",(x*a)%mod,(b*x)%mod);
		else 
		{
			long long y=((a-b)*x)%mod;
			long long m=((a+b)*x)%mod;
			if(y<0)y=y+mod;
			if(m<0)m=m+mod;
		    printf("%lld %lld\n",m,y);
			
		}
	}
    return 0; 
}

取模运算的性质：

(a×b)%p==[(a%p)×(b%p)]%p

如果取模以后是负数的话，要再加一个mod.

正题

如果我们要算3^10^，暴力的做法是ans=1，ans*=3，一直×10次，但是如果不是10，而是10^9^,这个增量是可怕的，long long类型也不能装下，直接溢出了，所以我们要对ans进行取模。取模以后，算10^9^次，这个对计算机一秒的运算量也是达到了极限，所以我们可以再优化一下，还是拿3^10^ 来举例，我们可以先算出3^5^,然后让其自乘，那么我们如何计算出3^5^呢，这是我们发现指数5不能均分，但是我们可以拆成3×3^2^×3^2^.以此类推，3^2^=3×3.

我们可以总结如下规律：

  • 如果指数是偶数，那么将指数均分，让底数幂相乘

  • 如果指数是偶数，先拿出一个底数，再与均分后的底数幂相乘

上代码

1
2
3
4
5
6
7
8
9
10
11
12
ll fast_power(ll a,ll b){
	ll ans=1;
	a%=mod;//为了防止输入的a过大，直接对a取模 
	while(b){
		if(b&1){//在二进制下，如果b是奇数，那么最后一位是1，和1&之后，应该还是1 
			ans=(ans*a)%mod;
		}
		a=(a*a)%mod;
		b>>=1;
	} 
	return ans;
}

前缀和

一维前缀和

sum[i,j]=sum[j]-sum[i-1]

问题：

求l，r区间的前缀和

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define maxn 200005
using namespace std;
int a[maxn];
int main(){
	int a[maxn]={0};
	int b[maxn]={0};
	int n,t;
	cin>>n;
	for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			b[i]=b[i-1]+a[i];
		}
	cin>>t;
	while(t--)
	{
		int l,r;
		cin>>l>>r;
		cout<<b[r]-b[l-1]<<endl; 
	}
}

P5638 【CSGRound2】光骓者的荣耀 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
#include<cmath>
#include <algorithm>
#include <string>
const int maxn=1e6+5;
using namespace std;
typedef long long ll;
ll sum[maxn];
int main(){
	ll x,n,k;
	cin>>n>>k;
	sum[1]=0;
	for(int i=2;i<=n;i++){
		cin>>x;
		sum[i]+=sum[i-1]+x;//计算前缀和 
	}
	ll ans=0;
	for(int i=k;i<=n;i++){
		ans=max(ans,sum[i]-sum[i-k]);//找到距离为k的两城市最大时间 
	}
	cout<<sum[n]-ans<<endl;
	return 0;
}

二维前缀和

sum[x1,y1][x2,y2]=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]-sum[x1-1][y1-1]//多减的要加回来 那么sum是怎么算出来的？ sum[i][j]=sum[i][j-1]+sum[i-1][j]+g[i][j]-sum[i-1][j-1] 注意当i=0，j=0时，sum[0][0]=g[0][0] 当i=0时，相当于前缀和 sum[0][j]=sum[0][j-1]+g[0][j] 当j=0时，相当于一维前缀和 sum[i][0]=sum[i-1][0]+g[i][0]

计算(x1,y1)到(x2,y2)那部分粉色的区域和，可以用sum(x2,y2)-绿色部分-深蓝色部分，但是浅绿色部分减了两次，因此要加回来。

特别地，当x1=0时，只需要减去深蓝色部分即可。

img

同理，当y1=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
#include<iostream>
#include<cstdio>
#include<cmath>
#include <algorithm>
#include <string>
const int maxn=1e6+5;
using namespace std;
typedef long long ll;
int t[1001][1001];
const int n=3,m=4;
int sum[n][m];
int g[n][m]={ {1,5,6,8},
              {9,6,7,3},
			  {5,3,2,4}};
void pre_sum(){
	sum[0][0]=g[0][0];
	for(int i=1;i<n;i++)sum[i][0]=sum[i-1][0]+g[i][0];//第一列
	for(int j=1;j<m;j++)sum[0][j]=sum[0][j-1]+g[0][j];//第一行
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
			sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
		}
	} 
}
int get_sum(int x1,int y1,int x2,int y2){
	if(x1==0&&y1==0)return sum[x2][y2];//相当于求左上角，直接返回sum[i][j]即可
	if(x1==0)return sum[x2][y2]-sum[x2][y1-1];
	if(x2==0)return sum[x2][y2]-sum[x1-1][y2];
	else return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}
int main(){
	pre_sum();
	cout<<get_sum(1,1,2,2)<<" "<<get_sum(0,1,1,3);
	return 0;
}

下标为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
#include<iostream>
#include<cstdio>
#include<cmath>
#include <algorithm>
#include <string>
const int maxn=1e6+5;
using namespace std;
typedef long long ll;
int n,m;
int sum[1001][1001];
int g[1001][1001];
void pre_sum(){
	sum[0][0]=g[0][0];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
		}
	} 
}
int get_sum(int x1,int y1,int x2,int y2){
	 return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
		}
	}
	pre_sum();
	cout<<get_sum(2,2,3,3)<<" "<<get_sum(1,2,2,4);
	return 0;
}

题目连接：P2004 领地选择 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<iostream>
#include<cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int n,m;
int g[3002][3002];
int sum[3002][3002];
int maxx=-9999999999999;
int xi,yi;
int main(){
	int a;
	cin>>n>>m>>a;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j]; 
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j];
		}
		
	}
	for(int i=1;i<=n-a+1;i++){
		for(int j=1;j<=m-a+1;j++){//i+a-1,j+a-1为右下角下标
			int ans=sum[i+a-1][j+a-1]-sum[i+a-1][j-1]-sum[i-1][j+a-1]+sum[i-1][j-1];
			if(maxx<ans){
				maxx=ans;
				xi=i,yi=j;
			}
		}
	}
	cout<<xi<<" "<<yi<<endl;
}

差分

一维差分

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
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int d[6]={0};
void add(int l,int r,int v)
{
	d[l]+=v;
	d[r+1]-=v;
}
int main()
{
	int arr[5]={1,3,7,5,2};
	add(2,4,5);
	add(1,3,2);
	add(0,2,-3);
	for(int i=1;i<5;i++){
		d[i]+=d[i-1];
		cout<<d[i]<<" ";
		
	}
	cout<<endl;
	for(int i=0;i<5;i++){
		arr[i]+=d[i];
		cout<<arr[i]<<" ";
	}
	memset(d,0,sizeof(d));
	
	return 0;
	
}

由于优化，这里我们不用一个数组记录值，减少一个数组的空间，但是我们要记录前一项的值。

•题目链接：AcWing 【797. 差分】

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
#include <iostream>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn=2e5+5;
int m,n,l,r,c;
int b[maxn];
int main(){
	cin>>n>>m;
	int last=0,now;//last记录前一项的值
	for(int i=1;i<=n;i++){
		cin>>now;
		b[i]=now-last;
		last=now;
	}
	for(int i=1;i<=m;i++){
		cin>>l>>r>>c;
		b[l]+=c;
		b[r+1]-=c;
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum+=b[i];
		cout<<sum<<" ";
	}
	return 0;
}

语文成绩

传送门：P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 nn，pp，代表学生数与增加分数的次数。

第二行有 nn 个数，a_1 \sim a_na1∼a**n，代表各个学生的初始成绩。

接下来 pp 行，每行有三个数，xx，yy，zz，代表给第 xx 个到第 yy 个学生每人增加 zz 分。

输出格式

输出仅一行，代表更改分数后，全班的最低

参考代码

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#include <stdlib.h>//分配空间 
const int maxn=5e6+5;
int a[maxn],d[maxn]={0};
using namespace std;
void add(int l,int r,int v)
{
	d[l]+=v;
	d[r+1]-=v;
}
int main(){
	int n,m;
	cin>>n>>m;
	cin>>a[0];
	for(int i=1;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z; 
		add(x-1,y-1,z);
	}
	for(int i=1;i<n;i++){
		d[i]+=d[i-1];
	}
	int minn=a[0];
	for(int i=0;i<n;i++){
		a[i]+=d[i]; 
		minn=min(minn,a[i]);
	}
	cout<<minn<<endl;
}

二维差分

二维差分和二维前缀和类似，多减去的区域要加回来。

在(x1,y2+1)-v，影响的区域是粉色部分，

在(x2,y1+1)-v，影响的区域是绿色部分。

二者重叠部分是浅绿色区域。

上代码：

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
#include<iostream>
#include<cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int n=3,m=4;
int sum[n][m];
int d[n+1][m+1];
int g[n][m]={ {1,5,6,8},
              {9,6,7,3},
			  {5,3,2,4}};
void pre_sum(){//对修改后的d进行前缀和，看看改动的终态 
	sum[0][0]=d[0][0];
	for(int i=1;i<n;i++)sum[i][0]=sum[i-1][0]+d[i][0];//第一列
	for(int j=1;j<m;j++)sum[0][j]=sum[0][j-1]+d[0][j];//第一行
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
			sum[i][j]=d[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)g[i][j]+=sum[i][j];//g[i][j]原数组加上变化终态即是结果 
	} 
}


void add(int x1,int y1,int x2,int y2,int v){//二维差分 
	d[x1][y1]+=v;
	d[x2+1][y1]-=v;
	d[x1][y2+1]-=v;
	d[x2+1][y2+1]+=v; 
}
int main(){
	add(0,0,2,1,3);
	add(1,1,2,2,-1);
	pre_sum();
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)cout<<g[i][j]<<" ";
		cout<<endl; 
	}
	return 0;
}

排序

冒泡

略，时间复杂度O(n^2)

选择

时间复杂度O(n^2)

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕

1
2
3
4
5
6
7
8
9
10
11
12
int main(){
	int a[]={1,4,5,2,4,5,2},len=7;
	for(int i=0;i<len-1;i++){//最后一次不用排了，已经全部有序
		int min=i;
		for(int j=i+1;j<len;j++){//注意这里j<len
			if(a[j]<a[min])min=j;
		}
		swap(a[min],a[i]);	
	}
	for(int i=0;i<6;i++)cout<<a[i]<<" ";
	cout<<endl; 
}

插入

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面)

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
void insertion_sort(int a[],int len){
	for(int i=1;i<len;i++){
		int key=a[i];
		int j=i-1;
		while((j>=0)&&(key<a[j])){
			a[j+1]=a[j];//右移1
			j--;
		}
		a[j+1]=key;
	}
}
//用数组0位置来充当暂存单元
/*假设第一个序列（ i=1）为有序序列，则后面都是无序序列*/
void insertsort(int a[],int n){
	for(int i=2;i<=n;i++){
			a[0]=a[i];//a[0]暂存a[i]的值，防止后面移动数组覆盖丢失
			int j=i-1;
			while(a[0]<a[j]){//a[0]在查找插入位置循环中充当件事哨兵 
				a[j+1]=a[j];
				j--;
			} 
			a[j+1]=a[0];
	}
} 
//ps:此写法数组下标必须从1开始

希尔排序

时间复杂度：O(nlog2n)

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

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
//下标从1开始
void shellsort(int a[],int n){
	for(int d=n/2;d>=1;d/=2){
		for(int i=d+1;i<=n;i++){
			a[0]=a[i];
			int j=i-d;
			while(j>0&&a[0]<a[j]){
				a[j+d]=a[j];
				j-=d;
			}
			a[j+d]=a[0];
		}
	}
}
//下标从0开始
void shellsort(int a[],int n){
	for(int d=n/2;d>=1;d/=2){
		for(int i=d;i<n;i++){
			int temp=a[i];
			int j=i-d;
			while(j>=0&&temp<a[j]){
				a[j+d]=a[j];
				j-=d;
			}
			a[j+d]=temp;
		}
	}
}

虽然希尔排序有三重循环，但是一开始d比较大，分的组多，每个组的元素少，因此比较的速度快，之后数组逐渐变得有序，因此后期也不需要过多的操作，因此速度会快。

快速排序

数组排序任务也可以按如下完成：

1）设k=a[0], 将k挪到适当位置，使得比k小的元素都在k左边,比k大的元素都在k右边，和k相等的，不关心在k左右出现均可 （O(n)时间完成）

2 ）把k左边的部分快速排序

3 ）把k右边的部分快速排序

快速排序的三个优化方法：

\1. 规模很小时（如end－first＜10），使用插入排序代替快速排序。

\2. 使用栈模拟递归。

\3. 极端数据（如比较有序的数组）会使快速排序变慢，甚至退化为冒泡排序。可以采用“三者取中法”来解决这个问题：令k等于a[first]、a[end]、a[(first+end)/2]中的中间值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int partition(int a[],int first,int end){
	int i=first;
	int j=end;
	while(i<j){
		while(i<j&&a[i]<=a[j])j--;
		if(i<j)swap(a[i],a[j]);
		while(i<j&&a[i]<=a[j])i++;
		if(i<j)swap(a[i],a[j]);
	}
	return i;
	
}
void quicksort(int a[],int first,int end){
	if(first<end){
		int pos=partition(a,first,end);
		quicksort(a,first,pos-1);
		quicksort(a,pos+1,end); 	
	}	
}
void qsort(int l,int r)//应用二分思想
{
    int mid=a[(l+r)/2];//中间数
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;//查找左半部分比中间数大的数
        while(a[j]>mid) j--;//查找右半部分比中间数小的数
        if(i<=j)//如果有一组不满足排序条件（左小右大）的数
        {
            swap(a[i],a[j]);//交换
            i++;
            j--;
        }
    }while(i<=j);//这里注意要有=
    if(l<j) qsort(l,j);//递归搜索左半部分
    if(i<r) qsort(i,r);//递归搜索右半部分
}

归并排序

数组排序任务可以如下完成：

1） 把前一半排序

  1. 把后一半排序

3)将这两半归并到一个新的有序数组，然后再拷贝回原数组，排序完成。

●时间复杂度O(nlogn)

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
#include <iostream>
#include <stdlib.h>//分配空间
using namespace std;
//合并
void merge(int a[],int tmpa[],int left,int mid,int right){
	//标记左半区间第一个未排序的元素
	int l_pos=left; 
	//标记右半区间第一个未标记的元素
	int r_pos=mid+1;
	//临时数组的下标
	int i =left;
	//合并
	while(l_pos<=mid&&r_pos<=right){
		if(a[l_pos]<a[r_pos])//左半区间第一个剩余元素更小
			tmpa[i++]=a[l_pos++];
		else tmpa[i++]=a[r_pos++]; 
	}
	//合并左半区间剩余的元素 
	while(l_pos<=mid)tmpa[i++]=a[l_pos++];
	//合并右半区间剩余的元素
	while(r_pos<=right)tmpa[i++]=a[r_pos++];
	//把临时数组合并后的元素复制到原来的数组 
	while(left<=right){
		a[left]=tmpa[left];
		left++;
	}
} 
//归并排序入口
void msort(int a[],int tmpa[],int left,int right){
	//若只有一个元素，则无需划分，直接归并即可
	if(left<right){
		int mid=(left+right)/2;
		msort(a,tmpa,left,mid);
		msort(a,tmpa,mid+1,right);
		merge(a,tmpa,left,mid,right);
	} 
}
//归并排序入口 
void mergesort(int a[],int n){
	int *tmpa=(int*)malloc(n*sizeof(int));
	if (tmpa){//辅助数组分配成功
		 msort(a,tmpa,0,n-1);
		 free(tmpa);
	} 
}

Java版

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
package class02;

public class code01_MergeSort {

	public static void mergeSort(int[] arr) {
		if(arr==null||arr.length<2){
			return;
		}
		process(arr,0,arr.length-1);
		
	}
	public static void process(int[] arr, int L, int R) {
		if(L==R) {
			return ;
		}
		int mid=L+((R-L)>>1);
		process(arr,L,mid);
		process(arr,mid+1,R);
		merge(arr,L,mid,R);
	}
	public static void merge(int[] arr, int L, int mid, int R) {
		int[] help =new int[R-L+1];
		int p1=L;
		int p2=mid+1;
		int i=0;
		while(p1<=mid&&p2<=R) {
			help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
		}
		while(p1<=mid) {
			help[i++]=arr[p1++];
		}
		while(p2<=R) {
			help[i++]=arr[p2++];
		}
		for(int j=0;j<help.length;j++) {
			//因为是在L~R范围上merge，所以arr的下标从L开始
			arr[L+j]=help[j];
		}
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[]=new int[] {1,4,5,3,6,7,9,2,10,28
		};
		mergeSort(arr);
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
	}

}

引申题目：

小和问题

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
package class02;

public class code02_SmallSum {

	public static int smallSum(int[] arr) {
		if(arr==null||arr.length<2) {
			return 0;
		}
		return process(arr,0,arr.length-1);
	}
	
	public static int process(int[] arr, int l, int r) {
		if(l==r) {
			return 0;
		}
		int mid = l+((r-l)>>1);
		return process(arr,l,mid)+process(arr,mid+1,r)+merge(arr,l,mid,r);
	}
	public static int merge(int[] arr,int l, int mid, int r) {
		int[] help = new int[r-l+1];
		int res=0;
		int i=0;
		int p1=l;
		int p2=mid+1;
		
		while(p1<=mid&&p2<=r) {
			res+=arr[p1]<arr[p2]?(r-p2+1)*arr[p1]:0;
			//这里必须左组严格小于右组才拷贝，否则无法计算
			help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
		}
		while(p1<=mid) {
			help[i++]=arr[p1++];
		}
		while(p2<=l) {
			help[i++]=arr[p2++];
		}
		for(i=0;i<arr.length;i++) {
			arr[l+i]=help[i];
		}
		return res;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

逆序对问题

2.求有多少个逆序对？一样的，就是求右边有多少个比左边小

代码略

动态规划

参考自动态规划解题套路框架 - labuladong的算法小抄 (gitbook.io)

但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int fib(int n){
    //边界条件
	if (n==0)return 0;
	else if(n==1||n==2)return 1;
    //开辟长度为n+1的dp数组，元素初始化为0
	vector<int>dp(n+1,0);
	dp[1]=dp[2]=1;//边界条件初始化
	for(int i=3;i<=n;i++){//自底而上求出dp
		dp[i]=dp[i-1]+dp[i-2];
	}
	return dp[n];//返回顶部的dp值，即所求
}
int main(){
	int n;
	cin>>n;
	cout<<fib(n)<<endl;
	return 0;
}

因为当前状态之和前两个状态有关，所以没有必要开一个长度为n+1的数组，只需要用三个变量存储即可。将空间复杂度压缩为O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int fib(int n){
	if (n==0)return 0;
	else if(n==1||n==2)return 1;
	int sum=0,pre=1,now=1;
	for(int i=3;i<=n;i++){
		sum=pre+now;
		pre=now;
		now=sum;
	}
	return sum;
}
int main(){
	int n;
	cin>>n;
	cout<<fib(n)<<endl;
	return 0;
}

简单说说子序列和子串的区别，子序列是分开的，而子串是连续的。

例如23456的子序列可以是246(可分散)，而子串可以是456(必须连续)。

不能用暴力搜索，因为一个长度为n的序列拥有 2的n次方个子序列，它的时间复杂度是指数阶。直接炸掉。这时，我们需要借助动态规划来解决这个问题。

最长上升子序列问题（LIS）

1.设计状态

记f(i)为以a[i]结尾的LIS长度，那么LIS=max{f(i)}

2.推导f(i),f(i)从何而来

考虑比i小的每一个j，如果a[i]>a[j],那么f(i)=f(j)+1

3.状态转移方程

f(i)=max(f(i),f(j)+1) 前提：j<i,a[j]<a[i]

最后贴一下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <iostream>
const int maxn=1e5+5;
int a[maxn],f[maxn];
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		f[i]=1;//初始化为1
		cin>>a[i]; 
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]<a[i])
			f[i]=max(f[i],f[j]+1);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=max(ans,f[i]);
	cout<<ans<<endl;
	return 0;
}

最长上升子串问题

题目链接Problem - 580A - Codeforces

（最好不要这样写，会超时）

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
#include <iostream>
#include <cstdio>
const int maxn=2e5+5;
int a[maxn],f[maxn];
using namespace std;
int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		f[i]=1;
		scanf("%d",&a[i]); 
	}
	for(int i=1;i<=n;i++)
	{	f[i]=1;
		for(int j=1;j<i;j++)
		{
			if(a[j]<=a[i]&&i-j==1)
			{
				f[i]=max(f[i],f[j]+1);
			}
		}
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

推荐简单写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxn=1e6+5;
int a[maxn];
int f[maxn];
using namespace std;
int main(){
	int n,ans=0,maxx=1,pos=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)cin>>a[i];
	int cnt=1;
	for(int i=1;i<n;i++){
		if(a[i]>=a[i-1]){
			cnt++;
			maxx=(maxx,cnt);
		}
		else cnt=1;
	}
	printf("%d\n",maxx);
	return 0;
}

最长公共子序列(LCS)

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
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
char a[1001], b[1001];
int dp[1001][1001], len1, len2;
 
void lcs(int i,int j)
{
    for(i=1; i<=len1; i++)
    {
        for(j=1; j<=len2; j++)
        {
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else if(dp[i-1][j] > dp[i][j-1])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = dp[i][j-1];
        }
    }
}
 
int main()
{
    while(~scanf(" %s",a))
    {
        scanf(" %s", b);
        memset(dp, 0, sizeof(dp));
        len1 = strlen(a);
        len2 = strlen(b);
        lcs(len1, len2);
        printf("%d\n", dp[len1][len2]);
    }
    return 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
#include<cstdio>
#include<cstring>
using namespace std;
long long dp[5005][1005];
char s1[5005],s2[1005];
int main(){
	while(scanf("%s %s",s1,s2)!=-1){
		int len1=strlen(s1);
		int len2=strlen(s2);
		memset(dp,0,sizeof(dp));
		if(s1[0]==s2[0])dp[0][0]=1;
		for(int i=1;i<len1;++i){
			dp[i][0]=dp[i-1][0];
			if(s1[i]==s2[0])++dp[i][0];
		}
		for(int i=1;i<len1;++i){
			for(int j=1;j<len2;++j){
				if(s1[i]==s2[j]){
					dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%1000000007;
				}
				else dp[i][j]=dp[i-1][j];
			}
		}
		printf("%lld\n",dp[len1-1][len2-1]%1000000007);
	}
	return 0;
}

背包问题

01背包问题

未优化版

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
#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005;
int dp[100][100];
int c[100],w[100];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j<w[i])dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
		}
	}
	//输出dp 数组
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++)
		{
		 cout<<dp[i][j]<<" ";	
		}
		cout<<endl;
	}
	cout<<dp[n][m]<<endl;
    return 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
#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005;
int a,b,d,k,cnt;
long long ans1,ans2;
bool st[maxn];
int dp[100];
int c[100],w[100];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			if(j>=w[i])
			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
		}
		//for(int k=1;k<=m;k++)cout<<dp[k]<<" ";
		//cout<<endl;
	}
	cout<<dp[m]<<endl;
    return 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
#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100005;
int a,b,d,k,cnt;
long long ans1,ans2;
bool st[maxn];
int dp[100];
int c[100],w[100];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			for(int k=0;k<=j/w[i];k++)
				dp[j]=max(dp[j],dp[j-k*w[i]]+k*c[i]);
		}
	}
	cout<<dp[m]<<endl;
    return 0;
}

优化版本

1

图论

并查集

并查集(Union-find Sets)主要用来处理一些不相交集合的合并问题。

如求连通子图，求最小生成树的Kruskal算法和求最近公共祖先(LCA)等。

并查集的基本操作：

  1. 初始化init
  2. 查询find
  3. 合并union

初始化

1
2
3
4
5
int fa[MAXN];
void init(int n){
	for(int i=1;i<=n;i++)
		fa[i]=i;
}

用fa[]来存储每个元素的父结点。开始时，我们将它们的父结点初始化为它们自己。

因为最开始它们没有任何关系。之后合并才产生关系。

查询

找到i的祖先直接返回，未进行路径压缩。

1
2
3
4
int find(int i){
	if(fa[i]==i)return i;//递归出口
	else return find(fa[i]);//不断向上查找祖先
}

合并

1
2
3
4
5
void union(int i,int j){
	int i_fa=find(i);//找到i的祖先
	int j_fa=find(j);//找到j的祖先
	fa[i_fa]=fa[j_fa];//i的祖先指向j的祖先
}

但是这样我们会发现，每次都会重复找，效率非常低下，比如我们要合并(4,5),要去找4的祖先，合并(4,7)，还是要4的祖先，合并(4,100000000),依旧要找4的祖先，这条链很长，重复找的话会使时间复杂度变大。我们思考：那有什么办法可以压缩路径节省时间呢。

路径压缩

1
2
3
4
5
6
7
int find(int i){
	if(i==fa[i])return i;
	else{
		fa[i]=find(fa[i]);//直接设置f[i]的父结点
		return fa[i];
	}
}

before:

after:

题目：P3367 【模板】并查集 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

AC代码：

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
#include<iostream>
#include<cstdio>
const int maxn=1e5+1;
using namespace std;
int fa[maxn],b[maxn],map[maxn];
int find(int i){
	if(i==fa[i])return i;
	else{
		fa[i]=find(fa[i]);//直接设置f[i]的父结点
		return fa[i];
	}
}
void unionn(int i,int j){
	int i_fa=find(i);//找到i的祖先
	int j_fa=find(j);//找到j的祖先
	fa[i_fa]=fa[j_fa];//i的祖先指向j的祖先
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){//父结点初始化为自己
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>z>>x>>y;
		if(z==1)unionn(x,y);
		else{
			if(find(x)==find(y))cout<<"Y"<<endl;
			else cout<<"N"<<endl;
		}
	}
    return 0; 
}

贪心算法

基本定义

顾名思义，采用贪心策略，保证每次操作都是局部最优，从而使最后得到的结果是全局最优的。

分配问题

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干由一个大小。每个饼干有个大小。每个孩子只能吃最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入输出样例：

1
2
3
4
输入：2 3
     1 2
     1 2 3
输出：2

题解：

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。

简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cstdio>
#include<cmath>
#include <algorithm>
#include <string>
const int maxn=1e5;
using namespace std;
typedef long long ll;

int main(){
	int cookies[maxn];
	int children[maxn];
	int n,m;//孩子和饼干数量 
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>children[i]; 
	for(int i=0;i<m;i++)cin>>cookies[i];
	sort(children,children+n);
	sort(cookies,cookies+m);
	int i=0,j=0;
	while(i<n&&j<m){
		if(children[i]<=cookies[j++])i++;
	}
	cout<<i<<endl;
	return 0;
}

区间问题

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

输入输出样例

1
2
3
4
5
input: 3
	   1 2
       2 4
       1 3
output:1

移除[1,3]，剩下区间便不会重叠

题解

在选择要保留区间时，区间的结尾十分重要:选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。

因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。具体实现方法为， 先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。在样例中，排序后的数组为[[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]; 由于[1,3]与[1,2]相交,我们跳过该区间;由于[2,4]与[1,2]不相交,我们将其保留。因此最终保留的区间为[[1 ,2], [2,4]]。

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include <algorithm>
#include <string>
const int maxn=1e5;
using namespace std;
typedef long long ll;

struct cnt{  
    int a;  
    int b;  
} node[103];  
int cmd(cnt x, cnt y){  
    return x.b < y.b;  
} 
int main(){
	int n; 
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>node[i].a>>node[i].b;
		
	}
	sort(node,node+n,cmd);
	int count=0;//满足的区间个数 
	int pre=node[0].b;//第一个元素的结尾 
	for(int i=1;i<n;i++){
		if(node[i].b>=pre){//当前元素 的结尾大于前一个元素的结尾，说明是可以选择的 
			++count;
			pre=node[i].b;
		}
		
	}
	cout<<n-count<<endl;
	return 0;
}

买卖股票的最佳时机

给定一个数组，它的第i个元素是一支给定 股票第i天的价格。

股票)

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入输出样例

1
2
3
4
输入:7 1 5 3 6 4
输出:7
//在第二天（price=1）的时候买入，在第三天（price=5）的时候卖出，这笔交易所能获得利润=5-1=4
随后，在第4天（price=3）的时候买入，在第5天（price=6）的时候卖出，这笔交易所能获得利润=6-3=3.

题解

贪心的思想：如果今天买明天卖可以赚钱，那就买入。

贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<cstdio>
#include<cmath>
#include <algorithm>
#include <string>
const int maxn=1e5;
using namespace std;
typedef long long ll;

int main(){
	int a[maxn],n=0;
	while(cin>>a[n]){
		if(cin.get()=='\n')break;
		n++;
	}
	int profit=0;
	for(int i=0;i<n-1;i++){
		if(a[i]<a[i+1])profit+=a[i+1]-a[i];
	}
	cout<<profit<<endl;
	return 0;
}

不过很多时候贪心往往得不到最优解，所以选择贪心的时候一定要慎重。

数论

莫比乌斯反演

前置知识

容斥原理

两集合容斥原理：

AUB=A+B-A∩B=总数-外

三集合容斥原理：

W=AUBUC-A∩B-A∩C-B∩C+A∩B∩C

素数筛

也叫[Eratosthenes筛法(埃式筛法)

时间复杂度O(nloglogn)

理论依据：唯一分解定力（算术基本定理）

任何一个数至少存在一个小于等于自己的质因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<cstdio>
#include<cmath>
#include <algorithm>
#include <string>
using namespace std;
bool a[100001000];//初始化为0说明一开始都是素数 
int main(){
	int n,s=0;
	cin>>n;
	for(int i=2;i<=n;i++){//1肯定不是素数，略过 
		if(a[i]==0){//如果a[i]是素数，那么它的倍数一定不是素数，筛掉 
			for(int j=2;j*i<=n;j++){//它的倍数从2倍开始，j倍的i小于等于N 
				a[j*i]=1;//筛掉 ，就是达标记 
			}
			s++;//记录下a[i]这个素数 
		} 
	} 
	cout<<s<<endl;
	return 0;
}

线性筛

时间复杂度O(n)

思想：用最小的质因子把它筛掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstdio>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int prime[100001000];//prime[i]就是i的最小质因子 
int tag[100001000];
int cnt=0;

int prim(int n){
	tag[0]=1;
	tag[2]=0;
	prime[0]=2;
	cnt=1;
	for(int i=3;i<=n;i+=2){
		if(!tag[i]){
			prime[cnt++]=i;
		}
		for(int j=0;j<cnt&&i*prime[j]<=n;j++){
			tag[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
	return cnt;
}
int main(){
	int n,s=0;
	cin>>n;
	cout<<prim(n)<<endl;
	return 0;
}

交换位运算

异或运算，相同为0，不同为1。也可以理解为不进位加法。

swap：

1
2
3
4
//满足交换律和结合律，
a = a ^ b; //a = 甲 ^ 乙， b=乙
b = a ^ b; //a = 甲 ^ 乙， b=甲 ^ 乙 ^ 乙=甲
a = a ^ b; //a = 甲 ^ 乙 ^ 甲 = 乙 ，b = 甲

这样就完成了a和b的交换，前提：a 和 b的内存必须是不同的两块

思考：

1.一组数中只有一个数出现了奇数次，其他数出现了偶数次 ，怎么找到那个出现了奇数次的数？

O(n)；

int eor=0; for(int i=0;i<arr.length;i++){ eor^=a[i];} 最后eor就是那个出现奇数次的数

二分

大部分是有序才二分，比如找某个值，找 >=num的最左侧值，但是找局部最小值也可以二分，先看两边，如果直接首尾直接是局部最小值直接返回，否则一直二分，总会找到一个局部最小值

反转链表

准备两个指针，一个pre，一个cur，再来一个temp保持cur->next，先让cur->next指向pre，然后移动pre到cur的位置，最后再移动cur到temp的位置

最后返回pre即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=NULL;
        ListNode* cur=head;
        while(cur!=NULL){
            ListNode* temp=cur->next;
            cur->next=pre; //改变指向
            pre=cur; //移动pre
            cur=temp; //移动cur（
        }
        return pre;
    }
};

字符串

manacher

求最长回文子串

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
class Solution {
public:
    int getLongestPalindrome(string A) {
        // write code here
        char str[A.length()];
        strcpy(str, A.c_str()); //A转字符数组
        int reslen = A.length() * 2 + 1;
        char res[reslen];
        int index = 0;
	for(int i = 0; i < reslen; i++){ //增加特殊字符方便处理奇偶问题
        //如果下标是奇数位置，则插入#，否则拷贝原数组字符
		res[i] = (i & 1) == 0 ? '#' : str[index++];
	}
    //回文半径数组
	int Rarr[reslen];
	int c = -1;//中心
	int r = -1;//最右边界的下一个位置
	int maxx=1;
	for(int i = 0;i < reslen; i++){//从i位置开始每次都扩充
        //拿到至少不用判断的回文半径
		Rarr[i] = r > i ? min(Rarr[2*c-i], r-i) : 1;
        //跳过捷径往外扩
		while(i + Rarr[i] < reslen && i-Rarr[i] > -1){
			if(res[i + Rarr[i]] == res[i - Rarr[i]]){
				Rarr[i]++;
			}else {
				break;
			}
		}
		if(i + Rarr[i] > r){
			r = i + Rarr[i];
			c = i;
		}
		maxx=max(maxx,Rarr[i]);
	}
	return maxx-1;
    }
};

二叉树

如何判断一个链表是否有环？

  • set容器，每遍历一个结点就看set里面有没有重复，如果没有就放在set容器里，否则那个结点就是第一个入环结点（需要额外空间）
  • 快慢指针：快指针走两步，慢指针走一步，如果快指针走到null则无环；否则当快慢指针第一次相遇的时候，快指针回到原点，慢指针留在原地，之后快慢指针都一步一步走，当快慢指针第一次相遇时那个结点就是入环结点

两个链表可能有环也可能无环，求第一个相交结点：

image-20220307145023310

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
121
122
123
124
125
126
127
128
129
130
131
package class_04;

public class Code_07_FindFirstIntersectNode {

	public static class Node {
		public int value;
		public Node next;
		
		public 	Node(int data) {
			this.value = data;
		}
	}
	
	//找到链表第一个入环节点，如果无环，返回null
	public static Node getLoopNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		Node n1 = head.next; //n1 -> slow
		Node n2 = head.next.next;  //n2 -> fast
		while (n1 != n2) {
			if(n2.next==null||n2.next.next==null) {
				return null;
			}
			n1=n1.next;
			n2=n2.next.next;
		}
		//跳出循环说明快慢指针已经相遇了
		n2=head;
		while(n1!=n2) {
			n1=n1.next;
			n2=n2.next;
		}
		return n1;
	}
	
	//如果两个链表都无环，返回第一个相交结点，如果不相交返回null
	public static Node noLoop(Node head1, Node head2) {
		if(head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		
		int len1=0;
		int len2=0;
		
		while(cur1.next!=null) { //不是要走到空，而是要走到最后一个结点
			len1++;
			cur1 = cur1.next;
		}
		while(cur2.next!=null) {
			len2++;
			cur2=cur2.next;
		}
		if(cur1!=cur2) {
			return null;
		}
		
		if(len1>len2) {
			cur1=head1;
			cur2=head2;
		}else {
			cur1=head2;
			cur2=head1;
		}
		
		int n=len1-len2;
		while(Math.abs(n)!=0) {
			n--;
			cur1=cur1.next;
		}
		while (cur1!=cur2) {
			cur1=cur1.next;
			cur2=cur2.next;
		}
		return cur1;
	}
	
	//两个有环链表，返回第一个相交结点，如果不相交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		if(loop1==loop2) {//入环结点相同,当作无环链表处理，loop1和loop2是链表的终止结点
			cur1=head1;
			cur2=head2;
			int len1=0;
			int len2=0;
			while (cur1!=loop1) {
				len1++;
				cur1=cur1.next;
			}
			while (cur2!=loop2) {
				len2++;
				cur2=cur2.next;
			}
			if(len1>len2) {
				cur1=head1;
				cur2=head2;
			}else {
				cur1=head2;
				cur2=head1;
			}
			int n=len1-len2;
			while(Math.abs(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;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

二叉树的遍历

递归实现先，中，后序遍历

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
public class code01_PreInPosTranversal {
	public static class Node {
		public int value;
		public Node left;
		public Node right;
		public Node(int data) {
			this.value = data;
		}
	}

	public static void f(Node head) {
		if(head==null) {
			return ;
		}
		f(head.left);
		f(head.right);
	}
	
	public static void preOrderRecur(Node head) {
		if(head==null) {
			return ;
		}
		System.out.print(head.value+" ");
		preOrderRecur(head.left);
		preOrderRecur(head.right);
	}
	
	public static void inOrderRecur(Node head) {
		if(head==null) {
			return ;
		}
		
		inOrderRecur(head.left);
		System.out.print(head.value+" ");
		inOrderRecur(head.right);
	}
	
	public static void posOrderRecur(Node head) {
		if (head==null) {
			return;
		}
		
		posOrderRecur(head.left);
		posOrderRecur(head.right);
		System.out.print(head.value+" ");
	}
}

非递归实现

既然系统不帮我们实现压栈，那就自己实现。

前序遍历

准备一个栈，

  1. 每次从栈中弹出一个结点cur
  2. 打印（处理）cur
  3. 先右再左（如果有）
  4. 重复上述步骤

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void preOrderUnRecur(Node head) {
		System.out.print("pre-order");
		if(head!=null) {
			//准备一个栈
			Stack<Node>stack=new Stack<Node>();
			//头结点压栈
			stack.add(head);
			while(!stack.isEmpty()) {
				//从栈中弹出一个结点，赋给head
				head=stack.pop();
				//打印当前结点
				System.out.print(head.value+" ");
				if(head.right!=null) {
					stack.push(head.right);
				}
				if(head.left!=null) {
					stack.push(head.left);
				}
			}
		}
		System.out.println();
	}
中序遍历

准备一个栈：

  1. 先把所有左子树入栈
  2. 弹出，打印，如果有右子树，右树入栈（其所有左子树一并入栈）
  3. 重复上述步骤

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void inOrderUnRecur(Node head) {
		System.out.print("in-order");
		if(head!=null) {
			Stack<Node>stack=new Stack<Node>();
			while(!stack.isEmpty()||head!=null) {
				//此分支的所有左子树入栈
				if(head!=null) {
					stack.push(head);
					head=head.left;
				}
				else {
					//弹出结点并打印，然后移动到右树上，继续上面的步骤
					head=stack.pop();
					System.out.print(head.value+" ");
					head=head.right;
				}
			}
		}
		System.out.println();
	}

理解：任何一颗二叉树都可以根据左树划分，比如左头右，但是右可以继续分成左头

这样就形成了循环，因为右树总是后面遍历的，总有一天会遇到空的情况。所以就是我们要求的中序遍历。

后序遍历

准备两个栈：

  1. 弹出cur
  2. 将cur放入收集栈
  3. 先左再右
  4. 重复上述步骤

原理：

s1中的顺序是头右左

s2中的顺序是左右头，刚好实现后序遍历

code：

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
public static void posOrderUnRecur(Node head) {
		System.out.print("pos-order");
		if(head!=null) {
			//准备2个栈
			Stack<Node>s1=new Stack<Node>();
			Stack<Node>s2=new Stack<Node>();
			//头结点压栈
			s1.add(head);
			while(!s1.isEmpty()) {
				//从栈中弹出一个结点，赋给head
				head=s1.pop();
				s2.push(head);
				if(head.left!=null) {
					s1.push(head.left);
				}
	
				if(head.right!=null) {
					s1.push(head.right);
				}
			}
			while(!s2.isEmpty()) {
				System.out.print(s2.pop().value+" ");
			}
		}
		System.out.println();
	}

如何直观打印一棵二叉树

。。。

二叉树的广度优先遍历

队列先进先出

头入队，弹出头，打印头，然后左右孩子入队，左孩子出队，打印，左孩子的左右孩子入队，重复此过程

在 java中LinkedList就是队列，因为双向链表可以用来充当队列。

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void w(Node head) {
		if(head==null) {
			return ;
		}
		Queue<Node> queue=new LinkedList<>();
        //头结点入队
		queue.add(head);
		while(!queue.isEmpty()) {
            //弹出结点
			Node cur = queue.poll();
            //打印结点
			System.out.print(cur.value+" ");
            //左右孩子入队
			if(cur.left!=null) {
				queue.add(cur.left);
			}
			if(cur.right!=null) {
				queue.add(cur.right);
			}
		}
	}
Q:求一棵二叉树的宽度

way one：使用hash表

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
public static void w(Node head) {
		if(head==null) {
			return ;
		}
		Queue<Node> queue=new LinkedList<>();
		queue.add(head);
        //用来记录当前结点已经当前结点所在的层
		HashMap<Node,Integer> levelMap = new HashMap<>();
        //head在第一层
		levelMap.put(head,1);
        //当前的遍历到的层数
		int curLevel=1;
        //当前层的结点数
		int curLevelNodes=0;
        //记录层的最大结点数
		int max=Integer.MIN_VALUE;
		while(!queue.isEmpty()) {
			Node cur = queue.poll();
            //获取当前结点所在的层
			int curNodeLevel=levelMap.get(cur);
            //如果结点所在的层数等于当前遍历到的层数
			if(curNodeLevel==curLevel) {
                //当前层的结点数+1
				curLevelNodes++;
			}else {//说明已经遍历到下一层了
                //更新max
				max=Math.max(max, curLevelNodes);
                //遍历的层数+1
				curLevel++;
                //当前层的结点数置零
				curLevelNodes=0;
			}
			System.out.print(cur.value+" ");
			if(cur.left!=null) {
                //存入当前结点的左孩子，以及左孩子所在的层
				levelMap.put(cur.left, curNodeLevel+1);
				queue.add(cur.left);
			}
			if(cur.right!=null) {
                //存入当前结点的右孩子，以及右孩子所在的层
				levelMap.put(cur.right, curNodeLevel+1);
				queue.add(cur.right);
			}
		}
	}

way two： 不用hash表

用4个变量

  1. curend
  2. nextend
  3. curnodes
  4. max

code：

1
//略

搜索二叉树

即每一棵树左树都比右树小

image-20220319221131090

如何判断一棵树是不是搜索二叉树？

用中序遍历一下，如果一直都是升序，则说明是。如果出现降序，则不是。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static int preValue = integer.MIN_VELUE; //全局变量
public static boolean checkBST(Node head) {
	if(head = null){
		return true;
	}
	boolean isLeftBst=checkBST(head.left);
	if(!isLeftBst){
		return false;
	}
	if(head.value<=preValue){
		return false;
	}else {
		preValue=head.value;
	}
	return checkBST(head.right);
}

code2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static boolean checkBST2(Node head) {
		if(head!=null) {
            int preValue = Integer.MIN_VALUE;
			Stack<Node>stack=new Stack<Node>();
			while(!stack.isEmpty()||head!=null) {
				//此分支的所有左子树入栈
				if(head!=null) {
					stack.push(head);
					head=head.left;
				}
				else {
					//弹出结点并打印，然后移动到右树上，继续上面的步骤
					head=stack.pop();
					if(head.value<=preValue){
                        return false;
                    }else {
                        preValue = head.value;
                    }
					head=head.right;
				}
			}
		}
		System.out.println();
	}

完全二叉树

如何判断一颗二叉树是不是完全二叉树？

  1. 任一结点，有右无左，返回false
  2. 在不违背1的基础上，如果遇到了第一个左右孩子不全的结点，则后续遇到的结点必须全部是叶节点，否则返回false

code

1