devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

[Rust学习:四] Vec和栈_rust 栈

作者：Gausst松鼠会 | 2024-05-03 06:10:54

赞

踩

rust 栈

[Rust学习:四] Vec和栈

一、前言

  • 本文练习了栈的用法，顺便练习了match，还顺便练习了loop{break i}操作。
    • 学习了一波Vec的接口。
    • match写法:
      match c{
        'f' => nums.push(0),
        't' => nums.push(1),
        '(' => nums.push(-1),
        _ => (),  // 注意，必须写未匹配的部分，否则会报错。
        }

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
    • 另外注意,Vec的pop操作返回的是Some类型，要么用Some包一下，要么直接unwrap()，才能用。
  • 找了一圈，标准库里并没有栈这个玩意，但是好在我们可以用Vec或者VecDeque模拟。

二、阅读Vec源码尝试常用接口。

1. 创建Vec

	let mut vec = Vec::new();  // 创建一个无类型的vec，当第一次push后类型才会被推断出来，因此直接print会报错
    let mut vec = vec![1,2,3];  // 创建一个i32的vec:[1,2,3]
    let mut vec = vec![1;5];  // 创建一个长度为5的i32的vec:[1,1,1,1,1]
    
    // vec还可以从各种集合类型里转换而来
    assert_eq!(Vec::from([1, 2, 3]), vec![1, 2, 3]); // "vec_from_array", since = "1.44.0"
    assert_eq!(Vec::from(&[1, 2, 3][..]), vec![1, 2, 3]);  // "rust1", since = "1.0.0"
    
    let o: Cow<[i32]> = Cow::Owned(vec![1, 2, 3]);
    let b: Cow<[i32]> = Cow::Borrowed(&[1, 2, 3]);    
    assert_eq!(Vec::from(o), Vec::from(b)); // "vec_from_cow_slice", since = "1.14.0"

    assert_eq!(Vec::from("123"), vec![b'1', b'2', b'3']);  // "rust1", since = "1.0.0")

    let b: Box<[i32]> = vec![1, 2, 3].into_boxed_slice();
    assert_eq!(Vec::from(b), vec![1, 2, 3]);  // "vec_from_box", since = "1.18.0"

    assert_eq!(Vec::from(&mut [1, 2, 3][..]), vec![1, 2, 3]); // "vec_from_mut", since = "1.19.0")

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

2. 在尾部添加push\extend\append

	let mut vec1 = vec![1,2,3];  // 创建一个i32的vec:[1,2,3]
    vec1.push(4);  // [1,2,3,4]
    vec1.pop();  // [1,2,3]
    let mut vec2 = Vec::from(vec1.clone());  // [1, 2, 3] 注意如果不clone会使vec1失效
    // vec1.extend(vec2);  // vec1:[1, 2, 3, 1, 2, 3] ,注意 本操作会导致vec2失效.since = "1.6.0"
    // vec1.append(&mut vec2);  // vec1:[1, 2, 3, 1, 2, 3]  vec2:[];注意实参&mut，会把vec2的所有数据倒进vec1。内部调用了一个append)elements方法。 since = "1.4.0"

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

3. 任意位置添加insert

这个操作很明显是O(n)的，慎用。

	let mut vec1 = vec![1,2,3];  // 创建一个i32的vec:[1,2,3]
    vec1.insert(1,5);  // [1, 5, 2, 3]

  • 1
  • 2

4. 在尾部删除pop/split_off

	// 在尾部删除 pop/split_off
    let mut vec1 = vec![1,2,3];  // 创建一个i32的vec:[1,2,3]
    let p = vec1.pop();  // vec1:[1, 2], p = Some(3)
    let p = vec1.pop().unwrap();  // vec1:[1], p = 2

    let mut vec1 = vec![1,2,3];  // 创建一个i32的vec:[1,2,3]
    let vec2 = vec1.split_off(1);  // vec1:[1] vec2:[2,3],从下标1把vec1切开，返回尾巴

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

5. 在任意部位删除remove/swap_remove

  • swap_remove其实是一个不常用的随机集合删除优化，当不需要保持元素顺序，但又想随机化访问列表中的元素时，可以使用本方法，即我们删除一个元素时，把数组尾巴拿过来替换这个位置，实际删除尾巴，这样可以把复杂度降低到O(1)。
  • 应用：假设要设计一个随机元素访问的集合，但又要支持O(1)的删除/添加操作，就可以用这个方法。例题381. O(1) 时间插入、删除和获取随机元素 - 允许重复
    // 在任意位置删除 remove/swap_remove
    let mut vec1 = vec![1,2,3,4];  // 创建一个i32的vec:[1,2,3,4]
    let p = vec1.remove(1);  // 删除下标1的元素:vec:[1,3,4],p=2
    let p = vec1.swap_remove(0);  // 删除下标0的元素且用4替换这个位置:vec:[4,3],p=1

  • 1
  • 2
  • 3
  • 4

