算法分析

• 1、模拟减法规则，从个位到高位进行相减，若个位不够减则向上一个高位借1

• 2、sub(A,B)函数中，C = A - B, 若A >= B 则求A - B，否则A < B 则求(B - A),最后再把'-'号添上

• 3、若遍历完整个A，需要将最靠左的且为 0 的高位全部去除掉

时间复杂度 $O(n)$

参考文献

参考y总的模版归纳：https://www.acwing.com/blog/content/277/

Java 代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    //判断A与B的大小关系 A >= B 返回true
    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);
        //若A = B 返回true
        return true;

    }
    // C = A - B, 若A >= B 则求A - B，否则A < B 则求(B - A),最后再把'-'号添上
    public static List<Integer> sub(List<Integer> A,List<Integer> B)
    {
        if(!cmp(A,B)) return sub(B,A);
        for(int i = 0,t = 0;i < A.size();i++)
        {
            t = A.get(i) - t;
            if(i < B.size()) t -= B.get(i);
            A.set(i, (t + 10) % 10);
            if(t < 0) t = 1;
            else t = 0;
        }
        //若该数的头为0，则去掉（注意：该数的数学顺序是倒序）
        while(A.size() > 1 && A.get(A.size() - 1) == 0) A.remove(A.size() - 1);
        return A;
    }
    public static void main(String[] args) {
        //传进两个字符串
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();

        List<Integer> A = new ArrayList<Integer>();
        List<Integer> B = new ArrayList<Integer>();
        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');
        //若该数为负数,添上负号
        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)));
    }

}