[数据结构与算法]rust leetcode 周赛 286

模拟比赛，1:33:00（超时3分钟），no dirty，第一名时间 0:10:40。。。猫猫疑惑，写同样的题目花人家9倍时间，酱紫慢？

rust snippet:

1. 从 vec 构建 hashset：HashSet::<i32>::from_iter(nums1.into_iter());，里面也可以是 .iter.clone()
2. reverse string：.chars().rev().collect::<String>()
3. string 不能加 string，但可以加 &str，可以用 & 或者 .as_ref() 转
4. 没找到优雅的在 vec 前面插入零的链式方法。
   update：问了nb群友得到了答案，std::iter::once(0).chain(...) 就行。

链式写法相比 c++ 确实太爽了。

tips:

1. 遇事不决开始 dp，先从慢的方法想起，注意题目数据范围隐含的时间复杂度要求，可能慢的也可以
2. 二维 dp 可以考虑滚动数组，或者原地 dp 来节省空间。

2215 找出两数组的不同

impl Solution {
pub fn find_difference(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<Vec<i32>> {
    use std::collections::HashSet;
    use std::iter::FromIterator;
    let nums1 = HashSet::<i32>::from_iter(nums1.into_iter());
    let nums2 = HashSet::<i32>::from_iter(nums2.into_iter());

    vec![
        nums1.iter().filter(|&x| !nums2.contains(x)).map(|&x| x).collect(),
        nums2.iter().filter(|&x| !nums1.contains(x)).map(|&x| x).collect(),
    ]
}
}

2216 美化数组的最少删除数

impl Solution {
pub fn min_deletion(nums: Vec<i32>) -> i32 {
    /*
    dp[i] = nums[0..=i] 已经被删了若干，剩下一个子序列，长度为偶数且满足要求，的最小删除数。
    dp[0] = 1
    dp[1] = a[0] == a[1] ? 2 : 0
    dp[2] = min(dp[0] + a[1]==a[2]?2:0, dp[1]+1);

    dp[i] = min(dp[i-2] + a[i-1]==a[i]?2:0, dp[i-1]+1);
    */
    let mut dp = vec![0; nums.len()];
    dp[0] = 1;
    if nums.len() > 1 {
        dp[1] = if nums[0] == nums[1] {2} else {0};
    }
    for i in 2..nums.len() {
        dp[i] = std::cmp::min(dp[i-2] + if nums[i] == nums[i-1] {2} else {0}, dp[i-1] + 1);
    }
    dp[nums.len()-1]
}
}

2217 找到指定长度的回文数

impl Solution {
fn kth_palindrome_helper(query: i32, len: i32) -> i64 {
    if len % 2 == 0 {
        if query > 9 * i32::pow(10,len as u32 / 2 - 1) {
            return -1;
        }
        let num = i32::pow(10, len as u32 / 2 - 1) + query - 1;
        let str = num.to_string() + num.to_string().chars().rev().collect::<String>().as_ref();
        return str.parse::<i64>().unwrap();
    }
    if query > 9 * i32::pow(10,len as u32 / 2) {
        return -1;
    }
    let num = i32::pow(10, len as u32 / 2) + query - 1;
    let str = num.to_string() + num.to_string().chars().rev().collect::<String>()[1..].as_ref();
    return str.parse::<i64>().unwrap();
}

pub fn kth_palindrome(queries: Vec<i32>, int_length: i32) -> Vec<i64> {
    queries.iter().map(|&x| Solution::kth_palindrome_helper(x, int_length)).collect()
}

}

2218 从栈中取出 K 个硬币的最大面值和

impl Solution {
pub fn max_value_of_coins(piles: Vec<Vec<i32>>, k: i32) -> i32 {
    let k = k as usize;
    /*
    dp[i][j] 在 0..=i 中取 j 个硬币的最大价值
    答案是 dp[n-1][k]

    dp[i][j] = max_{u=0..=min(j, piles[i].len())} dp[i-1][j-u] + piles_sum[i][u]
        note, sum[0] = 0.
    */
    let sum = piles.iter().map(
        |pile| {
            let mut t = pile.iter().scan(
                0, |acc, &x| {*acc += x; Some(*acc)}
            ).collect::<Vec<i32>>();
            t.insert(0, 0);
            t
        }
    ).collect::<Vec<Vec<i32>>>();
    let mut dp = vec![vec![0; k+1]; piles.len()];

    for i in 0..piles.len() {
        if i == 0 {
            for j in 0..=k.min(piles[0].len()) {
                dp[i][j] = sum[i][j];
            }
            continue;
        }
        for j in 0..=k {
            for u in 0..=j.min(piles[i].len()) {
                dp[i][j] = dp[i][j].max(dp[i-1][j-u] + sum[i][u]);
            }
        }
    }
    
    dp[piles.len() - 1][k]
}
}

阅读世界，共赴山海

423全民读书节，邀你共读