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

Commit a2dfcc4

Browse files
jhidekijhideki
committed
dp
1 parent 878a916 commit a2dfcc4

13 files changed

+431
-1
lines changed

‎src/climbing_stairs.rs

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
pub struct Solution {}
2+
use std::collections::HashMap;
3+
impl Solution {
4+
pub fn climb_stairs(n: i32) -> i32 {
5+
let (mut one, mut two) = (1, 1);
6+
for i in 0..n {
7+
let temp = two;
8+
two = one + two;
9+
one = temp;
10+
}
11+
two
12+
}
13+
}

‎src/clone_graph.rs

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
pub struct Solution {}
2+
impl Solution {}

‎src/course_schedule.rs

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
4+
use std::collections::{HashMap, HashSet};
5+
let mut map: HashMap<i32, Vec<i32>> = HashMap::new();
6+
let mut visited = HashSet::new();
7+
for pr in prerequisites {
8+
map.entry(pr[0])
9+
.and_modify(|e| e.push(pr[1]))
10+
.or_insert(vec![pr[1]]);
11+
}
12+
fn dfs(map: &mut HashMap<i32, Vec<i32>>, course: i32, visited: &mut HashSet<i32>) -> bool {
13+
if !map.contains_key(&course) {
14+
return true;
15+
}
16+
if visited.contains(&course) {
17+
return false;
18+
}
19+
let prereqs = map.get(&course).unwrap().clone();
20+
visited.insert(course);
21+
for pr in prereqs {
22+
if !dfs(map, pr, visited) {
23+
return false;
24+
}
25+
}
26+
visited.remove(&course);
27+
map.remove(&course);
28+
return true;
29+
}
30+
for i in 0..num_courses {
31+
if !dfs(&mut map, i, &mut visited) {
32+
return false;
33+
}
34+
}
35+
true
36+
}
37+
}

‎src/course_schedule2.rs

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn find_order(num_courses: i32, prerequisistes: Vec<Vec<i32>>) -> Vec<i32> {
4+
use std::collections::{HashMap, HashSet};
5+
let mut map: HashMap<i32, Vec<i32>> = HashMap::new();
6+
let mut res: Vec<i32> = Vec::new();
7+
let mut visited = HashSet::new();
8+
let mut cycle = HashSet::new();
9+
for pr in prerequisistes {
10+
map.entry(pr[0])
11+
.and_modify(|e| e.push(pr[1]))
12+
.or_insert(vec![pr[1]]);
13+
}
14+
fn dfs(
15+
map: &mut HashMap<i32, Vec<i32>>,
16+
course: i32,
17+
visited: &mut HashSet<i32>,
18+
cycle: &mut HashSet<i32>,
19+
res: &mut Vec<i32>,
20+
) -> bool {
21+
if visited.contains(&course) {
22+
return true;
23+
}
24+
if visited.contains(&course) {
25+
return false;
26+
}
27+
let p = map.get(&course);
28+
if p.is_some() {
29+
let prereqs = p.unwrap().clone();
30+
cycle.insert(course);
31+
for pr in prereqs {
32+
if !dfs(map, pr, visited, cycle, res) {
33+
return false;
34+
}
35+
}
36+
cycle.remove(&course);
37+
}
38+
visited.insert(course);
39+
res.push(course);
40+
return true;
41+
}
42+
for i in 0..num_courses {
43+
if !dfs(&mut map, i, &mut visited, &mut cycle, &mut res) {
44+
return vec![];
45+
}
46+
}
47+
res
48+
}
49+
}

‎src/main.rs

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

‎src/max_area_island.rs

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn max_area_of_island(grid: Vec<Vec<i32>>) -> i32 {
4+
use std::collections::HashSet;
5+
use std::collections::VecDeque;
6+
fn bfs(visited: &mut HashSet<(i32, i32)>, row: i32, col: i32, grid: &Vec<Vec<i32>>) -> i32 {
7+
visited.insert((row, col));
8+
let mut queue = VecDeque::new();
9+
let mut total = 0;
10+
queue.push_front((row, col));
11+
while !queue.is_empty() {
12+
total += 1;
13+
let (r, c) = queue.pop_back().unwrap();
14+
let dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)];
15+
for dir in dirs {
16+
let (row, col) = (r + dir.0, c + dir.1);
17+
if row >= 0
18+
&& col >= 0
19+
&& row < grid.len() as i32
20+
&& col < grid.len() as i32
21+
&& !visited.contains(&(row, col))
22+
&& grid[row as usize][col as usize] != 0
23+
{
24+
queue.push_front((row, col));
25+
}
26+
}
27+
}
28+
total
29+
}
30+
let mut visited: HashSet<(i32, i32)> = HashSet::new();
31+
let mut max = 0;
32+
for row in 0..grid.len() as i32 {
33+
for col in 0..grid[0].len() as i32 {
34+
if !visited.contains(&(row, col)) {
35+
max = std::cmp::max(bfs(&mut visited, row, col, &grid), max);
36+
}
37+
}
38+
}
39+
max
40+
}
41+
}

