rust的leetcode练习

代码：https://gitee.com/dr12730/leetcode.git

数组

移动零

描述

给定nums，将所有0移动到数组末尾，同时保持非零元素相对顺序

in: [0, 1, 0, 3, 12] out: [1, 3, 12, 0, 0]

思路

遍历数组nums，把非零元素保存在[0, i-1]，把[i, n-1]设置为0

解法

array.rs

 pub struct Solution;

 impl Solution {
     pub fn move_zeros(nums: &mut Vec<i32>) {
         let mut copyto: usize = 0;

         for nz in 1..nums.len() {
             if nums[nz] != 0 {
                 nums[copyto] = nums[nz];
                 copyto += 1;
             }
         }
         for z in copyto..nums.len() {
             nums[z] = 0;
         }
     }
 }

main.rs

 mod array;

 fn main() {
     let mut nums: Vec<i32> = vec![0, 1, 0, 3, 12];
     println!("nums: {:?}", nums);
     array::Solution::move_zeros(&mut nums);
     println!("移动零后: {:?}", nums);
 }

加一

给定由整数组成的非空数组所表示的非负整数，在该数基础上加一。最高位在数组首位

in: [1, 2, 3] out: [1, 2, 4]

in: [9, 9, 9] out: [1, 0, 0, 0]

思路

数组反序，如果是9要进位，不是9加1即可

解法

pub fn add_one(mut nums: Vec<i32>) -> Vec<i32> {
    for num in nums.iter_mut().rev() {
        if *num != 9 {
            *num += 1;
            return nums;
        }
        *num = 0;
    }
    nums.insert(0, 1);
    nums
}

删除重复元素

给定数组nums，在原地删除重复出现的元素，使得每个元素只出现一次

in: [1,1,2] -> out: [1, 2] in: [0,0,1,1,1,2,2,3,3,4] -> [0,1,2,3,4]

思路

设置快、慢指针，遍历数组nums：

nums[i] == nums[j]，跳过重复项
nums[i] != nums[j]，把nums[j]重复给nums[i+1]
当nums中没有重复元素时，每次都会把num[j]复制一遍
- 增加一个判断，当重复元素的个数大于1时才复制

解法

pub fn remove_duplicates(mut nums: Vec<i32>) -> Vec<i32> {
    if nums.len() == 0 {
        return nums;
    }

    let mut slow: usize = 0;
    for fast in 1..nums.len() {
        if nums[slow] != nums[fast] {
            if fast - slow > 1 {
                slow += 1;
                nums[slow] = nums[fast];
            }
        }
    }
    for _ in slow..nums.len() - 1 {
        nums.remove(slow + 1);
    }
    nums
}

栈和队列

最小栈

说明

设计一个支持push, pop, top操作，能在常数时间内检索到最小元素的栈

push：数据压栈
pop：删除栈顶元素
top：获取栈顶元素
get_min：检索栈中的最小元素

MinStack mistack = new MinStack();
minstack.push(-2);
minstack.push(0);
minstack.push(-3);
minstack.get_min(); // 返回-3
minstack.pop(); 
minstack.top(); // 返回0
minstack.get_min(); // 返回-2

思路

使用2个栈

数据栈stack存放出入栈的数据
minstack存取stack中的最小值
- 相当于便利stack中的元素，把升序的数据删除，留下一个从栈底到栈顶降序的栈

解法

#[derive(Debug)]
pub struct MinStack{
    stack: Vec<i32>,
    minstack: Vec<i32>,
}

impl MinStack {
    pub fn new() -> Self {
        Self {stack: vec![], minstack: vec![]}
    }

    pub fn push(&mut self, data: i32) -> &mut Self {
        self.stack.push(data);

        if self.minstack.is_empty() || *self.minstack.last().unwrap() > data {
            self.minstack.push(data);
        }

        self
    }

    pub fn pop(&mut self) -> i32 {
        let num = self.stack.pop().unwrap();

        if num == *self.minstack.last().unwrap() {
            self.minstack.pop();
        }

        num
    }

    pub fn get_min(&self) -> i32 {
        *self.minstack.last().unwrap()
    }

    pub fn top(&self) -> i32 {
        *self.stack.last().unwrap()
    }
}

有效的括号

题目

给定只包含”()[]{}”的字符串，判断括号是否配对

in: “()[]{}”, out: true in: “([)]”, out: false

思路

通过栈完成括号匹配的判断

解法

pub struct Solution;
impl Solution {
    pub fn is_match(s: &String) -> bool{
        if s.len() == 0{
            return true;
        }
        let chs:Vec<char> = s.chars().collect();

        let mut v:Vec<char> = Vec::new();
        for ch in chs{
            if ch == '(' {
                v.push(')');
            }else if ch == '[' {
                v.push(']');
            }else if ch == '{' {
                v.push('}') ;
            } else if v.is_empty() || v.pop().unwrap() != ch {
                return false;
            }
        }
        
        v.is_empty()
    }
}

