问题
实现两个很大很大的数相加,求出它们的和。
要求
1、是整数;
2、两个数无限大,long 都装不下;
3、不能用 BigInteger;
4、不能用任何包装类提供的运算方法;
5、两个数都是以字符串的方式提供。
以下算法根据《漫画算法》小灰的算法之旅一书,并结合自己的心得,优化整理。
思路
- 用数组来处理很大的数
- 用“竖式”遍历相加,结果用数组来存储。
- 最后将数组倒序为 String 即可实现。
代码实现
package practise;
public class BigNumAdd {
public static void main(String[] args) {
System.out.println(bigNumberNum("6868", "128080989089093"));
}
public static String bigNumberNum(String bigNumberA, String bigNumBerB) {
int maxLength = Math.max(bigNumberA.length(), bigNumBerB.length());
int[] arrayA = new int[maxLength + 1];
for (int i = 0; i < bigNumberA.length(); i++) {
arrayA[i] = bigNumberA.charAt(bigNumberA.length() - 1 - i) - '0';
}
int[] arrayB = new int[maxLength + 1];
for (int i = 0; i < bigNumBerB.length(); i++) {
arrayB[i] = bigNumBerB.charAt(bigNumBerB.length() - 1 - i) - '0';
}
int[] result = new int[maxLength + 1];
for (int i = 0; i < result.length; i++) {
int temp = result[i];
temp += arrayA[i];
temp += arrayB[i];
if (temp >= 10) {
temp = temp - 10;
result[i + 1] = 1;
}
result[i] = temp;
}
StringBuilder sb = new StringBuilder();
boolean findFist = false;
for (int i = result.length - 1; i >= 0; i--) {
if (!findFist) {
if (result[i] == 0) {
continue;
}
findFist = true;
}
sb.append(result[i]);
}
return sb.toString();
}
}
小结:
时间复杂度为 o(n)。算法可以进一步优化。
网上有很多关于大数相加的解法,这个解法个人认为比较好理解,好上手。
在理解以上几个关键的点之后,很容易写出来。
扩展阅读:
- 进一步了解 java 中的工具类 BigInterger 和 BigDecimal。
- 其他相关算法:
LeetCode 字符串相乘
LeetCode 字符相加
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)