每日一题-2020803

题目

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

注意:

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

题解

双指针,每一位置相加可以看成由 x, y, carry 进位组成。
时间复杂度 O(max(num1.length, num2.length))
空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
object Solution {
def addStrings(num1: String, num2: String): String = {
var i = num1.length - 1
var j = num2.length -1
var carry = 0

var ans = Seq[Int]()

while (i >= 0 || j >=0 || carry !=0) {
val x = if (i < 0) 0 else num1(i) - '0'
val y = if (j < 0) 0 else num2(j) - '0'
val result = x + y + carry
carry = result / 10
ans = ans :+ result % 10
i -= 1
j -= 1

}

ans.reverse.mkString("")
}
}
使用搜索:谷歌必应百度