题解 | #高精度整数加法#

解法：
1、用java的BigInteger调api
2、用数组保存每一位然后开始做加法

第1种解法是我刚看到题目就想到的，写完提交结果时间比前几名多太多了（我24ms，java版的top1是6ms）

下面着重介绍第2种解法:

抄的top1的答案，但是也要去理解别人的解题思路。

题目意思为两个正数相加，但是top1老哥把负数也考虑到了，但是异号时存在bug所以异号情况先不讲解，等我自己理清思路再编辑。

讲解均放在代码注释中。

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = br.readLine()) != null && line.length() > 0) {
            System.out.println(add(line.trim(), br.readLine().trim()));
        }
    }
 
    static String add(String s1, String s2) {
        if (s1.length() == 0 || s2.length() == 0)
            return "";
      	// 判断正负号
        boolean neg1 = s1.charAt(0) == '-';
        boolean neg2 = s2.charAt(0) == '-';
 
      	// 同号异号处理，最终效果是s1长度大于等于s2
        if (!(neg1 ^ neg2)) {
            if (s1.length() < s2.length()) {
                String temp = s1;
                s1 = s2;
                s2 = temp;
            }
        } else if (neg1) {
            if (s1.length() < s2.length() + 1) {
                String temp = s1;
                s1 = s2;
                s2 = temp;
                neg1 = false;
                neg2 = true;
            }
        } else if (neg2) {
            if (s1.length() + 1 < s2.length()) {
                String temp = s1;
                s1 = s2;
                s2 = temp;
                neg1 = true;
                neg2 = false;
            }
        }
 
      	// 把大数字存入数组
        int[] lmax = new int[neg1 ? s1.length() - 1 : s1.length()];
        for (int i = neg1 ? 1 : 0; i < lmax.length; ++i)
          	// 用ascii码的差值计算每位数字
            lmax[i] = s1.charAt(i) - '0';
        int[] lmin = new int[neg2 ? s2.length() - 1 : s2.length()];
        for (int i = neg2 ? 1 : 0; i < lmin.length; ++i)
            lmin[i] = s2.charAt(i) - '0';
 
        int i = lmax.length - 1, j = lmin.length - 1;
      	// 同号做加法，异号做减法
        if (!(neg1 ^ neg2)) {
          	// 最终进位标志
            int[] carry = new int[1];
            while (j >= 0) {
              	// lmax与lmin数组做加法运算，最终有进位则存入carry数组中
                add(lmax, i, lmin[j], carry);
                --i;
                --j;
            }
          	// 最终根据是否有进位以及正负号进行输出
            StringBuilder sb = new StringBuilder();
            if (neg1)
                sb.append('-');
            if (carry[0] == 1)
                sb.append(1);
            for (i = 0; i < lmax.length; ++i)
                sb.append(lmax[i]);
            return sb.toString();
        } else {
            int flag = 0;
            boolean neg = true;
            if (i == j) {
                flag = -1;
                for (int k = 0; k <= i; ++k) {
                    if (lmax[k] > lmin[k]) {
                        flag = 0;
                        neg = neg1;
                        break;
                    } else if (lmax[k] < lmin[k]) {
                        flag = 1;
                        neg = neg2;
                        break;
                    }
                }
            }
            if (flag == -1)
                return "0";
            if (flag == 1) {
                int[] temp = lmax;
                lmax = lmin;
                lmin = temp;
            }
            while (j >= 0) {
                minus(lmax, i, lmin[j]);
                --i;
                --j;
            }
            int L = 0;
            for (i = 0; i < lmax.length; ++i) {
                if (lmax[i] == 0) {
                    ++L;
                } else {
                    break;
                }
            }
            StringBuilder sb = new StringBuilder();
            if (neg)
                sb.append('-');
            for (i = L; i < lmax.length; ++i)
                sb.append(lmax[i]);
            return sb.toString();
        }
    }
 
    static void add(int[] lmax, int i, int val, int[] carry) {
      	// 如果算到lmax中的第一位仍有进位则存入carry数组中
        if (i == -1) {
            carry[0] = 1;
            return;
        }
        lmax[i] += val;
      	// 检查lmax中每一位是否有进位
        if (lmax[i] >= 10) {
            lmax[i] = lmax[i] - 10;
          	// 有进位则继续计算lmax中的前一位是否有进位
            add(lmax, --i, 1, carry);
        }
    }
 
    static void minus(int[] max, int i, int val) {
        max[i] -= val;
        if (max[i] < 0) {
            max[i] = max[i] + 10;
            minus(max, --i, 1);
        }
    }
 
}