用Rust刷LeetCode之66 加一
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;
}
(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）。
范围表达式有两种形式：
-
start..end：表示从start（包含）到end（不包含）的半开区间，迭代器将包含从start到end-1的值。 -
start..=end：表示从start（包含）到end（包含）的闭区间，迭代器将包含从start到end的值。
参考资料
66. 加一: https://leetcode.cn/problems/plus-one/
本文由 mdnice 多平台发布