LeetCode in Rust

LeetCode 1254. Number of Closed Islands

Problem Statement

Typical BFS.


use std::collections::VecDeque;

impl Solution {
    pub fn closed_island(grid: Vec<Vec<i32>>) -> i32 {
        let (m, n, mut ans) = (grid.len(), grid[0].len(), 0);
        let (dx, dy) : ([i32; 4], [i32; 4]) = ([1, -1, 0, 0], [0, 0, 1, -1]);
        let mut g = grid;
        for i in 0..m {
            for j in 0..n {
                if g[i][j] == 1 || g[i][j] == -1 {
                    continue;
                }
                let mut q = VecDeque::new();
                q.push_back((i, j));
                g[i][j] = -1;
                let mut valid = true;

                while !q.is_empty() {
                    let (x, y) = q.pop_front().unwrap();
                    for k in 0..4 {
                        let (xx, yy) = (x as i32 + dx[k], y as i32 + dy[k]);
                        if xx < 0 || yy < 0 || xx >= m as i32 || yy >= n as i32 {
                            valid = false; continue;
                        }
                        let (nx, ny) = (xx as usize, yy as usize);
                        if g[nx][ny] == 1 || g[nx][ny] == -1 {
                            continue;
                        }
                        q.push_back((nx, ny));
                        g[nx][ny] = -1;
                    }
                }

                if valid {
                    ans += 1;
                }
            }
        }

        return ans;
    }
}

LeetCode in Rust

LeetCode 688. Knight Probability in Chessboard

Problem Statement

DP, be careful about pow overflow.


impl Solution {
    pub fn knight_probability(n: i32, k: i32, r: i32, c: i32) -> f64 {
        if k == 0 {
            return 1 as f64;
        }

        let (dx, dy) : ([i32; 8], [i32; 8]) = (
            [-1, -2, -2, -1, 1, 2, 2, 1],
            [-2, -1, 1, 2, 2, 1, -1, -2]);
        let mut dp = vec![vec![1 as f64; n as usize]; n as usize];
        for _m in 0..k {
            let mut tmp = vec![vec![0 as f64; n as usize]; n as usize];
            for i in 0..n {
                for j in 0..n {
                    for k in 0..8 {
                        let (xx, yy) = (i + dx[k], j + dy[k]);
                        if xx < 0 || yy < 0 || xx >= n || yy >= n {
                            continue;
                        }
                        tmp[i as usize][j as usize] += dp[xx as usize][yy as usize];
                    }
                }
            }
            dp.swap_with_slice(&mut tmp[0..]);
        }

        return dp[r as usize][c as usize] / 8_f64.powf(k as f64);
    }
}

LeetCode in Rust

LeetCode 924 Minimize Malware Spread

Problem Statement

For each initially infected node, try remove it and then count the total number of infected nodes through BFS.
Pick up the solution that if removing such a node will yield the minimum number of infected nodes.


use std::vec::Vec;
use std::collections::VecDeque;

impl Solution {
    pub fn min_malware_spread(graph: Vec<Vec<i32>>, initial: Vec<i32>) -> i32 {
        let (mut ans, mut min) = (-1, 400);
        let mut input = initial;
        input.sort();

        for t in &input {
            let mut bad = vec![0; graph.len()];
            let mut q = VecDeque::new();
            for n in &input {
                if *n == *t {
                    continue;
                }
                bad[*n as usize] = 1; q.push_back(*n as usize);
            }

            let mut affected = input.len() - 1;
            while !q.is_empty() {
                let n = q.pop_front().unwrap();
                for (i, item) in graph[n].iter().enumerate() {
                    if bad[i as usize] == 1 || *item == 0 {
                        continue;
                    }
                    affected += 1; bad[i as usize] = 1; q.push_back(i as usize);
                }
            }

            if affected < min {
                min = affected;
                ans = *t;
            }
        }

        return ans;
    }
}