✔ ★算法基础笔记（Acwing）（一）—— 基础算法(20道题)【java版本】

一、快速排序

1. 快速排序例题

原题链接

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}quickSort(0,n-1,nums);for (int i=0; i<n; i++) {System.out.print(nums[i] + " ");}}public static void quickSort (int l,int r,int[] nums) {if(l>=r) {return;}int x = nums[(l+r)/2];int i = l - 1,j = r + 1;while (i < j) {while (nums[++i] < x);while (nums[--j] > x);if (i < j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}}quickSort(l,j,nums);quickSort(j+1,r,nums);}
}

2. 第k个数( 快速选择 ) ✔ ✔1.31

原题链接

import java.util.*;public class Main {public static int k;public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();k = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}System.out.print(quickSortTheK_thNumber(0,n-1,nums));}public static int quickSortTheK_thNumber (int l,int r,int[] nums) {if (l >= r) {return nums[r];}int x = nums[(l+r)>>1];int i = l - 1, j = r + 1;while (i < j) {while (nums[++i] < x);while (nums[--j] > x);if (i < j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}}if (j < k-1) {return quickSortTheK_thNumber(j+1,r,nums);} else {return quickSortTheK_thNumber(l,j,nums);}}
}

★快排二刷总结( 4点 )

1. if (l >= r) return;
2. 没有等于号
3. 交换有条件if (i < j) swap(q[i], q[j]);
4. 基值要固定x = q[l + r >> 1]
5. j最后的角标表示 l-j 是小于x的

二、归并排序

void merge_sort(int q[], int l, int r)
{if (l >= r) return;int mid = l + r >> 1;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

1. 先分段
2. 用一个额外数组，汇总两个分数组的排序

1. 归并排序模板题 ✔ ✔1.31

★二刷总结

1. r = mid + 1
2. while if
3. temp 的k = 1
   a 的i = L

原题链接

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}merge_sort(0,n-1,nums);for (int i = 0; i < n; i++) {System.out.print(nums[i] + " ");}}public static void merge_sort (int l,int r,int[] nums) {if (l >= r) {return;}int mid = (l+r) >> 1;int i = l,j = mid + 1;merge_sort(l,mid,nums);merge_sort(mid+1,r,nums);int[] temp = new int[r - l + 1];int k = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];}}while (i <= mid) {temp[k++] = nums[i++];}while (j <= r) {temp[k++] = nums[j++];}for (int q = l,p = 0; q <= r; q++) {nums[q] = temp[p++];}}
}

★2. 逆序对的数量 ✔ ✔1.31

原题链接

★二刷总结

1. java中new不能全new

import java.util.*;public class Main {public static long ans = 0;public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}numberOfReverseOrderPairs(0,n-1,nums);System.out.print(ans);}public static void numberOfReverseOrderPairs(int l,int r,int[] nums){if (l >= r) {return;}int mid = (l+r)>>1;int i = l,j = mid+1;numberOfReverseOrderPairs(l,mid,nums);numberOfReverseOrderPairs(mid+1,r,nums);int[] temp = new int[r-l+1];int k = 0;while (i <= mid && j <= r) {if (nums[i] <= nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];ans += mid - i + 1;}}while (i <= mid) {temp[k++] = nums[i++];}while (j <= r) {temp[k++] = nums[j++];}for (int q = l,p = 0; q <= r; q++) {nums[q] = temp[p++];}}
}

三、二分

1. 数的范围 ✔1.31

原题链接

★二刷总结(mid >= x 则是 输出最左边一个)

第一个大于等于x的数 || 最后一个大于等于x的数

mid < x 则是 往右

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}for (int i = 0; i < m; i++) {int x = scanner.nextInt();int p = 0,q = 0;int l = 0,r = n-1;while (l < r) {int mid = (l+r)>>1;if (nums[mid] < x) {l = mid+1;} else {r = mid;}}p = r;l = 0;r = n-1;while (l < r) {int mid = (l+r+1)>>1;if (nums[mid] <= x) {l = mid;} else {r = mid - 1;}}q = r;if (nums[q] != x) {System.out.println(-1 + " " + -1); } else {System.out.println(p + " " + q);}}}
}

