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

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

image.png

3 分 - 数组中的字符串匹配
4 分 - 查询带键的排列
5 分 - HTML 实体解析器
7 分 - 给 N x 3 网格图涂色的方案数

提供一个第四题DP的思路吧,先Orz一下数学大佬们

  • 由于1x3的一共只有12种放法, 因此以后每一行最多可能有12种放法(一定小于这个数).

我们用状态压缩来表示每种放法, 因为一个位置能填3种颜色, 因此我们可以用2个bit表示一个位置. 01-red 10-yellow 11-green. 因此, 可以用6个bits标示这些状态.

f[i][j]表示前i行, 第i行放状态j(j对应的二进制表示)一共有多少种方法. 所以最终答案就是f[n].sum()

由于f[i][j]只和f[i-1]有关, 因此可以把这一维省略

我们可以用f[j]来表示每种状态的可行解数目.

检查放法: 由于我们枚举的12种放法在水平上都是可行的, 因此我们只关心它和上一排是否有冲突. 由于进行了状态压缩, 因此很容易判断. 每个颜色占两个bits, 只需要看对应的bits是否完全一样, 如果有一样的, 说明颜色会冲突.

impl Solution {
    pub fn num_of_ways(n: i32) -> i32 {
        const MOD: i64 = 1000000007;
        if n == 1 {
            return 12;
        }
        let mut available = vec![];
        for i in 1..64usize { // 每个位置2bits, 只需要6位, 也就是最大0b111111=63
            let c1 = i & 3;
            let c2 = (i>>2)&3;
            let c3 = (i>>4)&3;
            if c1 !=0 && c2 != 0 && c3 != 0 && c3 != c2 && c2 != c1 {
                available.push(i);
            }
        }
        assert_eq!(12, available.len());
        let mut count = [0; 64];
        for &v in &available {
            count[v as usize] = 1i64;
        }
        for _ in 1..n {
            let mut new_count = [0; 64];
            for &pre_color in &available { // 枚举上一行的每种可行解
                let num = count[pre_color];
                if num == 0 {
                    continue;
                }
                let c1 = pre_color & 3;
                let c2 = (pre_color>>2)&3;
                let c3 = (pre_color>>4)&3;
                for &color in &available { // 枚举下一行怎么填
                    let t1 = color & 3;
                    let t2 = (color>>2)&3;
                    let t3 = (color>>4)&3;
                    if t1 != c1 && t2 != c2 && t3 != c3 { // 如果垂直方向无冲突
                        new_count[color] += num;
                        new_count[color] %= MOD;
                    }
                }
            }
            count = new_count;
        }
        ((count.iter().sum::<i64>()) % MOD) as i32
    }
}
展开全部 46 讨论