用Rust刷LeetCode之66 加一

fliter

发布于 2023-12-13 13:18:10

1710

发布于 2023-12-13 13:18:10

文章被收录于专栏：旅途散记

66. 加一[1]

难度: 简单

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版本:

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代码:

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;
}