C#LeetCode刷题之#415-字符串相加（Add Strings）

问题

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

1. num1 和num2 的长度都小于 5100.
2. num1 和num2 都只包含数字 0-9.
3. num1 和num2 都不包含任何前导零。
4. 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

1. The length of both num1 and num2 is < 5100.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

示例

public class Program {

    public static void Main(string[] args) {
        var num1 = "392";
        var num2 = "19823";

        var res = AddStrings(num1, num2);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static string AddStrings(string num1, string num2) {
        //定义一个大1位的数组
        var max = Math.Max(num1.Length, num2.Length) + 1;
        var total = new int[max];
        //向左补0到相同数量，否则需要额外处理边界
        num1 = num1.PadLeft(max, '0');
        num2 = num2.PadLeft(max, '0');
        //进位标识
        var carry = false;
        var sum = 0;
        for(int i = max - 1; i >= 0; i--) {
            sum = int.Parse(num1[i].ToString()) + int.Parse(num2[i].ToString());
            if(carry) sum++;
            total[i] = int.Parse(sum.ToString()[sum.ToString().Length - 1].ToString());
            carry = sum > 9;
        }
        //定义结果
        var res = string.Empty;
        //遍历输出到res
        total.ToList().ForEach(r => { res += r.ToString(); });
        //取消最高位0
        res = res.TrimStart('0');
        //如果空了，返回0
        if(res.Length == 0) res = "0";
        //返回结果
        return res;
    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

20215

分析：

显而易见，以上算法的时间复杂度为：  。