基础算法汇总

文章目录 一、快速排序1. 快排2.第k个值（快排应用） 二、归并排序3.归并排序4.逆序对（归并应用） 三、二分5.数的范围（二分应用）6.数的三次方根（二分应用） 四、高精度7.高精度加法8.高精度减法9.高精度乘法10.高精度除法 五、前缀和与差分11.前缀和12.子矩阵的和（前缀和）13.差分（前缀和的逆运算）14.差分矩阵 六、双指针15.最长连续不重复子序列（双指针）16.判断子序列 七、位运算17.位运算 八、离散化18.区间和（离散化：域很大，点稀疏） 九、区间合并19.区间合并

一、快速排序 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); } 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)); } } 二、归并排序 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]+" "); } } } 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; } 三、二分 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+" "); } } } } 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); } } 四、高精度 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); } 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); } } 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); } } 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); } } 五、前缀和与差分 11.前缀和 for(int i=0;i<n;i++){ sum[i+1]=sum[i]+nums[i]; } 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]); 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]+" "); } } } 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]; } } 六、双指针 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); } } 16.判断子序列 int i=0,j=0; while(i<n&&j<m){ if(a[i]==b[j])i++; j++; } 七、位运算 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); } }

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

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

-x=(~x+1)

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

二进制中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+" "); } } } 八、离散化 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; } } 九、区间合并 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; } }