y總說 java不能用Scanner讀入，要用Buffer.read();快十倍二十倍；

y總19年5月的視頻，牛13！

第一講 基礎(chǔ)算法

包括排序、二分、高精度、前綴和與差分、雙指針?biāo)惴?、位運(yùn)算、離散化、區(qū)間合并等內(nèi)容。

快速排序

一定要先移動(dòng)end（就是把大數(shù)移到右邊），后移動(dòng)start；

否則 先找小數(shù)，會(huì)出現(xiàn)end start重合位置大于基準(zhǔn)數(shù)，在交換位置就左邊不全是小數(shù)了！

處理大數(shù)據(jù)最快的排序算法之一

public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);
      /*
        快速排序：
            第一輪：以0索引的數(shù)字為基準(zhǔn)數(shù)，確定基準(zhǔn)數(shù)在數(shù)組中正確的位置。
            比基準(zhǔn)數(shù)小的全部在左邊，比基準(zhǔn)數(shù)大的全部在右邊。
            后面以此類推。
      */
        int[] arr = {1,1, 6, 2, 7, 9, 3, 4, 5, 1,10, 8};

        System.out.println(Arrays.toString(arr));
        //課堂練習(xí)：
        //我們可以利用相同的辦法去測試一下，選擇排序，冒泡排序以及插入排序運(yùn)行的效率
        //得到一個(gè)結(jié)論：快速排序真的非常快。
    }

    /*
     *   參數(shù)一：我們要排序的數(shù)組
     *   參數(shù)二：要排序數(shù)組的起始索引
     *   參數(shù)三：要排序數(shù)組的結(jié)束索引
     * */
    public static void quickSort(int[] arr, int i, int j) {
        //定義兩個(gè)變量記錄要查找的范圍
        int start = i;
        int end = j;

        if(start > end){
            //遞歸的出口
            return;
        }
        //記錄基準(zhǔn)數(shù)
        int baseNumber = arr[i];
        //利用循環(huán)找到要交換的數(shù)字
        while(start != end){
            //利用end，從后往前開始找，找比基準(zhǔn)數(shù)小的數(shù)字
            //int[] arr = {1, 6, 2, 7, 9, 3, 4, 5, 10, 8};
            while(true){
                if(end <= start || arr[end] < baseNumber){
                    break;
                }
                end--;
            }
            System.out.println(end);
            //利用start，從前往后找，找比基準(zhǔn)數(shù)大的數(shù)字
            while(true){
                if(end <= start || arr[start] > baseNumber){
                    break;
                }
                start++;
            }
            //把end和start指向的元素進(jìn)行交換
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
        //當(dāng)start和end指向了同一個(gè)元素的時(shí)候，那么上面的循環(huán)就會(huì)結(jié)束
        //表示已經(jīng)找到了基準(zhǔn)數(shù)在數(shù)組中應(yīng)存入的位置
        //基準(zhǔn)數(shù)歸位
        //就是拿著這個(gè)范圍中的第一個(gè)數(shù)字，跟start指向的元素進(jìn)行交換
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;
        //確定6左邊的范圍，重復(fù)剛剛所做的事情
        quickSort(arr,i,start - 1);
        //確定6右邊的范圍，重復(fù)剛剛所做的事情
        quickSort(arr,start + 1,j);

    }
}

三部排序

AcWing 785. 快速排序(模板)

快速排序?qū)儆诜种嗡惴?，快速排序的算法步驟，用分治的思想

確定分界點(diǎn)，數(shù)組內(nèi)任意一個(gè)值（這里建議取中點(diǎn)，即(l+r)/2）；

調(diào)整區(qū)間，讓x左邊的數(shù)都小于x，右邊的數(shù)都大于x；

遞歸處理左右兩個(gè)區(qū)間，直到細(xì)分到不能細(xì)分

