数组加一（66）

题目

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例

输入: [1,2,3] 输出: [1,2,4]

输入: [4,3,2,1] 输出: [4,3,2,2]

算法

末尾数字加一，分为三种情况：

1. 末尾加一不进位，直接输出
2. 末尾加一进位，但是在数组中间某一位停止进位
3. 末尾加一进位，直到第一位还是进位，输出一个length+1的首位为1其余位为0的数组

循环

末尾位加一，判断加一的位是否进位，若不进位则输出数组；若进位则向前一位加一，继续重复判断

export const plusOne = (digits) => {
	let index = digits.length - 1;
	digits[index] += 1;
	while (digits[index] > 9) {
		digits[index] %= 10;
		index -= 1;
		if (index < 0) {
			digits.unshift(1);
			break;
		}
		digits[index] += 1;
	}
	return digits;
};

循环

从最后一位到第一位循环加一，如果某一位末尾数字不为0则输出数组，如果没有跳出循环则说明该数组加一后一直进位到最高位仍需进位，则返回一个长度为length+1、首位位1、其余位为0的数组

export const plusOne = (digits) => {
	const len = digits.length;
	for (let i = len - 1; i >= 0; i--) {
		digits[i] += 1;
		digits[i] %= 10;
		if (digits[i] !== 0) {
			return digits;
		}
	}
	return [1].concat([...Array(len)].map((item) => 0));
};

递归

思路如上，此处传递的digits是引用变量，所以传递地址，循环中可以直接更改目标对象

export const plusOne = (digits) => {
	helper(digits, 0, digits.length - 1);
	return digits;
};

function helper(digits, start, end) {
	if (digits[end] !== 9) {
		digits[end] += 1;
		return;
	}
	digits[end] = 0;
	if (start === end) {
		digits.unshift(1);
	} else {
		helper(digits, start, end - 1);
	}
};