牛客-NC1-大数加法

NC1. 大数加法(medium)


牛客-NC1-大数加法

方法一:模拟进位法

思路:上一题两个链表生成相加链表,我写的三个ArrayList发挥作用了哈(思路很像),但这里可千万别把每一个位置计算得到的值放到ArrayList中,会超时的,样例中有特别特别大的数。那只能另辟蹊径,用StringBuffer直接存储每一位计算得到的值,将int变成character进行存储,从而巧妙地避免了大数越界的问题。于是,我们直接上代码:

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        StringBuffer ret = new StringBuffer();
        int i = s.length() - 1;
        int j = t.length() - 1;
        boolean isFlag = false;
        while (i >= 0 || j >= 0) {
            int cur = 0;
            if (j < 0) {
                cur = s.charAt(i) - '0';
                i -= 1;
            } else if (i < 0) {
                cur = t.charAt(j) - '0';
                j -= 1;
            } else {
                cur = (s.charAt(i)- '0') + (t.charAt(j) - '0');
                i -= 1;
                j -= 1;
            }

            if (isFlag) {
                cur += 1;
            }
            // 10
            if (cur >= 10) {
                ret.insert(0, cur - 10 + "");
                isFlag = true;
            } else {
                ret.insert(0, cur + "");
                isFlag = false;
            }

        }
        if (isFlag) {
            // 还剩进位
            ret.insert(0, "1");
        }
        return ret.toString();
    }
}

时间复杂度: O(max(M + N)),M,N分别是s和t的链表长度。
空间复杂度: O(1),常量级空间复杂度(因为我们必须返回计算结果,所以用来存结果的ret并不用算额外的空间)。

上一篇:整理的linux面试运维题


下一篇:125.验证回文串Java