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/文章来源:https://www.toymoban.com/news/detail-759749.html
本文由 mdnice 多平台发布文章来源地址https://www.toymoban.com/news/detail-759749.html
到了这里,关于用Rust刷LeetCode之66 加一的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!