leetcode

Solve questions in leetcode by Rust

前言

由于 Rust 写数据结构相关的资料特别少并且理解非常困难，所以专门建了个 Repo 用来记录 Rust 刷 leetcode 的解法并包含心得体会，欢迎 Star ✨ 会长期稳定更新。
努力写出最容易理解的 Rust 代码。 https://github.com/zhangyuang/leetcode

注: 以下代码并没有刻意追求最优解，主要目的在于熟悉 Rust 语法以及使用可读性强便于理解的代码来解决问题。欢迎 Star✨ 长期稳定保持更新。

debug in VSCode

建议本地编码时使用 VSCode 自带的 lldb 调试功能来进行断点调试，提升开发效率

// setting.json
{
  "version": "0.2.0",
  "configurations": [
    {
      "type": "lldb",
      "request": "launch",
      "name": "Debug",
      "args": [],
      "cwd": "${workspaceFolder}",
      "cargo": {
        "args": [
          "test",
          "--manifest-path=.test_repo/Cargo.toml"
        ],
        "filter": {
          "name": "leetcodebyrust",
          "kind": "lib"
        }
      },
    }
  ]
}

F5/Fn+F5 启动调试

lldb 调试 Rust

我们通过 lldb 来调试 Rust 代码，同样我们会经常需要在 Debug Console 中打印出当前的一些变量值。这里需要特殊配置，根据 VScode LLDB 文档描述 Debug Console 提供两种执行模式。分别是以 lldb commands 模式执行，或者 expressions 表达式的形式执行。

当我们需要进行表达式求值时需要在前面加上 ? 符号。例如 ?foo 打印 foo 的值。

也可以通过 settings.json 中配置 "lldb.consoleMode": "evaluate" 默认启用 evaluate 模式，不再需要输入 ? 符号。此时调用 lldb commands 需要添加 /cmd 开头

分类

链表(linkedList)
二叉树(binaryTree)
动态规划(dynamic programing)
HOT100 🔥

linkedList

链表

Rust 解链表题思路

Go 程序员已经下班 Cpp 程序员还在打断点 Rust 程序员还在编译

Rust 解决数据结构问题相比于其他语言十分的困难，就在于变量所有权的 move(转移)与 borrow(借用)。

遍历链表

通常使用可变引用来遍历, 注意这里需要对 Option<Box<ListNode>> struct 使用 as_ref 或者 as_mut 来进行引用遍历。根据官方文档的解释，我们可以看出 as_ref/as_mut 在这里的作用是 Converts from &Option<T> to Option<&T>。

let mut root = &mut head;
while let Some(node) = root {
  let next_node = &mut node.next;
  // 使用as_mut获取next_node的引用，使用&mut获取.next的引用。以此来获取root下一个节点的下一个节点的引用。直接使用unwrap会导致所有权的move
  let next_node_next = &mut next_node.as_mut()?.next;
  // 这里面不能再直接使用head，因为head的所有权已经借给了root，在循环体中未归还
  // other code...
  root = &mut node.next;
}

写法二

while head.as_mut()?.next.is_some() {
    head = &mut head.as_mut()?.next;
}

转移获取链表节点所有权

take 方法使用方式见文档
Copy 以及 Clone 的区别可查看该文章

// 因为next为Box智能指针存储在堆上的节点，不具备Copy属性，无法直接从堆上转移数据否则会造成多次释放的问题。使用take方法将所有权转移出去，并且在原位置留下了None。
let next_node = node.next.take();

树

Rust 解决树题思路

共享树节点

这里我们尽量不使用 clone 或者 take 来重复获取树节点的所有权，这样会导致性能低下以及影响入参树的数据结构, 这里我们使用 Rc::clone

let root_borrow = root.as_ref().unwrap().borrow();
let left = if root_borrow.left.is_some() {
    Some(Rc::clone(root_borrow.left.as_ref().unwrap()))
} else {
    None
};
let right = if root_borrow.right.is_some() {
    Some(Rc::clone(root_borrow.right.as_ref().unwrap()))
} else {
    None
};

解题代码

皆通过 leetcode 测试用例，可直接粘贴到 leetcode 编辑器中调试，刷题建议由浅入深，按知识点来刷,不要左右横跳。

Easy

简单难度的链表题

Medium

中等难度的链表题

Tree

树，二叉树

解题思路

Rust 构造树需要使用 Rc引用计数智能指针以及 RefCell，使得一个数据具有多个可变的所有者。因为一个子节点可能被多个父节点所共享。

Easy

简单难度的树题二叉搜索树解题思路：中序遍历的结果是递增数组

Medium

中等难度的树题

Hard

二叉树后序遍历|postorder_traversal

DynamicPrograming

动态规划

Rust 解动态规划题思路

主要思路与其他语言类似。还是通过寻找状态转移方程(递推关系)，通常要使用 vec 来保存之前的结果来提升性能。常用到的空间优化方式有滚动数组，来将二维数组压成一维或减少数组空间大小。大部分情况都是背包问题(01背包，完全背包，多重背包)问题的变种。学习资料: liweiwei leetcode 经典动规解析