Rust 动态数组Vec基本概念及其用法

这篇具有很好参考价值的文章主要介绍了Rust 动态数组Vec基本概念及其用法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Rust 动态数组Vec基本概念及其用法,Rust,rust,开发语言

目录

一、基本概念

Vec是什么?

Vec的特点

(1)动态大小:

(2)可变性:

(3)泛型:

二、基础用法

1. 创建

(1) Vec::new()方法

(2) Vec::from()方法

(3) vec! 宏

2. 基础用法

三、Vec的简单实现及其宏模拟

四、leetcode 实战

1. 长度最小的子数组 Minimum-size-subarray-sum

2. 最大子数组和  Maximum Subarray

3. 螺旋矩阵 Spiral Matrix


Rust中的Vec是一种动态数组,它可以在运行时自动调整大小。Vec是Rust标准库的一部分,提供了一种高效、安全的方式来处理大量数据。基于堆内存申请的连续动态数据类型,其索引、压入(push)、弹出(pop) 操作的时间复杂度为 O(1) 。

一、基本概念

Vec是什么?

Vec,是“vector”的缩写。一种动态数组,它可以在运行时自动调整大小。Vec的底层实现是基于数组的,因此它的性能非常高。Vec可以存储任何类型的数据,包括整数、浮点数、字符串等。

Vec其实是一个智能指针,用于在上分配内存的动态数组。它提供了一些方法来操作数组,如添加、删除和访问元素。与C或Python中的数组不同,Vec会自动处理内存分配和释放,从而避免了常见的内存泄漏和悬挂指针错误。

Vec的本质就是一个三元组,指针、长度、容量,在rust标准库中的定义如下:

pub struct Vec<T, A: Allocator = Global> {
    buf: RawVec<T, A>,
    len: usize,
}
impl<T> Vec<T> {
    #[inline]
    pub const fn new() -> Self {
        Vec { buf: RawVec::NEW, len: 0 }
    }
//...略...
}

Rust 动态数组Vec基本概念及其用法,Rust,rust,开发语言

Vec的核心功能之一是动态增长和收缩。当向Vec中添加元素时,如果堆上的内存不足,Vec会自动分配更多的内存来容纳元素。这个过程称为“扩容”。同样,当从Vec中删除元素时,如果堆上的内存过多,Vec会自动收缩以释放内存。这个过程称为“缩容”。这种自动内存管理机制使得使用Vec变得非常方便,同时也避免了手动管理内存的错误。

除了基本的添加、删除和访问元素操作之外,Vec还提供了许多其他功能。例如,它们可以按索引访问元素,可以使用迭代器遍历元素,并且支持多种方法(如push()、pop()、insert()和remove())来修改Vec的内容。Vec还提供了一些有用的静态方法(如capacity()、len()和is_empty()),可以用来获取Vec的属性。

虽然Vec是一个非常强大的数据结构,但它们也有一些限制。例如,Vec在堆上分配内存,这意味着访问元素的速度可能会比在栈上分配内存的数组慢。此外,由于Vec是智能指针,因此它们的大小不是固定的,这可能会导致一些编程错误。例如,如果尝试将Vec赋值给一个固定大小的数组或另一个Vec,则会发生编译时错误。

Vec的特点

(1)动态大小:

Vec可以根据需要自动调整大小,无需预先分配内存。当元素数量发生变化时,Vec会自动重新分配内存并复制元素。

(2)可变性:

Vec是可变的,这意味着我们可以在不创建新Vec的情况下修改现有元素。这使得我们在处理大量数据时更加灵活。

(3)泛型:

Vec是泛型的,这意味着我们可以使用相同的方法来处理不同类型的数据。例如,我们可以使用vec![1, 2, 3]创建一个包含整数的Vec,使用vec!["a", "b", "c"]创建一个包含字符串的Vec。

动态数组是一种基于堆内存申请的连续动态数据类型,拥有 O(1) 时间复杂度的索引、压入(push)、弹出(pop)。 

二、基础用法

1. 创建

(1) Vec::new()方法

只创建一个空列表时,必须注明类型(否则通不过编译)。如下例的正确用法:

fn main() {
    let vec: Vec<i32> = Vec::new();
    println!("{:?}", vec);
}

输出:

[] 

注:print!、println!输出Vec时需要使用格式符 "{:?}" 。

但如果下一步要添加元素,比如使用push(x)方法,就非必须注明类型,默认就是 i32 类型:

示例: 

fn main() {
    let mut vec = Vec::new();
    vec.push(1);
    vec.push(2);
    vec.push(3);
    println!("{:?}", vec);
}

