这里是我刷算法题的笔记，来自于acwing，我会将我做算法题的心得和改进写在笔记中用于分享和交流，你也可以和我一起刷一起交流。AcWing 786. 第k个数题目一开始我想到的是，用快排，然后遍历做一个判断(看起来笨笨的，新手只能想到这个QAQ)import java.util.Scanner; import java.util.stream.IntStream; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = IntStream.range(0,n).map(i -> sc.nextInt()).toArray(); int[] sortedArr = quickSort(arr,0,n-1); for(int i = 0; i < sortedArr.length; i++){ if(i == (k-1)){ System.out.println(sortedArr[i]); } } } private static int[] quickSort(int[] q,int l,int r){ if(l >= r) return q; int p = q[l+ r >>1],i = l-1,j = r+1; while(i<j){ while(q[++i] < p); while(q[--j] > p); if(i<j){ int t = q[i]; q[i] = q[j]; q[j] = t; } } quickSort(q,l,j); quickSort(q,j+1,r); return q; } }这样写勉勉强强过了，但是这样处理笨笨的，我在看了y总的题解之后知道这道题有一种更好的办法。实际上我们先回顾快排的步骤确定分解点（一共有四种，听说现在使用中点和随机不会超时）处理分界点左边和右边的数，保证左边的最大值小于右边的最小值，当然分界点的元素相同的话分布在左右两边递归处理左边和右边的数快排的时间复杂度平均是 [label color="blue"]O(nlogn)[/label] ,这道题其实上使用的是快速选择排序。我们可以这样考虑，找第k个数，无非是在处理完分解点之后，将一组数分成两部分，我们可以比较第k个数的位置，那么此会产生两种情况当左区间的个数sl大于k，说明k在左边当左区间的个数sl小于k，说明k在右边。此时k在右边的位置应该是k-sl。通过这两种思路我们只需要把k作为形参放在快排方法中，方法的第三步我们稍作调整，递归中加入k，根据不同的情况返回不同的递归值。如果遍历有右区间，那么应该寻找的是第k - sl个数。 [label color="red"]会保证第k小的数一直在递归的区间中，那么当区间里只有一个数的时候，就一定是要找的数了。[/label] 那么我们需要调整返回值，和一开始的出口返回数组的左边界（q[l]）即可。import java.util.Scanner; import java.util.stream.IntStream; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = IntStream.range(0,n).map(i -> sc.nextInt()).toArray(); System.out.println(quickSort(arr,0,n-1,k)); } private static int quickSort(int[] q,int l,int r, int k){ if(l >= r) return q[l]; int p = q[l+ r >>1],i = l-1,j = r+1; while(i<j){ while(q[++i] < p); while(q[--j] > p); if(i<j){ int t = q[i]; q[i] = q[j]; q[j] = t; } } //计算左区间的长度 int sl = j - l + 1; //始终保持k在递归区间，当区间只有一个数的时候,那么就是我们要找的数 if(sl >= k){ return quickSort(q,l,j,k); }else{ return quickSort(q,j+1,r,k-sl); } } }这样的话第一遍是n，第二遍就是n/2，第三遍就是n/4....T(n) = n + n/2 + n/4 + ... < 2n考虑一下时间复杂度就是 [label color="blue"]O(n)[/label]AcWing 788. 逆序对的数量看到了不会做，一点思路都没有看了y总的题解之后觉得真的牛，实际上核心思路就是通过不断的递归+分治，实际上的三种情况只需要考虑，黄球的情况，而递归可以将整个部分连续划分，就不存在红球和绿球的情况了，定义变量res，一方面逆序数等于左右两个半的和，另一部分左半边元素大于右半边元素记录逆序数。我才用API+Stream的方式拿下。import java.util.*; import java.util.stream.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = IntStream.range(0,n).map(i->sc.nextInt()).toArray(); System.out.println(mergeSort(arr,0,n-1)); } private static long mergeSort(int[] q,int l ,int r){ if(l >= r) return 0; int mid = l+r >> 1; long res = mergeSort(q,l,mid)+ mergeSort(q,mid+1,r); int i =l,j=mid+1,k=0; int[] t = new int[r-l+1]; while(i<=mid && j<= r){ if(q[i] <= q[j]){ t[k++] = q[i++]; }else{ t[k++] = q[j++]; res += mid - i + 1; } } while(i<=mid) t[k++] = q[i++]; while(j<=r) t[k++] = q[j++]; //物归原主 for(i=l,j=0; i<= r; i++,j++) q[i] = t[j]; return res; } }随后我想使用缓冲流来试试，结果发现缓冲流使用比Scanner类快得多，但是代码太长了不好写。import java.util.*; import java.io.*; public class MergeSortTest5{ //优先定义一个数据规模 static int N = 100010; static int[] arr = new int[N]; public static void main(String[] args) throws IOException{ //使用缓冲流来录入数据 BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(reader.readLine()); String[] arrStr = reader.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(arrStr[i]); } //输出逆序数 System.out.println(mergeSort(arr, 0, n-1)); //关闭流 reader.close(); } private static long mergeSort(int[] q,int l ,int r){ if(l >= r) return 0; int mid = l+r >> 1; long res = mergeSort(q,l,mid)+ mergeSort(q,mid+1,r); int i =l,j=mid+1,k=0; int[] t = new int[r-l+1]; while(i<=mid && j<= r){ if(q[i] <= q[j]){ t[k++] = q[i++]; }else{ t[k++] = q[j++]; res += mid - i + 1; } } while(i<=mid) t[k++] = q[i++]; while(j<=r) t[k++] = q[j++]; //物归原主 for(i=l,j=0; i<= r; i++,j++) q[i] = t[j]; return res; } }AcWing 789. 数的范围这道题给我感觉也是比较有难度，刚开始左右二分不太会套，后面也是看了几遍题解才有收获，还是要多刷一刷。算法给我总体感觉是要有思路，技巧性比较强.我单纯一两句话说不明白，附上视频把[video title="acwing.789.数的范围 " url="https://img.kaijavademo.top/typecho/uploads/2023/08/videos/2023-08-25%2015-32-55.mkv " container="bxb9du5xq5f" subtitle=" " poster=" "] [/video]我在视频中是初始化开辟了一块空间，但是我实际上并没有使用arr这个数组，在main方法内部，我声明了一次，相当于白开辟了一个数组，只需要把main方法中，直接让arr = 那一部分就可以了，稍微改一下(我录完才知道问题的。。)import java.util.*; import java.util.stream.*; public class Main{ //789. 数的范围 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int q = sc.nextInt(); int[] arr = IntStream.range(0, n).map(i->sc.nextInt()).toArray(); while(q-- > 0) { int k = sc.nextInt(); int[] ans = binarySarch(arr, q); IntStream.range(0, 2).mapToObj(i-> ans[i] + " ").forEach(System.out::print); System.out.println(); } } private static int[] binarySarch(int[] q,int tar) { int[] res = new int[2]; int n = q.length; int l = 0; int r = n-1; //左边界二分查找 while(l<r) { int mid = l+r>>1; //我要求寻找的内容位于右侧，意味着全部大于tar if(q[mid] >= tar) r = mid; else l = mid + 1; } //如果没有找到，则默认-1 -1 if(q[l] != tar) return new int[] {-1,-1}; //将初始索引归位，并初始化 res[0] = l; l = 0; r = n-1; //右边界二分查找 while(l<r) { int mid = l+r +1>>1; //此时我要求我要寻找的内容位于左侧，全部小于tar if(q[mid] <= tar) l=mid; else r = mid -1; } //物归原主 res[1] = l; return res; } } AcWing 798. 差分矩阵可以看看视频[video title="差分矩阵 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/2023-09-01%2002-26-18.mkv " container="bi9ibzhavb" subtitle=" " poster=" "] [/video]附上代码import java.io.*; public class Main{ private static final int N = 1010; private static final int[][] a = new int[N+5][N+5]; private static final int[][] b = new int[N+5][N+5]; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); int m = Integer.parseInt(arrStr[1]); int q = Integer.parseInt(arrStr[2]); for(int i = 1; i<= n;i++){ arrStr = br.readLine().split(" "); for(int j = 1; j<= m; j++){ a[i][j] = Integer.parseInt(arrStr[j -1]); diff(i,j,i,j,a[i][j]); } } while(q-- >0){ arrStr = br.readLine().split(" "); int x1 = Integer.parseInt(arrStr[0]); int y1 = Integer.parseInt(arrStr[1]); int x2 = Integer.parseInt(arrStr[2]); int y2 = Integer.parseInt(arrStr[3]); int c = Integer.parseInt(arrStr[4]); diff(x1,y1,x2,y2,c); } sumPrefix(n , m); for(int i = 1;i<= n ;i++){ for(int j = 1; j <= m ; j++){ System.out.print(a[i][j] +" "); } System.out.println(); } br.close(); } private static void diff(int x1,int y1,int x2,int y2,int c){ b[x1][y1] += c; b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c; b[x2 + 1][y2 + 1] += c; } private static void sumPrefix(int n ,int m){ for(int i =1;i<= n ; i++){ for(int j = 1; j<= m;j++){ a[i][j] = a[i-1][j] + a[i][j - 1] -a[i - 1][j -1] + b[i][j]; } } } }原先时间复杂度如果是扫一边二维数组应该是O(n^2)我好像说错了捏。AcWing 803. 区间合并原址import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ //803. 区间合并 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); int[][] a = new int[n][8]; for(int i=0;i< n;i++) { arrStr = br.readLine().split(" "); int l = Integer.parseInt(arrStr[0]); int r = Integer.parseInt(arrStr[1]); a[i][0] = l; a[i][9] = r; } int[][] ans = merge(a); System.out.println(ans.length); br.close(); } private static int[][] merge(int[][] a){ if( a==null || a.length == 0||a[0].length == 0) { return new int[0][10]; } //升序排列a数组 Arrays.sort(a,Comparator.comparingInt(i -> i[0])); List<int[]> res = new ArrayList<>(); for(int[] arr : a) { int l = arr[0]; int r = arr[1]; if(res.size() == 0 || res.get(res.size() - 1)[1] < l) { res.add(new int[]{l,r}); }else { int newRight = Math.max(r,res.get(res.size() - 1)[1]); res.set(res.size() - 1, new int[]{res.get(res.size() - 1)[0],newRight}); } } return res.toArray(new int[res.size()][11]); } } 附上我的视频讲解，哈哈[video title="合并区间 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/2023-09-05%2022-54-32.mkv " container="bntyqzgbkpb" subtitle=" " poster=" "] [/video]AcWing 802. 区间和这道题也是困扰我好久了，算是第一章最难的题了把，然后看了一下老哥这位老哥的题解，我觉得写的非常好，让我很快就明白了orz。原址解题过程import java.io.*; import java.util.*; import java.util.stream.*; public class Main { private static final int N = 300010; private static final int[] a = new int[N]; private static final int[] s = new int[N]; public static void main(String[] args) throws IOException{ //802. 区间和 //1.准备 //2.准备a数组，并前缀和s //3.返回离散化后的查询结果 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); int m = Integer.parseInt(arrStr[1]); //1.准备三个集合 List<Integer> alls = new ArrayList<Integer>(); //来存储n次插入 List<Pair> add = new ArrayList<Pair>(); //来储存m次查询 List<Pair> query = new ArrayList<Pair>(); //2.填充好集合 for(int i = 0; i< n; i++) { arrStr = br.readLine().split(" "); int x = Integer.parseInt(arrStr[0]); int c = Integer.parseInt(arrStr[1]); add.add(new Pair(x, c)); alls.add(x); } for(int i =0 ; i<m ;i++) { arrStr = br.readLine().split(" "); int l = Integer.parseInt(arrStr[0]); int r = Integer.parseInt(arrStr[1]); query.add(new Pair(l, r)); alls.add(l); alls.add(r); } alls = alls.stream().distinct().sorted().collect(Collectors.toList()); //4.离散化，将离散的稀疏的离散区间，整合到一个稠密区间，从而才可以通过前缀和运算 for(Pair item : add) { int i = find(item.first,alls); a[i] += item.secound; } //前缀和公式 for(int i = 1;i<= alls.size();i++) s[i] = s[i - 1] + a[i]; for(Pair item: query) { int l = find(item.first,alls); int r = find(item.secound,alls); System.out.println(s[r] - s[l - 1]); } br.close(); } //3.写二分查找 private static int find(int x,List<Integer> list) { int l = 0; int r = list.size()- 1; while(l< r) { int mid = l+r>>1; if(list.get(mid) > x) r = mid; else l = mid + 1; } return l + 1; } } //来记录操作的类，包括查询和存入 class Pair{ int first; int secound; public Pair(int x,int c) { this.first = x; this.secound = c; } }附上我的视频方便复习~~~[video title="离散化区间和 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/2023-09-06%2022-52-22.mkv " container="bb5asleqqwm" subtitle=" " poster=" "] [/video]一开始紧张说错了，首先应该想到的是前缀和 ToT~~AcWing 800. 数组元素的目标和原址解题过程import java.util.*; import java.io.*; public class Main{ private static final int N = 100010; private static final int[] a = new int[N]; private static final int[] b = new int[N]; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] arrStr = br.readLine().split(" "); int n = Integer.parseInt(arrStr[0]); int m = Integer.parseInt(arrStr[1]); int x = Integer.parseInt(arrStr[2]); arrStr = br.readLine().split(" "); for(int i= 0 ;i < n ;i++) a[i] = Integer.parseInt(arrStr[i]); arrStr = br.readLine().split(" "); for(int i= 0 ;i < m ;i++) b[i] = Integer.parseInt(arrStr[i]); List<int[]> ans = doublePoint(a,n,b,m,x); //使用迭代(增强)for 循环进行输出 for(int[] arr: ans){ System.out.println(arr[0] + " " + arr[1]); } br.close(); } private static List<int[]> doublePoint(int[] a,int n ,int[] b,int m ,int x){ List<int[]> res = new ArrayList<>(); for(int i=0,j=m - 1; i < n; i++){ while(j >= 0 && a[i] + b[j] > x) j--; if(j >= 0 && a[i] + b[j] == x) res.add(new int[]{i,j}); } return res; } }附上我的视频便于复习~~[video title="双指针 " url="https://img.kaijavademo.top/typecho/uploads/2023/09/videos/%E5%8F%8C%E6%8C%87%E9%92%88.mkv " container="ba2ey700a6j" subtitle=" " poster=" "] [/video]我书写这篇文章的初衷就是总结学习的进度，遗忘之际可以拿出来翻看，如有不对的地方还望指正，多多海涵。