對于第二步的調(diào)整區(qū)間，具體就是弄兩個(gè)指針，分別指向數(shù)組的左右邊界；不斷的向中間遍歷，將遍歷過程中左邊比x大的數(shù)和右邊比x小的數(shù)交換；直到i，j相遇。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] q = new int[n];
        for(int i=0; i<n; i++){q[i] = sc.nextInt();}

        quickSort(q, 0, n-1);
        for(int i=0; i<n; i++){System.out.print(q[i] + " ");}
    }

    public static void quickSort(int[] q, int l, int r){
        if(l >= r) return;//邊界l==r也可以
? ? ? ? //先把基準(zhǔn) 定在數(shù)組 中間 ,兩側(cè)指針的位置決定后面的邊界寫法
        int x = q[l + r >> 1], i = l - 1, j = r + 1;
        while(i < j){
            do{i++;} while( q[i] < x );//>x的時(shí)候停
? ? ? ? ? ? do{j--;} while( q[j] > x) ;//<x的時(shí)候停

            if(i < j){//兩個(gè)指針都停了還沒相遇的話就交換
                int t = q[i];
                q[i] = q[j];
                q[j] = t;
            }
        }
        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
}

AcWing 786. 第k個(gè)數(shù)

太簡單了就是輸出arr[k-1];不寫了

歸并排序

具體思想：弄個(gè)臨時(shí)數(shù)組，將有序的兩個(gè)數(shù)組通過兩個(gè)指針將數(shù)從小到大放入臨時(shí)數(shù)組，然后再將臨時(shí)數(shù)組里面已經(jīng)排好序的數(shù)放回本數(shù)組那段位置。

先遞歸再合一

AcWing 787. 歸并排序（模版）

import java.util.*;

class Main{
    static int N=100010;//題目里給的數(shù)據(jù)不超過100000
    static int[] a=new int[N];

    static void merge_sort(int l,int r){
        if(l>=r) return;

        int mid=l+r>>1;//分成兩半，
        merge_sort(l,mid);
        merge_sort(mid+1,r);
? ? ? ? //合二為一
        int[] h=new int[r-l+1];//結(jié)果數(shù)組
        int idx=0,i=l,j=mid+1;//idx是結(jié)果數(shù)組的起始，雙指針指向兩半數(shù)組的起始 
        while(i<=mid&&j<=r){ 
? ? ? ? //前面的指針值 和 后面的指針值 比較； 哪個(gè)小放哪個(gè)
            if(a[i]<=a[j]) h[idx++]=a[i++];//=的時(shí)候取前面數(shù)組的值，保證位置的穩(wěn)定性
            else h[idx++]=a[j++];
        }

        while(i<=mid) h[idx++]=a[i++];//May i指針沒走完，就把后面的補(bǔ)到結(jié)果數(shù)組
        while(j<=r) h[idx++]=a[j++];//May j指針沒走完，就把后面的補(bǔ)到結(jié)果數(shù)組

        for(int k=l;k<idx;k++){
            a[k]=h[k];//結(jié)果 區(qū)域數(shù)組賦值給 原數(shù)組+l，結(jié)果輸出原數(shù)組
        }
    }
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        for(int i = 0;i < n;i++){a[i] = s.nextInt();}
        merge_sort(0,n-1);
        for(int i = 0;i < n;i++){System.out.print(a[i] + " ");}
    }
    //import java.io.*; //感覺快讀挺危險(xiǎn)的
    // public static void main(String[]args)throws IOException{
    //     BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
    //     int n=Integer.parseInt(in.readLine());

    //     String[]arr=in.readLine().split(" ");
    //     for(int i=0;i<n;i++) a[i]=Integer.parseInt(arr[i]);

    //     merge_sort(0,n-1);
    //     for(int i=0;i<n;i++) System.out.print(a[i]+" ");
    // }
}

AcWing 788. 逆序?qū)Φ臄?shù)量

最后返回一個(gè)Long res當(dāng)右邊a[j]＞左邊a[i]時(shí)，要res+=(mid-i+1)；

二分查找

