# algorithm

**Repository Path**: x-yunfei/algorithm

## Basic Information

- **Project Name**: algorithm
- **Description**: 算法刷题仓库
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 7
- **Forks**: 0
- **Created**: 2022-12-18
- **Last Updated**: 2024-12-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README



## 算数基本定理

任何一个大于1的自然数N，如果N不为质数，都可以唯一分解成有限个[质数](https://baike.baidu.com/item/质数?fromModule=lemma_inlink)的乘积

![img](https://bkimg.cdn.bcebos.com/formula/d879b88987aa2544a64c94be0e5af01a.svg)

它的正[因数](https://baike.baidu.com/item/因数?fromModule=lemma_inlink)个数为

![img](https://bkimg.cdn.bcebos.com/formula/70a59ee42e34cee1aa27ca4c8803ce72.svg)

 ## 质数预处理

判断某一区间内的数是否为质数(埃氏筛)

```
static boolean[] is_prime=new boolean[N];

//预处理出所有的质数
public static void get_primes(int n){
    for (int i = 2; i <= n; ++i) {
        is_prime[i] = true;
    }
    for (int i = 2; i <= n; ++i) {
        for (int j = i * 2; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}
```

## 给定字符串和进制数求十进制数(秦九韶算法)

```
public static int base(String s,int b){
	int res=0;
	for(int i=0;i<s.length();i++){
		res=res*b+(s.charAt(i)-'0');	//乘b相当于左移一位，右边补一个0
	}
	return res;
}
```

## 求最大公约数

```
//最大公约数
public static int gcd(int a,int b) {
	if(a%b==0) {
		return b;
	}
	return gcd(b,a%b);
}
```

## 求最小公倍数

```
//最小公倍数
public static int lcd(int a,int b) {
	return a*b/gcd(a,b);
}
```

## 求组合函数

```
//求组合函数,a大b小
public static int C(int a,int b) {
	int res=1;
    for(int i=a,j=1;j<=b;i--,j++) {
    	res=res*i/j;
    }
    return res;
}
```

## 求排列函数

```
// 求排列数 A(n,m) n>m
public static int A(int n, int m) {
	int result = 1;
	// 循环m次,如A(6,2)需要循环2次，6*5
	for (int i = m; i > 0; i--) {
		result *= n;
		n--;// 下一次减一
	}
	return result;
}
```



## 前缀和

### 一维前缀和

#### 	预处理公式:

```
s[i]=s[i-1]+a[i];
```

#### 	区间和公式[l,r]:

```
ans=s[r]-s[l-1];
```

### 二维前缀和

#### 	预处理公式

```
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
```

#### 	区间和公式(x1,y1)到(x2,y2):

```
ans=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
```



## 差分

### 一维差分

#### 	预处理公式:

```
b[i]=a[i]-a[i-1];  		//差分与前缀和互为逆运算
```

#### 	给区间[l,r]每个数加上c:

```
b[l]+=c;		//相当于给每个i>=l的a[i]加上了c
b[r+1]-=c;		//相当于给每个i>=r+1的a[i]减了c
```

```
//差分加减c之后再求前缀和即为结果
for(int i=1;i<=n;i++){
	b[i]+=b[i-1];		//求前缀和
}
```

### 二维差分

#### 预处理公式:

```
//1.直接构建
b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
//2.利用下列函数
insert(i,j,i,j,a[i][j]);
```

#### 给(x1,y1)到(x2,y2)范围内的数加c:

```
//封装函数，相当于个该范围内的数加上c
public void insert(int x1,int y1,int x2,int y2,int c){
	b[x1][y1]+=c;
	b[x1][y2+1]-=c;
	b[x2+1][y1]-=c;
	b[x2+1][y2+1]+=c;
}
```

```
//加完c后利用二维前缀和求结果
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
	}
}
```

## 二分

```
//在arr数组的区间[1,n]上找target
int l=0,r=n;
while(l<r){
	int mid=l+r>>1;
	if(arr[mid]>=target){
		r=mid;
	}else{
		l=mid+1;
	}
}
```

## 双指针

两个索引之间存在单调的函数关系，即j=f(i)，可以把O(n*n)优化到O(n);

```
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        String T = sc.next();
        char[] str1 = S.toCharArray();
        char[] str2 = T.toCharArray();
        int count=0;
        for(int i=0,j=0;i<str1.length;i++){
            if(str1[i]==str2[j]){
                count++;
                j++;
            }
        }
        System.out.println(count);
    }
}
```



## 二叉树

```
import java.util.Arrays;
import java.util.Scanner;

public class Ac3555 {

	static int N=1010;
	static int[] l=new int[N];	//表示左儿子
	static int[] r=new int[N];	//表示右儿子
	static int[] p=new int[N];	//表示父节点
	static int[] dist=new int[N];	//表示各个节点到根节点的距离
	
	//遍历二叉树,求各个节点到根节点的距离
 	public static void dfs(int i,int d) {	
		dist[i]=d;
		if(l[i]!=-1) {
			dfs(l[i],d+1);		//继续搜左儿子
		}
		if(r[i]!=-1) {
			dfs(r[i],d+1);		//继续搜右儿子
		}
	}
	
 	//爬树法求最近公共祖节点
 	public static int getLca(int a,int b) {
 		if(dist[a]>dist[b]) {
 			//默认a比b高
 			int temp=a;
 			a=b;
 			b=temp;
 		}
 		while(dist[a]<dist[b]) {
 			b=p[b];		//b往上爬直到与a同一高度
 		}
 		while(a!=b) {
 			a=p[a];
 			b=p[b];		//a,b继续往上爬直到ab相等
 		}
 		return a;
 	}
 	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		while(T-->0) {
			int n=sc.nextInt();
			int m=sc.nextInt();
			Arrays.fill(l, -1);
			Arrays.fill(r, -1);
			for(int i=1;i<=n;i++) {
				int a=sc.nextInt();
				int b=sc.nextInt();
				l[i]=a;
				r[i]=b;
				if(a!=-1) {
					p[a]=i;
				}
				if(b!=-1) {
					p[b]=i;
				}
			}
			dfs(1,0);		//深搜遍历算出各个节点离根节点的距离
			
			for(int i=1;i<=m;i++) {
				int a=sc.nextInt();
				int b=sc.nextInt();
				//两节点距离等于他们分别到根节点的距离之和减去两倍的最近公共祖节点到根节点的距离
				System.out.println(dist[a]+dist[b]-2*dist[getLca(a,b)]);	
			}
		}
	}
}
```

## DFS

```
import java.util.Scanner;

public class P8601 {
    
    private static int m;   //行数
    private static int n;   //列数
    private static int[][] chs;     //表示棋盘，从1开始
    private static boolean[][] isGo;    //表示该地是否走过
    private static int target;      //棋盘上数总和的一半
    private static int min = Integer.MAX_VALUE;         //输出结果,最小的格子数
    private static int xarr[] = {0,1,0,-1};    //走法
    private static int yarr[] = {1,0,-1,0};
    
    private static void dfs(int x,int y,int step,int sum){      //xy为当前横纵坐标,step为当前格子数,sum为当前总和
        if(sum == target){      //达到目标要求
            min = Math.min(min,step);
        }
        for(int i=0;i<4;i++){
            int dx = x + xarr[i];
            int dy = y + yarr[i];    
            if(dx>0 && dx<=m && dy>0 && dy<=n && !isGo[dx][dy]){      //剪枝: 不出界且没走过
                isGo[dx][dy] = true;
                dfs(dx,dy,step+1,sum+chs[dx][dy]);
                isGo[dx][dy] = false;     //回溯
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n =sc.nextInt();        //n列
        m =sc.nextInt();        //m行
        chs = new int[m+1][n+1];
        isGo =new boolean[m+1][n+1];
        int total = 0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                chs[i][j] = sc.nextInt();
                isGo[i][j] = false;
                total += chs[i][j];
            }
        }
        target = total/2;
        dfs(1,1,1,chs[1][1]);
        if(min == Integer.MAX_VALUE){
            System.out.println(0);
        }else {
            System.out.println(min);
        }
    }
}

```

## BFS

```
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Bfs {

	static int n,a,b;
	static int[][] g=new int[210][210];		//临接矩阵存储有向图
	static int[] dist=new int[210];		//表示到达当节点经过了几条边
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		a=sc.nextInt();
		b=sc.nextInt();
		//创建有向无权图
		for(int i=1;i<=n;i++) {
			int k=sc.nextInt();
			if(i+k<=n) {
				g[i][i+k]=1;
			}
			if(i-k>=1) {
				g[i][i-k]=1;
			}
		}
		//bfs求最短路径
		Arrays.fill(dist, -1);
		boolean[] st=new boolean[n+1];
		Queue<Integer> queue=new LinkedList<>();
		queue.add(a);
		st[a]=true;
		dist[a]=0;
		while(!queue.isEmpty()) {
			Integer i=queue.remove();		//当前节点
			if(i==b) {
				System.out.println(dist[i]);
				return;
			}
			for(int j=1;j<=n;j++) {
				if(!st[j] && g[i][j]==1) {	//若该节点未访问过并且有路径到达,则添加进队列并更新距离
					queue.add(j);
					st[j]=true;
					dist[j]=dist[i]+1;
				}
			}
		}
		System.out.println(-1);
	}
}
```

## Dijkstra(最短路径问题)

#### 求1到n的最短路径

```
static int n,m;
static int INF=(int)1e9;
static int[][] g=new int[1010][1010];       //存储有向图,初始化为INF
static int[] dist=new int[1010];      		//存储每个点到1号点的距离
static boolean[] st=new boolean[1010];      //存储该节点是否访问过

public static int dijkstra(){
	Arrays.fill(dist,INF);		//第一步,不能往后放
	dist[1]=0;					//若以x为起点,则改为dist[x]=0;
	for(int i=0;i<n-1;i++){		//遍历除起点以外的点
		//1.找出离起点最近的点
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j] && (t==-1 ||dist[j]<dist[t])){
				t=j;
			}
		}
		st[t]=true;
		//2.更新其邻居的距离
		for(int j=1;j<=n;j++){
			dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
		}
	}
	if(dist[n]==INF){			//若以y为终点,则改为dist[y]
		return -1;		//不存在,返回-1
	}
	return dist[n];
}
```



## 最小生成树

#### 什么是连通图？

​	在一个无向图中任意两节点之间都有路径相同，就是连通图

#### 什么是树？

​	如果一个无向连通图不含回路(没有环)，那么就是一颗树

#### 什么是最小生成树？

​	生成树是连通图的连通子图，包含连通图的全部顶点，有且仅有构成一颗树的的n-1条边(如果生成树中再加一条边必定构成环)，

连通图中所有生成树中边权之和最小的成为最小生成树

​	有向图：最短路径，无向图：最小生成树

#### 最小生成树的应用

​	要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

### Prim

prim与dijkstra相似，二者的区别在于：

​	1.dijkstra用于处理最短路径问题(有向图)；prim用于处理最小生成树问题(无向图)

​	2.dijkstra更新的是**节点到起点的距离**(dist存储的是到起点的距离)；prim更新的是**节点到集合的距离**(dist存储的是到集合的距离)

```
static int n,m;
static int INF=(int)1e9;
static int[][] g=new int[1010][1010];		//邻接矩阵
static int[] dist=new int[1010];			//表示各节点到集合的距离
static boolean[] st=new boolean[1010];		//表示该节点是否在集合中
//返回值为最小生成树的边权之和
public static int prim(){
	Arrays.fill(dist,INF);		//第一步,很关键别忘了
	int res=0;
	for(int i=0;i<n;i++){		//依次将n个节点加入到集合中
		int t=-1;
		//1.找出离集合最近的点
		for(int j=1;j<=n;j++){
			if(!st[j] && (t==-1 || dist[j]<dist[t])){
				t=j;
			}
		}
		if(i>0 && dist[t]==INF){
			return INF;			//图不连通
		}
		if(i>0){
			res+=dist[t];
		}
		st[t]=true;			//把当前节点加入到集合中
		//2.更新各个点到集合的距离
		for(int j=1;j<=n;j++){
			dist[j]=Math.min(dist[j],g[t][j]);
		}
	}
	return res;
}
```



## 并查集

并查集是一种树型的数据结构，用于处理一些不相交的集合的合并与查询问题

```
static int[] pre=new int[N];		//存储父节点

//查询该树的父节点
public static int find(int x){
	if(x!=pre[x]){			//根节点的pre等于它本身
		return find(pre[x]);
	}
	return pre[x];
}

//合并两颗树
public static void union(int a,int b){
	//找出两元素的根节点
	int x=find(a);
	int y=find(b);
	//把其中一个根节点的父节点设为另一个根节点
	pre[x]=y;
}
```

​	例题：合根植物

```
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class BingChaji {

	static int m,n,k;
	static int[] pre=new int[1010*1010];		//存储根节点
	
	//查找根节点
	public static int find(int x) {
		if(pre[x]==x) {
			return x;
		}
		return find(pre[x]);
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		m=sc.nextInt();
		n=sc.nextInt();
		k=sc.nextInt();
		for(int i=1;i<=m*n;i++) {
			pre[i]=i;		//默认根等于本身
		}
		for(int i=0;i<k;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int fa=find(a);
			int fb=find(b);
			if(fa!=fb) {
				pre[fa]=fb;		//根不相等,合并
			}
		}
		Set<Integer> set=new HashSet<>();
		for(int i=1;i<=m*n;i++) {
			set.add(find(i));
		}
		System.out.println(set.size());
	}
}
```



## 区间DP

​	核心思想：求解出小区间上的最优解并合并，进而求出大区间上的最优解

```
for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }
```