415. 字符串相加(Add Strings)E

英文题目

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

• Example 1:

• Input: num1 = "11", num2 = "123"
  Output: "134"
  

• Example 2:

• Input: num1 = "456", num2 = "77"
  Output: "533"
  

• Example 3:

• Input: num1 = "0", num2 = "0"
  Output: "0"
  

• Constraints:

• 1 <= num1.length, num2.length <= 10^4

• num1 and num2 consist of only digits.

• num1 and num2 don't have any leading zeros except for the zero itself.

• Follow up: Could you solve it without using any built-in BigInteger library or converting the inputs to integer directly?

中文题目

• 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

• 你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

• 示例 1：

• 输入：num1 = "11", num2 = "123"
  输出："134"
  

• 示例 2：

• 输入：num1 = "456", num2 = "77"
  输出："533"
  

• 示例 3：

• 输入：num1 = "0", num2 = "0"
  输出："0"
  

• 提示：

  • 1 <= num1.length, num2.length <= 10^4
  • num1 和num2 都只包含数字 0-9
  • num1 和num2 都不包含任何前导零

模拟

• 时间复杂度 O(max(len1, len2))，空间复杂度O(1)

  # python3: 时间 48 ms, 击败 75.11%; 内存 16 MB, 击败 61.93%
  class Solution:
      def addStrings(self, num1: str, num2: str) -> str:
          res = ""
          i1, i2, carry = len(num1)-1, len(num2)-1, 0
          while i1 >= 0 or i2 >= 0:
              n1 = int(num1[i1]) if i1 >= 0 else 0
              n2 = int(num2[i2]) if i2 >= 0 else 0
              # 计算单个位的和
              tmp = n1 + n2 + carry
              # 计算进位
              carry = tmp // 10
              res = str(tmp % 10) + res
              i1, i2 = i1-1, i2-1
          return str(carry)+res if carry > 0 else res
  

  // c++: 时间 20 ms, 击败 8.27%; 内存 54.4 MB, 击败 7.66%
  class Solution {
  public:
      string addStrings(string num1, string num2) {
          string res = "";
          int i1 = num1.size()-1, i2 = num2.size()-1;
          int carry = 0;
          while (i1 >= 0 || i2 >= 0) {
              // 注意此处字符转数字，不能直接int(num1[i1]),
              // 否则会得到字符对应的ascii的数字
              int n1 = i1 >= 0 ? num1[i1]-'0' : 0;
              int n2 = i2 >= 0 ? num2[i2]-'0' : 0;
              int tmp = n1 + n2 + carry;
              carry = tmp / 10;
              // 注意此处数字转字符串要调用to_string
              res = to_string(tmp % 10) + res;
              --i1;
              --i2;
          }
          return carry > 0 ? to_string(carry) + res : res;
      }
  };
  

  // java: 时间 6 ms, 击败 9.47%; 内存 42.8 MB, 击败 6.33%
  class Solution {
      public String addStrings(String num1, String num2) {
          String res = "";
          int i1 = num1.length()-1, i2 = num2.length()-1;
          int carry = 0;
          while (i1 >= 0 || i2 >= 0) {
              int n1 = i1 >= 0 ? num1.charAt(i1) - '0' : 0;
              int n2 = i2 >= 0 ? num2.charAt(i2) - '0' : 0;
              int tmp = n1 + n2 + carry;
              carry = tmp / 10;
              res = String.valueOf(tmp % 10) + res;
              --i1;
              --i2;
          }
          return carry > 0 ? String.valueOf(carry) + res : res;
      }
  }
  

  // go: 时间 4 ms, 击败 82.85%; 内存 7.2 MB, 击败 64.93%
  func addStrings(num1 string, num2 string) string {
      res := ""
      i1, i2 := len(num1)-1, len(num2)-1
      carry := 0
      for i1 >= 0 || i2 >= 0 {
          n1, n2 := 0, 0
          if i1 >= 0 {
              // 注意此处要用int转，否则得到的类型是uint8
              n1 = int(num1[i1] - '0')
          }
          if i2 >= 0 {
              n2 = int(num2[i2] - '0')
          }
          tmp := n1 + n2 + carry
          carry = tmp / 10
          res = strconv.Itoa(tmp % 10) + res
          i1--;
          i2--;
      }
      if carry > 0 {
          return strconv.Itoa(carry) + res
      }
      return res
  }
  

  // javascript: 时间 60 ms, 击败 95.23%; 内存 43.4 MB, 击败 51.48%
  /**
   * @param {string} num1
   * @param {string} num2
   * @return {string}
   */
  var addStrings = function(num1, num2) {
      let res = "";
      let i1 = num1.length-1, i2 = num2.length-1;
      let carry = 0;
      while (i1 >= 0 || i2 >= 0) {
          let n1 = i1 >= 0 ? num1.charAt(i1)-'0' : 0;
          let n2 = i2 >= 0 ? num2.charAt(i2)-'0' : 0;
          let tmp = n1 + n2 + carry;
          carry = Math.floor(tmp / 10);
          res = (tmp % 10).toString() + res;
          --i1;
          --i2;
      }
      return carry > 0 ? carry.toString() + res : res;
  };