66. 加一

🟢   🔖  数组 数学  🔗 力扣 LeetCode

题目

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]

Output: [1,2,4]

Explanation: The array represents the integer 123.

Incrementing by one gives 123 + 1 = 124.

Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]

Output: [4,3,2,2]

Explanation: The array represents the integer 4321.

Incrementing by one gives 4321 + 1 = 4322.

Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]

Output: [1,0]

Explanation: The array represents the integer 9.

Incrementing by one gives 9 + 1 = 10.

Thus, the result should be [1,0].

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0's.

题目大意

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

解题思路

• 给出一个数组，代表一个十进制数，数组的 0 下标是十进制数的高位。要求计算这个十进制数加一以后的结果。
• 简单的模拟题。从数组尾部开始往前扫，逐位进位即可。最高位如果还有进位需要在数组里面第 0 位再插入一个 1 。

代码

思路一

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
	let carry = 1, // 进位
		i = digits.length - 1, // 从数组尾部开始往前扫
		sum = 0;

	// 当不再有进位时，循环结束
	while (carry !== 0) {
		// 最高位如果还有进位，在数组里面第 0 位再插入一个 1
		if (i < 0) {
			digits.unshift(carry);
			carry = 0;
		} else {
			// 模拟加法过程
			sum = carry + digits[i];
			carry = (sum / 10) | 0;
			digits[i] = sum % 10;
			i--;
		}
	}
	return digits;
};

思路二

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function (digits) {
	for (let i = digits.length - 1; i >= 0; i--) {
		// digits[i] 小于 9 时，不会发生进位，直接求和，并停止遍历
		if (digits[i] < 9) {
			digits[i] += 1;
			return digits;
		}

		// 否则发生进位，将 digits[i] 直接改为 0，继续遍历高位
		digits[i] = 0;
	}

	// 最高位如果还有进位，在数组里面第 0 位再插入一个 1
	digits.unshift(1);

	return digits;
};

相关题目

题号	标题	题解	标签	难度
43	字符串相乘	[✓]	数学 字符串 模拟
67	二进制求和	[✓]	位运算 数学 字符串 1+
369	给单链表加一 🔒	[✓]	链表 数学
989	数组形式的整数加法		数组 数学
2571	将整数减少到零需要的最少操作数		贪心 位运算 动态规划