‎src/min_cost_stairs.rs

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn min_cost_climbing_stairs(mut cost: Vec<i32>) -> i32 {
4+
cost.push(0);
5+
for i in (0..cost.len() as i32 - 2).rev() {
6+
cost[i as usize] += std::cmp::min(cost[i as usize + 1], cost[i as usize + 2]);
7+
}
8+
std::cmp::min(cost[0], cost[1])
9+
}
10+
}

‎src/number_of_islands.rs

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
4+
use std::collections::HashSet;
5+
use std::collections::VecDeque;
6+
if grid.is_empty() {
7+
return 0;
8+
}
9+
let mut set: HashSet<(i32, i32)> = HashSet::new();
10+
let mut res = 0;
11+
fn bfs(set: &mut HashSet<(i32, i32)>, row: i32, col: i32, grid: &Vec<Vec<char>>) {
12+
let mut queue = VecDeque::new();
13+
set.insert((row, col));
14+
queue.push_back((row, col));
15+
while !queue.is_empty() {
16+
let (row, col) = queue.pop_front().unwrap();
17+
let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];
18+
for dir in directions {
19+
let (r, c) = (row + dir.0, col + dir.1);
20+
if r > 0
21+
&& r < grid.len() as i32
22+
&& c > 0
23+
&& c < grid.len() as i32
24+
&& !set.contains(&(r, c))
25+
&& grid[r as usize][c as usize] != '0'
26+
{
27+
queue.push_back((row + dir.0, col + dir.1));
28+
set.insert((row + dir.0, col + dir.1));
29+
}
30+
}
31+
}
32+
}
33+
for i in 0..grid.len() {
34+
for j in 0..grid[0].len() {
35+
if grid[i][j] == '1' && !set.contains(&(i as i32, j as i32)) {
36+
bfs(&mut set, i as i32, j as i32, &grid);
37+
res += 1;
38+
}
39+
}
40+
}
41+
res
42+
}
43+
}
44+

‎src/pacific_water_flow.rs

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn pacific_atlantic(heights: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
4+
use std::collections::HashSet;
5+
let mut res: Vec<Vec<i32>> = Vec::new();
6+
for i in 0..heights.len() as i32 {
7+
for j in 0..heights[0].len() as i32 {
8+
let mut visited: HashSet<(i32, i32)> = HashSet::new();
9+
let mut pacific = false;
10+
let mut atlantic = false;
11+
dfs(
12+
&heights,
13+
i,
14+
j,
15+
i32::MAX,
16+
&mut pacific,
17+
&mut atlantic,
18+
&mut visited,
19+
);
20+
if pacific && atlantic {
21+
res.push(vec![i, j]);
22+
}
23+
}
24+
}
25+
fn dfs(
26+
heights: &Vec<Vec<i32>>,
27+
x: i32,
28+
y: i32,
29+
prev: i32,
30+
pacific: &mut bool,
31+
atlantic: &mut bool,
32+
visited: &mut HashSet<(i32, i32)>,
33+
) {
34+
if visited.contains(&(x, y)) {
35+
return;
36+
}
37+
if x > heights.len() as i32 || y < 0 {
38+
*atlantic = true;
39+
return;
40+
}
41+
if x < 0 || y > heights[0].len() as i32 {
42+
*pacific = true;
43+
return;
44+
}
45+
if heights[x as usize][y as usize] > prev {
46+
return;
47+
}
48+
let dirs: [(i32, i32); 4] = [(0, 1), (1, 0), (-1, 0), (0, -1)];
49+
let prev = heights[x as usize][y as usize];
50+
visited.insert((x, y));
51+
for dir in dirs {
52+
dfs(
53+
heights,
54+
x + dir.0,
55+
y + dir.1,
56+
prev,
57+
pacific,
58+
atlantic,
59+
visited,
60+
);
61+
}
62+
}
63+
res
64+
}
65+
}