输出:

[1, 2, 3]

(2) Vec::from()方法

    let vec = Vec::from([1,2,3]);

(3) vec! 宏

    let vec = vec![1,2,3];

用法示例及判断是否相等:

fn main() {
    let vec1 = Vec::from([1,2,3]);
    println!("{:?}", vec1);
    let vec2 = vec![1,2,3];
    println!("{:?}", vec2);
    assert_eq!(vec1, vec2);
    assert_eq!(vec1, [1,2,3]);
    assert_eq!(vec2, [1,2,3]);
    println!("{}", vec1 == vec2);
}

输出:

[1, 2, 3]
[1, 2, 3]
true

vec! 宏 的另外用法: 

创建 len 个相同元素 n 的Vec,如:vec![n; len]。

示例:

fn main() {
    let vec = vec![0; 5];
    assert_eq!(vec, [0, 0, 0, 0, 0]);
    println!("{:?}", vec);
    let vec = vec![1; 3];
    assert_eq!(vec, [1, 1, 1]);
    println!("{:?}", vec);
    let vec = vec![1; 0];
}

以下是vec![1; 3]的等效方法,但速度较慢:

​fn main() {
    let mut vec = Vec::with_capacity(3);
    vec.resize(3, 1);
    assert_eq!(vec, [1, 1, 1]);
}

以上3种创建方法中,使用第3种方法的vec!宏来创建Vec相对比较方便。

二维Vec的创建和遍历

fn main() {
    // 创建一个2x3的二维向量
    let matrix: Vec<Vec<i32>> = vec![
        vec![1, 2, 3], 
        vec![4, 5, 6]
    ];
    
    // 遍历二维向量
    for row in &matrix {
        for &num in row {
            print!("{} ", num);
        }
        println!();
    }

    // 创建一个3x5的二维向量,所有元素都为 1
    let (m, n) = (3, 5);
    let number = 1;
    let matrix = vec![vec![number; n]; m];
    for row in &matrix {
        for &num in row {
            print!("{} ", num);
        }
        println!();
    }
}

输出:

1 2 3 
4 5 6 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 


2. 基础用法

Vec内置了非常丰富的内置方法,以下方法收集自网络,有重复暂时没空余时间去好好整理。

new(): 创建一个空的 Vec。
with_capacity(capacity: usize): 创建一个具有指定容量的空 Vec。
capacity() -> usize: 返回 Vec 的当前容量。
reserve(new_cap: usize): 为 Vec 分配额外的空间。
reserve_exact(new_cap: usize): 为 Vec 分配精确的额外空间。
shrink_to_fit(): 缩小 Vec 的容量以匹配其当前大小。
len() -> usize: 返回 Vec 的当前长度。
is_empty() -> bool: 检查 Vec 是否为空。
push(value: T): 将一个值添加到 Vec 的末尾。
pop() -> Option<T>: 删除并返回 Vec 的最后一个元素。
insert(index: usize, element: T): 在指定位置插入一个元素。
remove(index: usize) -> T: 删除并返回指定位置的元素。
swap(index1: usize, index2: usize): 交换指定位置上的两个元素。
truncate(len: usize): 将 Vec 截断为指定长度。
clear(): 删除 Vec 中的所有元素。
iter() -> Iter<T>: 返回一个迭代器,它允许按顺序遍历 Vec 中的元素。
iter_mut() -> IterMut<T>: 返回一个可变迭代器,它允许按顺序遍历 Vec 中的元素并进行修改。
into_iter() -> IntoIter<T>: 返回一个迭代器,它允许按顺序遍历 Vec 中的元素并转移所有权。
split_off(at: usize) -> Vec<T>: 从指定位置将 Vec 拆分为两个独立的 Vec。
append(&mut self, other: &mut Vec<T>): 将另一个 Vec 的所有元素附加到当前 Vec 的末尾。

