LEETCODE 1411. Number of Ways to Paint N × 3 Grid 解题思路分析

题目大意:

给 N x 3 网格图涂色的方案数

你有一个 n x 3 的网格图 grid ,你需要用 红,黄,绿 三种颜色之一给每一个格子上色,且确保相邻格子颜色不同(也就是有相同水平边或者垂直边的格子颜色不同)。

给你网格图的行数 n 。

请你返回给 grid 涂色的方案数。由于答案可能会非常大,请你返回答案对 10^9 + 7 取余的结果。

示例 1:

输入:n = 1
输出:12
解释:总共有 12 种可行的方法:

示例 2:

输入:n = 2
输出:54

示例 3:

输入:n = 3
输出:246

示例 4:

输入:n = 7
输出:106494

示例 5:

输入:n = 5000
输出:30228214

提示:

  • n == grid.length
  • grid[i].length == 3
  • 1 <= n <= 5000

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1411

解题思路分析:

本周参加周赛的状态实际上还是不错的,前三题只用了不到20分钟,但读完第四题也就是本题之后,肚子突然翻江倒海,让我不得不在厕所耗费了近50分钟。再回来做本题时已毫无状态,只能用了一个很low的解法算是蒙混过关,今后有时间我会重新优化一下本题的写法。

回到本题,实际上本题的思路还是非常清晰的,由于一行只有3列,因此保证每一行内不重复的排列方式一共有12种。推导过程为;第一个格子有3种选择,第二个格子由于不能与相邻的第一个格子相同,因此只有2种选择,同理,第三个格子不能与相邻的第二个格子颜色相同,因此也只有2种选择。3乘以2再乘以2等于12种。这12种组合实际上就是题目例子1中给出的排列方式:

当存在n行时,当前行能够选取上述哪几种组合,完全取决于相邻的上一行的情况。为了方便描述,我们为上述12中方式编号为0-11(如何编号,看个人喜好),之后,我们分别找出每一个图形的相邻行能摆放哪些图形。比如编号0的下方可以连接编号1,2,4,5,10,这样会保证他们之间每一个相邻的格子都不重复。再比如编号7下面可以连接2,3,5,11。由于总体的数量不是很多,因此我用肉眼,统计出了每一种编号下方可以连接的其他编号。我们使用一个boolean型数组来记录他们之间的关系,boolean[i][j]表示编号i和j是否可以相连。

boolean[][] map = new boolean[12][12];
map[0][1]=true;
map[0][2]=true;
map[0][4]=true;
map[0][5]=true;
map[0][10]=true;

map[1][0]=true;
map[1][3]=true;
map[1][6]=true;
map[1][8]=true;
map[1][11]=true;

map[2][0]=true;
map[2][3]=true;
map[2][6]=true;
map[2][7]=true;

map[3][1]=true;
map[3][2]=true;
map[3][7]=true;
map[3][10]=true;

map[4][0]=true;
map[4][6]=true;
map[4][8]=true;
map[4][9]=true;

map[5][0]=true;
map[5][6]=true;
map[5][7]=true;
map[5][9]=true;
map[5][10]=true;

map[6][1]=true;
map[6][2]=true;
map[6][4]=true;
map[6][5]=true;
map[6][11]=true;

map[7][2]=true;
map[7][3]=true;
map[7][5]=true;
map[7][11]=true;

map[8][1]=true;
map[8][3]=true;
map[8][9]=true;
map[8][10]=true;

map[9][4]=true;
map[9][5]=true;
map[9][8]=true;
map[9][11]=true;

map[10][0]=true;
map[10][3]=true;
map[10][5]=true;
map[10][8]=true;
map[10][11]=true;

map[11][1]=true;
map[11][6]=true;
map[11][7]=true;
map[11][9]=true;
map[11][10]=true;

接下来我们可以将本题想象为一个多叉树,多叉树的第一层有12个节点。然后每个节点都有多个子节点,这里的子节点实际上就是能与当前编号相连接的其他编号,我们只要统计出第n层存在节点的数量,就是我们本题的结果。

解题时可以使用dfs来递归所有路径。实现代码:

int[][] memo;
public int numOfWays(int n) {
    memo=new int[12][n];
    boolean[][] map = new boolean[12][12];
    map[0][1]=true;
    map[0][2]=true;
    map[0][4]=true;
    map[0][5]=true;
    map[0][10]=true;
    map[1][0]=true;
    map[1][3]=true;
    map[1][6]=true;
    map[1][8]=true;
    map[1][11]=true;
    map[2][0]=true;
    map[2][3]=true;
    map[2][6]=true;
    map[2][7]=true;
    map[3][1]=true;
    map[3][2]=true;
    map[3][7]=true;
    map[3][10]=true;
    map[4][0]=true;
    map[4][6]=true;
    map[4][8]=true;
    map[4][9]=true;
    map[5][0]=true;
    map[5][6]=true;
    map[5][7]=true;
    map[5][9]=true;
    map[5][10]=true;
    map[6][1]=true;
    map[6][2]=true;
    map[6][4]=true;
    map[6][5]=true;
    map[6][11]=true;
    map[7][2]=true;
    map[7][3]=true;
    map[7][5]=true;
    map[7][11]=true;
    map[8][1]=true;
    map[8][3]=true;
    map[8][9]=true;
    map[8][10]=true;
    map[9][4]=true;
    map[9][5]=true;
    map[9][8]=true;
    map[9][11]=true;
    map[10][0]=true;
    map[10][3]=true;
    map[10][5]=true;
    map[10][8]=true;
    map[10][11]=true;
    map[11][1]=true;
    map[11][6]=true;
    map[11][7]=true;
    map[11][9]=true;
    map[11][10]=true;
    long res=0;
    for(int i=0;i<12;i++){
        res+=help(map,i,1,n);
    }
    return (int)(res%1000000007);
}

int help(boolean[][] map, int preRowType, int row,int n){
    if(row==n) return 1;
    if(memo[preRowType][row]>0) return memo[preRowType][row];
    long count=0;
    for(int i=0;i<12;i++){
        if(map[preRowType][i]){
            count+=help(map,i,row+1,n);
        }
    }
    int res = (int)(count%1000000007);
    memo[preRowType][row]=res;
    return res;
}

本题解法执行时间为27ms。

Runtime: 27 ms, faster than 26.23% of Java online submissions for Number of Ways to Paint N × 3 Grid.

Memory Usage: 39.2 MB, less than 100.00% of Java online submissions for Number of Ways to Paint N × 3 Grid.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1411-number-of-ways-to-paint-n-x-3-grid-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。