‎src/redundant_connection.rs

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
4+
let mut par: Vec<i32> = (0..edges.len() as i32 + 1).collect();
5+
let mut rank: Vec<i32> = vec![1; edges.len() + 1];
6+
for edge in edges {
7+
if !Self::union(edge[0], edge[1], &mut par, &mut rank) {
8+
return edge;
9+
}
10+
}
11+
return vec![];
12+
}
13+
pub fn find(n: i32, par: &mut Vec<i32>) -> i32 {
14+
let mut p = par[n as usize];
15+
while p != par[p as usize] {
16+
par[p as usize] = par[par[p as usize] as usize];
17+
p = par[p as usize];
18+
}
19+
p
20+
}
21+
pub fn union(n1: i32, n2: i32, par: &mut Vec<i32>, rank: &mut Vec<i32>) -> bool {
22+
let (p1, p2) = (Self::find(n1, par), Self::find(n2, par));
23+
if p1 == p1 {
24+
return false;
25+
}
26+
27+
if rank[p1 as usize] >= rank[p2 as usize] {
28+
par[p2 as usize] = p1;
29+
rank[p1 as usize] += rank[p2 as usize];
30+
} else {
31+
par[p1 as usize] = p2;
32+
rank[p2 as usize] += rank[p1 as usize];
33+
}
34+
return true;
35+
}
36+
}

‎src/rotting_oranges.rs

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
4+
use std::collections::VecDeque;
5+
let mut queue = VecDeque::new();
6+
let mut res = 0;
7+
let mut fresh = 0;
8+
for i in 0..grid.len() {
9+
for j in 0..grid[0].len() {
10+
if grid[i][j] == 2 {
11+
queue.push_back((i as i32, j as i32));
12+
} else if grid[i][j] == 1 {
13+
fresh += 1;
14+
}
15+
}
16+
}
17+
let dirs: [(i32, i32); 4] = [(0, 1), (0, -1), (1, 0), (-1, 0)];
18+
while !queue.is_empty() && fresh > 0 {
19+
for i in 0..queue.len() {
20+
let (r, c) = queue.pop_front().unwrap();
21+
for dir in dirs {
22+
let (row, col) = (dir.0 + r, dir.1 + c);
23+
if row < 0
24+
|| row as usize >= grid.len()
25+
|| col < 0
26+
|| col as usize >= grid[0].len()
27+
|| grid[row as usize][col as usize] != 1
28+
{
29+
continue;
30+
}
31+
grid[row as usize][col as usize] = 2;
32+
queue.push_back((row, col));
33+
fresh -= 1;
34+
}
35+
}
36+
res += 1;
37+
}
38+
if fresh == 0 {
39+
return res;
40+
}
41+
-1
42+
}
43+
}

‎src/surrounded_regions.rs

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
pub struct Solution {}
2+
impl Solution {
3+
pub fn solve(board: &mut Vec<Vec<char>>) {
4+
use std::collections::HashSet;
5+
let mut set: HashSet<(i32, i32)> = HashSet::new();
6+
for i in 0..board.len() as i32 {
7+
for j in 0..board[0].len() as i32 {
8+
if board[i as usize][j as usize] == 'O'
9+
&& ((i == 0 || i == board.len() as i32 - 1)
10+
|| (j == 0 || j == board[0].len() as i32 - 1))
11+
{
12+
dfs(board, &mut set, i, j);
13+
}
14+
}
15+
}
16+
for i in 0..board.len() {
17+
for j in 0..board[0].len() {
18+
if board[i][j] == 'O' && !set.contains(&(i as i32, j as i32)) {
19+
board[i][j] = 'X';
20+
}
21+
}
22+
}
23+
24+
fn dfs(board: &mut Vec<Vec<char>>, set: &mut HashSet<(i32, i32)>, r: i32, c: i32) {
25+
if r < 0
26+
|| r >= board.len() as i32
27+
|| c < 0
28+
|| c >= board[0].len() as i32
29+
|| board[r as usize][c as usize] == 'X'
30+
|| set.contains(&(r, c))
31+
{
32+
return;
33+
}
34+
set.insert((r, c));
35+
let dirs: [(i32, i32); 4] = [(0, 1), (1, 0), (-1, 0), (0, -1)];
36+
for dir in dirs {
37+
let (row, col) = (r + dir.0, c + dir.1);
38+
dfs(board, set, row, col);
39+
}
40+
}
41+
}
42+
}

0 commit comments

Comments
 (0)
0