package array_and_string

/**
66. 加一

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

示例1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：
输入：digits = [0]
输出：[1]

提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
*/

func plusOne(digits []int) []int {
	// 异常参数校验
	if len(digits) == 0 {
		return digits
	}

	// 获取切片长度
	length := len(digits) - 1
	// 因为数字是高位在前，所以我们从后往前遍历
	for length >= 0 {
		// 如果数字当前位的值小于9，则加1后的值肯定也不会大于9，不需要进位
		if digits[length] < 9 {
			// 因此，直接将当前位的值加1后，返回即可
			digits[length] = digits[length] + 1
			return digits
		}
		// 否则的话，将当前位的值置0，表示进位
		// 实际上，除了最后一次循环外，下一次循环就表示已进位
		digits[length] = 0
		// 将切片长度减1，继续下一次循环
		length--
	}

	// 如果在上面的循环没有返回，则意味着digits的各个位的值都是9
	// 因此，创建一个新的切片，其长度为digits的长度加1，并将首位置为1即可
	newDigits := make([]int, len(digits)+1)
	newDigits[0] = 1
	return newDigits
}