在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


LeetCode #66 加一

题目

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

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

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

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123

示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321

解题思路

题目的任务: 在一个 已排序的数组 中找到目标值的位置。

思路:
这道题看似很简单,只需要数组最后一个元素加一即可。但是需要注意最后元素需要进位的情况。
一共会出现以下 3 种情况:

  • 普通情况:[1, 2, 4] –> [1, 2, 5]
  • 特殊情况1:[1, 2, 9] –> [1, 3, 0]
  • 特殊情况2:[9, 9, 9] –> [1, 0, 0, 0]

在特殊情况1中,我们倒叙遍历数组元素,当元素等于9时改为0,否则元素加一。
在特殊情况2中,我们遍历完数组后仍然无法返回,则说明数组所有元素都为9,处于特殊情况2。我们只需要创建一个比原数组长度多1的新数组,然后将第一个元素改为1即可(int数组默认值为0,所以不需要对后面的元素赋值)。

代码:

class Solution {
public int[] plusOne(int[] digits) {
int length = digits.length;
for(int i = length-1; i >= 0; i--){
// 普通情况,加一直接返回
if(digits[i] != 9){
digits[i] += 1;
return digits;
}
// 特殊情况1,进一位进行遍历
digits[i] = 0;
}
// 特殊情况2,创建新数组
int[] result = new int[length + 1];
result[0] = 1;
return result;
}
}

评论