swap(index1: usize, index2: usize): 交换指定位置的两个元素。
get(index: usize) -> Option<&T>: 获取指定位置的元素的引用。
get_mut(index: usize) -> Option<&mut T>: 获取指定位置的元素的可变引用。
first() -> Option<&T>: 获取 Vec 的第一个元素的引用。
first_mut() -> Option<&mut T>: 获取 Vec 的第一个元素的可变引用。
last() -> Option<&T>: 获取 Vec 的最后一个元素的引用。
last_mut() -> Option<&mut T>: 获取 Vec 的最后一个元素的可变引用。
split_at(index: usize) -> (&[T], &[T]): 将 Vec 分成两个部分,从指定位置进行分割。
split_at_mut(index: usize) -> (&mut [T], &mut [T]): 将 Vec 分成两个部分,从指定位置进行分割,返回可变引用。
as_slice() -> &[T]: 将 Vec 转换为切片,返回不可变引用。
as_mut_slice() -> &mut [T]: 将 Vec 转换为切片,返回可变引用。
iter() -> Iter<'_, T>: 返回一个迭代器,用于遍历 Vec 中的元素。
iter_mut() -> IterMut<'_, T>: 返回一个迭代器,用于遍历 Vec 中的元素,并返回可变引用。
into_iter() -> IntoIter<T>: 返回一个迭代器,用于遍历 Vec 中的元素,Vec 在迭代过程中将被移动。
clone_from(other: &Vec<T>): 从另一个 Vec 复制元素到当前 Vec。
truncate(len: usize): 删除 Vec 的尾部元素,直到长度为指定值。
clear(): 删除 Vec 中的所有元素。

as_slice() -> &[T]: 将 Vec 转换为不可变的切片。
as_mut_slice() -> &mut [T]: 将 Vec 转换为可变的切片。
split_first() -> Option<(&T, &[T])>: 返回 Vec 的第一个元素和其余部分的元组。
split_first_mut() -> Option<(&mut T, &mut [T])>: 返回 Vec 的第一个元素和其余部分的可变引用。
split_last() -> Option<(&T, &[T])>: 返回 Vec 的最后一个元素和其余部分的元组。
split_last_mut() -> Option<(&mut T, &mut [T])>: 返回 Vec 的最后一个元素和其余部分的可变引用。
chunks(chunk_size: usize) -> Chunks<'_, T>: 返回一个迭代器,该迭代器按块大小切分 Vec。
chunks_mut(chunk_size: usize) -> ChunksMut<'_, T>: 返回一个迭代器,该迭代器按块大小切分 Vec,并返回可变引用。
windows(window_size: usize) -> Windows<'_, T>: 返回一个迭代器,该迭代器在 Vec 上滑动,返回指定大小的窗口。
iter() -> Iter<'_, T>: 返回一个不可变引用的迭代器,该迭代器遍历 Vec 中的每个元素。
iter_mut() -> IterMut<'_, T>: 返回一个可变引用的迭代器,该迭代器遍历 Vec 中的每个元素。
into_iter() -> IntoIter<T>: 返回一个拥有所有权的迭代器,该迭代器遍历 Vec 中的每个元素。

chunks_exact(chunk_size: usize) -> ChunksExact<'_, T>: 返回一个迭代器,该迭代器按块大小切分 Vec,每个块都是固定大小的。
chunks_exact_mut(chunk_size: usize) -> ChunksExactMut<'_, T>: 返回一个迭代器,该迭代器按块大小切分 Vec,每个块都是固定大小的,并返回可变引用。
windows(window_size: usize) -> Windows<'_, T>: 返回一个迭代器,该迭代器按指定大小滑动窗口遍历 Vec。
iter() -> Iter<'_, T>: 返回一个不可变的迭代器,遍历 Vec 的元素。
iter_mut() -> IterMut<'_, T>: 返回一个可变的迭代器,遍历 Vec 的元素并返回可变引用。
into_iter() -> IntoIter<T>: 返回一个将 Vec 转换为迭代器的方法。
retain<F>(&mut self, f: F):在保留满足给定谓词的元素的情况下,删除不满足谓词的所有元素。
dedup(&mut self):删除连续重复的元素。只保留第一个出现的元素,其他的都被删除。

retain<F>(&mut self, f: F):在保留满足给定谓词的元素的同时,移除不满足谓词的元素。
truncate(len: usize): 将 Vec 的长度截断为指定长度。
dedup(): 移除 Vec 中相邻的重复元素。
dedup_by_key<F>(&mut self, key: F):使用指定的键函数,移除 Vec 中相邻的具有相同键的元素。
clone_from(&self, source: &[T]): 从指定的 slice 复制元素到 Vec 中。
extend<I>(&mut self, iter: I):将迭代器中的元素添加到 Vec 的末尾。
extend_from_slice(slice: &[T]): 将 slice 中的元素添加到 Vec 的末尾。
resize(&mut self, new_len: usize, value: T):将 Vec 的长度更改为指定长度,并使用指定的值填充新元素。
resize_with<F>(&mut self, new_len: usize, f: F):将 Vec 的长度更改为指定长度,并使用指定的函数填充新元素。
swap_remove(index: usize) -> T:删除并返回指定位置的元素,并用最后一个元素替换它。
truncate(len: usize): 将 Vec 的长度截断为指定长度。

