leetcode [#415] | GCidea's blog

JerryXia 发表于 2018-03-18 11:59:59 , 阅读 (18)

1. 题目
2. 解决方案
3. 注意事项

题目

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.
Note:
The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

解决方案

public class Solution {
    public String addStrings(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int delta = Math.abs(len1 - len2);
        int max = Math.max(len1, len2);
        int[] intVal1 = new int[max];
        int[] intVal2 = new int[max];
        if(len1 >= len2){
            for(int i = 0; i < max; i++){
                intVal1[i] = Integer.parseInt(String.valueOf(num1.charAt(i)));
            }
            for(int j = 0; j < max; j++){
                if(j < delta){
                    intVal2[j] = 0;
                } else {
                    intVal2[j] = Integer.parseInt(String.valueOf(num2.charAt(j - delta)));
                }
            }
        } else {
            for(int i = 0; i < max; i++){
                intVal1[i] = Integer.parseInt(String.valueOf(num2.charAt(i)));
            }
            for(int j = 0; j < max; j++){
                if(j < delta){
                    intVal2[j] = 0;
                } else {
                    intVal2[j] = Integer.parseInt(String.valueOf(num1.charAt(j - delta)));
                }
            }
        }
        StringBuilder builder = new StringBuilder("");
        handle(max, 0, intVal1, intVal2, builder);
        return builder.reverse().toString();
    }

    private static void handle(int max, int more, int[] val1, int[] val2, StringBuilder builder){
        int temp = 0;
        if(max >= 1){
            temp = val1[max - 1] + val2[max - 1] + more;
        } else {
            temp = val1[0] + val2[0] + more;
        }
        if(max-1 > 0){
            if(temp <= 9){
                builder.append(Integer.toString(temp));
                handle(--max, 0, val1, val2, builder);
            } else {
                builder.append(Integer.toString(temp % 10));
                handle(--max, 1, val1, val2, builder);
            }
        } else {
            if(temp <= 9){
                builder.append(Integer.toString(temp));
            } else {
                builder.append(Integer.toString(temp % 10));
                builder.append("1");
            }
        }
    }
}

注意事项

不能考虑任何直接转向整型进行求和的方法。字符串最多达到5099位，这不是常规数据类型能够表示的，同时又不能使用大整数的库。那么，就要将问题化简为最简的情况进行处理—考虑两个1位数求和的情况，结合进位情况，递归考虑下去。
为了简便，在进行递归处理前，先做了一系列处理：
a. 无论两个字符串各自多长，统一处理成较长长度的数组。
b. 遍历每个位置的字符，直接构建整型数组而不是字符串数组。
c. 始终保证intVal1[]存储的是本来较长的字符串转换的数组；而intVal2[]存储的是经过高位补零构成的数组。
经过以上处理，开始递归。注意进位状况，跳出递归的条件是遍历到达了数组的最低位（亦即“数字”的最高位）。

[ 技术文章推荐 ]