As I’m learning Rust recently, LeetCode has become a good place to write small programs 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 than I expected to deal with the strict compiler. Pretty fun though, and I think it did help me get my hands dirty.
However, personally I won’t suggest using Rust in LeetCode contests or in real interviews as Python/Ruby would be a much better choice. Rust could be useful in some other aspects which I’ll check later. (safety, speed, and concurrency? + WebAssembly) 🦀️
1234. Replace the Substring for Balanced String
Keyword: Sliding window
Use a counter to keep track of the appearances outside of the sliding window, and try to make 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:
- Update a counter’s value for a character, I’m using:
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 ascounter[c] += 1in Python. Seems too long in Rust. - For the place
while i < length && counter[&'Q'] <= expected && counter[&'W'] <= expected&& counter[&'E'] <= expected && counter[&'R'] <= expected, it would beall([counter[x] <= expected for x in 'QWER'])in Python 😅
1235. Maximum Profit in Job Scheduling
Keyword: DP
Use [(ending_time, max_profit)] to keep track of possible best profit for each end time. For a new job, use binary search to find the possible previous ending time for the last job, and calculate whether the profit would be better than the current best (last element in the DP record); if so, append it to the end of the 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);
}
}1223. Dice Roll Simulation
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 the compiler. I finally made it pass with the code below. The <'a> is an 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)
}
}1240. Tiling a Rectangle with the Fewest Squares
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);
}
}