resize_with<F>(&mut self, new_len: usize, f: F):将 Vec 的长度更改为指定长度,并使用指定的函数生成新元素。
try_reserve(n: usize) -> Result<(), AllocError>:尝试为至少包含指定数量的元素的 Vec 分配空间。
shrink_to_fit(): 缩小 Vec 的容量以匹配其当前长度。
as_ptr() -> *const T:返回 Vec 的指针。
as_mut_ptr() -> *mut T:返回 Vec 的可变指针。
capacity() -> usize:返回 Vec 的容量。
reserve(&mut self, additional: usize):为 Vec 分配额外的空间。
reserve_exact(&mut self, additional: usize):为 Vec 分配确切的额外空间。
set_len(&mut self, len: usize):设置 Vec 的长度,不检查新长度是否小于或大于容量。
into_boxed_slice(self) -> Box<[T]>:将 Vec 转换为包含所有元素的堆分配数组。
into_raw_parts(self) -> (*mut T, usize, usize):将 Vec 转换为原始指针,长度和容量的三元组。

into_boxed_slice(self) -> Box<[T]>:将 Vec 转换为包含所有元素的 Box<[T]>。
into_raw_parts(self) -> (*mut T, usize, usize):将 Vec 转换为其原始指针、长度和容量的元组。
from_raw_parts(ptr: *mut T, len: usize, cap: usize) -> Vec<T>:从原始指针、长度和容量的元组创建 Vec。
from_raw_parts_mut(ptr: *mut T, len: usize, cap: usize) -> Vec<T>:从原始指针、长度和容量的元组创建可变的 Vec。
drain<R>(&mut self, range: R) -> Drain<'_, T>:删除指定范围内的元素,并返回一个迭代器,该迭代器遍历已删除的元素。

splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, R::End, I::IntoIter>:将指定范围内的元素替换为迭代器中的元素,并返回一个迭代器,该迭代器遍历已删除的元素。
retain<F>(&mut self, f: F):在保留满足给定谓词的元素的同时,移除不满足谓词的元素。
partition<F>(&mut self, f: F) -> (Vec<T>, Vec<T>):根据给定谓词,将 Vec 中的元素分成两个新 Vec。
sort(&mut self):对 Vec 中的元素进行排序。
sort_by_key<K, F>(&mut self, key: F):使用指定的键函数,对 Vec 中的元素进行排序。
sort_by<F>(&mut self, compare: F):使用指定的比较函数,对 Vec 中的元素进行排序。
sort_unstable(): 对 Vec 中的元素进行不稳定排序。
splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, R::End, I::IntoIter>:将指定范围内的元素替换为迭代器中的元素,并返回一个迭代器,该迭代器遍历已删除的元素。
split_off(&mut self, at: usize) -> Vec<T>:将 Vec 拆分为两个 Vec,从指定位置开始拆分。
swap_remove(&mut self, index: usize) -> T:删除指定索引处的元素并返回它。
swap_remove_item(&mut self, item: &T) -> bool:查找并删除第一个等于给定元素的元素,并返回是否找到该元素。
truncate(&mut self, len: usize):将 Vec 的长度截断为指定长度。
unwrap():将包装在 Option 中的 Vec 解包,如果是 None,则 panic。
unwrap_or(default: Vec<T>) -> Vec<T>:将包装在 Option 中的 Vec 解包,如果是 None,则返回提供的默认值。
unwrap_or_default() -> Vec<T>:将包装在 Option 中的 Vec 解包,如果是 None,则返回默认值。

unwrap_or(default: Vec<T>) -> Vec<T>:将包装在 Option 中的 Vec 解包,如果是 None,则返回指定的默认值。
unwrap_or_else<F: FnOnce() -> Vec<T>>(f: F) -> Vec<T>:将包装在 Option 中的 Vec 解包,如果是 None,则调用指定的函数生成默认值。
zip<U>(self, other: U) -> Zip<Self, U::IntoIter>:创建一个迭代器,该迭代器通过将 self 和其他迭代器的元素进行配对来生成元组。
iter() -> Iter<'_, T>:返回一个迭代器,该迭代器遍历 Vec 的元素。
iter_mut() -> IterMut<'_, T>:返回一个可变迭代器,该迭代器遍历 Vec 的元素。
into_iter(self) -> IntoIter<T>:将 Vec 转换为其元素的迭代器。
len() -> usize:返回 Vec 的长度。
is_empty() -> bool:如果 Vec 为空,则返回 true,否则返回 false。
last() -> Option<&T>:返回 Vec 的最后一个元素的引用,如果 Vec 为空,则返回 None。
last_mut() -> Option<&mut T>:返回 Vec 的最后一个元素的可变引用,如果 Vec 为空,则返回 None。
split_first(&self) -> Option<(&T, &[T])>:返回 Vec 的第一个元素的引用和剩余元素的 slice,如果 Vec 为空,则返回 None。
split_first_mut(&mut self) -> Option<(&mut T, &mut [T])>:返回 Vec 的第一个元素的可变引用和剩余元素的可变 slice,如果 Vec 为空,则返回 None。