給定某個(gè)區(qū)間，在區(qū)間上定義了某種性質(zhì)(check函數(shù))，使得整個(gè)區(qū)間一分為二，一個(gè)區(qū)間滿足性質(zhì)，另一個(gè)不滿足，二分可以尋找性質(zhì)的邊界

為什么要+1？

C++和Java除法向下取整，假設(shè)L=r-1；(L+r)/2=L；check(mid),假設(shè)為true，mid==L；死循環(huán)

什么情況用哪個(gè)模版？

先寫check函數(shù)，根據(jù)check函數(shù)判斷，答案區(qū)間如何劃分，是l=mid(設(shè)mid的時(shí)候要+1)還是r=mid（不+1）；

AcWing 789. 數(shù)的范圍（整數(shù)二分模版）

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

2187. 完成旅途的最少時(shí)間

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        Arrays.sort(time);
        long left = 0;
        // 記錄當(dāng)前最大完成旅途的時(shí)間
        long right = 1L*  time[0] * totalTrips ;
        // 在最小時(shí)間和最大時(shí)間之間搜索符合條件的時(shí)間
        while (left < right ){
            long mid = right + left >>1;
            // 記錄當(dāng)前完成旅途的車
            long trips = 0;
            // 遍歷每個(gè)車次需要完成的時(shí)間
            for(int t : time){
                if(mid < t){
                    break;
                }
                // 記錄當(dāng)前時(shí)間能完成的趟數(shù)
                trips += mid / t;
            }
            // 如果當(dāng)前完成的車次已經(jīng)到達(dá)了完成的次數(shù)則縮小范圍 搜索前面時(shí)間范圍
            if(trips >= totalTrips){
                right = mid;
            } else {
                // 反之搜索后面時(shí)間范圍
                left = mid + 1;
            }
        } 
        return left;
    }
}

AcWing 790. 數(shù)的三次方根

(前提是 數(shù)據(jù)有序) 說明：元素必須是有序的，從小到大，或者從大到小都是可以的。

public static int binarySearc(int[] arr,int number){
        int min=0;
        int max=arr.length-1;
        while(true){
            if(min>max){
                return -1;
            }
            int mid=(max+min)/2;
            if(arr[mid]==number)
                return mid;
            else if(arr[mid]>number) 
                max=mid-1;
            else if(arr[mid]<number) 
                min=mid+1;
        }
    }

35. 搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right  = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

268. 丟失的數(shù)字 太簡單了

34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

這道題目比Acw789 加了數(shù)據(jù)比如說[],0;[1] 1;

class Solution {//y總模板解法
    public int[] searchRange(int[] nums, int target) {
        if(nums.length==0)
            return new int[]{-1,-1};
        int l=0,r=nums.length-1,mid=l+r>>1;
        while(l<r){
            mid=l+r+c>>1;
            if(nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        int[] res=new int[2];
        if(nums[l]!=target) 
            return new int[]{-1,-1};
        else{
            res[0]=l;
            l=0;r=nums.length-1;
            while(l<r){
                mid=l+r+1+c>>1;
                if(nums[mid]<=target) l=mid;
                else r=mid-1;
            }
            res[1]=l;
            return res;
        }
    }
}

class Solution {//不能解決數(shù)組內(nèi) 負(fù)數(shù) 問題
    public int[] searchRange(int[] nums, int target) {
        if(nums.length==0)
            return new int[]{-1,-1};    
        int[] arr=new int[nums[nums.length-1]+1];
        for(int i=0;i<nums.length;i++){
            arr[i]=0;
        }
        int c=-1;
        for(int i=0;i<nums.length;i++){
            arr[ nums[i] ]++;
            if(nums[i]==target&&arr[nums[i]]==1)
                c=i;            
            }
        if(c!=-1)
            return new int[]{c ,(c+arr[target]-1)};
        else
           return new int[]{-1,-1};  
    }
}

//https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
//他不是找目標(biāo)位置，而是找第一個(gè)等于的位置和第一個(gè)>的位置
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);//第一個(gè)=target的位置
        int rightIdx = binarySearch(nums, target, false) - 1;//第一個(gè)》target-1的位置
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

74. 搜索二維矩陣

class Solution {//自己寫的
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] arr=new int[matrix.length];
        if(matrix.length==1){//特殊情況，只有一個(gè)數(shù)組
            for(int index:matrix[0] )
                        if(index==target)
                            return true;
            return false;
        }
        for(int i=0;i<matrix.length-1;i++)
            if(matrix[i][0]<=target&&matrix[i+1][0]>target)
                {
                    for(int index:matrix[i] )
                        if(index==target)
                            return true;
                }
            else{//二維數(shù)組最后一行
                for(int index:matrix[i+1] )
                        if(index==target)
                            return true;
            }
        return false;
    }
}

