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数组
- nums[i]压栈
解法
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]