is_empty() -> bool:如果 Vec 为空,则返回 true,否则返回 false。
as_slice(&self) -> &[T]:将 Vec 转换为其元素的切片。
as_mut_slice(&mut self) -> &mut [T]:将 Vec 转换为其元素的可变切片。
last(&self) -> Option<&T>:返回 Vec 的最后一个元素的引用,如果 Vec 为空,则返回 None。
last_mut(&mut self) -> Option<&mut T>:返回 Vec 的最后一个元素的可变引用,如果 Vec 为空,则返回 None。
first(&self) -> Option<&T>:返回 Vec 的第一个元素的引用,如果 Vec 为空,则返回 None。
first_mut(&mut self) -> Option<&mut T>:返回 Vec 的第一个元素的可变引用,如果 Vec 为空,则返回 None。
binary_search(&self, x: &T) -> Result<usize, usize>:在已排序的 Vec 中搜索指定元素,并返回其索引。
sort(&mut self):按升序对 Vec 的元素进行排序。
sort_by_key<K, F>(&mut self, f: F):按升序对 Vec 的元素进行排序,其中排序关键字由指定的函数生成。
sort_by<F>(&mut self, compare: F):按升序对 Vec 的元素进行排序,其中比较函数由指定的函数生成。

binary_search(&self, x: &T) -> Result<usize, usize>:在已排序的 Vec 中搜索指定元素,并返回它的索引。如果元素不存在,则返回 Err,该 Err 包含元素应该插入的位置的索引。
binary_search_by<F>(&self, f: F) -> Result<usize, usize> where F: FnMut(&T) -> Ordering:在已排序的 Vec 中使用指定的比较函数搜索指定元素,并返回它的索引。如果元素不存在,则返回 Err,该 Err 包含元素应该插入的位置的索引。
binary_search_by_key<K, F>(&self, key: &K, f: F) -> Result<usize, usize> where F: FnMut(&T) -> K, K: Ord:在已排序的 Vec 中使用指定的键函数搜索指定键,并返回它的索引。如果键不存在,则返回 Err,该 Err 包含键应该插入的位置的索引。
sort(&mut self):对 Vec 中的元素进行排序。
sort_by<F>(&mut self, compare: F):使用指定的比较函数对 Vec 中的元素进行排序。
sort_by_key<K, F>(&mut self, f: F):使用指定的键函数对 Vec 中的元素进行排序。
reverse(&mut self):反转 Vec 中元素的顺序。
split_off(&mut self, at: usize) -> Vec<T>:将 Vec 拆分为两个 Vec,从指定位置开始拆分。

chunks(&self, chunk_size: usize) -> Chunks<'_, T>:返回一个迭代器,该迭代器遍历 Vec 的不重叠的块,每个块包含指定数量的元素。
chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T>:返回一个可变迭代器,该迭代器遍历 Vec 的不重叠的块,每个块包含指定数量的元素。
windows(&self, window_size: usize) -> Windows<'_, T>:返回一个迭代器,该迭代器遍历 Vec 的连续窗口,每个窗口包含指定数量的元素。
try_fold<B, F, R>(&self, init: B, f: F) -> R where F: FnMut(B, &T) -> Result<B, R>, R: From<B>:对 Vec 中的每个元素执行指定的操作,并返回结果。如果任何操作返回 Err,则停止并返回 Err,否则返回 Ok。
try_for_each<F, R>(&self, f: F) -> R where F: FnMut(&T) -> Result<(), R>, R: From<()>:对 Vec 中的每个元素执行指定的操作,并返回结果。如果任何操作返回 Err,则停止并返回 Err,否则返回 Ok。

