989. 数组形式的整数加法

🟢   🔖  数组 数学  🔗 力扣 LeetCode

题目

The array-form of an integer num is an array representing its digits in left to right order.

• For example, for num = 1321, the array form is [1,3,2,1].

Given num, the array-form of an integer, and an integer k, return thearray-form of the integer num + k.

Example 1:

Input: num = [1,2,0,0], k = 34

Output: [1,2,3,4]

Explanation: 1200 + 34 = 1234

Example 2:

Input: num = [2,7,4], k = 181

Output: [4,5,5]

Explanation: 274 + 181 = 455

Example 3:

Input: num = [2,1,5], k = 806

Output: [1,0,2,1]

Explanation: 215 + 806 = 1021

Constraints:

• 1 <= num.length <= 10^4
• 0 <= num[i] <= 9
• num does not contain any leading zeros except for the zero itself.
• 1 <= k <= 10^4

题目大意

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

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

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

示例 1：

输入： num = [1,2,0,0], k = 34

输出：[1,2,3,4]

解释： 1200 + 34 = 1234

示例 2：

输入： num = [2,7,4], k = 181

输出：[4,5,5]

解释： 274 + 181 = 455

示例 3：

输入： 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

解题思路

可以模拟数字的逐位加法，从数组的最右边开始进行加法（从 num 的最后一位和 k 的个位开始），逐位加到最终的结果中。每一位加法可能会产生一个进位，需要将进位保留并继续到下一位。

1. 变量初始化:

   • i = num.length - 1: 从 num 数组的末尾开始处理。
   • carry = 0: 进位初始化为 0。

2. 循环处理每一位:

   • 在 while 循环中，条件是 i >= 0 或 k > 0，即仍有 num 中的数字或者 k 中的数字需要处理。
   • 每次通过 k % 10 获取 k 的当前个位数
   • 如果 i >= 0，当前和为 sum = (k % 10) + carry + num[i]，将当前和的个位数更新到 num[i]。
   • 否则，当前和为 sum = (k % 10) + carry，将当前和的个位数直接插入到 num 的最前面。
   • 更新进位 carry 和 k，carry 为当前和的十位部分，k 则右移一位。

3. 处理进位: 如果加法过程中产生了最终的进位（carry 不为零），将其插入到数组的最前面。

4. 返回结果: 返回更新后的 num 数组。

复杂度分析

• 时间复杂度: O(max(n, log(k)))，n 为 num 数组的长度，log(k) 是 k 的位数。需要对 num 和 k 的每一位进行处理，时间复杂度是二者的最大值。
• 空间复杂度: O(1)，只使用了常数空间来存储进位。

代码

/**
 * @param {number[]} num
 * @param {number} k
 * @return {number[]}
 */
var addToArrayForm = function (num, k) {
	let i = num.length - 1,
		carry = 0;
	while (i >= 0 || k > 0) {
		let sum = (k % 10) + carry;
		if (i < 0) {
			num.unshift(sum % 10); // 如果 num 已经遍历完，直接将结果插入 num 的最前面
		} else {
			sum += num[i];
			num[i] = sum % 10; // 当前位更新为加法结果的个位
		}
		carry = Math.floor(sum / 10); // 计算进位
		k = Math.floor(k / 10); // 将 k 除以 10 以去掉当前位
		i--;
	}
	if (carry) num.unshift(carry); // 如果最后有进位，插入到最前面
	return num;
};

相关题目

题号	标题	题解	标签	难度	力扣
2	两数相加	[✓]	递归 链表 数学	🟠	🀄️ 🔗
66	加一	[✓]	数组 数学	🟢	🀄️ 🔗
67	二进制求和	[✓]	位运算 数学 字符串 1+	🟢	🀄️ 🔗
415	字符串相加	[✓]	数学 字符串 模拟	🟢	🀄️ 🔗