8000 backtracking · jhideki/rust_leetcode@277c0a9 · GitHub
[go: up one dir, main page]
Skip to content

Commit 277c0a9

Browse files
jhidekijhideki
committed
backtracking
1 parent 68c1885 commit 277c0a9

File tree

6 files changed

+145
-1
lines changed

6 files changed

+145
-1
lines changed

‎src/combination_sum.rs

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
4+
fn rec(
5+
i: usize,
6+
candidates: &Vec<i32>,
7+
subset: &mut Vec<i32>,
8+
res: &mut Vec<Vec<i32>>,
9+
target: i32,
10+
mut sum: i32,
11+
) {
12+
if i >= candidates.len() || sum > target {
13+
return;
14+
}
15+
if sum == target {
16+
res.push(subset.clone());
17+
return;
18+
}
19+
subset.push(candidates[i]);
20+
rec(i, candidates, subset, res, target, sum + candidates[i]);
21+
let n = subset.pop().unwrap();
22+
rec(i + 1, candidates, subset, res, target, sum);
23+
}
24+
25+
let mut res: Vec<Vec<i32>> = Vec::new();
26+
let mut subset: Vec<i32> = Vec::new();
27+
rec(0, &candidates, &mut subset, &mut res, target, 0);
28+
res
29+
}
30+
}

‎src/find_median_data_stream.rs

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
use std::cmp::Reverse;
2+
use std::collections::BinaryHeap;
3+
struct MedianFinder {
4+
min: BinaryHeap<Reverse<i32>>,
5+
max: BinaryHeap<i32>,
6+
}
7+
8+
/**
9+
* `&self` means the method takes an immutable reference.
10+
* If you need a mutable reference, change it to `&mut self` instead.
11+
*/
12+
impl MedianFinder {
13+
fn new() -> Self {
14+
MedianFinder {
15+
min: BinaryHeap::new(),
16+
max: BinaryHeap::new(),
17+
}
18+
}
19+
20+
fn add_num(&mut self, num: i32) {
21+
self.max.push(num);
22+
if self.min.peek().is_some() && self.max.peek().is_some() {
23+
if self.min.peek().unwrap().0 > *self.max.peek().unwrap() {
24+
self.min.push(Reverse(self.max.pop().unwrap()));
25+
}
26+
}
27+
if self.max.len() > 1 + self.min.len() {
28+
self.min.push(Reverse(self.max.pop().unwrap()));
29+
} else if self.min.len() > 1 + self.max.len() {
30+
self.max.push(self.min.pop().unwrap().0);
31+
}
32+
}
33+
34+
fn find_median(&self) -> f64 {
35+
if self.min.len() > self.max.len() {
36+
return self.min.peek().unwrap().0 as f64;
37+
} else if self.max.len() > self.min.len() {
38+
return *self.max.peek().unwrap() as f64;
39+
}
40+
(self.min.peek().unwrap().0 + self.max.peek().unwrap()) as f64 / 2.0
41+
}
42+
}

‎src/main.rs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,2 +1,2 @@
1-
mod design_twitter;
1+
mod subsets_two;
22
fn main() {}

‎src/permutations.rs

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
4+
use std::collections::VecDeque;
5+
let mut deque: VecDeque<i32> = VecDeque::from(nums);
6+
fn rec(mut nums: VecDeque<i32>) -> Vec<Vec<i32>> {
7+
let mut r = Vec::new();
8+
if nums.len() == 1 {
9+
let mut res = Vec::new();
10+
res.push(nums.clone().into());
11+
return res;
12+
}
13+
for i in 0..nums.len() {
14+
let n = nums.pop_front().unwrap();
15+
let mut perms = rec(nums.clone());
16+
for perm in &mut perms {
17+
perm.push(n);
18+
}
19+
nums.push_back(n);
20+
r.extend(perms.clone());
21+
}
22+
23+
return r;
24+
}
25+
let mut res = Vec::new();
26+
res.extend(rec(deque));
27+
res
28+
}
29+
}

‎src/subsets.rs

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
4+
fn rec(i: usize, nums: Vec<i32>, res: &mut Vec<Vec<i32>>, sub: &mut Vec<i32>) {
5+
if i >= nums.len() {
6+
res.push(sub.clone());
7+
return;
8+
}
9+
sub.push(nums[i]);
10+
rec(i + 1, nums.clone(), res, sub);
11+
sub.pop();
12+
rec(i + 1, nums.clone(), res, sub);
13+
}
14+
let mut res: Vec<Vec<i32>> = Vec::new();
15+
let mut sub: Vec<i32> = Vec::new();
16+
rec(0, nums, &mut res, &mut sub);
17+
res
18+
}
19+
}

‎src/subsets_two.rs

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
4+
fn rec(mut i: usize, res: &mut Vec<Vec<i32>>, subset: &mut Vec<i32>, nums: &Vec<i32>) {
5+
if i >= nums.len() {
6+
res.push(subset.clone());
7+
return;
8+
}
9+
subset.push(nums[i]);
10+
rec(i + 1, res, subset, nums);
11+
subset.pop();
12+
while i + 1 < nums.len() && nums[i] == nums[i + 1] {
13+
i += 1;
14+
}
15+
rec(i + 1, res, subset, nums);
16+
}
17+
18+
let mut res = Vec::new();
19+
let mut subset = Vec::new();
20+
nums.sort();
21+
rec(0, &mut res, &mut subset, &nums);
22+
res
23+
}
24+
}

0 commit comments

Comments
 (0)
0