try_for_each<F, R>(&self, f: F) -> R where F: FnMut(&T) -> Result<(), R>, R: From<()>:对 Vec 中的每个元素执行指定的操作,并返回结果。如果任何操作返回 Err,则停止并返回 Err,否则返回 Ok。
contains(&self, x: &T) -> bool:如果 Vec 包含指定的元素,则返回 true,否则返回 false。
dedup(&mut self):删除 Vec 中的重复元素。只保留第一次出现的元素。
dedup_by_key<F>(&mut self, key: F):删除 Vec 中的重复元素。只保留第一次出现的元素。比较是使用指定的键函数进行的。
retain<F>(&mut self, f: F):从 Vec 中删除不满足指定条件的所有元素。
split_off(&mut self, at: usize) -> Vec<T>:从 Vec 中分离指定索引之后的所有元素,并返回一个新的 Vec。
truncate(&mut self, len: usize):将 Vec 的长度截断为指定长度。如果指定长度小于 Vec 的当前长度,则删除多余的元素。


三、Vec的简单实现及其宏模拟

trait MyVec {
    type Item;
    fn new() -> Self;
    fn len(&self) -> usize;
    fn push(&mut self, element: Self::Item);
    fn pop(&mut self) -> Option<Self::Item>;
}

impl<T> MyVec for Vec<T> {
    type Item = T;

    fn new() -> Vec<T> {
        Vec::new()
    }

    fn len(&self) -> usize {
        Vec::len(self)
    }

    fn push(&mut self, element: T) {
        Vec::push(self, element)
    }
    
    fn pop(&mut self) -> Option<T> {
        Vec::pop(self)
    }
}

macro_rules! myvec {
    ( $( $x:expr ),* ) => {
        {
            let mut vec = <Vec<_> as MyVec>::new();
            $(
                vec.push($x);
            )*
            vec
        }
    };
}

fn main() {
    let mut v = myvec![1,2,3,4];
    println!("{:?}, size = {}", v, v.len());
    
    if let Some(last) = v.pop() {   // 检查向量是否为空
        println!("弹出的尾部元素: {:?}", last);
        println!("{:?}, size = {}", v, v.len());
    } else {
        println!("Vector is empty");  // 向量为空的情况
    }

    v.push(5);
    println!("{:?}, size = {}", v, v.len());
}

输出:

[1, 2, 3, 4], size = 4
弹出的尾部元素: 4
[1, 2, 3], size = 3
[1, 2, 3, 5], size = 4


四、leetcode 实战

1. 长度最小的子数组 Minimum-size-subarray-sum

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

提示:

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

代码1:

fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
    let mut i = 0;
    let mut j = 0;
    let mut sum = 0;
    let mut min_len = std::usize::MAX;
    while j < nums.len() {
        sum += nums[j];
        j += 1;
        while sum >= target {
            min_len = min_len.min(j - i);
            sum -= nums[i];
            i += 1;
        }
    }
    if min_len == std::usize::MAX {
        0
    } else {
        min_len as i32
    }
}

fn main() {
    let nums = vec![2, 3, 1, 2, 4, 3];
    println!("{}", min_sub_array_len(7, nums));
    let nums = vec![1, 4, 4];
    println!("{}", min_sub_array_len(4, nums));
}

代码2:

fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
    let mut min_len = i32::MAX;
    let (mut left, mut right) = (0, 0);
    let mut sum = 0;
    while right < nums.len() {
        sum += nums[right];
        while sum >= target {
            min_len = min(min_len, (right - left + 1) as i32);
            sum -= nums[left];
            left += 1;
        }
        right += 1;
    }
    if min_len == i32::MAX {
        return 0;
    }
    min_len
}
    
fn min(a: i32, b: i32) -> i32 {
    if a < b {
        a
    } else {
        b
    }
}

fn main() {
    let nums = vec![2, 3, 1, 2, 4, 3];
    println!("{}", min_sub_array_len(7, nums));
    let nums = vec![1, 4, 4];
    println!("{}", min_sub_array_len(4, nums));
}

2. 最大子数组和  Maximum Subarray

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组 是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

进阶:如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的 分治法 求解。

代码1: 动态规划

fn max_sub_array(nums: &[i32]) -> i32 {
    let n = nums.len();
    let mut dp = vec![0; n];
    dp[0] = nums[0];
    for i in 1..n {
        dp[i] = std::cmp::max(dp[i-1] + nums[i], nums[i]);
    }
    let mut res = dp[0];
    for i in 1..n {
        res = std::cmp::max(res, dp[i]);
    }
    res
}

fn main() {
    let nums = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
    println!("{}", max_sub_array(&nums));
    let nums = vec![1];
    println!("{}", max_sub_array(&nums));
    let nums = vec![5,4,-1,7,8];
    println!("{}", max_sub_array(&nums));
}

