415.md

Question:

Given two non-negative integers 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.

Analysis

咋一看题目，首先想到的是，字符串转整型，然后整型再转字符串，好像很简单的样子，于是就有了下面的“解法一”。 唯一值得担忧的是，数字的长度会不会超过。再看题目，长度小于5100，晕啊，分明就是大数相加的题目了啊，不能这么做。

于是按照大数相加来求解，由于字符串方便的遍历方法是从左往右，而数字方面的加减计算是从低位到高位，即从右往左，故而，直观地讲原来的数字先来个转置，然后再一位一位地加。 加的时候要注意两个事情：

1. 可能有进位
2. 位数不一样长，有可能迭代到一定的时候，某个数已经先遍历完了，所以要注意判断

当然了，也可以改进下，从而可以不需要这个字符串转置，字符串怎么从后往前遍历呢。首先计算其长度l, l-0就是最后一个，l-2倒数第二个...如此一来就好了，成就了我们的方法三。

Tips

• 如何prepend到一个slice

a := []string{"b", "c", "d"}
x := append([]string("a"), a...)

Code

解法一，误解

func str2int(str string) int {
	var ret int
	for _, n := range str {
		ret = ret*10 + int(byte(n)-48)
	}
	return ret
}

func int2str(n int) string {
	ret := make([]byte, 0)
	for n != 0 {
		x := n % 10
		n /= 10
		ret = append([]byte{byte(x) + 48}, ret...)
	}
    if len(ret) == 0 {
		return "0"
	}
	return string(ret)
}

func addStrings(num1 string, num2 string) string {
	return int2str(str2int(num1) + str2int(num2))
}

解法二

func reverseStr(str string) string {
	s := []byte{}
	for _, n := range str {
		s = append([]byte{byte(n)}, s...)
	}
	return string(s)
}

func addStrings(num1 string, num2 string) string {
	num1, num2 = reverseStr(num1), reverseStr(num2)
	maxLen := len(num1)
	if maxLen < len(num2) {
		maxLen = len(num2)
	}

	isPromote := false
	var ret []byte
	for i := 0; i < maxLen; i++ {
		var left, right byte
		if i < len(num1) {
			left = byte(num1[i]) - 48
		}
		if i < len(num2) {
			right = byte(num2[i]) - 48
		}
		sum := left + right
		if isPromote {
			sum++
		}
		ret = append(ret, sum%10+48)
		isPromote = sum/10 == 1
	}
	// handle the last promote
	if isPromote {
		ret = append(ret, 49)
	}

	return reverseStr(string(ret))
}

解法三

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func addStrings(num1, num2 string) string {
    i1, i2 := len(num1)-1, len(num2)-1
    keep := 0
    
    max_len := max(len(num1), len(num2)) + 1
    
    num3 := make([]byte, max_len)
    j := max_len-1
    
    for i1 >= 0 || i2 >= 0 {
        
        val1 := 0
        if i1 >= 0 {
            val1 = int(num1[i1] - '0')
        }

        val2 := 0
        if i2 >= 0 {
            val2 = int(num2[i2] - '0')
        }

        sum := val1 + val2 + keep
        val := sum % 10
        keep = sum / 10
        
        num3[j] = byte(val + '0')

        j--
        i1--
        i2--
    }
    if keep > 0 {
        num3[j] = byte(keep + '0')
        j--
    }

    return string(num3[j+1:])
}