算法：如何实现两个大数相加

文章目录

​​问题​​​​要求​​​​思路​​​​代码实现​​

问题

实现两个很大很大的数相加，求出它们的和。

要求

1、是整数； 2、两个数无限大，long 都装不下； 3、不能用 BigInteger； 4、不能用任何包装类提供的运算方法； 5、两个数都是以字符串的方式提供。

以下算法根据《漫画算法》小灰的算法之旅一书，并结合自己的心得，优化整理。

思路

用数组来处理很大的数用“竖式”遍历相加，结果用数组来存储。最后将数组倒序为 String 即可实现。

代码实现

package practise;/** *

 *     author : June Yang *     time   : 2022/07/25 *     desc   : 两个大数相加 *     version: 1.0 * 

*/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]; // 将 String 转化成 int for (int i = 0; i < bigNumberA.length(); i++) { arrayA[i] = bigNumberA.charAt(bigNumberA.length() - 1 - i) - '0'; } int[] arrayB = new int[maxLength + 1]; // 将 String 转化成 int for (int i = 0; i < bigNumBerB.length(); i++) { arrayB[i] = bigNumBerB.charAt(bigNumBerB.length() - 1 - i) - '0'; } // 得到结果的数组 int[] result = new int[maxLength + 1]; // 核心算法：竖式相加 满 10 进 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; // 将进位后的 1 存到数组的下一位 } result[i] = temp; } // 将 result 数组倒序之后再转成 String StringBuilder sb = new StringBuilder(); boolean findFist = false; for (int i = result.length - 1; i >= 0; i--) { if (!findFist) { if (result[i] == 0) { continue; // continue 的作用：跳过当前循环继续下一个循环。此处 用于跳过结果数组末尾的 "0" } findFist = true; } sb.append(result[i]); } return sb.toString(); }}

小结：

时间复杂度为 o(n)。算法可以进一步优化。 网上有很多关于大数相加的解法，这个解法个人认为比较好理解，好上手。 在理解以上几个关键的点之后，很容易写出来。

扩展阅读：

进一步了解 java 中的工具类 BigInterger 和 BigDecimal。其他相关算法：​​​LeetCode 字符串相乘​​​​LeetCode 字符相加​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。