0x0 前言

用Rust写算法应该怎么组织目录结构比较好，我到各种论坛上找了都没见到有人谈这个话题，可能大家都有自己的组织方式，我作为Rust新人就有点懵. 幸运的是我在GitHub上找到一个大哥维护的LeetCode in Rust项目感觉非常不错，就抄了他的结构，本文做一个简要叙述，方便Rust新人通过写算法题的方式上手Rust. 可能我的方法不是Rust写算法题组织文件的最优解，但对我来说足够了，也希望对你有帮助.

首先来配置一下Rust的开发和调试环境.

0x1 Rust开发和调试环境配置

Clion自带的Bundled MinGW就可以编译和调试Rust

  • 安装Clion
  • Settings-Build, Execution, Deployment-toolchains 自动识别
  • Clion Rust插件
  • 安装rust
    1. 自定义安装 选2
    2. 输入指定toolchain x86_64-pc-windows-gnu
    3. 其他的默认就好

如果已经装过了，可以通过rustup default 查看默认toolchain，

通过 rustup default stable-x86_64-pc-windows-gnu 修改默认toolchain.

结束.

0x2 Rust工程目录简述

主要目录

D:\RustProject\LeetCode
├─src // 源码目录
│ ├─problem_0164_maximum_gap // 每个算法问题目录

│ │ ├─mod.rs // 模块声明 or 模块接口

│ │ ├─buckets_and_pigeonhole.rs // 解法1

│ │ └─solve2.rs // 解法2

│ ├─problem_0372_super_pow
│ ├─…
│ ├─problem_xxxx_k_radius_subarray_averages

│ └─main.rs

├─target // 编译生成目录
│ └─…

├─Cargo.toml // cargo 配置文件

└─README.md // 如果设置git同步到远端的话，写一个简单的仓库说明

解题工作流

以算法题目0164 maximum_gap为例：

leetcode-cn 网站上给的Rust模板为：

impl Solution {
    pub fn maximum_gap(nums: Vec<i32>) -> i32 {
        
    }
}
  1. 我们在src目录创建子目录problem_0164_maximum_gap

​ 遵从 problem_id_title 的格式，我这里的问题编号是从leetcode-cn.com上取的，不是主站 leetcode.com.

  1. 在 main.rs 中调用当前模块

将你当前调试的模块导入到main.rs中，以problem_0164_maximum_gap 为例：

// mod problem_xxxx_xxxxxx; 
mod problem_0164_maximum_gap;
// other problem
fn main() {
    println!("[+]main.rs| Compile Success");
}

导入的目的是让Clion在你写子模块的时候进行代码分析，帮你自动补全.

注意，调试完的模块就注释掉防止使用 cargo test 测试时测试到不需要的模块.

  1. 在子目录创建文件 mod.rs ，将测试输入写在这个文件中

mod.rs

pub mod buckets_and_pigeonhole; // 解法1
pub mod solve2; // 解法2

pub trait Solution {
    fn maximum_gap(nums: Vec<i32>) -> i32;
}

#[cfg(test)]
mod tests {
    use super::Solution;

    pub fn run<S: Solution>() {
        let test_cases = [
            (&[3, 6, 9, 1] as &[_], 3),
            (&[10], 0),
            (&[1, 3, 100], 97),
            (&[1, 1, 1, 1], 0),
            (&[1, 11], 10),
            (&[1, 1, 1, 1, 1, 5, 5, 5, 5, 5], 4),
        ];

        for (nums, expected) in test_cases {
            assert_eq!(S::maximum_gap(nums.to_vec()), expected);
        }
    }
}

上述代码中定义了名为Solution的trait，规定了我们在写具体的算法的时候必须实现的函数接口.

最上面的buckets_and_pigeonhole和solve2是我们写的具体算法的文件名.

#[cfg(test)] 注解下是我们写的测试代码，其中test_cases变量中保存了我们的测试样例，每条样例中包括输入和预期输出.

测试算法时就通过 cargo test 即可测试这些样例.

  1. 具体算法实现

在相应的问题文件夹下创建rust文件求解，以 buckets_and_pigeonhole.rs 为例：

pub struct Solution;

impl Solution {
    pub fn maximum_gap(nums: Vec<i32>) -> i32 {
        let mut result = 0;
        let maybe_min_value = nums.iter().copied().min();
        let maybe_max_value = nums.iter().copied().max();

        if maybe_min_value != maybe_max_value {
            let min_value = maybe_min_value.unwrap();
            let max_value = maybe_max_value.unwrap();
            let length = max_value - min_value;

            // The maximum gap must be greater than or equal to length / (n - 1), so as long as the bucket size is less
            // than length / (n - 1) + 1, the maximum gap can not be inside one bucket. So we only need to check gaps
            // between buckets.

            let bucket_size = {
                let n = nums.len() as i32;

                (length + n - 2) / (n - 1)
            };

            let mut buckets = vec![(-1, 0); (length / bucket_size + 1) as _];

            for num in nums {
                let (left, right) = &mut buckets[((num - min_value) / bucket_size) as usize];

                if *left == -1 {
                    *left = num;
                    *right = num;
                } else if num < *left {
                    *left = num;
                } else if num > *right {
                    *right = num;
                }
            }

            let mut bucket_iter = buckets.into_iter().filter(|(left, _)| *left != -1);
            let mut previous = bucket_iter.next().unwrap().1;

            for (left, right) in bucket_iter {
                result = result.max(left - previous);

                previous = right;
            }
        }

        result
    }
}

// ------------------------------------------------------ snip ------------------------------------------------------ //

impl super::Solution for Solution {
    fn maximum_gap(nums: Vec<i32>) -> i32 {
        Self::maximum_gap(nums)
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn test_solution() {
        super::super::tests::run::<super::Solution>();
    }
}

snip注释下面的代码是为了将当前的Solution方法作为mod.rs中trait的实现，用于测试.

使用Clion做测试调试时，可以通过下图debug按钮调试：

image-20220325161519397

0x3 Git同步

如有需要，将除了target目录以外的文件夹加入git，同步到远端，这样就可以在多台设备上优雅的同步代码了.

0x4 其他

在大哥的代码库中包含了:

mod data_structures;
mod test_utilities;

这两个模块，和main.rs同级目录，其作用是一些比较重要的且rust标准库不提供的数据结构，还有一些测试用的函数，在某些问题中你可能需要用到这些.

此外，他还配置了一些github action用于自动化编译和生成展示网页：LeetCode Progress Report (efanzh.org)

对于我这样的新手就没什么用，所以也不需要配置了.

Ref：

https://github.com/EFanZh/LeetCode 快给大哥一个Star

https://github.com/Ch3nYe/LeetCode 也可以给我一个Star 😘