算法题：基础算法篇

这里是我刷算法题的笔记，来自于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总的题解之后知道这道题有一种更好的办法。
实际上我们先回顾快排的步骤

• 确定分解点（一共有四种，听说现在使用中点和随机不会超时）
• 处理分界点左边和右边的数，保证左边的最大值小于右边的最小值，当然分界点的元素相同的话分布在左右两边
• 递归处理左边和右边的数

快排的时间复杂度平均是 O(nlogn) ,这道题其实上使用的是快速选择排序。
我们可以这样考虑，找第k个数，无非是在处理完分解点之后，将一组数分成两部分，我们可以比较第k个数的位置，那么此会产生两种情况

1. 当左区间的个数sl大于k，说明k在左边
2. 当左区间的个数sl小于k，说明k在右边。此时k在右边的位置应该是k-sl。

通过这两种思路我们只需要把k作为形参放在快排方法中，方法的第三步我们稍作调整，递归中加入k，根据不同的情况返回不同的递归值。如果遍历有右区间，那么应该寻找的是第k - sl个数。 会保证第k小的数一直在递归的区间中，那么当区间里只有一个数的时候，就一定是要找的数了。 那么我们需要调整返回值，和一开始的出口返回数组的左边界（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
考虑一下时间复杂度就是 O(n)

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. 数的范围

这道题给我感觉也是比较有难度，刚开始左右二分不太会套，后面也是看了几遍题解才有收获，还是要多刷一刷。
算法给我总体感觉是要有思路，技巧性比较强.我单纯一两句话说不明白，附上视频把

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. 差分矩阵

• 可以看看视频

• 附上代码

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]);
        
    }
}

附上我的视频讲解，哈哈

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;
    }
}

附上我的视频方便复习~~~

一开始紧张说错了，首先应该想到的是前缀和 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;
    }
    
}

附上我的视频便于复习~~

我书写这篇文章的初衷就是总结学习的进度，遗忘之际可以拿出来翻看，如有不对的地方还望指正，多多海涵。