★2. 数的三次方根 1e-8 ✔1.31

原题链接

二刷总结

1. 精确度是1e-8
2. l或者r直接等于mid

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);double n = scanner.nextDouble();double l = (double)-1e5;double r = 1e5*1.0;while (r - l > 1e-8) {double mid = (l+r)/2;if (mid * mid * mid <= n) {l = mid;} else {r = mid;}}System.out.printf("%.6f",l);}
}

四、高精度

1. 高精度加法 ✔1.31

原题链接
二刷：

1. 因为先计算小数，所以先把小数入 vector
2. 存放的时候先存放小数，这样i 一个角标就可以作为两个数的运算位置进行运算，如果相反的话，因为需要先计算最小值，那么就需要用两个角标指向最小值了
   

BigInteger

import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);BigInteger a = scanner.nextBigInteger();BigInteger b = scanner.nextBigInteger();System.out.println(a.add(b));scanner.close();}}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();List<Integer> A = new ArrayList<>(s1.length());List<Integer> B = new ArrayList<>(s2.length());for (int i = s1.length() - 1; i >= 0; i--) A.add(s1.charAt(i) - '0');for (int i = s2.length() - 1; i >= 0; i--) B.add(s2.charAt(i) - '0');List<Integer> C = add(A, B);for (int i = C.size() - 1; i >= 0; i--) System.out.printf(C.get(i) + "");}private static List<Integer> add(List<Integer> A, List<Integer> B) {List<Integer>C=new ArrayList<>(Math.max(A.size(),B.size())+2);int t=0;for(int i=0;i<A.size() || i<B.size();i++){if(i<A.size())t+=A.get(i);if(i<B.size())t+=B.get(i);C.add(t%10);t/=10;}if(t!=0) C.add(t);return C;}
}

2. 高精度减法 ✔1.31

原题链接

二刷：

1. 小减大 需要转换成 大-小
2. 如果出现负数 (x+10)%10 t = 1不是-1
3. t = a[i] - t; t = t - b[i]

a.subtract(b)

import java.io.*;
import java.math.BigInteger;public class Main {public static void main(String[] args) throws IOException{BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));BigInteger a = new BigInteger(reader.readLine());BigInteger b = new BigInteger(reader.readLine());System.out.println(a.subtract(b));reader.close();}
}

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;public class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();List<Integer> A = new ArrayList<>();List<Integer> B = new ArrayList<>();for(int i = s1.length() - 1;i >= 0;i --) A.add(s1.charAt(i) - '0');for(int i = s2.length() - 1;i  >= 0; i --) B.add(s2.charAt(i) - '0');if(!cmp(A,B)){System.out.print("-");}List<Integer> C = sub(A,B);for(int i = C.size() - 1;i >= 0; i --){System.out.print(C.get(i));}}public static List<Integer> sub(List<Integer> A,List<Integer> B){if(!cmp(A,B)){return sub(B,A);}List<Integer> C = new ArrayList<>();int t = 0;for(int i = 0;i < A.size();i ++){//这里应该是A.get(i) - B.get(i) - t ，因为可能B为零，所以需要判断一下是不是存在t = A.get(i) - t;if(i < B.size()) t -= B.get(i);C.add((t + 10) % 10);if(t < 0) t = 1;else t = 0;}//删除指定下标下面的值while(C.size() > 1 && C.get(C.size() - 1) == 0)  C.remove(C.size() - 1);return C;}public static boolean cmp(List<Integer> A,List<Integer> B){if(A.size() != B.size()) return A.size() > B.size();/* if(A.size() >= B.size()){return true;}else{return false;}*/for(int i = A.size() - 1;i >= 0;i --){if(A.get(i) != B.get(i)) {return A.get(i) > B.get(i);}}return true;}
}

3. 高精度乘法

二刷：

1. 在草稿纸上演算一遍 运算过程，便知道 代码逻辑
   原题链接
   

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);String a = scanner.next();int b = scanner.nextInt();List<Integer> A = new ArrayList<>(a.length());for (int i = a.length()-1; i >= 0; i--) A.add(a.charAt(i) - '0');List<Integer> C = mul(A,b);for (int i = C.size()-1; i >= 0; i--) System.out.print(C.get(i));}public static List<Integer> mul (List<Integer> A,int b) {List<Integer> C = new ArrayList<>(A.size());int t = 0;for (int i = 0; i < A.size(); i++) {t = t + A.get(i)*b;C.add(t%10);t /= 10;}while (t != 0) {C.add(t%10);t /= 10;}while (C.size() > 1 && C.get(C.size()-1) == 0) {C.remove(C.size() - 1);}return C;}
}

