Learning rust

arrays_101.rs

use std::cmp::max;
use std::collections::{HashMap, HashSet};
use std::iter::Rev;

fn main() {
    fn mean(ns: &Vec<f64>) -> f64 {
        ns.iter().sum::<f64>() / (ns.len() as f64)
    }

    fn mode(ns: &Vec<i32>) -> Option<i32> {
        ns.into_iter()
            .fold(HashMap::new(), |mut usage, n| {
                usage.entry(*n).and_modify(|c| *c += 1).or_insert(0);
                usage
            })
            .into_iter()
            .max_by(|(_, a), (_, b)| a.cmp(b))
            .map(|(v, _)| v)
    }

    fn duplicate_zeros(arr: &mut Vec<i32>) {
        for i in (0..arr.len()).rev() {
            if arr[i] == 0 {
                arr.insert(i + 1, 0);
                arr.remove(arr.len());
            }
        }
    }

    fn merge(nums1: &mut Vec<i32>, mut m: i32, nums2: &mut Vec<i32>, mut n: i32) {
        while m > 0 || n > 0 {
            let i1 = (m - 1) as usize;
            let i2 = (n - 1) as usize;
            let i = i1 + i2 + 1;

            if (m == 0) || (n > 0 && nums1[i1] < nums2[i2]) {
                nums1[i] = nums2[i2];
                n -= 1;
            } else {
                nums1[i] = nums1[i1];
                m -= 1;
            }
        }
    }

    fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut j = 0 as usize;

        for i in 0..nums.len() {
            if nums[i] != val {
                nums[j] = nums[i];
                j += 1;
            }
        }

        j as i32
    }

    fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        match nums.get(0) {
            None => 0,
            Some(mut prev) => {
                let mut j: usize = 1;

                for i in 1..nums.len() {
                    if nums[i] != *prev {
                        nums[j] = nums[i];
                        prev = &nums[i];
                        j += 1;
                    }
                }

                j as i32
            }
        }
    }

    fn check_if_exist(arr: Vec<i32>) -> bool {
        let mut set: HashSet<i32> = HashSet::new();

        for x in arr {
            if set
                .get(&(x * 2))
                .or_else(|| (x % 2 == 0).then(|| (x / 2)).and_then(|min| set.get(&min)))
                .is_some()
            {
                return true;
            }

            set.insert(x);
        }

        false
    }

    fn bool_to_option(b: bool) -> Option<bool> {
        if b {
            Some(b)
        } else {
            None
        }
    }

    fn valid_mountain_array(arr: Vec<i32>) -> bool {
        bool_to_option((arr.len() >= 3))
            .and_then(|_| (0..(arr.len() - 1)).position(|i| arr[i] >= arr[i + 1]))
            .and_then(|top| if top > 0 { Some(top) } else { None })
            .and_then(|top| bool_to_option((top + 1..arr.len()).all(|i| arr[i - 1] > arr[i])))
            .is_some()
    }

    fn replace_elements(mut arr: Vec<i32>) -> Vec<i32> {
        let len = arr.len();
        if len == 0 {
            return arr;
        }

        let mut max = *arr.last().unwrap();

        arr[len - 1] = -1;

        for i in (0..len - 1).rev() {
            let cur = arr[i];

            arr[i] = max;

            if cur > max {
                max = cur
            }
        }

        arr
    }

    fn move_zeroes(nums: &mut Vec<i32>) {
        let mut i = 0;
        let mut zeros_count = 0;

        for j in 0..nums.len() {
            if nums[j] != 0 {
                nums[i] = nums[j];
                i += 1
            } else {
                zeros_count += 1
            }
        }

        for (i, _) in (0..nums.len()).enumerate().rev().take(zeros_count) {
            nums[i] = 0;
        }
    }

    fn sort_array_by_parity(mut nums: Vec<i32>) -> Vec<i32> {
        let mut res = Vec::with_capacity(nums.len());
        let mut odds = Vec::new();

        for n in nums {
            if n % 2 == 0 {
                res.push(n)
            } else {
                odds.push(n);
            }
        }

        res.append(&mut odds);

        res
    }

    fn height_checker(mut heights: Vec<i32>) -> i32 {
        let mut clone = heights.to_vec();

        clone.sort();

        clone.iter().enumerate().fold(
            0,
            |count, (i, &h)| if heights[i] != h { count + 1 } else { count },
        )
    }

    fn third_max(mut nums: Vec<i32>) -> i32 {
        nums.sort();

        let mut max = None;

        **nums
            .iter()
            .rev()
            .filter(|&&n| {
                if max != Some(n) {
                    max = Some(n);
                    true
                } else {
                    false
                }
            })
            .take(3)
            .collect::<Vec<_>>()
            .get(2)
            .unwrap_or(&nums.last().unwrap_or(&0))
    }

    fn find_disappeared_numbers(mut nums: Vec<i32>) -> Vec<i32> {
        for n in 0..nums.len() {
            let i = (nums[n].abs() - 1) as usize;

            if nums[i] > 0 {
                nums[i] = -nums[i]
            }
        }

        nums.into_iter()
            .enumerate()
            .filter(|(_, n)| *n > 0)
            .map(|(i, _)| (i + 1) as i32)
            .collect()
    }

    fn sorted_squares(mut nums: Vec<i32>) -> Vec<i32> {
        let mut res = vec![0; nums.len()];
        let mut ni = 0;
        let mut pi = nums.len() - 1;

        for i in (0..nums.len()).rev() {
            if pi > 0 && nums[pi] > nums[ni].abs() {
                res[i] = nums[pi].pow(2);
                pi -= 1;
            } else {
                res[i] = nums[ni].pow(2);
                ni += 1;
            }
        }

        res
    }
}

