Solve questions in leetcode by Rust
由于 Rust 写数据结构相关的资料特别少并且理解非常困难,所以专门建了个 Repo 用来记录 Rust 刷 leetcode 的解法并包含心得体会,欢迎 Star✨ 会长期稳定更新。 努力写出最容易理解的 Rust 代码。 https://github.com/zhangyuang/leetcode
注: 以下代码并没有刻意追求最优解,主要目的在于熟悉 Rust 语法以及使用可读性强便于理解的代码来解决问题。欢迎 Star✨ 长期稳定保持更新。
建议本地编码时使用 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
代码,同样我们会经常需要在 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🔥
链表
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;
}
// 因为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 编辑器中调试,刷题建议由浅入深,按知识点来刷,不要左右横跳。
简单难度的链表题
回文链表|is_palindrome 反转链表|reverse_list 链表的中间节点|middle_node 删除链表节点|delete_node 删除链表重复节点|delete_duplicates
中等难度的链表题
两数相加|add_two_numbers 两两交换链表中的节点|swap_pairs 删除链表的倒数第 N 个节点|remove_nth_from_end 合并两个链表|merge_in_between 旋转链表|rotate_right 从链表中删去总和值为零的连续节点|remove_zero_sum_sublists 链表中的下一个更大节点|next_larger_nodes 删除链表重复节点 2|delete_duplicate
树,二叉树
Rust 构造树需要使用 Rc引用计数智能指针以及 RefCell,使得一个数据具有多个可变的所有者。因为一个子节点可能被多个父节点所共享。
简单难度的树题 二叉搜索树解题思路:中序遍历的结果是递增数组
二叉树的层次遍历 II|level_order_bottom 二叉树的层平均值|average_of_levels 相同的树|is_symmetric 对称二叉树|is_same_tree 平衡二叉树|is_balanced 二叉树的所有路径|binary_tree_paths 二叉树的最小深度|min_depth 左叶子之和|sum_of_left_leaves 二叉搜索树中的众数|find_mode 二叉搜索树中的搜索|search_bst 二叉搜索树的第 k 大节点|kth_largest 二叉搜索树的范围和|range_sum_bst 二叉搜索树节点最小距离|min_diff_in_bst 把二叉搜索树转换为累加树|convert_bst 将有序数组转换为二叉搜索树|sorted_array_to_bst 另一个树的子树|is_subtree 叶子相似的树|leaf_similar 563 二叉树的坡度
中等难度的树题
二叉树前序遍历|preorder_traversal 二叉树中序遍历|inorder_traversal 二叉树层次遍历|level_order 二叉树展开为链表|flatten 不同的二叉搜索树|num_trees 验证二叉搜索树|is_valid_bst 二叉树的锯齿形层次遍历|zigzag_level_order 最长同值路径|longest_univalue_path 前缀树|Trie 从前序与中序遍历序列构造二叉树|build_tree 根据前序和后序遍历构造二叉树|construct_from_pre_post 最大二叉树|construct_maximum_binary_tree 完全二叉树的节点个数|count_nodes
动态规划
主要思路与其他语言类似。还是通过寻找状态转移方程(递推关系),通常要使用 vec 来保存之前的结果来提升性能。 常用到的空间优化方式有滚动数组,来将二维数组压成一维或减少数组空间大小。大部分情况都是背包问题(01背包,完全背包,多重背包)问题的变种。 学习资料: liweiwei leetcode 经典动规解析
简单难度的动态规划题
爬楼梯|climb_stairs 三步问题|ways_to_step 连续数列|max_sub_array 按摩师|massage 打家劫舍|rob 使用最小花费爬楼梯|min_cost_climbing_stairs 买卖股票的最佳时机|max_profit 最长连续递增序列|find_length_of_lcis 区域和检索 - 数组不可变|NumArray 有序数组的平方|sorted_squares 509 斐波那契数
中等难度的动态规划题
最长上升子序列|length_of_lis 最长递增子序列的个数|find_number_of_lis 最小路径和|min_path_sum 最长回文子串|longest_palindrome 打家劫舍 II|robs 打家劫舍 III|robs 不同路径 II|unique_paths_with_obstacles 二维区域和检索 - 矩阵不可变|NumMatrix 完全平方数|num_squares 55跳跃游戏 45跳跃游戏|| 413等差数列划分 221最大正方形
Hot100类型题
简单难度的HOT100题
柠檬水找零|lemonade_change 找到所有数组中消失的数字|find_disappeared_numbers 最短无序连续子数组|find_unsorted_subarray 字符串相加|add_strings 二分查找|binary_search 第一个错误的版本|first_bad_version
中等难度的HOT100题
除自身以外数组的乘积|product_except_self 分割等和子集|can_partition 全排列|permute 括号生成|generate_parenthesis 子集|subsets 零钱兑换|coin_change 不同路径|unique_paths 单词搜索|exist 单词拆分|word_break 无重复字符的最长子串|length_of_longest_substring 课程表|can_finish 在排序数组中查找元素的第一个和最后一个位置|search_range
困难难度的Hot100题目
其他分类的题目集合
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面|exchange 用栈实现队列|MyQueue 用队列实现栈|MyStack 最小栈|MinStack 用栈操作构建数组|build_array 判断子序列|is_subsequence 821 字符的最短距离 997 找到小镇的法官 118 杨辉三角
807 保持城市天际线 11 盛最多水的容器 475 供暖器 390 消除游戏 334 递增的三元子序列 373 查找和最小的K对数字
缺失的第一个正数|first_missing_positive
记录周赛题目