TNotes.leetcode

Appearance

0989. 数组形式的整数加法【简单】

0989. 数组形式的整数加法【简单】 ​

1. 📝 题目描述 ​

整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。

  • 例如，对于 num = 1321，数组形式是 [1,3,2,1]。

给定 num，整数的 数组形式，和整数 k，返回 整数 num + k 的 数组形式。

示例 1：

txt
输入：num = [1,2,0,0], k = 34
输出：[1,2,3,4]
解释：1200 + 34 = 1234

示例 2：

txt
输入：num = [2,7,4], k = 181
输出：[4,5,5]
解释：274 + 181 = 455

示例 3：

txt
输入：num = [2,1,5], k = 806
输出：[1,0,2,1]
解释：215 + 806 = 1021

提示：

  • 1 <= num.length <= 10^4
  • 0 <= num[i] <= 9
  • num 不包含任何前导零，除了零本身
  • 1 <= k <= 10^4

2. 🎯 s.1 - 逐位加法（维护进位） ​

js
/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function (num, k) {
  const res = []
  let i = num.length - 1
  let carry = 0

  while (i >= 0 || k > 0) {
    const x = i >= 0 ? num[i] : 0
    const y = k % 10
    const sum = x + y + carry
    res.push(sum % 10)
    carry = Math.floor(sum / 10)
    k = Math.floor(k / 10)
    i--
  }

  if (carry) res.push(carry)
  res.reverse()
  return res
}

// --------------------------------------------
// 【补充说明】
// 🤔 为什么不直接使用 unshift 来维护 res，而是先用 push 最后再 reverse？
// --------------------------------------------
// unshift 比 push 操作昂贵得多！
// 可以对比两个版本的提交时间来查看差异。
// 也可以在浏览器调试工具中执行以下示例来对比：
/* 
const arr = []

console.time('push')
for (let i = 0; i < 1_000_000; i++) {
  arr.push(i)
}
console.timeEnd('push')

const arr2 = []
console.time('unshift')
for (let i = 0; i < 1_000_000; i++) {
  arr2.unshift(i)
}
console.timeEnd('unshift')
*/
// 实测结果参考：
// push: 6.7861328125 ms
// unshift: 36471.3720703125 ms
  • 时间复杂度：O(n)，其中 n 为 num.length
  • 空间复杂度：O(1)（不计输出数组）

算法思路：

  • 从最低位开始与 k 的最低位做加法并维护进位，依次写入结果
  • 当数组与 k 都处理完后，若还有进位则追加
  • 最后反转得到正确顺序

Discussions