LeetCode in Rust

LeetCode 1016. Binary String With Substrings Representing 1 To N

Problem Statement

Typical BFS.


use std::collections::HashSet;

impl Solution {
    pub fn query_string(s: String, n: i32) -> bool {
        let mut set = HashSet::new();
        for i in 0..s.len() {
            for j in i..s.len() {
                let str = String::from(&s[i..j + 1]);
                let num = i32::from_str_radix(&str, 2).unwrap();
                if num > n {
                    break;
                }
                set.insert(num);
            }
        }

        for i in 1..n + 1 {
            if !set.contains(&i) {
                return false;
            }
        }
        return true;
    }
}

LeetCode in Rust

LeetCode 1020. Number of Enclaves

Problem Statement

Typical DFS. Similar to 1254. Number of Closed Islands


impl Solution {

    fn dfs(a : &mut Vec<Vec<i32>>, x : usize, y : usize) -> () {
        let (m, n) = (a.len(), a[0].len());
        let (dx, dy) : ([i32; 4], [i32; 4]) = ([0, 0, 1, -1], [1, -1, 0, 0]);
        for i in 0..4 {
            let (xx, yy) : (i32, i32) = (x as i32 + dx[i], y as i32 + dy[i]);
            if xx >= m as i32 || xx < 0 || yy >= n as i32 || yy < 0 {
                continue;
            }
            let (nx, ny) = (xx as usize, yy as usize);
            if a[nx][ny] == 0 {
                continue;
            }
            a[nx][ny] = 0;
            Self::dfs(a, nx, ny);
        }
    }

    pub fn num_enclaves(a: Vec<Vec<i32>>) -> i32 {
        let mut A = a;
        let (m, n, mut ans) = (A.len(), A[0].len(), 0);
        for i in 0..m {
            for j in 0..n {
                if i == 0 || j == 0 || i == m - 1 || j == n - 1 {
                    if A[i][j] != 0 {
                        A[i][j] = 0;
                        Self::dfs(&mut A, i, j);
                    }
                }
            }
        }

        for i in 0..m {
            for j in 0..n {
                if A[i][j] != 0 {
                    ans += 1;
                }
            }
        }

        return ans;
    }
}

LeetCode in Rust

LeetCode 1031 Maximum Sum of Two Non-Overlapping Subarrays

Problem Statement

Maintain a sliding window of two sub arrays with length L and M and slide through. For each slide check two cases:
L first, or M first. Use prefix sum to speed up calculation of sum of a given sub array.

use std::cmp;

impl Solution {
    pub fn max_sum_two_no_overlap(a: Vec<i32>, l: i32, m: i32) -> i32 {
        let A = a.iter().scan(0, |sum, i| {*sum += *i; Some(*sum)}).collect::<Vec<_>>();
        let (L, M) = (l as usize, m as usize);
        let (mut ans, mut lmax, mut rmax) = (A[L + M - 1], A[L - 1], A[M - 1]);
        for i in L + M..A.len() as usize {
            lmax = cmp::max(lmax, A[i - M] - A[i - M - L]);
            rmax = cmp::max(rmax, A[i - L] - A[i - L - M]);
            ans = cmp::max(ans, cmp::max(A[i] - A[i - L] + rmax, A[i] - A[i - M] + lmax));
        }
        return ans;
    }
}