https://leetcode.cn/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode-solut-vxui/
思路
若將矩陣每一行拼接在上一行的末尾，則會(huì)得到一個(gè)升序數(shù)組，我們可以在該數(shù)組上二分找到目標(biāo)元素。
代碼實(shí)現(xiàn)時(shí)，可以二分升序數(shù)組的下標(biāo)，將其映射到原矩陣的行和列上。
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;//m,n代表行和列
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];//映射
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

240. 搜索二維矩陣 II

思路與算法

由于矩陣 matrix 中每一行的元素都是升序排列的，因此我們可以對每一行都使用一次二分查找，判斷 target 是否在該行中，從而判斷 target 是否出現(xiàn)。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = search(row, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }

    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            } else {
                ++x;
            }
        }
        return false;
    }
}

高精度

大佬整理，侵權(quán)刪！

BigInteger 只可用于整數(shù) 構(gòu)造方法

BigInteger(byte[] val)
將包含BigInteger的二進(jìn)制補(bǔ)碼二進(jìn)制表達(dá)式的字節(jié)數(shù)組轉(zhuǎn)換為BigInteger
BigInteger(int numBits, Random rnd)
構(gòu)造一個(gè)隨機(jī)生成的BigInteger，均勻分布在0到（2 numBits - 1）的范圍內(nèi)。
BigInteger(String val)
將BigInteger的十進(jìn)制字符串表示形式轉(zhuǎn)換為BigInteger。

加法 add( )

import java.math.BigInteger;
import java.io.*;

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.add(b));
        reader.close();
    }
}

減法 subtract( )

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

乘法 multiply( )

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.multiply(b));
        reader.close();
    }
}

除法 divideAndRemainder( )

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());
        //divide 返回值為 a/b
        BigInteger[] c = a.divideAndRemainder(b); //返回值為數(shù)組，分別為a/b和a%b
        System.out.println(c[0]);
        System.out.println(c[1]);
        reader.close();
    }
}

取余 mod( )

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.mod(b));
        reader.close();
    }
}

BigDecimal 處理浮點(diǎn)數(shù)運(yùn)算

構(gòu)造方法

BigDecimal(char[] in)
一個(gè)轉(zhuǎn)換的字符數(shù)組表示 BigDecimal成 BigDecimal ，接受字符作為的相同序列 BigDecimal(String)構(gòu)造。
BigDecimal(char[] in, int offset, int len)
一個(gè)轉(zhuǎn)換的字符數(shù)組表示 BigDecimal成 BigDecimal ，接受字符作為的相同序列 BigDecimal(String)構(gòu)造，同時(shí)允許一個(gè)子陣列被指定。
BigDecimal(double val)
將 double轉(zhuǎn)換為 BigDecimal ，這是 double的二進(jìn)制浮點(diǎn)值的精確十進(jìn)制表示
BigDecimal(int val)
將 int成 BigDecimal
BigDecimal(long val)
將 long成 BigDecimal
BigDecimal(String val)

加法 add( )

import java.io.*;
import java.math.BigDecimal;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigDecimal a = new BigDecimal(reader.readLine());
        BigDecimal b = new BigDecimal(reader.readLine());
        System.out.println(a.add(b));
        reader.close();
    }
}

