面试算法题(2)--两个大数相加

两个大数相加 听说这是个频繁出现的算法题，在某某网站是的排行很靠前。 在找工作之前，同事提过一次，我没当回事，恰恰在我第一家面试时就碰到了。 两个大数相加。 1、是整数； 2、两个数无限大，long都装不下； 3、不能用BigInteger； 4、不能用任何包装类提供的运算方法； 5、两个数都是以字符串的方式提供。 两个字符串的数字，怎么相加？ 其实也简单，核心点考的是ASCII码和相加进位的问题。 比喻字符类型的'9'怎么转换成int的9？ '9' - '0' = 9。这个算法能理解吗？ char类型进行算数运算时是不是自动转换为int类型的了？ 字符9的ASCII值是不是比字符0的多9个？这是第一个关键点。 第二个关键点是，注意相加时的进位。 对两个字符串的数字，可以使用字符数组的方式处理，也可以用StringBuffer。 有人会问，StringBuffer每次append都是在后面追加，但是处理数字进位时需要在前面处理。 其实StringBuffer有个方法reverse()，翻转字符串 举个例子比喻下整个处理过程： String str1 = "123459"; string str2 = "123"; 两个字符串需要翻转，为什么？ 因为相加处理是从最右边的个位开始的，还有进位处理。 调用reverse()方法处理后： String str1 = "954321"; string str2 = "321"; 现在就好办了，个位对齐了。可以开始相加了，注意进位。 int carry = 0; 计算个位： int value = str1.charAt(0) + str2.charAt(0) - 2*'0' + carry; 上面这行代码能理解吗？ 翻译过来就是：'9' + '3' - 2*'0' + carry; 为什么 - 2*'0' ？ 字符进行算术运算时，会转换成ASCII值在进行运算。 故继续翻译为：57 + 51 - 2*48 + 0； 是不是等于 9 + 3 + 0 ? 好，不多废话了。相加后的值为12。 直接把12存储在个位上吗？当然不是，把进位的10部分存储到carry变量中，便于进行十位数字相加时使用： carry = 12 / 10; value = 12 % 10; 然后把value的值保存到最终的个位上。 一次上述步骤。 最后需要注意的是，输入的两个字符串数字长度不一定相等。 第一次循环时要以较短的字符串未结束点，计算两个数字和carry的相加和进位。 然后在基于较长的字符串长出的部分循环，与carry相加，处理进位。

上面都把核心点说了，直接来撸代码吧，有注释的：

public static void main(String[] args) { String str1 = "123459"; String str2 = "123"; System.out.println(add(str1, str2));//123582 } private static String add(String str1, String str2) { //任何一个字符串为null或空字符串，都不需要相加了 if (str1 == null || "".equals(str1)) { return str2; } if (str2 == null || "".equals(str2)) { return str1; } int maxLength = Math.max(str1.length(), str2.length()); //定义一个存贮结果的字符串，长度要比最大长度字符串还长一位，用于存储可能出现的进位 StringBuffer result = new StringBuffer(maxLength + 1); //翻转两个字符串 str1 = new StringBuffer(str1).reverse().toString(); str2 = new StringBuffer(str2).reverse().toString(); //反转后的结果分别为： //954321 //321 int minLength = Math.min(str1.length(), str2.length()); //进位 int carry = 0; //当前位上的数值 int currentNum = 0; //循环变量 int i = 0; for (; i < minLength; i++) { //分别获取两个字符对应的字面数值，然后相加，再加上进位 currentNum = str1.charAt(i) + str2.charAt(i) - 2 * '0' + carry; //获取进位 carry = currentNum / 10; //处理当前位的最终值 currentNum %= 10; //保存当前位的值到最终的字符缓冲区中 result.append(String.valueOf(currentNum)); } if (str1.length() < str2.length()) { //选择 str1 = str2; } for (; i < str1.length(); i++) { //分别获取两个字符对应的字面数值，然后相加，再加上进位 currentNum = str1.charAt(i) - '0' + carry; //获取进位 carry = currentNum / 10; //处理当前位的最终值 currentNum %= 10; //保存当前位的值到最终的字符缓冲区中 result.append(String.valueOf(currentNum)); } //处理最后一个的进位(当循环结束后，是不是还可能会有一个进位) if (carry > 0) { result.append(String.valueOf(carry)); } //最后翻转恢复字符串，再返回 return result.reverse().toString(); }

如果你有更好的想法，欢迎留言