66-加一(PlusOne)

news/2024/11/9 9:37:48/

大家好，我是anonymousC，一个算法小白0.0。

题目描述

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

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

你可以假设除了整数 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one

问题总结

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

问题分析

情况一：无进位(即最后一位小于9)如：[1,2,3,8] ==> [1,2,3,9]这种情况直接将最后一位加一就好了。
情况二：有进位i. 第一位不进位(即最有一位(或其他位置都为9)是9，但第一位小于9)如：[6,7,8,9] ==> [6,7,9,0][6,9,9,9] ==> [7,0,0,0]ii. 所有位都进位(即所有位置都为9)此时要扩大数组的大小(数字大小要加一)如：[9,9,9,9] ==> [1,0,0,0,0]

思路总结

我们可以从最后一位先开始进行加一，再判断是否有进位，若无进位则可以直接返回这个数组，若有进位，我们将该位值改为0，重复以上步骤。

步骤如下：

1.从最后一位先开始进行加一
2.判断是否有进位
3.若无进位则可以直接返回这个数组
4.若有进位，我们将该位值改为0，再重复以上步骤，直到最后依然没有返回数组，说明所有位置都发生了进位，即我们需要对数组长度进行加1，并且将数组的第一个值设置为1

JAVA代码

class Solution {public int[] plusOne(int[] digits) {// 从最后开始遍历for (int i = digits.length - 1; i >= 0; i--){digits[i]++; // 进行数字 + 1digits[i] %= 10; // 若有进位，则除10取余为0if (digits[i] != 0) { // 判断是否有进位return digits;  // 若没有进位，则返回}  }// 若for里面没有返回，则说明都发生了进位digits = new int[digits.length + 1]; // 数组长度加一digits[0] = 1;  // 将第一位赋值为1return digits;  // 返回数组}
}