What is the pattern used in the Plus One problem?

The Plus One problem follows the 'array plus math' pattern, focusing on iterating through an array and applying basic arithmetic operations to manage carries and updates.

How should edge cases like a number ending in 9 be handled?

Edge cases like numbers ending in 9 should be handled by propagating the carry and resizing the array if necessary, e.g., 999 becomes 1000.

Is there a way to solve this problem in constant space?

Yes, solving the problem in-place with careful manipulation of the array ensures constant space complexity.

Can this problem be solved with recursion?

While recursion can be applied, an iterative solution is generally more efficient in terms of both time and space.

What is the time complexity of this problem?

The time complexity is O(n), where n is the length of the digits array, because we may need to iterate over the entire array to propagate carries.

#66

Easy

auto_awesome数组·数学

LeetCode 题解工作台

加一

给定一个表示大整数的整数数组 digits ，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0 。将大整数加 1，并返回结果的数字数组。示例 1：输入： digits = [1,2,3] 输出： [1,2,4] 解释：…

数组数学

题目描述

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

将大整数加 1，并返回结果的数字数组。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
加 1 后得到 4321 + 1 = 4322。
因此，结果应该是 [4,3,2,2]。

示例 3：

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

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits 不包含任何前导 0。

lightbulb

解题思路

方法一：模拟

我们从数组的最后一个元素开始遍历，将当前元素加一，然后对 $10$ 取模，如果取模后的结果不为 $0$ ，说明当前元素没有进位，直接返回数组即可。否则，当前元素为 $0$ ，需要进位，继续遍历前一个元素，重复上述操作。如果遍历完数组后，仍然没有返回，说明数组中所有元素都为 $0$ ，需要在数组的头部插入一个 $1$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            digits[i] += 1
            digits[i] %= 10
            if digits[i] != 0:
                return digits
        return [1] + digits

speed

复杂度分析

指标	值
时间	complexity is O(n) where n is the length of the digits array, as we may need to traverse the entire array in the worst case. Space complexity is O(1) if modified in-place, or O(n) if a new array is created.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate handle the carry and array resizing efficiently?
question_mark
Does the candidate consider all edge cases, including the case of multiple carries?
question_mark
How well does the candidate optimize the solution in terms of space and time complexity?

warning

常见陷阱

外企场景

error
Forgetting to handle carry-over when incrementing digits.
error
Not properly adjusting the array length when a carry overflows the most significant digit.
error
Overcomplicating the solution by using extra data structures unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the array represents a negative number? Adjust the approach accordingly.
arrow_right_alt
How would the solution change if the number represented more than one digit per element (e.g., two-digit numbers per array element)?
arrow_right_alt
How do you handle cases where the array is empty?

help

常见问题

外企场景

继续练习

#48 旋转图像 #149 直线上最多的点数 #150 逆波兰表达式求值