Learning Rust from LeetCode

2019.10.13

1. Two Sum

Method 1: Brute-Force

use std::vec::Vec;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut x = 0;  // declare mutable variable
        let mut y = 0;
        for i in 0..nums.len() {  // use `a..b` for range [a, b)
            for j in i+1..nums.len() {
                if nums[i] + nums[j] == target {
                    x = i as i32;  //  use `as` to cast type
                    y = j as i32;
                }
            }
        }
        vec![x, y]  // use macro `vec!` to create new vector and return
    }
}

References:

Method 2: Hash

use std::collections::HashMap;
use std::vec::Vec;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut hash = HashMap::new();
        for (i, v) in nums.iter().enumerate() {  // `v` is &i32
            if let Some(&j) = hash.get(v) {  // unwrap value form Option in `if`
                return vec![j as i32, i as i32];
            } else {
                hash.insert(target - v, i);  // insert pair [i32, usize]
            }
        }
        vec![0, 0]
    }
}

References:

144. Binary Tree Preorder Traversal

Methods 1: Stack

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
use std::vec::Vec;

impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut stack = vec![root];  // use macro `vec!` to initial stack
        let mut result = vec![];
        while stack.len() > 0 {
            if let Some(node) = stack.pop().unwrap() {
                result.push(node.borrow().val);  // borrow from reference counted smart pointer
                stack.push(node.borrow().right.clone());  // clone node from borrow item
                stack.push(node.borrow().left.clone());
            }
        }
        result
    }
}

References:

Method 2: DFS

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::cell::RefCell;
use std::rc::Rc;
use std::vec::Vec;

impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, mut result: &mut Vec<i32>) {
        if let Some(root) = root {  // unwrap option with same name
            result.push(root.borrow().val);
            Self::dfs(&root.borrow().left, &mut result);
            Self::dfs(&root.borrow().right, &mut result);
        }
    }

    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = vec![];
        Self::dfs(&root, &mut result);
        result
    }
}

References:

557. Reverse Words in a String III

Method 1: Map-Reduce

impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.split(' ').map(|s| s.chars().rev().collect::<String>()).collect::<Vec<_>>().join(" ")
    }
}

References:

Method 2: Rev-Rev

impl Solution {
    pub fn reverse_words(s: String) -> String {
        s.chars().rev().collect::<String>().split(' ').rev().collect::<Vec<_>>().join(" ")
    }
}

References:

Trait std::iter::Iterator
Struct std::string::String
Struct std::vec::Vec