讨论/题目交流/🏆 第 162 场力扣周赛/
🏆 第 162 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 奇数值单元格的数目
4 分 - 重构 2 行二进制矩阵
5 分 - 统计封闭岛屿的数目
6 分 - 得分最高的单词集合

四道暴力

第一题

暴力枚举

第二题

先把colsum==2的填了,剩下的从左到右去填就行了,中间发现无法填直接返回empty

第三题

BFS染色,在染的过程中注意标记一下是不是染到边界了,染到边界了就不是isolated island,否则才是

第四题

看了下数据规模,2^14,完全可以暴力。因此,先dfs出要拼哪几个单词,最后算一下每种组合的总得分,取最大值即可


impl Solution {
    pub fn max_score_words(words: Vec<String>, letters: Vec<char>, score: Vec<i32>) -> i32 {
        let n = words.len();
        if n == 0 {
            return 0;
        }
        if letters.is_empty() {
            return 0;
        }
        let mut letter_count = vec![0; 26];
        for c in letters {
            letter_count[(c as u8 - b'a') as usize] += 1;
        }
        let mut used = vec![false; n];
        let mut ans = 0;
        Self::dfs(0, &words, &mut used, &letter_count, &score, &mut ans);
        ans
    }
    fn dfs(cur: usize, words: &Vec<String>, used: &mut Vec<bool>, char_count: &Vec<i32>, score: &Vec<i32>, ans: &mut i32) {
        if cur >= words.len() {
            let mut count = vec![0; 26];
            let mut get_score = 0;
            for i in 0..words.len() {
                if used[i] {
                    for &c in words[i].as_bytes() {
                        let pos = (c - b'a') as usize;
                        count[pos] += 1;
                        get_score += score[pos];
                        if count[pos] > char_count[pos] {
                            return;
                        }
                    }
                }
            }
            if get_score > *ans {
                *ans = get_score;
            }
            return;
        }
        for i in cur..words.len() {
            Self::dfs(i+1, words, used, char_count, score, ans);
            used[i] = true;
            Self::dfs(i+1, words, used, char_count, score, ans);
            used[i] = false;
        }
    }
}
1
展开全部 22 讨论