文章目录

• • 一、快速排序
  • • 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(leftwhile(left=ans){right--;}arrays[left]=arrays[right];while(leftleft++;}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(ido i++;while(nums[i]ans);if(iint 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;inums[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]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;inums[i]=scanner.nextInt();}sort(0,n-1);for(int i=0;iSystem.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;inums[i]=scanner.nextInt();}for(int i=0;iint target=scanner.nextInt();int l=0,r=n-1;//找左边界while(lint 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(lint 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 res = new ArrayList<>();int k=0;for(int i=0;iif(ik+=aa.get(i);}if(ik+=bb.get(i);}res.add(k%10);k=k/10;}if(k>0){res.add(1);}

8.高精度减法

	static void subtract(ArrayList a,ArrayListb){int k=0;for(int i=0;ik=a.get(i)-k;if(ik-=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;i0;i++){if(it+=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;ir=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;isum[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] 之间的每个数加上 cimport 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;iint 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;inums[i]=scanner.nextInt();}int res=0;for(int i=0,j=0;iwhile(jas[nums[j]]++;j++;}res=Math.max(res,j-i);as[nums[i]]--;}System.out.println(res);}}

16.判断子序列

  int i=0,j=0;while(iif(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 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;elsel = 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 add = new ArrayList<>();// 保存求和区间ArrayList 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(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 merge(ArrayList list) {ArrayList res = new ArrayList();int st=(int) -2e9,ed=(int) -2e9;for(Pair pair:list) {if(edif(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 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() {@Overridepublic 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;}}