Repository files navigation

Solve questions inleetcode by Rust

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

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

官方 API 文档
Rust 程序设计语言中文版

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

链表

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

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

通常使用可变引用来遍历

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

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

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

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

简单难度的链表题

回文链表|is_palindrome
反转链表|reverse_list
链表的中间节点|middle_node
删除链表节点|delete_node
删除链表重复节点|delete_duplicates

中等难度的链表题

两数相加|add_two_numbers
两两交换链表中的节点|swap_pairs
删除链表的倒数第 N 个节点|remove_nth_from_end

树，二叉树

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

中等难度的树题

二叉树前序遍历|preorder_traversal
二叉树中序遍历|inorder_traversal
二叉树层次遍历|level_order
二叉树展开为链表|flatten
不同的二叉搜索树|num_trees
验证二叉搜索树|is_valid_bst

二叉树后序遍历|postorder_traversal

动态规划

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

简单难度的动态规划题

爬楼梯|climb_stairs
三步问题|ways_to_step
连续数列|max_sub_array
按摩师|massage
打家劫舍|rob
使用最小花费爬楼梯|min_cost_climbing_stairs
买卖股票的最佳时机|max_profit
最长连续递增序列|find_length_of_lcis

中等难度的动态规划题

最长上升子序列|length_of_lis
最长递增子序列的个数|find_number_of_lis
最小路径和|min_path_sum
最长回文子串|longest_palindrome
打家劫舍 II|robs
打家劫舍 III|robs

Hot100类型题

简单难度的HOT100题

柠檬水找零|lemonade_change
找到所有数组中消失的数字|find_disappeared_numbers
最短无序连续子数组|find_unsorted_subarray
字符串相加|add_strings

中等难度的HOT100题

除自身以外数组的乘积|product_except_self
分割等和子集|can_partition
全排列|permute
括号生成|generate_parenthesis
子集|subsets
零钱兑换|coin_change
不同路径|unique_paths
单词搜索|exist
单词拆分|word_break
无重复字符的最长子串|length_of_longest_substring
课程表|can_finish

困难难度的Hot100题目

接雨水|trap

其他分类的题目集合

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面|exchange

记录周赛题目

第 k 个缺失的正整数|find_kth_positive
K 次操作转变字符串|can_convert_string