算法:两个超级大数相加

2024-01-03 17:48:05

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

一、问题描述

二、字符运算法

总结


提示:以下是本篇文章正文内容,下面案例可供参考

一、问题描述

给定两个字符串形式的非负整数 str1 和str2 ,计算它们的和。

str1 和str2 的长度都小于 5100.

str1 和str2 都只包含数字 0-9.

str1 和str2 都不包含任何前导零。

你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。

"1234569999"+"56999999"="1291569998"

二、字符运算法

解题思路:

既然不能转成数字类来运算,那就逐位运算,对应的位相加,如果大于10,则进位,需要注意的是,我们运算完了之后,得到的字符串是倒序的,正确的结果要进行反转。

代码示例:

public void test() {
    String str1 = "1234569999";
    String str2 = "56999999";
    // 第一个大数的长度
    int lenth1 = str1.length();
    // 第二个大数的长度
    int lenth2 = str2.length();
    // 记录相同的位相加之后超过10的部分, 初始为0
    int over = 0;
    // 利用栈的先进后出, 来记录运算后的结果位
    Stack stack = new Stack<>();
    // 个位数字位于高位, 所以从高位到低位运算, 假设str1比str2长
    while(lenth1-- > 0){
        // 提取指定位, 转成数字
        int left = str1.charAt(lenth1) - '0';
        lenth2--;
        // 提取指定位, 转成数字
        int right = lenth2 >= 0 ? str2.charAt(lenth2) - '0' : 0;
        // 计算提取位的和
        int total = left + right + over;
        // 将低于10的部分存于栈中
        stack.push(total % 10);
        // 将高于10的部分记录在over中, 用于下次运算
        over = total / 10;
    }
    // 存放运算后的各位数字
    StringBuilder s = new StringBuilder();
    while (!stack.isEmpty()) {
        // 弹出数字, 拼接结果
        s.append(stack.pop());
    }
    System.out.println(s);
}

总结

注释已添加,动动手练习练习,简单到有手就行!

文章来源:https://blog.csdn.net/ql_gome/article/details/135367132
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。