取余 remainder( )

import java.io.*;
import java.math.BigDecimal;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigDecimal a = new BigDecimal(reader.readLine());
        BigDecimal b = new BigDecimal(reader.readLine());
        System.out.println(a.remainder(b));
        reader.close();
    }
}

除法 divide( )

import java.io.*;
import java.math.BigDecimal;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BigDecimal a = new BigDecimal(reader.readLine());
        BigDecimal b = new BigDecimal(reader.readLine());
        System.out.println(a.divide(b));
        reader.close();
    }
}

AcWing 791. 高精度加法

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 a = scanner.next();
        String b = scanner.next();
        //String表示長度用length這個(gè)方法，集合中用size這個(gè)方法
        List<Integer> A = new ArrayList<>(a.length());
        List<Integer> B = new ArrayList<>(b.length());
        //add可以直接將數(shù)放到末尾，新開空間。
        //因?yàn)閿?shù)組添加設(shè)置為最后一位方便，因?yàn)閿?shù)組擴(kuò)容修改超級快
        //charAt返回指定下標(biāo)下面的char值，后面減去0是為了把字符變成數(shù)字
        for(int i = a.length() - 1;i >= 0; i --) A.add(a.charAt(i) - '0'); 
        for(int i = b.length() - 1;i >= 0; i --) B.add(b.charAt(i) - '0');

        List<Integer> C = add(A,B);
        for(int i = C.size() - 1;i >= 0; i--){
            System.out.print(C.get(i) + "");
        }
    }
    public static List<Integer> add(List<Integer> A ,List<Integer> B){
        List<Integer> C = new ArrayList<>();

        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 = t/10;
        }
        if(t != 0) C.add(1);//判斷t要不要借位
        return C;

    }
}

AcWing 792. 高精度減法

t作為 結(jié)果i位置 的值 的標(biāo)志有兩種可能：>=0 或 <0 ;

(t+10)%10： >=0 時(shí)，10抵消=本身； <0，t=t+10;

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 ++){
            //這里應(yīng)該是A.get(i) - B.get(i) - t ，因?yàn)榭赡蹷為零，
? ? ? ? ? ? //所以判斷一下是不是存在
            t = A.get(i) - t;
            if(i < B.size()) t -= B.get(i);
            //B > 當(dāng)前位數(shù),說明B[i]此時(shí)不為0;得-
            C.add((t + 10) % 10);

            if(t < 0) t = 1;
            else t = 0;
        }
        //刪除前導(dǎo)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();

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

AcWing 793. 高精度乘法

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<>();
        int t = 0;
                            //t不為0 就是 最高位還有進(jìn)位！
        for(int i = 0;i < A.size() || t != 0;i ++ ){
            if(i < A.size()) t += A.get(i) * b;
            C.add(t % 10);
            t /= 10;// 第i+1位 的 進(jìn)位數(shù)
        }
        while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);

        return C;
    }
}

AcWing 794. 高精度除法

文章來源地址http://www.zghlxwxcb.cn/news/detail-536929.html

import java.util.*;
public class Main{
    public static void main(String[] arg){
        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 = div(A,b);
        for(int i = C.size() - 2;i >= 0;i --) System.out.print(C.get(i));

        System.out.println();
        System.out.print(C.get(C.size() - 1));
    }
    public static List<Integer> div(List<Integer> A,int b){
        List<Integer> C = new ArrayList<>();

        int r = 0;//余數(shù)
        for(int i = A.size() - 1 ;i >= 0; i --){
            r = r * 10 + A.get(i);
            C.add(r / b);//add 商
            r %= b;
        }
        Collections.reverse(C);//for從高位add的所有要reverse
        while(C.size() > 1 && C.get(C.size() - 1) == 0) //去掉前導(dǎo)0
            C.remove(C.size() - 1);

        C.add(r);
        return C;
    }
}