Rust入门练习-Week8-LC392/1048/389/1481/799

LC799. Champagne Tower Med

看了下数据范围，只能是从行列上来入手了，感觉是个递推

impl Solution {
    pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
        let mut dp = vec![vec![0.0; 100]; 100];
        let (query_row, query_glass) = (query_row as usize, query_glass as usize);
        dp[0][0] = poured as f64;
        for i in 0..query_row {
            for j in 0..=i {
                if dp[i][j] > 1.0 {
                    let q: f64 = (dp[i][j] - 1.0) / 2.0;
                    dp[i + 1][j] += q;
                    dp[i + 1][j + 1] += q;
                }
            }
        }
        dp[query_row][query_glass].min(1.0)
    }
}

LC1481. Least Number of Unique Integers after K Removals Med

贪心，按出现个数排序，从最少的删

impl Solution {
    pub fn find_least_num_of_unique_ints(arr: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let cnt = arr.iter().fold(HashMap::new(), |mut m, x| {
            *m.entry(x).or_insert(0) += 1;
            m
        });
        let mut cnts = cnt.iter().map(|(_, &v)| v).collect::<Vec<_>>();
        cnts.sort_unstable();
        let mut k = k;
        for i in 0..cnts.len() {
            if k >= cnts[i] {
                k -= cnts[i];
                cnts[i] = 0;
            } else {
                cnts[i] -= k;
                return cnts[i..].len() as i32;
            }
        }
        0
    }
}

LC389. Find the Difference Ez

use std::collections::HashMap;
impl Solution {
    pub fn find_the_difference(s: String, t: String) -> char {
        let (mut m1, mut m2) = (HashMap::new(), HashMap::new());
        for i in s.bytes() {
            *m1.entry(i).or_insert(0) += 1;
        }
        for i in t.bytes() {
            *m2.entry(i).or_insert(0) += 1;
        }
        for i in m2.keys() {
            if m1.get(i).unwrap_or(&0) != m2.get(i).unwrap() {
                return *i as char;
            }
        }
        ' '
    }
}
use std::collections::HashMap;

impl Solution {
    pub fn find_the_difference(s: String, t: String) -> char {
        let m1 = s.bytes().fold(HashMap::new(), |mut acc, b| {
            *acc.entry(b).or_insert(0) += 1;
            acc
        });
        let m2 = t.bytes().fold(HashMap::new(), |mut acc, b| {
            *acc.entry(b).or_insert(0) += 1;
            acc
        });

        m2.iter()
            .find(|&(k, v)| m1.get(k).unwrap_or(&0) != v)
            .map(|(&k, _)| k as char)
            .unwrap()
    }
}

LC1048. Longest String Chain Med

最多1000个词，答案最多16项，考虑dp

先按长度排个序，分割一下，wordsi表示第j个长度为i的单词

dpi 表示目前长度为i，使用了第j个单词的可达性

dpi -> dpi+1 if j -> k

最后倒序看dp[i] 是否存在true

复杂度N^2乘个常数可过，这常数均摊应该不大的

惭愧，这代码基本上都是Copilot写的，我就写了点注释，改了改bug

impl Solution {
    pub fn longest_str_chain(words: Vec<String>) -> i32 {
        // a closure to check if a word is a predecessor of another word
        let is_predecessor = |a: &str, b: &str| -> bool {
            if a.len() + 1 != b.len() {
                return false;
            }
            let mut i = 0;
            let mut j = 0;
            let mut diff = 0;
            while i < a.len() {
                if a.chars().nth(i).unwrap() != b.chars().nth(j).unwrap() {
                    diff += 1;
                    if diff > 1 {
                        return false;
                    }
                    j += 1;
                } else {
                    i += 1;
                    j += 1;
                }
            }
            true
        };
        // separate words by length
        let mut words_by_length: Vec<Vec<String>> = vec![vec![]; 17];
        for word in words.iter() {
            words_by_length[word.len()].push(word.clone());
        }
        // dp[i][j] is the if length i string can ending with words_by_length[i][j]
        let mut dp: Vec<Vec<i32>> = vec![vec![1; 1000]; 17];
        let mut max_chain = 1;
        for i in 1..17 {
            for j in 0..words_by_length[i].len() {
                for k in 0..i {
                    for l in 0..words_by_length[k].len() {
                        if is_predecessor(&words_by_length[k][l], &words_by_length[i][j]) {
                            dp[i][j] = dp[i][j].max(dp[k][l] + 1);
                            max_chain = max_chain.max(dp[i][j]);
                        }
                    }
                }
            }
        }
        max_chain
        
    }
}

LC392. Is Subsequence Ez

impl Solution {
    pub fn is_subsequence(s: String, t: String) -> bool {
        let (mut p1, mut p2) = (0, 0);
        let (s, t) = (s.as_bytes(), t.as_bytes());
        while p1 < s.len() && p2 < t.len() {
            if s[p1] == t[p2] {
                p1 += 1;
            }
            p2 += 1;
        }
        p1 == s.len()
    }
}