As I’m learning Rust language recently, LeetCode becomes a good place to write some small program and to get familiar with Rust grammar and syntax. In the recent two contests I tried using Rust to solve some problems however it took much longer time than I expected, to deal with the strict compiler. Pretty fun though, and I think it did help me getting hands dirty.
However, personally I won’t suggest using Rust in LeetCode contests or in real interviews as Python/Ruby would be much better choice. Rust could be useful in some other aspects which I’ll check later. (safety, speed, and concurrency? + WebAssembly) 🦀️
Keyword: Sliding window
Use a counter to keep track of the appearances outside of the sliding window, and try to narrow the window as small as possible.
Rust solution:
use std::cmp;
use std::collections::HashMap;
struct Solution {}
impl Solution {
pub fn balanced_string(s: String) -> i32 {
let mut counter: HashMap<char, i32> = HashMap::new();
for c in ['Q', 'W', 'E', 'R'].iter() {
counter.insert(*c, 0);
}
for c in s.chars() {
let new_count = match counter.get(&c) {
Some(&val) => val + 1,
None => 1,
};
counter.insert(c, new_count);
}
let length = s.len() as i32;
let mut result = length;
let expected = length / 4;
let (mut j, mut i) = (0_i32, 0_i32);
while j < length {
let char_j = s.chars().nth(j as usize).unwrap();
counter.insert(char_j, counter.get(&char_j).unwrap() - 1);
// sliding window
while i < length
&& counter[&'Q'] <= expected
&& counter[&'W'] <= expected
&& counter[&'E'] <= expected
&& counter[&'R'] <= expected
{
result = cmp::min(result, j - i + 1);
let char_i = s.chars().nth(i as usize).unwrap();
counter.insert(char_i, counter.get(&char_i).unwrap() + 1);
i += 1;
}
j += 1;
}
result
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
let s = "QWER".to_string();
assert_eq!(Solution::balanced_string(s), 0);
let s = "QQWE".to_string();
assert_eq!(Solution::balanced_string(s), 1);
}
}Some places in the code may be not necessary:
let char_j = s.chars().nth(j as usize).unwrap(); counter.insert(char_j, counter.get(&char_j).unwrap() - 1); which is actually the same as counter[c] += 1 in Python. Seems too long in Rust.while i < length && counter[&'Q'] <= expected && counter[&'W'] <= expected && counter[&'E'] <= expected && counter[&'R'] <= expected, it would be all([counter[x] <= expected for x in 'QWER']) in Python 😅Keyword: DP
Use [(ending_time, max_profit)] to keep track of possible best profit for each end time. For new job, use binary search to find the possible previous ending time for last job, and calculate whether the profit would be better than current best(last element in DP record), if so append it to the end of DP record vector.
struct Solution{}
impl Solution {
pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
let mut jobs = Vec::new();
let length = start_time.len();
for i in 0..length {
jobs.push((start_time[i], end_time[i], profit[i]))
}
jobs.sort_by_key(|t1| t1.1);
println!("{:?}", jobs);
let mut record = vec![(0, 0)]; // (ending, max_profit)
for (s, e, p) in jobs {
let last_job_index = match record.binary_search_by_key(&s, |&t| t.0) {
Ok(i) => i,
Err(i) => i-1,
};
println!("{}, {:?}, {}", s, record, last_job_index);
if record[last_job_index].1 + p > record.last().unwrap().1 {
record.push((e, record[last_job_index].1 + p))
}
}
record.last().unwrap().1
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test1 () {
let starts = vec![1,2,3,4,6];
let ends = vec![3,5,10,6,9];
let profit = vec![20,20,100,70,60];
assert_eq!(Solution::job_scheduling(starts, ends, profit), 150);
}
}Keyword: Cache
To make it not TLE we use a cache to reduce time cost. However in Rust it happened to be the very first HashMap I used and cost me some time to deal with compiler…finally made it pass with this code below. The <'a> is explicit lifetime which could be implicit.
use std::collections::HashMap;
// struct Solution {}
type Cache<'a> = HashMap<String, i32>;
impl Solution {
pub fn die_simulator(n: i32, roll_max: Vec<i32>) -> i32 {
let mut cache: Cache = HashMap::new();
fn helper<'a>(
k: i32,
number: i32,
n: i32,
roll_max: &Vec<i32>,
cache: &mut Cache<'a>,
) -> i32 {
if n == 0 {
return 1;
}
let key_string = format!("{} {} {}", k, number, n);
let ref key = key_string.to_string();
match cache.get::<str>(&key) {
Some(&number) => return number,
_ => {}
}
let mut temp: i64 = 0;
for i in 0..6 {
if number != i {
temp += helper(1, i, n - 1, roll_max, cache) as i64;
} else if k < roll_max[i as usize] {
temp += helper(k + 1, i, n - 1, roll_max, cache) as i64;
}
}
let result = (temp % (10_i64.pow(9) + 7)) as i32;
cache.insert(key_string, result);
// println!("temp: {}, result: {}", temp % (9_i64.pow(10) + 7), result);
result
}
helper(0, 0, n, &roll_max, &mut cache)
}
}Keyword: DP
It’s an interesting DP problem, as it only cares about 1<=n,m<=13 cases. For larger ranges it would become very complicated, please check this link for more info.
Solution in Rust:
use std::cmp::min;
struct Solution {}
impl Solution {
pub fn tiling_rectangle(n: i32, m: i32) -> i32 {
let mut record = vec![vec![0; n as usize + 1]; m as usize + 1];
record[0][0] = 1;
//special case
if (n == 11 && m == 13) || (n == 13 && m == 11) {
return 6;
}
for i in 0..m as usize + 1 {
for j in 0..n as usize + 1 {
if i == 0 || j == 0 {
record[i][j] = 0;
continue;
}
if i == j {
record[i][j] = 1;
continue;
}
let mut temp = 13*13;
for k in 1..=min(i, j) {
temp = min(temp,
min(1 + record[i-k][j] + record[k][j-k], 1 + record[i][j-k] + record[i-k][k])
);
}
record[i][j] = temp;
}
}
// println!("{:?}", record);
*record.last().unwrap().last().unwrap()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
assert_eq!(Solution::tiling_rectangle(2, 3), 3);
assert_eq!(Solution::tiling_rectangle(5, 8), 5);
assert_eq!(Solution::tiling_rectangle(11, 13), 6);
}
}