4. 高精度除法 ✔(12分钟)2.1

原题链接

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> div(vector<int> &A, int b, int &r)
{vector<int> C;r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}int main()
{string a;vector<int> A;int B;cin >> a >> B;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');int r;auto C = div(A, B, r);for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];cout << endl << r << endl;return 0;
}

五、前缀和S与差分a

1. 前缀和(2分钟)

原题链接

import java.util.*;public class Main {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+1];int[] s = new int[n+1];for (int i = 1; i <= n; i++) { a[i] = scanner.nextInt(); }s[1] = a[1];for (int i = 2; i <= n; i++) {s[i] = a[i] + s[i-1];}while (m-- != 0) {int l = scanner.nextInt();int r = scanner.nextInt();System.out.println(s[r]-s[l-1]);}}
}

2. 子矩阵的和(7分钟)

原题链接

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int q = scanner.nextInt();int[][] a = new int[n+1][m+1];int[][] s = new int[n+1][m+1];for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++) {a[i][j] = scanner.nextInt();} }for(int i = 1 ; i <= n  ; i ++ ){for(int j = 1 ;j <= m ; j ++ ){s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];}}while (q-->0) {int x1 = scanner.nextInt();int y1 = scanner.nextInt();int x2 = scanner.nextInt();int y2 = scanner.nextInt();System.out.println(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);}}
}

3. 差分(9分钟)

二刷总结

1. 由差分求s时，是要有数据连续性的，前面的改变了，要保证对应后面的也跟着

原题链接

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[] nums = new int[n+2];for (int i = 1; i <= n; i++) {nums[i] = scanner.nextInt();}for (int i = n; i >= 1; i--) {nums[i] = nums[i]-nums[i-1];}for (int i = 0; i < m; i++) {int l = scanner.nextInt();int r = scanner.nextInt();int c = scanner.nextInt();nums[l] += c;nums[r+1] -= c;}for (int i = 1; i <= n; i++) {nums[i] += nums[i-1];System.out.printf("%d ",nums[i]);}}
}

4. 差分矩阵(12分钟)

原题链接

import java.util.*;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int q = scanner.nextInt();int[][] splits = new int[n+2][m+2];int[][] sum = new int[n+2][m+2];for (int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {sum[i][j] = scanner.nextInt();splits[i][j] = sum[i][j] - sum[i-1][j] - sum[i][j-1] + sum[i-1][j-1];}}for (int i = 0; i < q; i++) {int x1 = scanner.nextInt();int y1 = scanner.nextInt();int x2 = scanner.nextInt();int y2 = scanner.nextInt();int c = scanner.nextInt();splits[x1][y1] += c;splits[x1][y2+1] -= c;splits[x2+1][y1] -= c;splits[x2+1][y2+1] += c;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {sum[i][j] = splits[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];System.out.print(sum[i][j] + " ");}System.out.println();}}
}

六、双指针

★ 1. 最长连续不重复子序列(20分钟)

二刷总结(以空间换时间)

原题链接

import java.util.Scanner;
public class Main {public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();int[] a = new int[100010];int[] s = new int[100010];for(int i = 0 ; i < n ; i ++ ){a[i] = scan.nextInt();}int res = 0;for(int i = 0 , j = 0 ;i < n ; i ++ ){//比如一开始S[2]是0；然后你的a[1] = 2;那么s[2] = 1;//然后如果a[2] = 2 ;那么第二次出现所以s[2] = 2;这样来证明是不是出现两次s[a[i]] ++ ;while(j < i && s[a[i]] > 1){//一开始j是跟i在同个位置，i在移动，j原地不动，只要上面出现两次，j开始移动//j移动到i的位置，下面的代码就是i走过的路，让s[i] 数组里面加1的位置全部减1，就变回0；所以就继续往下统计长度s[a[j]] -- ;j++;}//i-j+1是统计长度的公式；res = Math.max(res, i-j+1);}System.out.println(res);}
}//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

2. 数组元素的目标和(7分钟)

原题链接

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int x = scanner.nextInt();int[] A = new int[n+1];int[] B = new int[m+1];for (int i = 0; i < n; i++) A[i] = scanner.nextInt();for (int i = 0; i < m; i++) B[i] = scanner.nextInt();for (int i = 0,j = m-1; i < n && j >= 0;) {if (A[i] + B[j] < x) {i++;} else if (A[i] + B[j] == x) {System.out.print(i + " " + j);break;} else {j--;}}}
}

