Skip to content

Commit bbd0f3a

Browse files
coderonioncoderonion
committed
update rust codes
1 parent 85881b0 commit bbd0f3a

File tree

11 files changed

+517
-4
lines changed

11 files changed

+517
-4
lines changed

‎rust/.gitignore

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
target/
2+
Cargo.lock

‎rust/Cargo.toml

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
[package]
2+
name = "hello-algo-rust"
3+
version = "0.1.0"
4+
edition = "2021"
5+
6+
[lib]
7+
name = "inc"
8+
path = "include/include.rs"
9+
10+
# Run Command: cargo run --bin time_complexity
11+
[[bin]]
12+
name = "time_complexity"
13+
path = "chapter_computational_complexity/time_complexity.rs"
14+
15+
# Run Command: cargo run --bin worst_best_time_complexity
16+
[[bin]]
17+
name = "worst_best_time_complexity"
18+
path = "chapter_computational_complexity/worst_best_time_complexity.rs"
19+
20+
# Run Command: cargo run --bin leetcode_two_sum
21+
[[bin]]
22+
name = "leetcode_two_sum"
23+
path = "chapter_computational_complexity/leetcode_two_sum.rs"
24+
25+
# Run Command: cargo run --bin array
26+
[[bin]]
27+
name = "array"
28+
path = "chapter_array_and_linkedlist/array.rs"
29+
30+
# Run Command: cargo run --bin list
31+
[[bin]]
32+
name = "list"
33+
path = "chapter_array_and_linkedlist/list.rs"
34+
35+
[dependencies]
36+
rand = "0.8.5"

‎rust/chapter_array_and_linkedlist/array.rs

Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
/**
2+
* File: array.rs
3+
* Created Time: 2023-01-15
4+
* Author: xBLACICEx (xBLACKICEx@outlook.com), sjinzh (sjinzh@gmail.com)
5+
*/
6+
7+
/* 随机返回一个数组元素 */
8+
fn random_access(nums: &[i32]) -> i32 {
9+
// 在区间 [0, nums.len()) 中随机抽取一个数字
10+
let random_index = rand::random::<usize>() % nums.len();
11+
// 获取并返回随机元素
12+
let random_num = nums[random_index];
13+
random_num
14+
}
15+
16+
/* 扩展数组长度 */
17+
fn extend(nums: Vec<i32>, enlarge: usize) -> Vec<i32> {
18+
// 初始化一个扩展长度后的数组
19+
let mut res: Vec<i32> = vec![0; nums.len() + enlarge];
20+
// 将原数组中的所有元素复制到新
21+
for i in 0..nums.len() {
22+
res[i] = nums[i];
23+
}
24+
// 返回扩展后的新数组
25+
res
26+
}
27+
28+
/* 在数组的索引 index 处插入元素 num */
29+
fn insert(nums: &mut Vec<i32>, num: i32, index: usize) {
30+
// 把索引 index 以及之后的所有元素向后移动一位
31+
for i in (index + 1..nums.len()).rev() {
32+
nums[i] = nums[i - 1];
33+
}
34+
// 将 num 赋给 index 处元素
35+
nums[index] = num;
36+
}
37+
38+
/* 删除索引 index 处元素 */
39+
fn remove(nums: &mut Vec<i32>, index: usize) {
40+
// 把索引 index 之后的所有元素向前移动一位
41+
for i in index..nums.len() - 1 {
42+
nums[i] = nums[i + 1];
43+
}
44+
}
45+
46+
#[allow(unused_variables)]
47+
/* 遍历数组 */
48+
fn traverse(nums: &[i32]) {
49+
let mut count = 0;
50+
// 通过索引遍历数组
51+
for _ in 0..nums.len() {
52+
count += 1;
53+
}
54+
// 直接遍历数组
55+
for _ in nums {
56+
count += 1;
57+
}
58+
}
59+
60+
/* 在数组中查找指定元素 */
61+
fn find(nums: &[i32], target: i32) -> Option<usize> {
62+
for i in 0..nums.len() {
63+
if nums[i] == target {
64+
return Some(i);
65+
}
66+
}
67+
None
68+
}
69+
70+
/* Driver Code */
71+
fn main() {
72+
let arr = [0; 5];
73+
print!("数组 arr = ");
74+
inc::print_util::print_array(&arr);
75+
// 在 Rust 中，指定长度时（[i32; 5]）为数组
76+
// 由于 Rust 的数组被设计为在编译期确定长度，因此只能使用常量来指定长度
77+
// 为了方便实现扩容 extend() 方法，以下将(Vec) 看作数组（Array）也是rust一般情况下使用动态数组的类型
78+
let nums = vec![ 1, 3, 2, 5, 4 ];
79+
print!("\n数组 nums = ");
80+
inc::print_util::print_array(&nums);
81+
82+
/* 随机访问 */
83+
let random_num = random_access(&nums);
84+
println!("\n在 nums 中获取随机元素 {}", random_num);
85+
86+
/* 长度扩展 */
87+
let mut nums = extend(nums, 3);
88+
print!("将数组长度扩展至 8 ，得到 nums = ");
89+
inc::print_util::print_array(&arr);
90+
91+
/* 插入元素 */
92+
insert(&mut nums, 6, 3);
93+
print!("\n在索引 3 处插入数字 6 ，得到 nums = ");
94+
inc::print_util::print_array(&nums);
95+
96+
/* 删除元素 */
97+
remove(&mut nums, 2);
98+
print!("\n删除索引 2 处的元素，得到 nums = ");
99+
inc::print_util::print_array(&nums);
100+
101+
/* 遍历数组 */
102+
traverse(&nums);
103+
104+
/* 查找元素 */
105+
let index = find(&nums, 3).unwrap();
106+
println!("\n在 nums 中查找元素 3 ，得到索引 = {}", index);
107+
}

