LCP-22-黑白方格画阶

LCP-22-黑白方格画

题目描述

• 小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色，所选行数、列数均可为 0。
• 小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。

注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。

示例 1：

输入：n = 2, k = 2

输出：4

解释：一共有四种不同的方案：
第一种方案：涂第一列；
第二种方案：涂第二列；
第三种方案：涂第一行；
第四种方案：涂第二行。

示例 2：

输入：n = 2, k = 1

输出：0

解释：不可行，因为第一次涂色至少会涂两个黑格。

示例 3：

输入：n = 2, k = 4

输出：1

解释：共有 2*2=4 个格子，仅有一种涂色方案。

算法思路

• 首先我们要明确几个特殊值
  • k=0时，返回值res=1（就是一格都不涂）
  • k<n时，返回值res=0（一行或者一列都涂不满）
  • k=n^2时，返回值res=1（全涂）

• 然后我们来分析一般情况

  • 假设我涂了i行，j列，那么一共所涂的方块数应该为 in+j(n-i) 注意因为我们先涂了行，再涂列时每涂一列变黑的方块数应为（n-i）
  • 由题意，k=in+j(n-1)，那么倒推一下就可以知道j=(k-i*n)/(n-i)
  • 那么怎么判断所取的i,j是否满足题意呢？
    • 只需要知道j是否为整数就行了，因为j不为整数时，相当于没有涂满一列。

• 最后再利用排列组合算出每一组i，j的情况C（n,i）*C(n,j)，再相加就是最后结果

class Solution {
    public static int paintingPlan(int n, int k) {
        // 1. 特判
        if(k == 0){         // 一个格子都不太涂
            return 1;
        }
        if(k < n){          // 任意一行或者一列都涂不满
            return 0;
        }
        if(k == n* n){      // 涂满所有的行和列
            return 1;
        }

        int res = 0;
        float i;            // 行
        float j;            // 列

        // 2. 普通情况 : 假设涂了i行,j列 那么一共涂的方块数应该是 in + j(n - i), 那么k = in + j(n - i) 可以得到 j = (k-in)/(n - i)
        for(i = 0;i < n;i++){
            float x = (k - n * i)/(n - i);
            if(x != (int) x){               // 判断x是否为整数
                continue;                   // 这种方案不可行 跳过
            }
            j = (int)x;
            i = (int)i;
            res += combine(n, (int) i) * combine(n, (int) j); // 最后再利用排列组合算出每一组i，j的情况C（n,i）*C(n,j)，再相加就是最后结果
        }
        return res;
    }

    // 求排列组合
    public static int combine(int x,int y){
        if(y == 0){
            return 1;
        } 
        if(y < 0){
            return 0;
        }

        int m = 1,n = 1,z = x - y + 1;
        while(x >= z){
            m *= x;
            x--;
        }
        while(y > 0){
            n *= y;
            y--;
        }
        return m/n;
    }
}

打赏