代码2: 贪心算法

fn max_sub_array(nums: &[i32]) -> i32 {
    let n = nums.len();
    let (mut cur_sum, mut max_sum) = (0, nums[0]);
    for i in 0..n {
        cur_sum += nums[i];
        if cur_sum > max_sum {
            max_sum = cur_sum;
        }
        if cur_sum < 0 {
            cur_sum = 0;
        }
    }
    max_sum
}

fn main() {
    let nums = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
    println!("{}", max_sub_array(&nums));
    let nums = vec![1];
    println!("{}", max_sub_array(&nums));
    let nums = vec![5,4,-1,7,8];
    println!("{}", max_sub_array(&nums));
}

输出:

6
1
23


3. 螺旋矩阵 Spiral Matrix

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:

Rust 动态数组Vec基本概念及其用法,Rust,rust,开发语言

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

Rust 动态数组Vec基本概念及其用法,Rust,rust,开发语言

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

代码1:

fn spiral_order(matrix: &[Vec<i32>]) -> Vec<i32> {
    if matrix.is_empty() {
        return vec![];
    }
    let (m, n) = (matrix.len(), matrix[0].len());
    let mut res = vec![0; m * n];
    let (mut top, mut bottom, mut left, mut right) = (0, m - 1, 0, n - 1);
    let mut idx = 0;
    while top <= bottom && left <= right {
        for i in left..=right {
            res[idx] = matrix[top][i];
            idx += 1;
        }
        for i in top + 1..=bottom {
            res[idx] = matrix[i][right];
            idx += 1;
        }
        if top < bottom && left < right {
            for i in (left..right).rev() {
                res[idx] = matrix[bottom][i];
                idx += 1;
            }
            for i in (top + 1..=bottom - 1).rev() {
                res[idx] = matrix[i][left];
                idx += 1;
            }
        }
        top += 1;
        bottom -= 1;
        left += 1;
        right -= 1;
    }
    res
}

fn main() {
    let matrix = vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ];
    println!("{:?}", spiral_order(&matrix));
    let matrix = vec![
        vec![1, 2, 3, 4],
        vec![5, 6, 7, 8],
        vec![9,10,11,12],
    ];
    println!("{:?}", spiral_order(&matrix));
}

代码2: 递归

fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
    fn spiral_helper(top: usize, bottom: usize, left: usize, right: usize, res: &mut Vec<i32>, idx: &mut usize, matrix: &Vec<Vec<i32>>) {
        if top > bottom || left > right {
            return;
        }
        
        // 从左到右遍历上边界
        for i in left..=right {
            res[*idx] = matrix[top][i];
            *idx += 1;
        }
        
        // 从上到下遍历右边界
        for i in (top + 1)..=bottom {
            res[*idx] = matrix[i][right];
            *idx += 1;
        }
        
        if top < bottom && left < right {
            // 从右到左遍历下边界
            for i in (left..right).rev() {
                res[*idx] = matrix[bottom][i];
                *idx += 1;
            }
            
            // 从下到上遍历左边界
            for i in ((top + 1)..bottom).rev() {
                res[*idx] = matrix[i][left];
                *idx += 1;
            }
        }
        
        // 矩形边界变小,递归调用spiral_helper继续遍历
        spiral_helper(top + 1, bottom - 1, left + 1, right - 1, res, idx, matrix);
        
    }
    
    let m = matrix.len();
    let n = matrix[0].len();
    let mut res = vec![0; m * n]; // 用于记录遍历结果
    let mut idx = 0; // 当前结果数组的下标
    
    // 从矩形最外层开始遍历
    spiral_helper(0, m - 1, 0, n - 1, &mut res, &mut idx, &matrix);
    
    res
}

fn main() {
    let matrix = vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ];
    println!("{:?}", spiral_order(matrix));
    
    let matrix = vec![
        vec![1, 2, 3, 4],
        vec![5, 6, 7, 8],
        vec![9,10,11,12],
    ];
    println!("{:?}", spiral_order(matrix));
}

输出:

[1, 2, 3, 6, 9, 8, 7, 4, 5]
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] 


文章来源地址https://www.toymoban.com/news/detail-536362.html