‎rust/chapter_array_and_linkedlist/list.rs

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
/**
2+
* File: list.rs
3+
* Created Time: 2023-01-18
4+
* Author: xBLACICEx (xBLACKICEx@outlook.com), sjinzh (sjinzh@gmail.com)
5+
*/
6+
7+
#[allow(unused_variables)]
8+
9+
/* Driver Code */
10+
fn main() {
11+
/* 初始化列表 */
12+
let mut list: Vec<i32> = vec![ 1, 3, 2, 5, 4 ];
13+
print!("列表 list = ");
14+
inc::print_util::print_array(&list);
15+
16+
/* 访问元素 */
17+
let num = list[1];
18+
println!("\n访问索引 1 处的元素，得到 num = {num}");
19+
20+
/* 更新元素 */
21+
list[1] = 0;
22+
print!("将索引 1 处的元素更新为 0 ，得到 list = ");
23+
inc::print_util::print_array(&list);
24+
25+
/* 清空列表 */
26+
list.clear();
27+
print!("\n清空列表后 list = ");
28+
inc::print_util::print_array(&list);
29+
30+
/* 尾部添加元素 */
31+
list.push(1);
32+
list.push(3);
33+
list.push(2);
34+
list.push(5);
35+
list.push(4);
36+
print!("\n添加元素后 list = ");
37+
inc::print_util::print_array(&list);
38+
39+
/* 中间插入元素 */
40+
list.insert(3, 6);
41+
print!("\n在索引 3 处插入数字 6 ，得到 list = ");
42+
inc::print_util::print_array(&list);
43+
44+
/* 删除元素 */
45+
list.remove(3);
46+
print!("\n删除索引 3 处的元素，得到 list = ");
47+
inc::print_util::print_array(&list);
48+
49+
/* 通过索引遍历列表 */
50+
let mut count = 0;
51+
for _ in 0..list.len() {
52+
count += 1;
53+
}
54+
55+
/* 直接遍历列表元素 */
56+
count = 0;
57+
for _ in &list {
58+
count += 1;
59+
} // 或者
60+
// list.iter().for_each(|_| count += 1);
61+
// let count = list.iter().fold(0, |count, _| count + 1);
62+
63+
/* 拼接两个列表 */
64+
let mut list1 = vec![ 6, 8, 7, 10, 9 ];
65+
list.append(&mut list1); // append（移动） 之后 list1 为空！
66+
// list.extend(&list1); // extend（借用） list1 能继续使用
67+
print!("\n将列表 list1 拼接到 list 之后，得到 list = ");
68+
inc::print_util::print_array(&list);
69+
70+
/* 排序列表 */
71+
list.sort();
72+
print!("\n排序列表后 list = ");
73+
inc::print_util::print_array(&list);
74+
}

‎rust/chapter_computational_complexity/leetcode_two_sum.rs

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/**
2+
* File: leetcode_two_sum.rs
3+
* Created Time: 2023-01-14
4+
* Author: xBLACICEx (xBLACKICEx@outlook.com), sjinzh (sjinzh@gmail.com)
5+
*/
6+
7+
use std::collections::HashMap;
8+
struct SolutionBruteForce;
9+
struct SolutionHashMap;
10+
11+
/* 方法一：暴力枚举 */
12+
impl SolutionBruteForce {
13+
pub fn two_sum(nums: &Vec<i32>, target: i32) -> Vec<i32> {
14+
let size = nums.len();
15+
// 两层循环，时间复杂度 O(n^2)
16+
for i in 0..size - 1 {
17+
for j in i + 1..size {
18+
if nums[i] + nums[j] == target {
19+
return vec![i as i32, j as i32];
20+
}
21+
}
22+
}
23+
vec![]
24+
}
25+
}
26+
27+
/* 方法二：辅助哈希表 */
28+
impl SolutionHashMap {
29+
pub fn two_sum(nums: &Vec<i32>, target: i32) -> Vec<i32> {
30+
// 辅助哈希表，空间复杂度 O(n)
31+
let mut dic = HashMap::new();
32+
// 单层循环，时间复杂度 O(n)
33+
for (i, num) in nums.iter().enumerate() {
34+
match dic.get(&(target - num)) {
35+
Some(v) => return vec![*v as i32, i as i32],
36+
None => dic.insert(num, i as i32)
37+
};
38+
}
39+
vec![]
40+
}
41+
}
42+
43+
// Driver Code
44+
fn main() {
45+
// ======= Test Case =======
46+
let nums = vec![ 2, 7, 11, 15 ];
47+
let target = 9;
48+
49+
// 方法一
50+
let res = SolutionBruteForce::two_sum(&nums, target);
51+
print!("方法一 res = ");
52+
inc::print_util::print_array(&res);
53+
// 方法二
54+
let res = SolutionHashMap::two_sum(&nums, target);
55+
print!("\n方法二 res = ");
56+
inc::print_util::print_array(&res);
57+
}

0 commit comments

Comments
 (0)