滑动窗口最大值

题目

给定数组nums，有一个大小为k的滑动窗口从左侧移到右侧。返回滑动窗口的最大值

in: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 out: [3, 3, 5, 5, 6, 7]

原理

用双端队列deque实现一个单调递减的队列
- 首部总是最大值
- nums为空或k=1返回[]
- 对前k个数字，得到初始的单调递减的双端队列deque
- 对[k, ..]
  - nums[i]压栈
    - 让双端队列deque弹出比nums[i]小的数
    - 把nums[i]从deque尾端压栈
  - 当deque的首部==k窗口的前一个元素
    - 弹出首部
    - 保持deque队列始终事窗口k个元素的单调递减元素的内容
  - 把最大值(deque的首部)拷贝到最终的max_vec数组

解法

pub struct SlideWin{
    pub nums: Vec<i32>,
    pub k: usize,
    pub deque: VecDeque<i32>,
    pub max_vec: Vec<i32>,
}

impl SlideWin {
    pub fn new(nums: Vec<i32>, k: usize) -> Self {
        Self {nums, k, deque: VecDeque::new(), max_vec: vec![]}
    }

    // 对前k个元素得到初始的单调递减队列
    pub fn frist_k(&mut self) -> &mut VecDeque<i32> {
        for i in 0..self.k {
            self.decreasing_push(self.nums[i]);
        }

        &mut self.deque
    }

    pub fn decreasing_push(&mut self, num:i32) -> &VecDeque<i32> {
        while !self.deque.is_empty() {
            if num >= *self.deque.back().unwrap() {
                self.deque.pop_back();
            } else {
                break;
            }
        }
        self.deque.push_back(num);
        &self.deque
    }

    pub fn max_value(&mut self) -> &Vec<i32> {
        if self.nums.len() == 0 || self.k == 1 {
            return &self.max_vec;
        }

        for i in self.k-1..self.nums.len(){
            if i == self.k-1 {
                self.frist_k();
                self.max_vec.push(*self.deque.front().unwrap());
            } else if i > self.k-1 {
                self.decreasing_push(self.nums[i]);

                if *self.deque.front().unwrap() == self.nums[i-self.k] {
                    self.deque.pop_front();
                }
                self.max_vec.push(*self.deque.front().unwrap());
            }
        }

        &self.max_vec
    }
}

验证

    println!("\n========== 滑动窗口k的最大值 ===========");
    let nums:Vec<i32> = vec![];
    let k:usize = 2;
    let mut slide_win = stack::SlideWin::new(nums, k);
    println!("nums: {:?}, k = {}", slide_win.nums, slide_win.k);
    println!("滑动窗口最大值: {:?}\n", slide_win.max_value()); 

    let nums:Vec<i32> = vec![1,2,3,4];
    let k:usize = 1;
    let mut slide_win = stack::SlideWin::new(nums, k);
    println!("nums: {:?}, k = {}", slide_win.nums, slide_win.k);
    println!("滑动窗口最大值: {:?}\n", slide_win.max_value()); 

    let nums:Vec<i32> = vec![1,2,3,4,3,2,1,2,3,4,5,6,5,4,3];
    let k:usize = 8;
    let mut slide_win = stack::SlideWin::new(nums, k);
    println!("nums: {:?}\nk = {}", slide_win.nums, slide_win.k);
    println!("对前{}个元素构建初始递减队列: {:?}", k, slide_win.frist_k());
    println!("k = {}的最大值列表: {:?}\n", k, slide_win.max_value());

    let nums:Vec<i32> = vec![1, 3, -1, -3, 5, 3, 6, 7];
    let k:usize = 3;
    let mut slide_win = stack::SlideWin::new(nums, k);
    println!("nums: {:?}\nk = {}", slide_win.nums, slide_win.k);
    println!("对前{}个元素构建初始递减队列: {:?}", k, slide_win.frist_k());
    println!("k = {}的最大值列表: {:?}\n", k, slide_win.max_value());

结果

========== 滑动窗口k的最大值 ===========
nums: [], k = 2
滑动窗口最大值: []

nums: [1, 2, 3, 4], k = 1
滑动窗口最大值: []

nums: [1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3]
k = 8
对前8个元素构建初始递减队列: [4, 3, 2]
k = 8的最大值列表: [4, 4, 4, 5, 6, 6, 6, 6]

nums: [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
对前3个元素构建初始递减队列: [3, -1]
k = 3的最大值列表: [3, 3, 5, 5, 6, 7]

上篇LwIP 分析

下篇设计模式·面向对象的设计原则