数据结构与算法 - Rust 语言实现
第一部分: 数据结构 Data Structures
1.
数组 Arrays
❱
1.1.
数组的基本操作
1.2.
反转数组
1.3.
旋转数组
1.4.
前缀和数组 Prefix Sum Array
1.5.
后缀数组 Suffix Array
2.
矩阵 Matrix
❱
2.1.
矩阵的常用操作
2.2.
稀疏矩阵
❱
2.2.1.
数组 Array
2.2.2.
链表 Linked List
2.2.3.
List of Lists
2.2.4.
十字链表 Orthogonal Linked List
2.2.5.
BTree
3.
动态数组 Vector
❱
3.1.
动态数组的常用操作
3.2.
标准库中 Vec 的实现
3.3.
位图 BitSet
3.4.
布隆过滤器 Bloom filter
3.5.
Hashed Array Tree
4.
字符串 String
❱
4.1.
字符串编码
4.2.
字符串的常用操作
5.
链表 List
❱
5.1.
链表的类型
5.2.
链表的基本操作
5.3.
单链表
5.4.
双链表
5.5.
环状双链表
5.6.
Header Linked List
5.7.
Unrolled Linked List
5.8.
List of Lists
5.9.
多层链表 Multi-level Linked List
5.10.
跳跃表 Skip List
❱
5.10.1.
跳跃表的基本操作
5.10.2.
跳跃表的实现
5.10.3.
跳跃表的应用
6.
栈 Stack
❱
6.1.
栈的基本操作
6.2.
栈的实现
6.3.
栈的应用
6.4.
单调栈 Monotonic stack
7.
队列 Queue
❱
7.1.
队列的分类
7.2.
队列的基本操作
7.3.
实现简单队列
7.4.
环形缓冲区 Circular Buffer
7.5.
单调队列 Monotonic queue
8.
双端队列 Deque
❱
8.1.
双端队列的基本操作
8.2.
双端队列的实现
8.3.
标准库中 VecDeque 的实现
9.
哈稀表 Hash Table
❱
9.1.
标准库中 HashMap 的实现
9.2.
标准库中 HashSet 的实现
9.3.
LinkedHashMap
10.
树 Tree
❱
10.1.
二叉树
❱
10.1.1.
二叉树的线性存储结构
10.1.2.
二叉树的链式存储结构
10.1.3.
二叉树的遍历 Traversal
10.1.4.
二叉树的前序遍历
10.1.5.
二叉树的中序遍历
10.1.6.
二叉树的后序遍历
10.1.7.
二叉树的层序遍历
10.2.
二叉搜索树 Binary Search Tree
❱
10.2.1.
平衡二叉树 Optimal BST
10.3.
AVL树
10.4.
Splay Tree
10.5.
红黑树 Red-Black Tree
10.6.
Left-leaning Red–Black Tree
10.7.
多叉树
10.8.
B-Tree
10.9.
B+-Tree
10.10.
B*-Tree
10.11.
T-tree
10.12.
LSM Tree
10.13.
Fractal tree
10.14.
标准库中 BTreeMap 的实现
10.15.
字典树 Trie
❱
10.15.1.
Radix Tree
10.15.2.
Suffix Tree
10.16.
地理空间分区 Spatial Data Partitioning Trees
❱
10.16.1.
R-tree
10.16.2.
Priority R-tree
10.16.3.
R* tree
10.16.4.
R+ tree
10.16.5.
X-tree
10.16.6.
k-d Tree
11.
优先级队列 Priority Queue (Heap)
❱
11.1.
Binary Heap
11.2.
双优先级队列 Dual Priority Queue
11.3.
Skew Heap
11.4.
Binomial Heap
11.5.
Brodal Queue
11.6.
Fibonacci Heap
11.7.
Strict Fibonacci Heap
11.8.
标准库中 Binary Heap 的实现
12.
图 Graph
❱
12.1.
深度优先搜索 DFS
12.2.
广度优先搜索 BFS
12.3.
最短路径
12.4.
最小生成树
13.
并发数据结构 Concurrent Data Structures
❱
13.1.
简介
13.2.
Lock-coupling Linked List
13.3.
Concurrent Ring Buffer
13.4.
Concurrent Hash Map
13.5.
Concurrent Linked List
13.6.
Concurrent Deque
13.7.
Concurrent Queue
13.8.
Concurrent SkipList Map
13.9.
Concurrent SkipList Set
13.10.
Concurrent Radix Tree
13.11.
Skip Graph
第二部分: 算法 Algorithms
14.
算法分析 Analysis
❱
14.1.
测试用的数据集
15.
排序 Sorting
❱
15.1.
冒泡排序 Bubble sort
15.2.
插入排序 Insertion sort
15.3.
选择排序 Selection sort
15.4.
归并排序 Merge sort
15.5.
Timsort
15.6.
快速排序 Quicksort
15.7.
堆排序 Heap Sort
15.8.
IntroSort
15.9.
pdqsort
15.10.
希尔排序 Shell Sort
15.11.
侏儒排序 Gnome Sort
15.12.
桶排序 Bucket sort
15.13.
基数排序 Radix Sort
15.14.
计数排序 Counting Sort
15.15.
标准库中排序算法的实现
16.
链表排序 List Sort
❱
16.1.
冒泡排序 Bubble Sort
16.2.
插入排序 Insertion Sort
16.3.
选择排序 Selection Sort
16.4.
归并排序 Merge Sort
16.5.
快速排序 Quicksort
17.
外部排序 External Sorting
❱
17.1.
Multiway Merge
17.2.
Polyphase Merge
17.3.
Distribution Sort
17.4.
Cache-oblivious Distribution Sort
18.
查找 Search
❱
18.1.
线性查找 Linear Search
18.2.
二分查找 Binary Search
18.3.
二分查找相关的问题列表
18.4.
三元查找 Ternary Search
18.5.
Jump Search
18.6.
Interpolation Search
18.7.
Exponential Search
18.8.
标准库中二分查找法的实现
19.
位运算 Bit Manipulation
❱
19.1.
对自己异或操作结果为0
20.
递归 Recursion
21.
数学 Math
❱
21.1.
排列与组合
21.2.
矩阵 Matrix
21.3.
质数
21.4.
数独
21.5.
任意精度算术运算
22.
双指针 Two Pointers
❱
22.1.
快慢型双指针
22.2.
靠拢型双指针
22.3.
并行双指针
23.
滑动窗口 Sliding Window
24.
回溯法 Backtracking
25.
分治法 Divide and Conquer
26.
动态规划 Dynamic Programming
27.
贪心算法 Greedy
28.
图算法 Graph
第三部分: 专题 Special
29.
内存 Memory
30.
缓存过期算法 Cache Management
❱
30.1.
倒计时 TTL
30.2.
最近最少使用 LRU
30.3.
最近最不频繁使用 LFU
31.
限流算法 Rate limiter
❱
31.1.
令牌桶 Token bucket
31.2.
漏桶算法 Leaking bucket
31.3.
固定窗口计数 Fixed window counter
31.4.
滑动窗口日志 Sliding window log
31.5.
滑动窗口计数 Sliding window counter
第四部分: leetcode 题解
32.
leetcode 问题分类
❱
32.1.
数组 Array
❱
32.1.1.
矩阵 Matrix
32.1.2.
前缀和 Prefix Sum
32.1.3.
双指针 Two Pointers
32.1.4.
滑动窗口 Sliding Window
32.1.5.
二分查找 Binary Search
32.1.6.
排序 Sorting
32.2.
链表 Linked List
❱
32.2.1.
链表排序 Sorting
32.2.2.
链表双指针 Two Pointers
32.3.
队列 Queue
❱
32.3.1.
单调队列 Monotonic Queue
32.4.
栈 Stack
❱
32.4.1.
单调栈 Monotonic Stack
32.5.
优先级队列 Priority Queue
32.6.
哈稀表 Hash Table
32.7.
字符串 String
❱
32.7.1.
字符串匹配 String Matching
32.7.2.
字典树 Trie
32.8.
树 Tree
❱
32.8.1.
二叉树的遍历 Traversal
32.8.2.
二叉树的还原 Restore
32.8.3.
二叉搜索树 Binary Search Tree
32.8.4.
二叉索引树 Binary Indexed Tree
32.8.5.
线段树 Segment Tree
32.8.6.
并查集 Union-Find Data Structure
32.9.
图 Graph
❱
32.9.1.
最小生成树 Minimum Spanning Tree
32.10.
递归 Recursion
32.11.
位运算 Bit Manipulation
32.12.
数学 Math
32.13.
回溯法 Backtracking
32.14.
分治法 Divide and Conquer
32.15.
深度优先搜索 DFS
32.16.
广度优先搜索 BFS
32.17.
动态规划 Dynamic Programming
32.18.
贪心算法 Greedy
33.
leetcode 题解
❱
33.1.
0001-0100
❱
33.1.1.
0001. 两数之和 Two Sum
33.1.2.
0002. 两数相加 Add Two Numbers
33.1.3.
0003. 无重复字符的最长子串 Longest Substring Without Repeating Characters
33.1.4.
0004. 寻找两个正序数组的中位数 Median of Two Sorted Arrays
33.1.5.
0005. 最长回文子串 Longest Palindromic Substring
33.1.6.
0007. 整数反转 Reverse Integer
33.1.7.
0011. 盛最多水的容器 Container With Most Water
33.1.8.
0012. 整数转罗马数字 Integer to Roman
33.1.9.
0013. 罗马数字转整数 Roman to Integer
33.1.10.
0015. 三数之和 3Sum
33.1.11.
0016. 最接近的三数之和 3Sum Closest
33.1.12.
0020. 有效的括号 Valid Parentheses
33.1.13.
0021.合并两个有序链表 Merge Two Sorted Lists
33.1.14.
0026. 删除有序数组中的重复项 Remove Duplicates from Sorted Array
33.1.15.
0031. 下一个排列 Next Permutation
33.1.16.
0034. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array
33.1.17.
0035. 搜索插入位置 Search Insert Position
33.1.18.
0039.组合总和 Combination Sum
33.1.19.
0040. 组合总和 II Combination Sum II
33.1.20.
0042. 接雨水 Trapping Rain Water
33.1.21.
0046. 全排列 Permutations
33.1.22.
0047. 全排列 II Permutations II
33.1.23.
0056. 合并区间 Merge Intervals
33.1.24.
0062. 不同路径 Unique Paths
33.1.25.
0066. 加一 Plus One
33.1.26.
0067. 二进制求和 Add Binary
33.1.27.
0069. x 的平方根 Sqrt(x)
33.1.28.
0071.简化路径 Simplify Path
33.1.29.
0074. 搜索二维矩阵 Search a 2D Matrix
33.1.30.
0075. 颜色分类 Sort Colors
33.1.31.
0078. 子集 Subsets
33.1.32.
0080. 删除排序数组中的重复项 II Remove Duplicates from Sorted Array II
33.1.33.
0082. 删除排序链表中的重复元素 II Remove Duplicates from Sorted List II
33.1.34.
0083. 删除排序链表中的重复元素 Remove Duplicates from Sorted List
33.1.35.
0088. 合并两个有序数组 Merge Sorted Array
33.1.36.
0090. 子集 II Subsets II
33.2.
0101-0200
❱
33.2.1.
0125. 验证回文串 Valid Palindrome
33.2.2.
0136. 只出现一次的数字 Single Number
33.2.3.
0137. 只出现一次的数字II Single Number II
33.2.4.
0150. 逆波兰表达式求值 Evaluate Reverse Polish Notation
33.2.5.
0153. 寻找旋转排序数组中的最小值 Find Minimum in Rotated Sorted Array
33.2.6.
0154. 寻找旋转排序数组中的最小值 II Find Minimum in Rotated Sorted Array II
33.2.7.
0155. 最小栈 Min Stack
33.2.8.
0162. 寻找峰值 Find Peak Element
33.2.9.
0167. 两数之和 II - 输入有序数组 Two Sum II - Input Array Is Sorted
33.2.10.
0189. 旋转数组 Rotate Array
33.2.11.
0191. 位1的个数 Number of 1 Bits
33.3.
0201-0300
❱
33.3.1.
0217. 存在重复元素 Contains Duplicate
33.3.2.
0219. 存在重复元素II Contains Duplicate II
33.3.3.
0231. 2的幂 Power of Two
33.3.4.
0234. 回文链表 Palindrome Linked List
33.3.5.
0238. 除自身以外数组的乘积 Product of Array Except Self
33.3.6.
0240. Search a 2D Matrix II Search a 2D Matrix II
33.3.7.
0278. 第一个错误的版本
33.3.8.
0287. 寻找重复数 Find the Duplicate Number
33.4.
0301-0400
❱
33.4.1.
0303. 区域和检索 - 数组不可变 Range Sum Query - Immutable
33.4.2.
0322. 零钱兑换 Coin Change
33.4.3.
0326. 3的幂 Power of Three
33.4.4.
0338. 比特位计数 Counting Bits
33.4.5.
0342. 4的幂 Power of Four
33.4.6.
0347. 前 K 个高频元素 Top K Frequent Elements
33.4.7.
0349. 两个数组的交集 Intersection of Two Arrays
33.4.8.
0350. 两个数组的交集 II Intersection of Two Arrays II
33.4.9.
0374. 猜数字大小 Guess Number Higher or Lower
33.4.10.
0394. 字符串解码 Decode String
33.5.
0401-0500
❱
33.5.1.
0463. 岛屿的周长 Island Perimeter
33.5.2.
0468. 验证IP地址 Validate IP Address
33.5.3.
0485. 最大连续1的个数 Max Consecutive Ones
33.5.4.
0496. 下一个更大元素 I Next Greater Element I
33.6.
0501-0600
❱
33.6.1.
0532.数组中的数对 K-diff Pairs in an Array
33.7.
0601-0700
❱
33.7.1.
0679. 24 点游戏 24 Game
33.7.2.
0680. 验证回文串 II Valid Palindrome II
33.8.
0701-0800
❱
33.8.1.
0704. 二分查找 Binary Search
33.8.2.
0707. 设计链表 Design Linked List
33.8.3.
0724. 寻找数组的中心下标 Find Pivot Index
33.8.4.
0739. 每日温度 Daily Temperatures
33.8.5.
0744. 寻找比目标字母大的最小字母 Find Smallest Letter Greater Than Target
33.9.
0801-0900
❱
33.9.1.
0852. 山脉数组的峰顶索引 Peak Index in a Mountain Array
33.10.
0901-1000
❱
33.10.1.
0925. 长按键入 Long Pressed Name
33.10.2.
0977. 有序数组的平方 Squares of a Sorted Array
33.11.
1001-1100
❱
33.11.1.
1004. 最大连续1的个数 III Max Consecutive Ones III
33.12.
1101-1200
33.13.
1201-1300
33.14.
1301-1400
33.15.
1401-1500
❱
33.15.1.
1422. 分割字符串的最大得分 Maximum Score After Splitting a String
33.15.2.
1480. 一维数组的动态和 Running Sum of 1d Array
33.15.3.
1498. 满足条件的子序列数目 Number of Subsequences That Satisfy the Given Sum Condition
33.16.
1501-1600
❱
33.16.1.
1518. 换水问题 Water Bottles
33.17.
1601-1700
33.18.
1701-1800
❱
33.18.1.
1732. 找到最高海拔 Find the Highest Altitude
33.18.2.
1780. 判断一个数字是否可以表示成三的幂的和 Check if Number is a Sum of Powers of Three
33.19.
1801-1900
❱
33.19.1.
1854. 人口最多的年份 Maximum Population Year
33.19.2.
1893. 检查是否区域内所有整数都被覆盖 Check if All the Integers in a Range Are Covered
33.20.
1901-2000
❱
33.20.1.
1991. 找到数组的中间位置 Find the Middle Index in Array
33.21.
2101-2200
❱
33.21.1.
2108. 找出数组中的第一个回文字符串 Find First Palindromic String in the Array
33.21.2.
2119. 反转两次的数字 A Number After a Double Reversal
33.22.
2401-2500
❱
33.22.1.
2485. 找出中枢整数 Find the Pivot Integer
33.23.
2501-2600
❱
33.23.1.
2574. 左右元素和的差值 Left and Right Sum Differences
33.24.
2801-2900
❱
33.24.1.
2848. 与车相交的点 Points That Intersect With Cars
33.25.
3001-3100
❱
33.25.1.
3028. 边界上的蚂蚁 Ant on the Boundary
第五部分: 华为 OD 机试题解
34.
OD 2024年E卷100分
❱
34.1.
流浪地球
34.2.
斗地主之顺子
34.3.
数大雁
34.4.
最大利润/贪心的商人 - 贪心算法
34.5.
boss的收入 - 递归
34.6.
猜字谜 - 字符串
34.7.
猜数字
34.8.
最大报酬 - 背包问题
34.9.
分糖果 - 位运算
34.10.
日志采集系统 - 动态规划
34.11.
最左侧冗余覆盖子串 - 滑动窗口
34.12.
增强的strstr - 字符串
34.13.
报文响应时间 - 字符串
34.14.
连续字母长度 - 字符串
34.15.
最长连续子序列 - 滑动窗口
34.16.
计算面积/绘图机器
34.17.
敏感字段加密 - 字符串
34.18.
出租车计费/靠谱的车 - 数学
34.19.
分苹果 - 位运算
34.20.
字符串变换最小字符串 - 贪心算法
34.21.
字符串分割转换 - 字符串
34.22.
简单的自动曝光/平均像素值
34.23.
计算三叉搜索树的高度 - 树
34.24.
补种未成活胡杨 - 滑动窗口
34.25.
最小的调整次数/特异性双端队列
34.26.
查找充电设备组合 - 动态规划
34.27.
智能成绩表 - 排序
34.28.
虚拟理财游戏 - 栈
34.29.
手机App防沉迷系统 - 排序
34.30.
构成正方形的数量
34.31.
单词接龙 - 字符串
34.32.
跳房子I
34.33.
第k个排列 - 排列组合
34.34.
喊7的次数重排
34.35.
英文输入法 - 字符串
34.36.
高矮个子排队 - 滑动窗口
34.37.
考勤信息
34.38.
找终点
34.39.
数组拼接 - 字符串
34.40.
整数对最小和
34.41.
环中最长子串/字符成环找偶数O - 字符串
34.42.
找数字/找等值元素
34.43.
光伏场地建设规划 - 前缀和
34.44.
We Are A Team - 并查集
34.45.
生成哈夫曼树 - 树
34.46.
内存资源分配 - 贪心
34.47.
矩形相交的面积 - 数学
34.48.
水仙花数I - 数学
34.49.
不等式是否满足约束并输出最大差
34.50.
字符统计及重排 - 字符串
34.51.
VLAN资源池
35.
OD 2024年E卷200分
❱
35.1.
空栈压数
35.2.
工号不够用了怎么办 - 数学
35.3.
最长连续方波信号 - 栈
35.4.
计算疫情扩散时间 - 图
35.5.
字符串化繁为简 - 字符串
35.6.
通过软盘拷贝文件 - 动态规划
35.7.
跳马 - BFS
35.8.
字母组合/过滤组合字符串 - 字符串
35.9.
最大社交距离
35.10.
模拟目录管理
35.11.
找单词 - DFS
35.12.
导师请吃火锅 - DFS
35.13.
最大相连男生数/学生方阵
35.14.
数字游戏
35.15.
云短信平台优惠活动 - DP
35.16.
寻找符合要求的最长子串 - 滑动窗口
35.17.
跳格子3 - 动态规划
35.18.
二叉树计算 - 树
35.19.
猴子吃桃/爱吃蟠桃的孙悟空 - 二分查找
35.20.
机器人活动区域 - DFS
35.21.
简易压缩算法/一种字符串压缩表示的解压 - 字符串
35.22.
智能驾驶 - 二分查找
35.23.
字符串拼接 - 字符串
35.24.
项目排期 - DFS
35.25.
文本统计分析
35.26.
电脑病毒感染 - 图
35.27.
周末爬山 - DFS
35.28.
计算网络信号/信号强度 - BFS
35.29.
九宫格按键输入
35.30.
服务器广播/需要广播的服务器数量 - 并查集
参考资料
Light
Rust
Coal
Navy
Ayu
数据结构与算法 - Rust 语言实现
环状双链表
与上文提到的双链表相比, 环状双向链表只是连接了链表的头部节点和尾部节点, 其它操作都差不多.
其结构如下图所示:
算法实现