三、练习栈

1. 习题 1106. 解析布尔表达式

2. 题解

  • 运算表达式的题，通常可以用双栈(数字栈和运算符栈)来方便地解决。
  • 本题是这类题中较简单的一题，只有三个运算符，分类讨论即可。
  • 当遇到’f\t’时，数字栈中入栈0或1。
  • 特别的，当遇到左括号’('时，数字栈入一个-1，来标志这一段结束了。
  • 当遇到运算符时，入运算符栈。
  • 当遇到右括号’)'，代表该运算了,这里分类讨论即可。

3. 代码实现

impl Solution {
    pub fn parse_bool_expr(expression: String) -> bool {
        let mut nums = vec![0;0];  // 数字栈 
        let mut ops:Vec<char> = vec![];  // 运算符栈
        for c in expression.chars(){
            match c{
                'f' => nums.push(0),
                't' => nums.push(1),
                '(' => nums.push(-1),
                '&'|'|'|'!' => {ops.push(c)},
                ')' =>{
                    // let op = ops.pop().unwrap();
                    match  ops.pop().unwrap() {
                        '!'=> {
                            let p = nums.pop().unwrap();
                            nums.pop();
                            nums.push(p^1);                    
                        },
                        '&'=>{
                          let mut p = 1;
                          let ans = loop{
                              let top = nums.pop().unwrap();
                              if top == -1{
                                  break p;
                              }
                              p &= top;
                          };
                          nums.push(ans);
                        },
                        '|' => {
                            let mut p = 0;
                            let ans = loop{
                                let top = nums.pop().unwrap();
                                if top == -1{
                                    break p ;
                                }
                                p |= top;
                            };
                            nums.push(ans);
                        },
                        _ =>(),
                    }
                },
                _ => (),
            }
        }
    return nums[0] == 1;
    }
}

  • 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
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

四、练习swap_remove(其实pop+替换更好)

1. 381. O(1) 时间插入、删除和获取随机元素 - 允许重复

2. 题解

  • 这是一道业务实现题。
  • 由于需要随机化获取一个值，为了保证概率相同，需要所有数据放到vec中，随机产生一个范围内下标即可。
  • 那如何才能实现O(1)的删除呢，就用到了swap_remove这个技巧，由于元素顺序不重要，因此删除一个元素时，把末位数字替换过来，实际删除尾巴即可实现O(1)操作。
  • 其余的部分就是需要哈希表实现O(1)的查找、插入，记录每个元素对应的所有下标即可。

3. 代码实现

use std::collections::*;
use rand::Rng;
struct RandomizedCollection {
    d: HashMap<i32,HashSet<usize>>,
    v: Vec<i32>,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl RandomizedCollection {

    fn new() -> Self {
       Self{
            d:HashMap::new(),
            v:Vec::new(),
       }        
    }
    
    fn insert(&mut self, val: i32) -> bool {
        self.v.push(val);  // 插入
        if !self.d.contains_key(&val) {
            self.d.insert(val,HashSet::new());
        }
        let mut p = self.d.get_mut(&val).unwrap();
        p.insert(self.v.len()-1);
        // println!("{:?}",p);
        p.len() == 1
    }
    
    fn remove(&mut self, val: i32) -> bool {
        if !self.d.contains_key(&val){
            return false;
        }
        let mut p = self.d.get_mut(&val).unwrap();
        if p.len() == 0 {
            return false;
        }
        let  &pos = p.iter().next().unwrap();
        
        p.remove(&pos);        
        // 如果是最后一个，直接移除即可
        if pos == self.v.len()-1{
            self.v.pop();    
        }
        else {  // 否则要把最后一个值的下标修改一下            
            let v = self.v.last().unwrap();
            let mut pp = self.d.get_mut(&v).unwrap();
            pp.remove(&(self.v.len()-1));           
            pp.insert(pos);
            self.v.swap_remove(pos);    
        }

        return true;
    }
    
    fn get_random(&self) -> i32 {
        return self.v[rand::thread_rng().gen_range(0, self.v.len())]
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * let obj = RandomizedCollection::new();
 * let ret_1: bool = obj.insert(val);
 * let ret_2: bool = obj.remove(val);
 * let ret_3: i32 = obj.get_random();
 */

  • 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
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

六、参考链接

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/528173
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号