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

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

image.png

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

前三题简单:暴力、模拟、调库就能过(第三题需要注意得把"&"放到最后,以免出现">"这样的情况)。
第四题分享一下我的思路吧。
题目例子很良心的给了n=1时的12种情况,可以利用这一点来计算。
建立一个ways[12]的数组,数组中的值对应着以这种情况为最后一行的情况数。比如ways[RYR]表示以RYR为最后一行的情况数。
n=1时,显然,ways[i]=1。
之后,每种情况的个数都是“能接在后面的情况数”之和。比如,对于RYR而言,其能接在YRY、GRY、YRG、GRG、YGY后面,因此ways[RYR]=ways[YRY]+ways[GRY]+ways[YRG]+ways[GRG]+ways[YGY]。可以利用这点来更新ways这个数组。
更新(n-1)次后,只要把ways数组的元素求和就能得到答案了。取模可以在每次加法运算后取。

public class Solution {
    public long[]update(long[]ways,string[]pattern){
        long[]result=new long[12];
        for(int i=0;i<12;i++)
            result[i]=0;
        for(int i=0;i<12;i++){
            for(int j=0;j<12;j++){
                if(pattern[i][0]!=pattern[j][0]&&pattern[i][1]!=pattern[j][1]&&pattern[i][2]!=pattern[j][2]){
                    result[i]=(result[i]+ways[j])%1000000007;
                }
            }
        }
        return result;
    }
    public int NumOfWays(int n) {
        string[]pattern=new string[]{"RYR","YRY","GRY","RYG","YRG","GRG","RGR","YGR","GYR","RGY","YGY","GYG"};
        long[] ways=new long[12];
        for(int i=0;i<12;i++)
            ways[i]=1;
        for(int i=1;i<n;i++)
            ways=update(ways,pattern);
        long result=0;
        for(int i=0;i<12;i++)
            result=(result+ways[i])%1000000007;
        return (int)result;
    }
}
展开全部 46 讨论