大整数相加问题

Leetcode上有很多线性表的题目，其中相当一部分可以归结为大整数相加问题。

比如：给两个字符串表示的十进制整数，如1003，202，求其和（字符串1205）。

此题还有很多变体，如：给一个字符串表示的大整数加1，或给定的整数为二进制。这些题如果试图通过强转成int或long来加，都是不行的，因为操作的是大整数，测试用例里肯定有超出整型范围的情况。

通用的解题步骤

我一开始写的代码十分复杂，而且很长。看了其他人写的之后，总结出此类问题的一个通用代码：

十进制整数相加

public static String addDecimal(String a, String b)
{
  int sizeA = a.length();
  int sizeB = b.length();
  int c = 0;
  StringBuilder sb = new StringBuilder();
  while(sizeA > 0 || sizeB > 0 || c > 0)
  {
    int tempResult = (sizeA > 0 ? a.charAt(sizeA - 1) - '0' : 0) + (sizeB > 0 ? b.charAt(sizeB - 1) - '0' : 0) + c;
    if(tempResult >= 10)
    {
      tempResult -= 10;
      c = 1;
    }
    else
    {
      c = 0;
    }
    sb.append(String.valueOf(tempResult));
    sizeA--;
    sizeB--;
  }

  return sb.reverse().toString();
}

二进制整数相加（原理相同）

public static String addBinary(String a, String b)
{
  int sizeA = a.length();
  int sizeB = b.length();
  int c = 0;
  StringBuilder sum = new StringBuilder();

  while (sizeA > 0 || sizeB > 0 || c > 0)
  {
    int tempResult = (sizeA > 0 ? (a.charAt(sizeA - 1) - '0') : 0) + (sizeB > 0 ? (b.charAt(sizeB - 1) - '0') : 0) + c;
    if (tempResult == 0)
    {
      sum.append('0');
      c = 0;
    }
    else if (tempResult == 1)
    {
      sum.append('1');
      c = 0;
    }
    else if (tempResult == 2)
    {
      sum.append('0');
      c = 1;
    }
    else
    {
      sum.append('1');
      c = 1;
    }
    sizeA--;
    sizeB--;
  }
  return sum.reverse().toString();
}

实际上原理很简单，和笔算“列竖式”的计算过程是一模一样的。