8000 Add more solutions · martwz/leetcode-rust@8d65df5 · GitHub
[go: up one dir, main page]

Skip to content

Commit 8d65df5

Browse files
committed
Add more solutions
1 parent 96f5b5b commit 8d65df5

File tree

8 files changed

+428
-1
lines changed

8 files changed

+428
-1
lines changed

README.md

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66

77
LeetCode is a website that has programming-related questions that are designed to be solved in a limited amount of time. This repository is a collection of some of my solutions written in [Rust](https://www.rust-lang.org/).
88

9-
## Solutions (115)
9+
## Solutions (124)
1010
| No. | Title | Solution | Problem | Difficulty |
1111
|:---:|:------|:--------:|:-------:|:----------:|
1212
| 1 | Two Sum | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/two_sum.rs) | [Leetcode](https://leetcode.com/problems/two-sum/) | ![easy](https://shields.io/badge/-easy-green) |
@@ -40,7 +40,9 @@ LeetCode is a website that has programming-related questions that are designed t
4040
| 174 | Dungeon Game | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/calculate_minimum_hp.rs) | [Leetcode](https://leetcode.com/problems/dungeon-game/) | ![hard](https://shields.io/badge/-hard-red) |
4141
| 200 | Number of Islands | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/num_islands.rs) | [Leetcode](https://leetcode.com/problems/number-of-islands/) | ![medium](https://shields.io/badge/-medium-yellow) |
4242
| 201 | Bitwise AND of Numbers Range | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/range_bitwise_and.rs) | [Leetcode](https://leetcode.com/problems/bitwise-and-of-numbers-range/) | ![medium](https://shields.io/badge/-medium-yellow) |
43+
| 207 | Course Schedule | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/course-schedule.rs) | [Leetcode](https://leetcode.com/problems/course-schedule/) | ![medium](https://shields.io/badge/-medium-yellow) |
4344
| 208 | Implement Trie (Prefix Tree) | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/implement_trie_prefix_tree.rs) | [Leetcode](https://leetcode.com/problems/implement-trie-prefix-tree/) | ![medium](https://shields.io/badge/-medium-yellow) |
45+
| 210 | Course Schedule II | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/course-schedule_two.rs) | [Leetcode](https://leetcode.com/problems/course-schedule-ii/) | ![medium](https://shields.io/badge/-medium-yellow) |
4446
| 212 | Word Search II | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/find_words.rs) | [Leetcode](https://leetcode.com/problems/word-search-ii/) | ![hard](https://shields.io/badge/-hard-red) |
4547
| 230 | Kth Smallest Element in a BST | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/kth_smallest.rs) | [Leetcode](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) | ![medium](https://shields.io/badge/-medium-yellow) |
4648
| 242 | Valid Anagram | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/is_anagram.rs) | [Leetcode](https://leetcode.com/problems/valid-anagram/) | ![easy](https://shields.io/badge/-easy-green) |
@@ -68,6 +70,7 @@ LeetCode is a website that has programming-related questions that are designed t
6870
| 516 | Longest Palindromic Subsequence | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/longest_palindrome_subseq.rs) | [Leetcode](https://leetcode.com/problems/longest-palindromic-subsequence/) | ![medium](https://shields.io/badge/-medium-yellow) |
6971
| 543 | Diameter of Binary Tree | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/diameter_of_binary_tree.rs) | [Leetcode](https://leetcode.com/problems/diameter-of-binary-tree/) | ![easy](https://shields.io/badge/-easy-green) |
7072
| 547 | Number of Provinces | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/interview/amazon/find_circle_num.rs) | [Leetcode](https://leetcode.com/problems/number-of-provinces/) | ![medium](https://shields.io/badge/-medium-yellow) |
73+
| 695 | Max Area of Island | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/max_area_of_island.rs) | [Leetcode](https://leetcode.com/problems/max-area-of-island/) | ![medium](https://shields.io/badge/-medium-yellow) |
7174
| 696 | Count Binary Substrings | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/count_binary_substrings.rs) | [Leetcode](https://leetcode.com/problems/count-binary-substrings/) | ![easy](https://shields.io/badge/-easy-green) |
7275
| 698 | Partition to K Equal Sum Subsets | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/can_partition_k_subsets.rs) | [Leetcode](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/) | ![medium](https://shields.io/badge/-medium-yellow) |
7376
| 713 | Subarray Product Less Than K | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/cheat.rs) | [Leetcode](https://leetcode.com/problems/subarray-product-less-than-k/) | ![medium](https://shields.io/badge/-medium-yellow) |
@@ -76,6 +79,7 @@ LeetCode is a website that has programming-related questions that are designed t
7679
| 741 | Cherry Pickup | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/cherry_pickup.rs) | [Leetcode](https://leetcode.com/problems/cherry-pickup/) | ![hard](https://shields.io/badge/-hard-red) |
7780
| 749 | Contain Virus | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/contain_virus.rs) | [Leetcode](https://leetcode.com/problems/contain-virus/) | ![hard](https://shields.io/badge/-hard-red) |
7881
| 774 | Minimize Max Distance to Gas Station | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/minmax_gas_dist.rs) | [Leetcode](https://leetcode.com/problems/minimize-max-distance-to-gas-station/) | ![medium](https://shields.io/badge/-medium-yellow) |
82+
| 841 | Keys and Rooms | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/keys-and-rooms.rs) | [Leetcode](https://leetcode.com/problems/keys-and-rooms/) | ![medium](https://shields.io/badge/-medium-yellow) |
7983
| 875 | Koko Eating Bananas | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/min_eating_speed.rs) | [Leetcode](https://leetcode.com/problems/koko-eating-bananas/) | ![medium](https://shields.io/badge/-medium-yellow) |
8084
| 901 | Online Stock Span | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/stock_span.rs) | [Leetcode](https://leetcode.com/problems/online-stock-span/) | ![medium](https://shields.io/badge/-medium-yellow) |
8185
| 922 | Sort Array By Parity II | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/sort_array_by_parity_ii.rs) | [Leetcode](https://leetcode.com/problems/sort-array-by-parity-ii/) | ![easy](https://shields.io/badge/-easy-green) |
@@ -95,6 +99,7 @@ LeetCode is a website tha F438 t has programming-related questions that are designed t
9599
| 1143 | Longest Common Subsequence | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/longest_common_subsequence.rs) | [Leetcode](https://leetcode.com/problems/longest-common-subsequence/) | ![medium](https://shields.io/badge/-medium-yellow) |
96100
| 1161 | Maximum Level Sum of a Binary Tree | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/max_level_sum.rs) | [Leetcode](https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/) | ![medium](https://shields.io/badge/-medium-yellow) |
97101
| 1167 | Minimum Cost to Connect Sticks | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/interview/amazon/connect_sticks.rs) | [Leetcode](https://leetcode.com/problems/minimum-cost-to-connect-sticks/) | ![medium](https://shields.io/badge/-medium-yellow) |
102+
| 1197 | Minimum Knight Moves | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/problem/min_knight_moves.rs) | [Leetcode](https://leetcode.com/problems/minimum-knight-moves/) | ![medium](https://shields.io/badge/-medium-yellow) |
98103
| 1216 | Valid Palindrome III | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/is_valid_palindrome.rs) | [Leetcode](https://leetcode.com/problems/valid-palindrome-iii/) | ![hard](https://shields.io/badge/-hard-red) |
99104
| 1239 | Maximum Length of a Concatenated String with Unique Characters | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/challenge/max_length.rs) | [Leetcode](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/) | ![medium](https://shields.io/badge/-medium-yellow) |
100105
| 1268 | Search Suggestions System | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/interview/amazon/suggested_products.rs) | [Leetcode](https://leetcode.com/problems/search-suggestions-system/) | ![medium](https://shields.io/badge/-medium-yellow) |
@@ -121,6 +126,10 @@ LeetCode is a website that has programming-related questions that are designed t
121126
| 2032 | Two Out of Three | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/weekly_262.rs) | [Leetcode](https://leetcode.com/problems/two-out-of-three/) | ![easy](https://shields.io/badge/-easy-green) |
122127
| 2033 | Minimum Operations to Make a Uni-Value Grid | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/weekly_262.rs) | [Leetcode](https://leetcode.com/problems/minimum-operations-to-make-a-uni-value-grid/) | ![medium](https://shields.io/badge/-medium-yellow) |
123128
| 2034 | Stock Price Fluctuation | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/weekly_262.rs) | [Leetcode](https://leetcode.com/problems/stock-price-fluctuation/) | ![medium](https://shields.io/badge/-medium-yellow) |
129+
| 2042 | Check if Numbers Are Ascending in a Sentence | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/weekly_263.rs) | [Leetcode](https://leetcode.com/problems/check-if-numbers-are-ascending-in-a-sentence/) | ![easy](https://shields.io/badge/-easy-green) |
130+
| 2043 | Simple Bank System | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/weekly_263.rs) | [Leetcode](https://leetcode.com/problems/simple-bank-system/) | ![medium](https://shields.io/badge/-medium-yellow) |
131+
| 2044 | Count Number of Maximum Bitwise-OR Subsets | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/weekly_263.rs) | [Leetcode](https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/) | ![medium](https://shields.io/badge/-medium-yellow) |
132+
| 2045 | Second Minimum Time to Reach Destination | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/weekly_263.rs) | [Leetcode](https://leetcode.com/problems/second-minimum-time-to-reach-destination/) | ![hard](https://shields.io/badge/-hard-red) |
124133
| 5885 | Minimum Number of Moves to Seat Everyone | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/biweekly_63.rs) | [Leetcode](https://leetcode.com/problems/minimum-number-of-moves-to-seat-everyone/) | ![easy](https://shields.io/badge/-easy-green) |
125134
| 5886 | Remove Colored Pieces if Both Neighbors are the Same Color | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/biweekly_63.rs) | [Leetcode](https://leetcode.com/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color/) | ![medium](https://shields.io/badge/-medium-yellow) |
126135
| 5888 | The Time When the Network Becomes Idle | [Rust](https://github.com/martinxxd/leetcode-rust/tree/master/./src/leetcode/contest/biweekly_63.rs) | [Leetcode](https://leetcode.com/problems/the-time-when-the-network-becomes-idle/) | ![medium](https://shields.io/badge/-medium-yellow) |

src/leetcode/contest/mod.rs

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,3 +2,4 @@ mod biweekly_62;
22
mod biweekly_63;
33
mod weekly_261;
44
mod weekly_262;
5+
mod weekly_263;

src/leetcode/contest/weekly_263.rs

Lines changed: 178 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,178 @@
1+
use std::collections::{BinaryHeap, HashMap, VecDeque};
2+
3+
// 2042. Check if Numbers Are Ascending in a Sentence, Easy
4+
// https://leetcode.com/problems/check-if-numbers-are-ascending-in-a-sentence/
5+
impl Solution1 {
6+
pub fn are_numbers_ascending(s: String) -> bool {
7+
let mut s = s;
8+
s.push('#');
9+
let mut prev: u32 = 0;
10+
let mut curr_digit: u32 = 0;
11+
12+
for ch in s.chars() {
13+
if ch.is_numeric() {
14+
curr_digit = curr_digit * 10 + ch.to_digit(10).unwrap();
15+
} else {
16+
if curr_digit != 0 {
17+
if prev >= curr_digit {
18+
return false;
19+
}
20+
prev = curr_digit;
21+
curr_digit = 0;
22+
}
23+
}
24+
}
25+
26+
true
27+
}
28+
}
29+
30+
struct Bank {
31+
accounts: HashMap<i32, i64>,
32+
}
33+
34+
// 2043. Simple Bank System, Medium
35+
// https://leetcode.com/problems/simple-bank-system/
36+
impl Bank {
37+
fn new(balance: Vec<i64>) -> Self {
38+
let mut hm = HashMap::new();
39+
for i in 0..balance.len() {
40+
hm.insert(i as i32 + 1, balance[i]);
41+
}
42+
43+
Bank { accounts: hm }
44+
}
45+
46+
fn transfer(&mut self, account1: i32, account2: i32, money: i64) -> bool {
47+
if !self.accounts.contains_key(&account1) || !self.accounts.contains_key(&account2) {
48+
return false;
49+
} else {
50+
let avail = *self.accounts.get(&account1).unwrap_or(&0);
51+
if avail >= money {
52+
self.accounts.entry(account1).and_modify(|b| *b -= money);
53+
self.accounts.entry(account2).and_modify(|b| *b += money);
54+
return true;
55+
} else {
56+
return false;
57+
}
58+
}
59+
}
60+
61+
fn deposit(&mut self, account: i32, money: i64) -> bool {
62+
if !self.accounts.contains_key(&account) {
63+
return false;
64+
} else {
65+
self.accounts.entry(account).and_modify(|b| *b += money);
66+
return true;
67+
}
68+
}
69+
70+
fn withdraw(&mut self, account: i32, money: i64) -> bool {
71+
if !self.accounts.contains_key(&account) {
72+
return false;
73+
} else {
74+
let avail = *self.accounts.get(&account).unwrap_or(&0);
75+
if avail >= money {
76+
self.accounts.entry(account).and_modify(|b| *b -= money);
77+
return true;
78+
} else {
79+
return false;
80+
}
81+
}
82+
}
83+
}
84+
85+
// 2044. Count Number of Maximum Bitwise-OR Subsets, Medium
86+
// https://leetcode.com/problems/count-number-of-maximum-bitwise-or-subsets/
87+
impl Solution3 {
88+
pub fn count_max_or_subsets(nums: Vec<i32>) -> i32 {
89+
let mut max_ors = 0;
90+
for num in nums.iter() {
91+
max_ors |= *num;
92+
}
93+
94+
fn subset(nums: &Vec<i32>, count: &mut i32, i: i32, a: i32, b: i32) {
95+
if i < 0 {
96+
return;
97+
}
98+
if a == b | nums[i as usize] {
99+
*count += 1
100+
}
101+
subset(&nums, count, i - 1, a, b);
102+
subset(&nums, count, i - 1, a, b | nums[i as usize]);
103+
}
104+
105+
let mut count = 0;
106+
subset(&nums, &mut count, nums.len() as i32 - 1, max_ors, 0);
107+
108+
count
109+
}
110+
}
111+
112+
// 2045. Second Minimum Time to Reach Destination, Hard
113+
// https://leetcode.com/problems/second-minimum-time-to-reach-destination/
114+
impl Solution4 {
115+
pub fn second_minimum(n: i32, edges: Vec<Vec<i32>>, time: i32, change: i32) -> i32 {
116+
let n = n as usize;
117+
let mut seen = vec![false; n + 1];
118+
seen[0] = true;
119+
120+
let mut queue: VecDeque<(i32, i32)> = VecDeque::new();
121+
queue.push_back((1, 0));
122+
seen[1] = true;
123+
124+
let mut dists: Vec<Vec<i32>> = vec![vec![]; n + 1];
125+
126+
let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
127+
for i in 0..=n {
128+
adj.insert(i as i32, vec![]);
129+
}
130+
for edge in edges.iter() {
131+
let (u, v) = (edge[0], edge[1]);
132+
adj.entry(u).and_modify(|e| e.push(v));
133+
adj.entry(v).and_modify(|e| e.push(u));
134+
}
135+
136+
while !queue.is_empty() {
137+
let (vertex, elapsed) = queue.pop_front().unwrap();
138+
139+
seen[vertex as usize] = true;
140+
141+
for &e in adj.get(&vertex).unwrap() {
142+
let cand: i32;
143+
if elapsed as i32 / change % 2 == 0 {
144+
cand = elapsed + time;
145+
} else {
146+
cand = (f32::ceil(elapsed as f32 / (2.0 * change as f32)) * (2.0 * change as f32) + time as f32) as i32;
147+
}
148+
149+
if dists[e as usize].is_empty() || (dists[e as usize].len() == 1 && dists[e as usize] != vec![cand]) {
150+
dists[e as usize].push(cand);
151+
queue.push_back((e, cand));
152+
}
153+
}
154+
}
155+
156+
*dists[n].iter().max().unwrap()
157+
}
158+
}
159+
160+
struct Solution1 {}
161+
struct Solution3 {}
162+
struct Solution4 {}
163+
164+
#[cfg(test)]
165+
mod tests {
166+
use super::*;
167+
use crate::{vec_string, vec_vec_i32};
168+
169+
#[test]
170+
fn test_second_minimum() {
171+
assert_eq!(Solution4::second_minimum(5, vec_vec_i32![[1, 2], [1, 3], [1, 4], [3, 4], [4, 5]], 3, 5), 13);
172+
}
173+
174+
#[test]
175+
fn test_minimum_moves2() {
176+
assert_eq!(Solution4::second_minimum(2, vec_vec_i32![[1, 2]], 3, 2), 11);
177+
}
178+
}
Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
use std::collections::{HashMap, VecDeque};
2+
3+
// 207. Course Schedule, Medium
4+
// https://leetcode.com/problems/course-schedule/
5+
impl Solution {
6+
pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
7+
let mut indegree = (0..num_courses).map(|f| 0).collect::<Vec<i32>>();
8+
9+
let mut hm = HashMap::<i32, Vec<i32>>::new();
10+
for prereq in prerequisites.iter() {
11+
let [course, pre_course] = [prereq[0], prereq[1]];
12+
hm.entry(pre_course).and_modify(|f| f.push(course)).or_insert(vec![course]);
13+
indegree[course as usize] += 1;
14+
}
15+
16+
let mut queue = VecDeque::new();
17+
for (i, course) in indegree.iter().enumerate() {
18+
if *course == 0 {
19+
queue.push_back(i as i32);
20+
}
21+
}
22+
23+
let mut count = 0;
24+
while !queue.is_empty() {
25+
let c = queue.pop_front().unwrap();
26+
count += 1;
27+
28+
for &v in hm.get(&c).unwrap_or(&vec![]) {
29+
indegree[v as usize] -= 1;
30+
if indegree[v as usize] == 0 {
31+
queue.push_back(v);
32+
}
33+
}
34+
}
35+
36+
count == num_courses
37+
}
38+
}
39+
40+
struct Solution {}
41+
42+
#[cfg(test)]
43+
mod tests {
44+
use super::*;
45+
use crate::vec_vec_i32;
46+
47+
#[test]
48+
fn test_can_finish() {
49+
assert_eq!(Solution::can_finish(2, vec_vec_i32![[1, 0]]), true);
50+
}
51+
52+
#[test]
53+
fn test_can_finish2() {
54+
assert_eq!(Solution::can_finish(2, vec_vec_i32![[1, 0], [0, 1]]), false);
55+
}
56+
57+
#[test]
58+
fn test_can_finish3() {
59+
assert_eq!(
60+
Solution::can_finish(20, vec_vec_i32![[0, 10], [3, 18], [5, 5], [6, 11], [11, 14], [13, 1], [15, 1], [17, 4]]),
61+
false
62+
);
63+
}
64+
}

0 commit comments

Comments
 (0)
0