基础算法汇总

一、快速排序

1. 快排

	static void sort(int[]arrays,int left,int right){
        if(left>=right)return;
        int ans=arrays[left];
        int l=left,r=right;
        while(left<right){
            while(left<right&&arrays[right]>=ans){
                right--;
            }
            arrays[left]=arrays[right];
            while(left<right&&arrays[left]<=ans){
                left++;
            }
            arrays[right]=arrays[left];
        }
        arrays[left]=ans;
        sort(arrays,l,left-1);
        sort(arrays,left+1,r);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.第k个值（快排应用）

    import java.util.*;
    public class Main{
        static int N = 100010;
        static int n;
        static int k;
        static int[] nums=new int[N];
        static int sort(int k,int l,int r){
            if(l>=r)return nums[k];
            int ans=nums[l],i=l-1,j=r+1;
            while(i<j){
                do i++;while(nums[i]<ans);
                do j--;while(nums[j]>ans);
                if(i<j){
                    int tmp=nums[i];
                    nums[i]=nums[j];
                    nums[j]=tmp;
                }
            }
            if(k<=j)return sort(k,l,j);
            else return sort(k,j+1,r);
        }
        public static void main(String[]args){
            Scanner scanner=new Scanner(System.in);
            n=scanner.nextInt();
            k=scanner.nextInt();
            for(int i=0;i<n;i++){
                nums[i]=scanner.nextInt();
            }
            System.out.println(sort(k-1,0,n-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

二、归并排序

3.归并排序

    import java.util.*;
    public class Main{
        static int N = 100010;
        static int n;
        static int[]nums = new int[N];
        static int[]tmps = new int[N];
        static void sort(int l,int r){
            if(l>=r)return;
            int mid=(r+l)/2;
            sort(l,mid);
            sort(mid+1,r);
            int i=l,j=mid+1,k=0;
            while(i<=mid&&j<=r){
                if(nums[i]<nums[j]){
                    tmps[k++]=nums[i++];
                }else{ 
                    tmps[k++]=nums[j++];
                }
            }
            while(i<=mid){
                tmps[k++]=nums[i++];
            }
            while(j<=r){
                tmps[k++]=nums[j++];
            }
            for(int t=0,s=l;s<=r;t++,s++){
                nums[s]=tmps[t];
            }
        }
        public static void main(String[]args){
            Scanner scanner = new Scanner(System.in);
            n=scanner.nextInt();
            for(int i=0;i<n;i++){
                nums[i]=scanner.nextInt();
            }
            sort(0,n-1);
            for(int i=0;i<n;i++){
                System.out.print(nums[i]+" ");
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

4.逆序对（归并应用）

 	static long get(int l,int r){
        if(l>=r)return 0;
        int mid=(r+l)/2;
        long res=get(l,mid)+get(mid+1,r);
        int i=l,j=mid+1,k=0;
        while(i<=mid&&j<=r){
            if(nums[i]<=nums[j]){
                tmps[k++]=nums[i++];
            }else{ 
                tmps[k++]=nums[j++];
                res+=mid-i+1;
            }
        }
        while(i<=mid){
            tmps[k++]=nums[i++];
        }
        while(j<=r){
            tmps[k++]=nums[j++];
        }
        for(int t=0,s=l;s<=r;t++,s++){
            nums[s]=tmps[t];
        }
        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

三、二分

5.数的范围（二分应用）

  	import java.util.*;
    public class Main{
        public static void main(String[] args){
            Scanner scanner=new Scanner(System.in);
            int n=scanner.nextInt();
            int q=scanner.nextInt();
            int[] nums=new int[n];
            for(int i=0;i<n;i++){
                nums[i]=scanner.nextInt();
            }
            for(int i=0;i<q;i++){
                int target=scanner.nextInt();
                int l=0,r=n-1;
                //找左边界
                while(l<r){
                    int mid=(l+r)/2;
                    if(nums[mid]>=target){
                        r=mid;
                    }else {
                        l=mid+1;
                    }
                }
                if(nums[l]!=target){
                    System.out.println("-1 -1");
                }else{
                    System.out.print(l+" ");
                    l=0;
                    r=n-1;
                    //找右边界
                    while(l<r){
                        int mid=(l+r+1)/2;
                        if(nums[mid]<=target){
                            l=mid;
                        }else {
                            r=mid-1;
                        }
                    }
                    System.out.println(l+" ");
                }
            }
        }
    }
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

6.数的三次方根（二分应用）

 	import java.util.*;
    public class Main{
        public static void main(String[]args){
            Scanner scanner=new Scanner(System.in);
            double n=scanner.nextDouble();
            double l=-1000,r=1000;
            while(r-l>1e-8){
                double mid = (l+r)/2.0;
                if(mid*mid*mid>=n){
                    r=mid;
                }else{
                    l=mid;
                }
            }
            System.out.printf("%.6f",l);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

四、高精度

7.高精度加法

	List<Integer> res = new ArrayList<>();
    int k=0;
    for(int i=0;i<aa.size()||i<bb.size();i++){
        if(i<aa.size()){
            k+=aa.get(i);
        }
        if(i<bb.size()){
            k+=bb.get(i);
        }
        res.add(k%10);
        k=k/10;
    }
    if(k>0){
        res.add(1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

8.高精度减法

	static void subtract(ArrayList<Integer> a,ArrayList<Integer>b){
        int k=0;
        for(int i=0;i<a.size();i++){
            k=a.get(i)-k;
            if(i<b.size()){
                k-=b.get(i);
            }
            res.add((k+10)%10);
            if(k<0)k=1;
            else k=0;
        }
        while(res.size()>1&&res.get(res.size()-1)==0){
            res.remove(res.size()-1);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9.高精度乘法

	static void multiply(){
        for(int i=0,t=0;i<aa.size()||t>0;i++){
            if(i<aa.size()){
                t+=aa.get(i)*b;
            }
            res.add(t%10);
            t=t/10;
        }
        //去除前导零
        while(res.size()>1&&res.get(res.size()-1)==0){
            res.remove(res.size()-1);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

10.高精度除法

	static void div(){
       r=0;
        for(int i=0;i<nums.size();i++){
            r=r*10+nums.get(i);
            res.add(r/b);
            r=r%b;
        }
        while(res.size()>1&&res.get(0)==0){
            res.remove(0);
        }
    }
1
2
3
4
5
6
7
8
9
10
11

五、前缀和与差分

11.前缀和

	for(int i=0;i<n;i++){
	 	sum[i+1]=sum[i]+nums[i];
	 }
1
2
3

12.子矩阵的和（前缀和）

  for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
         sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+nums[i][j];
      }
  }
  System.out.println(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);
1
2
3
4
5
6

13.差分（前缀和的逆运算）

Bi=Ai-A(i-1)

Bi的前缀和就是A数组

Ai=Bi+B(i-1)+…+B1

    //接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r] 之间的每个数加上 c
    import java.util.*;
    public class Main{
        static final int N = 100010;
        static int[]a=new int[N];
        static int[]b=new int[N];
        static void insert(int l,int r,int c){
            b[l]+=c;
            b[r+1]-=c;
        }
        public static void main(String[]args){
            Scanner scanner = new Scanner(System.in);
            int n=scanner.nextInt();
            int m=scanner.nextInt();
            
            for(int i=1;i<=n;i++){
                a[i]=scanner.nextInt();
                insert(i,i,a[i]);
            }
            
            for(int i=0;i<m;i++){
                int l=scanner.nextInt();
                int r=scanner.nextInt();
                int c=scanner.nextInt();
                insert(l,r,c);
            }
            for(int i=1;i<=n;i++){
                b[i]+=b[i-1];
            }
            for(int i=1;i<=n;i++){
                System.out.print(b[i]+" ");
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

14.差分矩阵

    static 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;
    }
        
    for(int i=1;i<=n;i++){
       for(int j=1;j<=m;j++){
          insert(i,j,i,j,a[i][j]);
       }
    }
            
    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];
       }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

六、双指针

15.最长连续不重复子序列（双指针）

  import java.util.*;
    
  class Main{
      public static void main(String[] args){
          Scanner scanner=new Scanner(System.in);
          int[] as=new int[100005];
          int n=scanner.nextInt();
          int[] nums=new int[n];
          for(int i=0;i<n;i++){
              nums[i]=scanner.nextInt();
          }
          int res=0;
          for(int i=0,j=0;i<n;i++){
              while(j<n&&as[nums[j]]==0){
                  as[nums[j]]++;
                  j++;
              }
              res=Math.max(res,j-i);
              as[nums[i]]--;
          }
          System.out.println(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

16.判断子序列

  int i=0,j=0;
  while(i<n&&j<m){
    if(a[i]==b[j])i++;
    j++;
  }
1
2
3
4
5

七、位运算

17.位运算

n的二进制第k位是几

  public static void main(String[] args) {
 		int n=10;
 		for(int k=3;k>=0;k--) {
 			System.out.print(n>>k&1);
 		}
 	}
1
2
3
4
5
6

lowbit(x)：返回x的最后一位1

eg: 10=>1010，lowbit(10)=10

-x=(~x+1)

  static long lowbit(long x){
     return x&(-x);
   }
1
2
3

二进制中1的个数

	import java.util.*;
    
    public class Main {
        static long lowbit(long x){
            return x&(-x);
        }
    	public static void main(String[] args) {
    		Scanner scanner=new Scanner(System.in);
    		int n=scanner.nextInt();
    		while((n--)>0){
    		    long k=scanner.nextLong();
    		    int cnt=0;
    		    while(k>0){
    		        k-=lowbit(k);
    		        cnt++;
    		    }
    		    System.out.print(cnt+" ");
    		}
    	}
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

八、离散化

18.区间和（离散化：域很大，点稀疏）

   	import java.util.*;
    
    public class Main {
    	static final int N = 300010;
    	// 记录每个坐标
    	static ArrayList<Integer> alls = new ArrayList<>();
    
    	static int find(int x) {
    		int l = 0, r = alls.size() - 1;
    		while (l < r) {
    			int mid = l + r >> 1;
    			if (alls.get(mid) >= x)
    				r = mid;
    			else
    				l = mid + 1;
    		}
    		return r + 1;
    	}
    
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		int n = scanner.nextInt();
    		int m = scanner.nextInt();
    		// 离散化对应的值
    		int[] a = new int[N];
    		// 前缀和
    		int[] s = new int[N];
    
    		// 保存添加的位置和值
    		ArrayList<Pair> add = new ArrayList<>();
    		// 保存求和区间
    		ArrayList<Pair> query = new ArrayList<>();
    		for (int i = 0; i < n; i++) {
    			int x = scanner.nextInt();
    			int c = scanner.nextInt();
    			add.add(new Pair(x, c));
    			alls.add(x);
    		}
    		for (int i = 0; i < m; i++) {
    			int l = scanner.nextInt();
    			int r = scanner.nextInt();
    			query.add(new Pair(l, r));
    			alls.add(l);
    			alls.add(r);
    		}
    		// 对alls进行去重并排序
    		alls = new ArrayList<Integer>(new HashSet<>(alls));
    		Collections.sort(alls);
    
    		// 进行离散化
    		for (Pair pair : add) {
    			int x=find(pair.first);
    			a[x]+=pair.second;
    		}
    		//前缀和
    		for(int i=1;i<=alls.size();i++) {
    			s[i]=s[i-1]+a[i];
    		}
    		for(Pair pair:query) {
    			int l=find(pair.first);
    			int r=find(pair.second);
    			System.out.println(s[r]-s[l-1]);
    		}
    	}
    }
    
    class Pair {
    	int first;
    	int second;
    
    	public Pair(int first, int second) {
    		this.first = first;
    		this.second = second;
    	}
    
    	public String toString() {
    		return first + " " + second;
    	}
    }
    
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

九、区间合并

19.区间合并

 	import java.util.*;
    
    public class Main {
    	static ArrayList<Pair> merge(ArrayList<Pair> list) {
    		ArrayList<Pair> res = new ArrayList();
    		int st=(int) -2e9,ed=(int) -2e9;
    		for(Pair pair:list) {
    			if(ed<pair.first) {
    				if(st!=-2e9) {
    					res.add(new Pair(st, ed));
    				}
    				st=pair.first;
    				ed=pair.second;
    			}else {
    				ed=Math.max(ed, pair.second);
    			}
    		}
    		if(st!=-2e9) {
    			res.add(new Pair(st, ed));
    		}
    		return res;
    	}
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		int n = scanner.nextInt();
    		ArrayList<Pair> list = new ArrayList();
    		while ((n--) > 0) {
    			int l = scanner.nextInt();
    			int r = scanner.nextInt();
    			list.add(new Pair(l, r));
    		}
    		Collections.sort(list, new Comparator<Pair>() {
    			@Override
    			public int compare(Pair a, Pair b) {
    				return a.first - b.first;
    			}
    		});
    		list=merge(list);
    		System.out.println(list.size());
    	}
    }
    
    class Pair {
    	int first;
    	int second;
    
    	public Pair(int first, int second) {
    		this.first = first;
    		this.second = second;
    	}
    
    	public String toString() {
    		return first + " " + second;
    	}
    }
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