Rust 笔试题
1 请阐述你对 Rust 所有权系统的理解，可从以下角度
A. 单一所有权
B. 内存管理方式
C. Copy/Move 语义
D. 借用规则
E. 如何把借用检查推迟到运行期
答：
在Rust中，在每个值都有一个所有者，一旦超出生命周期就会释放，并且由于单一所有权，同一个值只能有多个不可变引用和一个可变引用
引用类似于c语言中的引用，有不同与c语言，在rust中称呼为借用，区别在于在rust中默认是只读的
并且在执行变量赋值时，如果变量类型没有实现Copy、Clone的Trait，就会执行Move语义，反之就会默认进行Copy
借用检查推迟，我不是很了解，也没有尝试过这样做，但是我想应该是利用RefCell，毕竟这是一个动态检查的具有内部可变性的智能指针，但是我想将借用检查推迟是一个很危险的操作，这将可能导致悬垂引用
2 实现与vec![]功能类似的宏my_vec
/// 作答
#[macro_export]
macro_rules! my_vec {
() => {
std::vec::Vec::new()
};
($value:expr; $size:expr) => ({
let mut vec = std::vec::Vec::new();
for i in 0..$size {
vec.push($value);
}
vec
});
($($x:expr),*) => ({
let mut vec = std::vec::Vec::new();
$(vec.push($x);)*
vec
});
}
pub fn test_vec() {
let v1: Vec<i32> = my_vec!();
let v2 = my_vec!(2;4);
let v3 = my_vec!(1, 2, 3, 4);
println!("v1: {:?}, \nv2: {:?}, \nv3: {:?}", v1, v2, v3);
}
3 实现如下编程题
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
impl ListNode {
#[inline]
fn new(val: i32) -> Self {
ListNode { next: None, val }
}
}
/// 请在在一个链表中每相邻的两个节点间插入一个结点, 插入节点的val为两个节点val的最大公约数
/// 例如： [10, 5, 6] -> [10, 5, 5, 1, 6]
/// ^ ^
/// 复杂度要求： O(n)/O(1)
pub fn insert_greatest_common_divisors(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
/// 作答
let mut a = 0;
let mut b = 0;
let mut size = 0;
let mut flag = false;
let mut last: Option<Box<ListNode>> = head.clone();
while let Some(mut item) = last.as_mut().unwrap().next.as_mut() {
if size == 0 {
a = item.val;
continue;
}
if flag {
flag = false;
continue;
}
b = item.val;
let gcd = get_GCD(a, b);
let mut new_node = ListNode::new(gcd);
new_node.next = item.next.clone();
item.next = Some(Box::new(new_node));
a = item.val;
size += 1;
flag = true;
}
last
///
}
/// 作答
pub fn get_GCD(a: i32, b: i32) -> i32 {
let mut temp = i32::default();
let mut x = a;
let mut y = b;
while b != 0 {
temp = x % y;
x = y;
y = temp;
}
/// 作答
4 利用Vec实现一个栈Stack，要求top, pop, push, iter(栈顶到栈底的迭代), into_iter(栈顶到栈底的迭代)
/// 作答
struct Stack {
value: Vec<i32>,
}
impl Stack {
pub fn new() -> Self {
Self {
value: Vec::<i32>::new(),
}
}
pub fn top(&self) -> i32 {
self.value[0]
}
pub fn pop(&mut self) -> i32 {
let temp = self.value.remove(0);
temp
}
pub fn push(&mut self, v: i32) {
self.value.insert(0,v);
}
pub fn iter(&self) -> Iter<'_, i32> {
self.value.iter()
}
pub fn into_iter(&self) -> IntoIter<i32> {
self.value.clone().into_iter()
}
}
5 实现快速排序算法的非递归版本
/// 作答
pub fn quick(vec: &mut Vec<i32>) {
Self::quick_branch(vec, 0, vec.len() - 1);
}
fn quick_cure(vec: &mut Vec<i32>, start: usize, end: usize) -> usize {
let mut prev = start.clone();
let mut cur = end;
let mut key = start.clone();
while prev != cur {
while (prev < cur) & (vec[cur] >= vec[key]) {
cur -= 1;
}
while (prev < cur) & (vec[prev] <= vec[key]) {
prev += 1;
}
vec.swap(cur, prev);
}
vec.swap(key, prev);
prev
}
fn quick_branch(vec: &mut Vec<i32>, start: usize, end: usize) {
if start >= end {
return;
}
let mut stack = Vec::new();
stack.push((0, vec.len() - 1));
while let Some((f, l)) = stack.pop() {
if f >= l{
continue;
}
//let key = Self::quick_cure(vec, start, end);
let key = Self::quick_cure(vec, f, l);
if key > 0 {
//Self::quick_branch(vec, start, key - 1);
stack.push((f, key - 1));
}
//Self::quick_branch(vec, key + 1, end);
stack.push((key + 1, l));
}
}
6 实现一个双向链表
