趣味算法题

越刷越上头的趣味算法题
帅旋
关注
充电
IT宅站长,技术博主,共享单车手,全网id:arthinking。

一次遍历加数字进位解决加一问题

发布于 2024-03-14 | 更新于 2024-03-15

题目:66. 加一[1]

如果您已经有思路了,或者是N刷了,可以先自己写一遍。

题目分析

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

这个问题可以通过从数组的末尾向前遍历来解决,使用数组遍历数字进位的技术。

解题思路

通过从后向前的遍历,我们可以逐位处理加一和进位的问题,而无需考虑数组中剩余的部分:

  • 当遇到不是9的数字时,加一操作不会引起进位,直接返回结果即可;
  • 如果当前元素等于9,加一操作将导致当前位变成0,然后继续检查前一位;
  • 对于全是9的数组,新的数组长度会增加1,这是由数字的进位规则决定的;

Java解法

下面是使用Java语言的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
// 如果当前位小于9,直接加一返回
if (digits[i] < 9) {
digits[i]++;
return digits;
}
// 如果当前位是9,加一变成0
digits[i] = 0;
}
// 执行到这里说明所有位都是9,需要增加一位,并将第一位设为1
int[] newDigits = new int[digits.length + 1];
newDigits[0] = 1;
return newDigits;
}
}

References


  1. 66. 加一 ↩︎

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/algorithm/plus-one.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。