为什么要用Rust解题

优点

性能强大，但与c++不相上下，由于速度极快，内存利用率高。Rust的解法的运行速度很容易出现为0ms的情况（leecode目前还不支持毫秒级以下精度）。基本上O(n^2)和O(n)都会出现0ms。
函数式语法写起来简洁，可读性高。例如：

fn find_short(s: &str) -> u32 {
    s.split_whitespace().map(str::len).min().unwrap_or(0) as u32
}

fn longest_consec(strarr: Vec<&str>, k: usize) -> String {
    if strarr.is_empty() || k > strarr.len() {
        "".to_string()
    } else {
        strarr
            .windows(k)
            .rev() // wtf
            .map(|s| s.join(""))
            .max_by(|a, b| a.len().cmp(&b.len()))
            .unwrap()
    }
}

标准库中栈、队列等结构比较齐全，使用方便。

缺点

由于所有权机制导致链表操作极其复杂。
要考虑各种数据类型的转换，例如usize, u32, i32之间的转换。
leecode里有一些题不支持Rust。

小技巧

在确认长度的情况下可以优先分配大小，避免操作过程中因长度不够再次分配。如果长度不是很大，可以直接用固定长的数组，性能比集合要强。

1 2	Vec::with_capacity(capacity); HashMap::with_capacity(capacity);

善用ADT。当涉及到状态判断的时候，可以自定义enum结构，将内存占用降到最低。

#[derive(Debug, Clone, PartialEq, Eq)]
enum A {
    Zero,
    One,
    More,
};

impl A {
    fn add(&mut self) {
        match self {
            A::Zero => *self = A::One,
            A::One => *self = A::More,
            A::More => (),
        }
    }
    #[inline]
    fn is_one(&self) -> bool {
        match self {
            A::One => true,
            _ => false,
        }
    }
}

println!("{:?}", std::mem::size_of::<A>()); // 1
println!("{:?}", std::mem::size_of::<usize>()); // 8
let mut list = [A::Zero; 26];
// 采用自定义数据类型来代替数字判断，内存占用从26 * 8 bytes 降到8 bytes，而且不用考虑数字过大溢出的问题。

Rust的标准库没有随机数，leecode中又不方便引入第三方库，这时可以通过FFI使用c的随机数，再通过求余约束返回值的范围。

extern "C" {
  fn rand() -> i32;
}

println!("{}" unsafe { rand() % 10 });

排序。sort （归并排序）的排序是稳定的，在不考虑稳定性的情况下可以用sort_unstable （快速排序），可能获取更快的速度和更小的内存占用。对应的还有sort_unstable_by、sort_unstable_by_key。

Rust可以像c/c++一样原地（in-place)修改字符串，实现空间复杂为O(1)的解法。使用into_bytes返回字节数组后用下标访问和修改。

let s = String::from("xxxx");
let mut bytes = s.into_bytes();
let mut c = 'a' as u8;
std::mem::swap(&mut bytes[0], &mut c);
unsafe { String::from_utf8_unchecked(bytes) };
// 其他一些in-place操作的API有swap,take,replace

极端情况下可以用c或者汇编来解题。如汉明权重（二进制串中1的个数）。

fn hamming_weight(n: u32) -> u32 {
    let popcnt_input: usize = n as usize;
    let popcnt_output: usize;
    unsafe {
        asm!(
            "popcnt {popcnt_output}, {popcnt_input}",
            popcnt_input = in(reg) popcnt_input,
            popcnt_output = out(reg) popcnt_output,
        );
    }
    popcnt_output as u32
}

考虑浮点数精确度问题，不能直接用 == 判断，而是它们的差小于某一个值。

1
2
3

fn is_integer(float: f32) -> bool {
    (float - float.round()).abs() < f32::EPSILON
}

数字溢出。防止因数字过大，或者为负数导致的溢出。

let i: u32 = 1;
println!("{}", i.saturating_sub(10)); // 0
println!("{}", i.wrapping_sub(10)); // 4294967287
println!("{}", i - 10); // panicked at 'attempt to subtract with overflow'
let j: u8 = 255;
println!("{}", j.saturating_add(1)); // 255
println!("{}", j.wrapping_add(1)); // 0
println!("{}", j + 1); // panicked at 'attempt to add with overflow'

Follow your heart

Rust解leecode技术小总结

为什么要用Rust解题

优点

缺点

小技巧