leetcode66:加一

news/2024/12/14 10:20:16/

原题地址：66. 加一 - 力扣（LeetCode）

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

解题思路

题目要求对一个非负整数数组表示的数字加 1，并返回一个新的数组。
这是一个模拟加法操作的题目。主要需要处理两种情况：

普通情况：直接对最后一位加 1，并根据进位向前处理即可。
进位到最高位：当最高位有进位时，需要扩展数组长度。

算法思路如下：

从数组末尾开始遍历，对当前位进行加 1 操作，同时处理进位。
如果最高位存在进位，则创建一个新的数组，将进位放入最高位。
返回最终处理后的数组。

源码实现

class Solution {public int[] plusOne(int[] digits) {// 判断输入是否为空if (null == digits) {return digits; // 空输入直接返回}// 初始化进位变量为 0int cary = 0;// 从数组末尾开始遍历for (int i = digits.length - 1; i >= 0; i--) {if (i == digits.length - 1) { // 处理最低位int val = digits[i];digits[i] = (val + cary + 1) % 10; // 当前位加 1 并取余数cary = (val + cary + 1) / 10; // 更新进位} else { // 处理其他位int val = digits[i];digits[i] = (val + cary) % 10; // 加上进位并取余数cary = (val + cary) / 10; // 更新进位}}// 如果最高位还有进位if (cary > 0) {// 创建新数组，长度为原数组长度 + 1int[] temp = new int[digits.length + 1];temp[0] = cary; // 将进位放在最高位for (int i = 0; i < digits.length; i++) {temp[i + 1] = digits[i]; // 将原数组的值复制到新数组}return temp; // 返回新数组}// 没有进位，直接返回原数组return digits;}
}