这是 os summer of code 2020 项目每日记录的一部分：
github地址：https://github.com/yunwei37/os-summer-of-code-daily
其他一些 rust 的小练习：
笨办法系列
参考：Learn C The Hard Way 中文版
- c32-list: 练习32：双向链表
- c33-sort: 练习33：链表算法
- c40-bst: 练习40：二叉搜索树
- c42-stack-queue: 练习42：栈和队列
- c38-hashal：练习38：哈希算法
Leecode题目用Rust实现
参考：https://leetcode-cn.com/problemset/all/
文件夹中包含：
- README.md: 题目的出处和相关描述信息
- solution.rs: rust语言实现代码
- solution.c: c语言的实现代码
题目目录：
- leetcode-best-time-to-buy-and-sell-stock - 121. 买卖股票的最佳时机
- leetcode-binary-tree-inorder-traversal - 94. 二叉树的中序遍历
- leetcode-game-of-life - 289. 生命游戏
- leetcode-maximum-depth-of-binary-tree - 104. 二叉树的最大深度
- leetcode-maximum-subarray - 53. 最大子序和
- leetcode-remove-element - 27. 移除元素
- leetcode-set-matrix-zeroes - 73. 矩阵置零
- leetcode-valid-parentheses - 20. 有效的括号
- leetcode-longest-consecutive-sequence - 128. 最长连续序列
- leetcode-friend-circles - 547. 朋友圈
双向链表
注意，这里是很早的时候写的代码，实际上实现双向链表最好要使用 weak 来避免循环引用和内存泄漏问题。
数据结构定义：
代码语言：javascript复制use std::rc::Rc;
use std::cell::RefCell;
use std::clone::Clone;
#[derive(Debug)]
struct ListNode
{
value :i32,
next: Option<Rc<RefCell<ListNode>>>,
prev: Option<Rc<RefCell<ListNode>>>
}
#[derive(Debug)]
pub struct List{
count: i32,
first: Option<Rc<RefCell<ListNode>>>,
last: Option<Rc<RefCell<ListNode>>>
}函数实现
代码语言：javascript复制impl ListNode {
fn new(value:i32) -> Rc<RefCell<ListNode>>{
let pointer = Rc::new(RefCell::new(ListNode {
value,
next: None,
prev: None,
}));
Rc::clone(&pointer)
}
}
impl List {
pub fn new() -> List {
let first = ListNode::new(0);
let last = ListNode::new(0);
first.borrow_mut().next = Some(Rc::clone(&last));
last.borrow_mut().prev = Some(Rc::clone(&first));
List {
count: 0,
first: Some(first),
last: Some(last),
}
}
pub fn list_count(&self) -> i32 {
self.count
}
pub fn list_push(&mut self,value:i32){
let node = ListNode::new(value);
if let Some(ref l) = self.last {
let mut n = node.borrow_mut();
n.next = Some(Rc::clone(&l));
if let Some(ref p) = l.borrow().prev {
n.prev = Some(Rc::clone(&p));
p.borrow_mut().next = Some(Rc::clone(&node));
};
l.borrow_mut().prev = Some(Rc::clone(&node));
};
self.count = self.count 1;
}
pub fn list_unshift(&mut self, value:i32){
let node = ListNode::new(value);
if let Some(ref f) = self.first {
let mut n = node.borrow_mut();
n.prev = Some(Rc::clone(&f));
if let Some(ref p) = f.borrow().next {
n.next = Some(Rc::clone(&p));
p.borrow_mut().prev = Some(Rc::clone(&node));
};
f.borrow_mut().next = Some(Rc::clone(&node));
};
self.count = self.count 1;
}
pub fn list_shift(&mut self) -> i32 {
if self.count == 0 {
panic!("No Items for pop!");
}
let mut value = 0;
let mut pointer_pnext = None;
if let Some(ref f) = self.first {
if let Some(ref p) = f.borrow().next {
if let Some(ref pnext) = p.borrow().next {
pointer_pnext = Some(Rc::clone(&pnext));
pnext.borrow_mut().prev = Some(Rc::clone(&f));
}
value = p.borrow().value;
};
f.borrow_mut().next = pointer_pnext;
};
self.count = self.count-1;
value
}
pub fn list_pop(&mut self) -> i32 {
if self.count == 0 {
panic!("No Items for pop!");
}
let mut value = 0;
let mut pointer_pnext = None;
if let Some(ref l) = self.last {
if let Some(ref p) = l.borrow().prev {
if let Some(ref pnext) = p.borrow().prev {
pointer_pnext = Some(Rc::clone(&pnext));
pnext.borrow_mut().next = Some(Rc::clone(&l));
}
value = p.borrow().value;
};
l.borrow_mut().prev = pointer_pnext;
};
self.count = self.count-1;
value
}
pub fn list_first(&self) -> i32 {
if self.count == 0 {
panic!("No Items!");
}
let mut value = 0;
if let Some(ref f) = self.first {
if let Some(ref n) = f.borrow().next {
value = n.borrow().value;
};
}
value
}
pub fn list_last(&self) -> i32 {
if self.count == 0 {
panic!("No Items!");
}
let mut value = 0;
if let Some(ref l) = self.last {
if let Some(ref p) = l.borrow().prev {
value = p.borrow().value;
};
}
value
}
pub fn list_clear(&mut self){
while self.count > 0 {
self.list_pop();
}
}
}测试
代码语言：javascript复制#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_push_pop(){
let mut a = List::new();
a.list_push(1);
a.list_push(2);
assert_eq!(a.list_pop(),2);
assert_eq!(a.list_pop(),1);
}
#[test]
fn test_shift(){
let mut a = List::new();
a.list_unshift(3);
a.list_unshift(1);
a.list_unshift(2);
assert_eq!(a.list_shift(),2);
assert_eq!(a.list_shift(),1);
}
#[test]
fn test_shift_push(){
let mut a = List::new();
a.list_push(1);
a.list_push(2);
assert_eq!(a.list_shift(),1);
assert_eq!(a.list_shift(),2);
}
#[test]
fn test_clear(){
let mut a = List::new();
a.list_push(1);
a.list_push(2);
a.list_clear();
assert_eq!(a.list_count(),0);
}
#[test]
#[should_panic]
fn test_pop_empty(){
let mut a = List::new();
a.list_push(1);
a.list_pop();
a.list_pop();
}
#[test]
fn test_first_last(){
let mut a = List::new();
a.list_push(1);
a.list_push(2);
a.list_push(3);
assert_eq!(a.list_first(),1);
assert_eq!(a.list_last(),3);
}
}二叉树
数据结构定义：
代码语言：javascript复制use std::rc::Rc;
use std::mem::swap;
use std::cell::RefCell;
struct TreeNode {
key:i32,
value:String,
vaild:bool,
left: Option<Rc<RefCell<TreeNode>>>,
right: Option<Rc<RefCell<TreeNode>>>
}
pub struct Bst {
count:i32,
root: Option<Rc<RefCell<TreeNode>>>
}函数实现
代码语言：javascript复制impl TreeNode {
fn new(key:i32,value:String) -> Rc<RefCell<TreeNode>>{
Rc::new(RefCell::new(TreeNode {
key,
value,
vaild:true,
left: None,
right: None,
}))
}
}
fn bst_search(node:&Rc<RefCell<TreeNode>>,key:i32) -> Option<String>{
let mut result:Option<String> = None;
//println!("search {} {}",key,node.borrow().key);
if key == node.borrow().key {
if node.borrow().vaild {
return Some(node.borrow().value.clone());
}else {
return None;
}
}
else if key < node.borrow().key{
if let Some(ref n) = node.borrow().left {
result = bst_search(n,key);
}
}
else {
if let Some(ref n) = node.borrow().right {
result = bst_search(n,key);
}
}
//println!("res {:?}",result);
result
}
fn do_delete(node:&Rc<RefCell<TreeNode>>,key:i32){
let mut node1 = node.borrow_mut();
if key == node1.key {
node1.vaild = false;
}
else if key < node1.key{
if let Some(ref n) = node1.left {
do_delete(n,key);
}
}
else {
if let Some(ref n) = node1.right {
do_delete(n,key);
}
}
}
fn do_insert(node:&Rc<RefCell<TreeNode>>,key:i32,value:String) {
let mut node1 = node.borrow_mut();
//println!("doinsert {} {} {}",key,value,node1.key);
if key < node1.key {
match node1.left {
None => {
node1.left = Some(TreeNode::new(key,value));
},
Some(ref n) => {
do_insert(n,key,value);
}
}
}
else if key > node1.key {
match node1.right {
None => {
node1.right = Some(TreeNode::new(key,value));
},
Some(ref n) => {
do_insert(n,key,value);
}
}
}else{
node1.vaild = true;
node1.value = value;
}
}
impl Bst {
pub fn new() -> Bst {
Bst {
count:0,
root:None
}
}
pub fn insert(&mut self,key:i32,value:String){
if let Some(_) = self.bst_get(key) {
return;
}
match self.root {
None => {
self.root = Some(TreeNode::new(key,value));
},
Some(ref n) => {
do_insert(&n,key,value);
}
}
self.count = self.count 1;
}
pub fn bst_get(&self,key:i32) -> Option<String>{
match self.root {
None => None,
Some(ref n) => bst_search(n,key)
}
}
pub fn bst_delete(&self,key:i32){
if let None = self.bst_get(key) {
return;
}
match self.root {
None => {},
Some(ref n) => {
do_delete(n,key)
}
};
}
}测试
代码语言：javascript复制#[cfg(test)]
mod test {
use super::*;
fn insert(t:&mut Bst){
t.insert(5,String::from("Hello5"));
t.insert(3,String::from("Hello3"));
t.insert(6,String::from("Hello6"));
t.insert(4,String::from("Hello4"));
t.insert(1,String::from("Hello1"));
}
#[test]
fn test_search(){
let mut t = Bst::new();
insert(&mut t);
assert_eq!(t.bst_get(6),Some(String::from("Hello6")));
assert_eq!(t.bst_get(1),Some(String::from("Hello1")));
assert_eq!(t.bst_get(5),Some(String::from("Hello5")));
assert_eq!(t.bst_get(3),Some(String::from("Hello3")));
assert_eq!(t.bst_get(7),None);
}
#[test]
fn test_insert_delete(){
let mut t = Bst::new();
insert(&mut t);
t.bst_delete(4);
assert_eq!(t.bst_get(4),None);
t.insert(4,String::from("Hellokkk"));
assert_eq!(t.bst_get(4),Some(String::from("Hellokkk")));
}
}
