3. 大数相减

3. 大数相减

XMOJ 3. 大数相减


题目:3. 大数相减

描述:

两个长度超出常规整形变量上限的大数相减,请避免使用各语言内置大数处理库,如 Java.math.BigInteger 等。

输入:

有 N 行测试数据,每一行有两个代表整数的字符串 a 和 b,长度超过百位。规定 a>=b,a, b > 0。 测试结果可以用 linux 小工具 bc进行测试是否正确。

输出:

返回表示结果整数的字符串。

输入样例:

1231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739878951331231231237812739870-89513312312312378127398789513312312312378127398789513312312312378127398789513
1231231237812739878951331231231237812739878951331231231237812739878951331230000000000000000000000001-331231231237812739878951331231231

输出样例:

1231231237812739878951331231231237812739878951331231231237812650365639018918853110413950365639018918853110413950365639018918853110413950357
1231231237812739878951331231231237812739878951331231231237812739878620099998762187260121048668768770

方法:模拟

思路:将输入字符串处理从两个字符数组,根据数学减法规则,从尾向头进行运算。

运行数据:最大执行时间:86.96 ms,内存消耗:17396 KiB

复杂度分析:

由于输入数据组数无法确定,时间复杂度和空间复杂度只考虑一组数据。

  • 时间复杂度:O(n),n为输入字符串长度,一个循环进行运算,一个循环输出结果。
  • 空间复杂度:O(n),n为输入字符串长度,两个字符数组的空间消耗。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.Scanner;

public class Main {

public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
String line;
while (scan.hasNext()) {
line = scan.nextLine().trim();
String[] strs = line.split("-");
char[] cha1 = strs[0].toCharArray();
char[] cha2 = strs[1].toCharArray();
int len1 = cha1.length;
int len2 = cha2.length;
for (int i = len2 - 1,j = len1 - 1; i >= 0; i--,j--) {
int a = cha1[j] - 48;
int b = cha2[i] - 48;
if (a < b) {
if (j > 0) {
a += 10 - b;
cha1[j - 1] -= 1;
} else {
a -= b;
}
} else {
a -= b;
}
cha1[j] = (char) (a + 48);
}
boolean flag = true;
for (int i = 0; i < cha1.length; i++) {
if (cha1[i] == '0' && flag) {
continue;
} else {
flag = false;
}
System.out.print(cha1[i]);
}
}
}
}

学习所得,资料、图片部分来源于网络,如有侵权,请联系本人删除。

才疏学浅,若有错误或不当之处,可批评指正,还请见谅!


 
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×