AcWing 792. 高精度减法
原题链接
简单
作者:
ice_73
,
2025-01-17 22:39:51
,
所有人可见
,
阅读 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author iceewei
* @Description: 大整数算法 acwing-ycx
* @date 2025/1/17
*/
public class Main {
public static void main(String[] args) throws IOException {
String[] s = doInput();
ArrayList<Integer> A = new ArrayList<>();
ArrayList<Integer> B = new ArrayList<>();
for (int i = s[0].length() - 1; i >= 0 ; i--) A.add(s[0].charAt(i) - '0');
for (int i = s[1].length() - 1; i >= 0 ; i--) B.add(s[1].charAt(i) - '0');
ArrayList<Integer> C = minus(A, B);
for (int i = C.size() - 1; i >= 0; i--) {
if (i == C.size() - 1 && C.get(i) == -1) System.out.print("-");
else System.out.print(C.get(i));
}
}
// 关键是将问题转化为三个数相加,Ai+Bi+t
private static ArrayList<Integer> minus(ArrayList<Integer> A, ArrayList<Integer> B) {
if (!more(A, B)) {
ArrayList<Integer> minus = minus(B, A);
minus.add(-1);
return minus;
}
ArrayList<Integer> C = new ArrayList<>();
int t = 0;
for (int i = 0, j = 0; i < A.size() || j < B.size(); i++, j++) {
int remain = A.get(i) - (j < B.size()?B.get(j):0) - t;
if (remain >= 0) {
C.add(remain);
t = 0;
} else {
C.add((remain + 10) % 10);
t = 1;
}
}
while (C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);
return C;
}
private static boolean more(ArrayList<Integer> A, ArrayList<Integer> B) {
if (A.size() != B.size()) return A.size() > B.size();
for (int i = A.size() - 1, j = B.size() - 1; i >= 0 && j >= 0; i--, j--) {
if (A.get(i) != B.get(i))
return A.get(i) > B.get(i);
}
return true;
}
private static String[] doInput() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = new String[2];
int counter = 0;
String ss;
while ((ss = br.readLine()) != null) {
s[counter++] = ss;
}
return s;
}
}