3. 判断子序列(8分钟)

原题链接

import java.util.*;public class Main {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+1];int[] b = new int[m+1];for (int i = 0; i < n; i++) a[i] = scanner.nextInt();for (int j = 0; j < m; j++) b[j] = scanner.nextInt();boolean flag = false;for (int i = 0,j = 0; j < m; j++) {if (a[i] == b[j]) {i++;if (i == n) {System.out.print("Yes");flag = true;break;}}}if (flag == false) {System.out.print("No");}}
}

七、二进制

最全二进制算法总结

1. 位运算算法(2分钟)

返回n的最后一位1：lowbit(n) = n & -n

一共有多少1 ： while n = n ^（n & -n）或者 n -= n & -n

原题链接

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();System.out.print(numberOfOneInBinary(nums[i]) + " ");}}public static int numberOfOneInBinary(int num) {int cnt = 0;while (num != 0) {num -= (num & -num);cnt++;}return cnt;}
}

八、离散化

sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

去重 V.erase(unique(.begin(),.end()),.end());

1. ★ 区间和

原题链接

在草稿纸上列出需要几个数组，就清晰了

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();pair[] add = new pair[n+2];pair[] query = new pair[m];List<Integer> arrayMap = new ArrayList<>(n+m*2);int[] sum = new int[n+m*2];for (int i = 0; i < n; i++) {add[i] = new pair();add[i].l = scanner.nextInt();add[i].r = scanner.nextInt();arrayMap.add(add[i].l);}for (int i = 0; i < m; i++) {query[i] = new pair();query[i].l = scanner.nextInt();query[i].r = scanner.nextInt();arrayMap.add(query[i].l);arrayMap.add(query[i].r);}arrayMap = new ArrayList<>(new HashSet<>(arrayMap));Collections.sort(arrayMap);for (int i = 0; i < n; i++) {sum[arrayMapIndexOf(add[i].l,arrayMap)] += add[i].r;}for (int i = 0; i < arrayMap.size(); i++) {if(i != 0) {sum[i] += sum[i-1];}}for (int i = 0; i < query.length; i++) {int l = arrayMapIndexOf(query[i].l,arrayMap);int r = arrayMapIndexOf(query[i].r,arrayMap);if (l == 0) {System.out.print(sum[r] + "\n");} else {System.out.print(sum[r]-sum[l-1] + "\n");}}}static class pair {int l;int r;}private static int arrayMapIndexOf(int k,List<Integer> arrayMap) {int l = 0,r = arrayMap.size()-1;while (l < r) {int mid = (l+r+1) >> 1;if (arrayMap.get(mid) <= k) {l = mid;} else {r = mid - 1;}}return r;}
}

九、区间合并

1. 区间合并(7分钟)

原题链接

贪心做法

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();pair[] range = new pair[n];for (int i = 0; i < n; i++) {range[i] = new pair();range[i].l = scanner.nextInt();range[i].r = scanner.nextInt();}Arrays.sort(range,new Comparator<pair>(){@Overridepublic int compare(pair o1,pair o2) {if (o1.l == o2.l) {return o1.r - o2.r;} else {return o1.l - o2.l;}}});int st = (int)-2e9-1;int ed = (int)-2e9-1;int cnt = 0;for (int i = 0; i < n; i++) {if (ed < range[i].l) {st = range[i].l;ed = range[i].r;cnt++;} else {ed = Math.max(ed,range[i].r);}}System.out.print(cnt);}static class pair {int l;int r;}}