leetcode-66 加一

留言

66. 加一

难度: 简单


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func plusOne(digits []int) []int {
    length := len(digits)

    // 从最低位开始遍历，逐位加一
    for i := length - 1; i >= 0; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }

    // 如果循环结束仍然没有返回，则说明最高位也进位了，需要在数组首位插入 1
    return append([]int{1}, digits...)
}

解题思路

从最低位开始遍历，逐位加一。如果最高位进位，则在数组首位插入 1。

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们只遍历了数组一次。

空间复杂度：O(1)，除了返回的数组，没有其他额外的空间。


Rust版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pub fn plus_one(digits: Vec<i32>) -> Vec<i32> {
    let mut digits = digits;
    let length = digits.len();

    for i in (0..length).rev() {
        if digits[i] < 9 {
            digits[i] += 1;
            return digits;
        }
        digits[i] = 0;
    }

    digits.insert(0, 1); // 返回(),而非Vec<i32>
    digits // 或者 return digits;
}


几乎同样的写法,但Rust消耗的内存,比Go还要多一些..


完整的rust代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
fn main() {
    let digits = vec![1, 2, 3];
    let result = plus_one(digits);
    println!("{:?}", result); // 输出: [1, 2, 4]

    let digits = vec![9, 9, 9];
    let result = plus_one(digits);
    println!("{:?}", result); // 输出: [1, 0, 0, 0]

    let digits = vec![9, 1, 9];
    let result = plus_one(digits);
    println!("{:?}", result); // 输出: [9, 2, 0]
}

pub fn plus_one(digits: Vec<i32>) -> Vec<i32> {
    let mut digits = digits;
    let length = digits.len();

    for i in (0..length).rev() {
        if digits[i] < 9 {
            digits[i] += 1;
            return digits;
        }
        digits[i] = 0;
    }

    digits.insert(0, 1);
    digits // 或者 return digits;
}

(0..length).rev()中这两个语法糖挺不错


在 Rust 中，(0..length) 是一个范围（range）表达式，表示一个从 0 到 length-1 的半开区间。这个范围可以用于迭代、循环和其他需要遍历一系列整数的场景。

.rev() 是对范围进行反向迭代（reverse iteration）的方法调用。它返回一个可以从范围的最后一个元素向前迭代的迭代器。

因此，(0..length).rev() 表达式返回一个迭代器，可以从 length-1 开始迭代到 0。

在上述代码中，(0..length).rev() 用于循环遍历 digits 数组的每个索引，但是从最高位（最后一个元素）开始。这样可以方便地进行进位操作和遍历。


在 Rust 中，范围（range）表达式是一种用于表示一个数值范围的语法结构。它由两个点 .. 组成，并用于创建一个半开区间（half-open interval）。

范围表达式有两种形式：

  1. start..end：表示从 start（包含）到 end（不包含）的半开区间，迭代器将包含从 start 到 end-1 的值。
  2. start..=end：表示从 start（包含）到 end（包含）的闭区间，迭代器将包含从 start 到 end 的值。

文章目录