queue_101_bfc_perfect_squires.rs

use std::collections::VecDeque;

fn is_perfect_squire(n: f64) -> bool {
    let s = n.sqrt().floor();
    (s * s) == n
}

fn num_squares(n: i32) -> i32 {
    let perfect_squires: Vec<_> = (1..n + 1)
        .rev()
        .filter(|n| is_perfect_squire(*n as f64))
        .collect();

    let mut q = VecDeque::from(vec![(0, 0)]);

    while let Some((num, sum)) = q.pop_front() {
        if sum == n {
            return num;
        }

        for s in perfect_squires.iter().map(|ps| sum + ps) {
            if s <= n {
                q.push_back((num + 1, s));
            }
        }
    }

    -1
}

queue_101_bfs_update_matrix.rs

///Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
///
/// The distance between two adjacent cells is 1.
fn update_matrix(mut mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let height = mat.len();
    let width = mat[0].len();
    let mut zeros = VecDeque::new();

    for y in 0..height {
        for x in 0..width {
            if mat[y][x] == 0 {
                zeros.push_back((x as i32, y as i32));
            } else {
                mat[y][x] = i32::MAX;
            }
        }
    }

    let mut q = VecDeque::new();

    while let Some(zero) = zeros.pop_front() {
        q.clear();
        q.push_back(zero);

        while let Some((x, y)) = q.pop_front() {
            for (dx, dy) in &[(1, 0), (-1, 0), (0, 1), (0, -1)] {
                let nx = dx + x as i32;
                let ny = dy + y as i32;

                let new_distance = mat[y as usize][x as usize] + 1;

                if nx >= 0
                    && nx < width as i32
                    && ny >= 0
                    && ny < height as i32
                    && new_distance < mat[ny as usize][nx as usize]
                {
                    mat[ny as usize][nx as usize] = new_distance;
                    q.push_back((nx, ny));
                }
            }
        }
    }

    mat
}

queue_101_can_visit_all_rooms.rs

/// There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
///
/// When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
///
/// Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
    let mut visited = HashSet::new();
    let mut q = VecDeque::from(vec![0]);

    while let Some(room_id) = q.pop_front() {
        if !visited.contains(&room_id) {
            visited.insert(room_id);

            for next_room in &rooms[room_id] {
                q.push_back(*next_room as usize);
            }
        }
    }

    visited.len() == rooms.len()
}

recursion_101_pascal_triangle.rs

fn get_pascal_triangle_row(row_index: i32) -> Vec<i32> {
    if row_index == 0 {
        return vec![1];
    }

    let mut prev_row = get_pascal_triangle_row(row_index - 1);
    prev_row.push(1);

    let mut prev = 1;

    for i in 1..row_index {
        let temp = prev_row[i as usize];
        prev_row[i as usize] += prev;
        prev = temp;
    }

    prev_row
}

stack_101_decode_string.rs

/// Given an encoded string, return its decoded string.
///
/// The encoding rule is: k\[encoded_string\], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
///
/// You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
///
/// Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2\[4\].
fn decode_string(s: String) -> String {
    let mut acc = "".to_string();
    let mut repeat_acc = "".to_string();
    let mut stack: Vec<(String, usize)> = vec![];

    for c in s.chars() {
        match c {
            '[' => {
                stack.push((acc, repeat_acc.parse().unwrap()));

                repeat_acc.clear();
                acc = "".to_string();
            }
            ']' => {
                let (prev, repeat) = stack.pop().unwrap();

                acc = prev + &acc.repeat(repeat)[..]
            }
            _ => {
                if c.is_digit(10) {
                    repeat_acc.push(c);
                } else {
                    acc.push(c);
                }
            }
        }
    }

    acc
}

stack_101_eval_rpn.rs

fn apply(op: &str, a: i32, b: i32) -> i32 {
    match op {
        "+" => a + b,
        "-" => a - b,
        "*" => a * b,
        "/" => a / b,
        _ => panic!("WTF man!"),
    }
}

fn eval_rpn(tokens: Vec<String>) -> Option<i32> {
    let mut s = vec![];

    for t in tokens {
        let t = &t[..];

        match t {
            "+" | "-" | "*" | "/" => {
                let a = s.pop()?;
                let b = s.pop()?;

                s.push(apply(t, a, b))
            }
            n => s.push(n.parse::<i32>().ok()?),
        }
    }

    s.pop()
}

stack_101_flood_fill.rs

fn flood_fill(mut image: Vec<Vec<i32>>, sr: i32, sc: i32, new_color: i32) -> Vec<Vec<i32>> {
    let old_color = image[sr as usize][sc as usize];
    let width = image.len();
    let height = image[0].len();

    let mut q = vec![(sr as usize, sc as usize)];

    while let Some((x, y)) = q.pop() {
        let cell = image[x][y];
        if cell != new_color && cell == old_color {
            image[x][y] = new_color;

            if x > 0 {
                q.push((x - 1, y))
            }
            if y > 0 {
                q.push((x, y - 1))
            }
            if x + 1 < width {
                q.push((x + 1, y))
            }
            if y + 1 < height {
                q.push((x, y + 1))
            }
        }
    }

    image
}

stack_101_validate_brackets.rs

fn closing_bracket_for(opening: char) -> char {
    match opening {
        '(' => ')',
        '{' => '}',
        '[' => ']',
        _ => panic!("WTF man!"),
    }
}

fn is_valid(s: String) -> bool {
    let mut stack = vec![];

    s.chars().all(|c| match c {
        '(' | '{' | '[' => {
            stack.push(closing_bracket_for(c));
            true
        }
        ')' | '}' | ']' => stack.pop().map(|closing| closing == c).unwrap_or(false),
        _ => true,
    }) && stack.len() == 0
}