到了这里,关于Rust 动态数组Vec基本概念及其用法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Rust: Vec类型的into_boxed_slice()方法

    比如,我们经常看到Vec类型,但取转其裸指针,经常会看到into_boxed_slice()方法,这是为何? 其实,你看标准文档,就很清楚, 也就是说,转成了Box[T]后,指针所指向的类型,更简短了,丢弃多余的 capacity。 看看输出了啥? 上面,还可以看到,实际分配内存和预分配内存不一

    2024年02月14日
    浏览(35)
  • 2023-05-20:go语言的slice和rust语言的Vec的扩容流程是什么?

    2023-05-20:go语言的slice和rust语言的Vec的扩容流程是什么? 答案2023-05-20: go版本是1.20.4。 扩容流程见源码见runtime/slice.go文件中的 growslice 函数。 growslice 函数的大致过程如下: 1.如果元素类型的大小为零,则返回具有 nil 指针但非零长度的切片。否则,下一步。 2.计算新切片的

    2024年02月05日
    浏览(36)
  • Rust之旅 - Rust概念、Windows安装、环境配置

    🌹作者主页:青花锁 🌹简介:Java领域优质创作者🏆、Java微服务架构公号作者😄 🌹简历模板、学习资料、面试题库、技术互助 🌹文末获取联系方式 📝 [Java项目实战] 介绍Java组件安装、使用;手写框架等 [Aws服务器实战] Aws Linux服务器上操作nginx、git、JDK、Vue等 [Java微服务

    2024年01月22日
    浏览(39)
  • Rust 笔记:Rust 语言中哈希结构(哈希映射,HashMap)、集合(哈希集,HashSet)及其使用

    Rust 笔记 Rust 语言中映射(HashMap)与集合(HashSet)及其用法 作者 : 李俊才 (jcLee95):https://blog.csdn.net/qq_28550263?spm=1001.2101.3001.5343 邮箱 : 291148484@163.com 本文地址 :https://blog.csdn.net/qq_28550263/article/details/130876735 【介绍】:本文介绍 Rust 中哈希结构相关概念及其使用。在 R

    2024年02月09日
    浏览(42)
  • 【跟小嘉学 Rust 编程】四、理解 Rust 的所有权概念

    【跟小嘉学 Rust 编程】一、Rust 编程基础 【跟小嘉学 Rust 编程】二、Rust 包管理工具使用 【跟小嘉学 Rust 编程】三、Rust 的基本程序概念 【跟小嘉学 Rust 编程】四、理解 Rust 的所有权概念 本章节将讲解 Rust 独有的概念(所有权)。所有权是 Rust 最独特的特性,它使得 Rust 能够

    2024年02月10日
    浏览(38)
  • Rust学习-通用编程概念

    静态类型(statically typed)的语言,必须在编译期知道所有变量的类型 允许使用类型后缀来指定类型,例如 57u8 数字字面量还可以使用 _ 作为可视分隔符以方便读数,如 1_000 使用 --release 参数进行发布(release)模式构建时,Rust 不检测会导致 panic 的整型溢出,Rust 会进行一种

    2024年02月13日
    浏览(28)
  • Rust通用编程概念

    变量与可变性 在Rust中,声明变量使用let,并且默认情况下,声明的变量是不可变的,要使变量可变需要在声明变量时,在变量前面加上mut。如下: 如果将上述代码中的mut去掉,那么在编译代码时就会报错,报错结果就是不能对不可变的变量进行二次赋值

    2024年02月08日
    浏览(33)
  • Rust 语言常见的一些概念(上)

    目录 1、变量的可变性 常量  隐藏 2、数据类型 2.1 标量类型 整型 浮点型 数值运算 布尔型 字符类型 复合类型 元组类型 数组类型 变量默认是不可改变的(immutable)。这是 Rust 提供给你的众多优势之一,让你得以充分利用 Rust 提供的安全性和简单并发性来编写代码。不过,你

    2024年02月06日
    浏览(29)
  • Rust 语言常见的一些概念(下)

    目录 1、函数 参数 语句和表达式 具有返回值的函数 2、注释 文档注释 多行注释 3、控制流 3.1 if 表达式 3.2 使用esle if 处理多重条件 3.3 在 let 语句中使用 if 3.4 使用循环重复执行 使用 loop 重复执行代码 从循环中返回值 循环标签:在多个循环之间消除歧义 while 条件循环 使用

    2024年02月06日
    浏览(34)
  • Rust教程:How to Rust-基本类型

    本专栏是优质Rust技术专栏,推荐精通一门技术栈的蟹友,不建议完全无计算机基础的同学 感谢Rust圣经开源社区的同学,为后来者提供了非常优秀的Rust学习资源 本文使用: 操作系统macOS Sonoma 14 / Apple M1 编译器:Rustc Cargo 感谢一路相伴的朋友们,感谢你们的支持 ^ _ ^ Rust教

    2024年04月12日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包