首页 > 试题广场 >

填充数组

[编程题]填充数组
  • 热度指数：4335 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

牛妹给了牛牛一个长度为 的下标从开始的正整型数组 ，粗心的牛牛不小心把其中的一些数字删除了。

假如被删除了，则。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：

  • 且对于所有的满足 。

函数传入一个下标从开始的数组 和一个正整数 ，请返回合法的填充方案数对 取模的值,保证不存在方案数为0的数据。

示例1

输入

[0,4,5],6

输出

4

说明

所有的合法填充方案是：[1,4,5],[2,4,5],[3,4,5],[4,4,5]，共4种。
示例2

输入

[1,0,0],3

输出

6

说明

所有的合法填充方案是：[1,1,1],[1,1,2],[1,2,2],[1,2,3],[1,3,3],[1,1,3]共6种
示例3

输入

[0,0,0,0,0,67,0,0],100

输出

746845806

备注:
数组满足
算法知识视频讲解
添加回答
秋喀喀喀头像 秋喀喀喀
双指针+一维数组优化+CPP
5ms 
444KB
利用双指针来确定连续0的区域，确定连续0的左端点值设为min，右端点值设为max，那么区域内的0只能用[min,max]中的值来填充，当只有一个0的时候，总方案数就是[min,max]内的值都选择一次，故可以设置一个数组tmp,其长度为max-min+1，为方便理解，不妨设下标为min-max，表示第一个0填充的值等于下标时的方案数，比如若第一个0用min去填充，那么tmp[min]就代表第一个0填充min时的方案数，那么总的方案数就是tmp[min]+...+tmp[max]，tmp[]初始化全为1，因为只有一个0时，只能填充一次，采用“后缀和”也就是从后往前累加，如此tmp[min]就是总方案数：tmp[min]=max-min+1,这样做也是为了方便后续处理不止一个0时的情况；
当有两个连续0时，先固定第一个0的取值，然后去填充第二个0，第一个0填充min，那么tmp[min]就等于填充第二个0的可行方案数：大于等于min，小于等于max的填充值的个数max-min+1；第一个0填充min+1时，tmp[min+1]就等于填充第二个0的可行方案数：大于等于min+1，小于等于max的填充值的个数max-min......第一个0填充max时，tmp[max]就等于填充第二个0的方案数：等于max的个数:1。可以发现和“后缀和”处理后的tmp[]一致，那么同样后缀和处理，此时tmp[min]就是两个连续0时的总方案数；
依此类推，每多一个0就后缀和处理一次。
同时，为了不用特别处理边界问题，可以用值1作为起始值，k作为末尾值

  
class Solution {
public:
    int FillArray(vector<int>& a, int k) {
        vector<long long> res;
        long long ans=1,mod=1000000007;
        long len=a.size(),l=0,r=0;
        a.insert(a.begin(),1);
        a.push_back(k);
        for(long i=0;i<len+2;i++){
            if(a[i]==0){
                l=i-1;
                while(a[i]==0)
                    i++;
                r=i;
                vector<long long> tmp(a[r]-a[l]+1,1);
                for(long j=r-l-1;j>0;j--){
                    for(long long t=a[r]-a[l]-1;t>=0;t--){
                        tmp[t]+=tmp[t+1]%mod;//样例数很恶心，时刻注意取余
                    }
                }
                res.push_back(tmp[0]%mod);
            }
        }
        for(long i=0;i<res.size();i++)
            ans=(ans*res[i])%mod;
        return ans;
    }
};

编辑于 2022-02-28 23:52:23 回复(0)
Java
牛客226198207号头像 牛客226198207号
运行时间70ms
占用内存14716KB
   1.必须要使用BigInteger,不然会溢出;
    2.方案数拆开来其实是个简单的数列自增问题
    3.fillZero方法是关键(不要递归,递归效率会崩)因为太久不做数学题导致敏感性下降,结果很简单的问题本来看懂了规律却没想出来公式,只能套递归,崩了,参考了评论里的第一条才想明白公式原来这么简单,看来人已经废了...

    public int FillArray (int[] a, int k) {
        // write code here
        return findSolution(a,k).mod(BigInteger.valueOf(1000000007)).intValue();
    }
    private BigInteger findSolution (int[] a, int k) {
        int[] b = new int[a.length+2];
        b[0] = 1;
        b[b.length-1] = k;
        System.arraycopy(a,0,b,1,a.length);

        BigInteger res = BigInteger.ONE;
        int begin=1;
        int lastIndex = b.length-1;

        while(begin<lastIndex){
            while(0!=b[begin]){
                if (lastIndex == begin) return res;
                begin++;
            }
            int min= b[begin-1];
            int zero=0;
            while(0==b[begin]){
                zero++;
                begin++;
            }
            int max= b[begin];
            int sols= max-min+1;
            res = res.multiply(fillZero(sols,zero));
        }
        return res;
    }

   private BigInteger fillZero (int sols, int zero) {
        if (zero > 1) {
            BigInteger[] prob = new BigInteger[sols];
            for (int i=0;i<sols;i++){
                prob[i]= BigInteger.valueOf(i+1);
            }
            while (zero-->1){
                BigInteger[] temp = new BigInteger[sols];
                for (int j=1;j<sols;j++){
                    prob[j]=prob[j-1].add(prob[j]);
                }
            }
            return prob[sols-1];
        } else {
            return BigInteger.valueOf(sols);
        }
    }
编辑于 2021-12-13 23:58:52 回复(0)
唐氏综合征头像 唐氏综合征
这道题，除了使用动态规划，其他的方法很难跑通示例，原因就是精度不够精确导致的结果误差很大，如下的解法是非动态规划解法，是可以通过的，原理如下：

1. 遍历数组，找到值为 0 的下标范围
2. 对 0 的值进行填充，填充时考虑到第一个0前面一个元素，最后一个0后面一个元素以及k，找到可能的范围 len
3. 如果当前 0 的范围为 [i, j-1], 则该范围内都有可能取值 [1, len], 并且要保证顺序（高斯算法，数学证明略）
   ① 当有2个0时，可能性为 (1+2+...+ len) * len /2*1 ，即 (len+1)*len/(2*1)
   ② 当有n个0时,可能性为 len * (len+1) * ...*(len+n-1) / (n!), 其实就是一个 (len+n-1) 中选择 n 个的随机组合，并不考虑顺序，因此相当于 C(len+n-1，n)
4. 代码如下，一定要注意精度！！否则过不了！ 

import java.util.*;

import java.math.BigDecimal;

public class Solution {

    private static final int MOD = 1000000007;
    public static int FillArray(int[] a, int k) {
        // write code here
        BigDecimal res = new BigDecimal(1);
        int i = 0;
        while (i < a.length) {
            if (a[i] == 0) {
                int j = i + 1;
                while (j < a.length && a[j] == 0)
                    j++;
                int len = j < a.length ? a[j] : k;
                if (i > 0) len -= a[i - 1] - 1;
                len += j - i - 1;
                res =  res .multiply(C(len, j - i));
                i = j;
            } else
                i++;
        }
        return res.remainder(BigDecimal.valueOf(MOD)).intValue();
    }

    // 求出 m 中选出 n 的所有可能数，不考虑顺序
    private static BigDecimal C(int m, int n) {
        BigDecimal res = new BigDecimal(1);
        for (int i = m; i > m - n; i--)
            res = res.multiply(BigDecimal.valueOf(i));
        for (int i = n; i >= 1; i--)
            res  = res.divide(BigDecimal.valueOf(i));
        return res;
    }

}


二： 接下来介绍 DP 解法：


其实 DP 解法为了累加历史的可能性数，考虑了两件事

1. 如果当前元素的值为0，那么意味着当前元素可以填充 1~k 的任意值，因此要累加填充 1~k 时的任意可能性，此时的情况并未考虑前后元素非递减的约束
2. 如果当前元素值不为0，那么只有一种可能性，就是填充当前元素，直接继承上一个状态的可能性值即可，如何进行状态传递呢？我们知道需要考虑到前后两个元素的非递减特性，因此下一个元素一定不能小于上一个元素，已知当前元素的右边界为 j， 因此我们不妨在当前元素值等于j的时候开始传递状态值，即 a[i-1] = j， 这个条件满足时，则开始将上个dp的中的状态传递过来，给到sum累加进去,使得 sum > 0 , 表示历史累加值，这只是 a[i-1] = j 的情况，j >= a[i-1] 时，也应该保持这个累加值不变,因为只有一种情况

3. 当再次遇到0时，sum 的值总是在上一个元素对应值的基础上才开始累加，其他时间全为0，这就保证了全局非递减特性
4. 最后，dp[n][k] 对应的值就是n个数，最大值不超过k的最终累加的结果


原始版的代码如下： 

public class Solution {
    private static final int MOD = 1000000007;

    public int FillArray(int[] a, int k) {
        int n = a.length;
        long[][] dp = new long[n + 1][k + 1];

        // 初始化第一行
        for (int j = 0; j <= k; j++) {
            dp[0][j] = 1;
        }

        for (int i = 1; i <= n; i++) {
            long sum = 0;
            for (int j = 1; j <= k; j++) {
                if (a[i - 1] == 0 && i == 1)
                    dp[i][j] = j;
                else {
                    if (a[i - 1] == 0 || a[i - 1] == j) {
                        sum = (sum + dp[i - 1][j]) % MOD;
                    }
                     dp[i][j] = sum;
                }

            }
        }

        return (int) dp[n][k];
    }
}

上述代码的 i == 1 的情况可以优化，因为初始的累加步长就是1，当第一次遇到0满足条件触发累加时，就是从 1,2,3... 累加的，因此简化如下：

public class Solution {
    private static final int MOD = 1000000007;

    public int FillArray(int[] a, int k) {
        int n = a.length;
        long[][] dp = new long[n + 1][k + 1];
        
        // 初始化第一行
        for (int j = 0; j <= k; j++) {
            dp[0][j] = 1;
        }
        
        for (int i = 1; i <= n; i++) {
            long sum = 0;
            for (int j = 1; j <= k; j++) {
                if (a[i-1] == 0 || a[i-1] == j) {
                    sum = (sum + dp[i-1][j]) % MOD;
                }
                dp[i][j] = sum;
            }
        }
        
        return (int) dp[n][k];
    }



发表于 2024-07-16 09:23:29 回复(0)
tach1koma头像 tach1koma 
class Solution {
public:
    int FillArray(vector<int>& a, int k) {
        int n = a.size();
        vector<vector<int> > dp(n + 1, vector<int>(k + 1));
        const int MOD = 1000000007;
        for (int j = 1; j <= k; ++j)
            dp[1][j] = j;
        for (int i = 2; i <= n; ++i)
            dp[i][0] = 0;
        for (int i = 2; i <= n; ++i)
            for (int j = 1; j <= k; ++j)
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
        int i = 0;
        int ans = 1;
        while (i < n) {
            while (i < n && a[i] != 0)
                ++i;
            if (i == n)
                break;
            int st = i;
            int lo = (i > 0 ? a[i-1] : 1);
            while (i < n && a[i] == 0)
                ++i;
            int ed = i;
            int hi = (i < n ? a[i] : k);
            ans = ((long long)ans * dp[ed-st][hi-lo+1]) % MOD;
        }
        return ans;
    }
};
发表于 2022-01-13 15:35:58 回复(0)
s1mplecc头像 s1mplecc

通过全部用例
运行时间 220ms
占用内存 17744KB

public class Solution {

    private static final long MOD_VALUE = 1000000007L;
    private static final int THRESHOLD = 10;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param a int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int fillArray(int[] a, int k) {
        // write code here
        int start = 1, end = k;
        int count = 0;
        BigInteger result = BigInteger.ONE;

        int[] a1 = new int[a.length + 2];
        a1[0] = 1;
        a1[a.length + 1] = k;
        System.arraycopy(a, 0, a1, 1, a.length);

        for (int i = 0; i < a1.length; i++) {
            if (a1[i] != 0) {
                if (count == 0) {
                    start = Math.max(1, a1[i]);
                } else {
                    end = Math.min(a1[i], k);
                    result = result.multiply(BigInteger.valueOf(partialFillArray(start, count, end)));
                    count = 0;
                    start = end;
                }
            } else {
                count++;
            }
        }

        return mod(result);
    }

    // [start, 0, ... , 0, end]
    public int partialFillArray(int start, int count, int end) {
        System.out.printf("[%d, 0 * %d, %d]\n", start, count, end);
        int n = end - start + 1;
        if (count < THRESHOLD || n < THRESHOLD) {
            return partialFillArray(n, count);
        } else {
            return bigIntegerPartialFillArray(n, count);
        }
    }

    private int partialFillArray(int n, int count) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = 1;
        }

        for (int i = 1; i < count; i++) {
            for (int j = n - 2; j >= 0; j--) {
                array[j] = array[j] + array[j + 1];
            }
        }

        return Arrays.stream(array).sum();
    }

    private int bigIntegerPartialFillArray(int n, int count) {
        BigInteger[] array = new BigInteger[n];
        for (int i = 0; i < n; i++) {
            array[i] = BigInteger.ONE;
        }

        for (int i = 1; i < count; i++) {
            for (int j = n - 2; j >= 0; j--) {
                array[j] = array[j].add(array[j + 1]);
            }
        }

        BigInteger sum = Arrays.stream(array).reduce(BigInteger.ZERO, (x, y) -> x = x.add(y));
        return mod(sum);
    }

    private int mod(BigInteger result) {
        return result.remainder(BigInteger.valueOf(MOD_VALUE)).intValue();
    }
}

测试用例

public class SolutionTest {
    private final Solution solution = new Solution();
    @Test
    public void should_fill_array_correct_for_case1() {
        int[] a = new int[]{0, 4, 5};
        int k = 6;
        int result = solution.fillArray(a, k);
        assertThat(result).isEqualTo(4);
    }
    @Test
    public void should_fill_array_correct_for_case2() {
        int[] a = new int[]{1, 0, 0};
        int k = 3;
        int result = solution.fillArray(a, k);
        assertThat(result).isEqualTo(6);
    }
    @Test
    public void should_fill_array_correct_for_case3() {
        int[] a = new int[]{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 58, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 104, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 182, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 410, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 450, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 564, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 585, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 895, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        int k = 1000;
        int result = solution.fillArray(a, k);
        assertThat(result).isEqualTo(232250860);
    }
    @Test
    public void should_fill_array_correct_for_case4() {
        int[] a = new int[]{1, 0, 2, 0, 0, 4};
        int k = 3;
        int result = solution.fillArray(a, k);
        assertThat(result).isEqualTo(6);
    }
    @Test
    public void should_fill_array_correct_for_case5() {
        int[] a = new int[]{2, 3, 0, 5, 0, 7, 8, 8, 9, 10, 11, 12, 12, 12, 13, 0, 14, 0, 0, 0, 0, 17, 17, 20, 20, 21, 21, 21, 22, 22, 22, 23, 0, 23, 0, 25, 0, 0, 0, 27, 30, 30, 31, 31, 31, 32, 32, 33, 0, 34, 0, 34, 35, 35, 0, 36, 0, 37, 0, 38, 0, 0, 39, 39, 40, 40, 40, 41, 0, 0, 42, 42, 0, 43, 45, 0, 46, 47, 0, 47, 47, 0, 48, 0, 50, 0, 51, 52, 52, 52, 53, 53, 54, 54, 54, 55, 55, 55, 55, 56, 0, 56, 0, 57, 57, 58, 59, 59, 0, 60, 0, 0, 63, 63, 64, 0, 66, 66, 67, 67, 0, 0, 68, 68, 0, 69, 0, 70, 0, 70, 71, 72, 0, 73, 73, 73, 73, 74, 0, 0, 75, 0, 76, 0, 0, 77, 78, 79, 79, 0, 0, 81, 81, 83, 84, 85, 85, 85, 85, 0, 86, 86, 0, 88, 88, 0, 91, 91, 0, 0, 0, 92, 93, 0, 0, 94, 94, 0, 95, 95, 0, 0, 96, 96, 97, 0, 97, 98, 0, 99, 0, 0, 102, 0, 0, 105, 107, 109, 110, 0, 111, 111, 112, 0, 0, 115, 115, 115, 0, 0, 119, 119, 119, 0, 120, 0, 121, 122, 124, 126, 0, 0, 130, 0, 0, 132, 132, 132, 133, 134, 0, 135, 0, 136, 0, 137, 137, 138, 0, 142, 143, 143, 143, 144, 144, 145, 145, 0, 0, 0, 149, 150, 0, 151, 153, 0, 154, 156, 156, 0, 162, 162, 163, 163, 166, 168, 168, 168, 169, 0, 170, 0, 171, 171, 171, 0, 0, 0, 172, 0, 173, 173, 174, 174, 174, 0, 0, 178, 178, 178, 179, 0, 0, 180, 0, 181, 0, 181, 182, 182, 183, 0, 184, 0, 186, 186, 187, 0, 187, 0, 189, 189, 190, 191, 193, 193, 0, 0, 194, 195, 0, 0, 0};
        int k = 197;
        int result = solution.fillArray(a, k);
        assertThat(result).isEqualTo(149523514);
    }
    @Test
    public void should_fill_array_correct_for_case6() {
        int[] a = new int[]{43, 49, 50, 80, 172, 182, 0, 206, 209, 245, 274, 279, 286, 356};
        int k = 356;
        int result = solution.fillArray(a, k);
        assertThat(result).isEqualTo(25);
    }
    @Test
    public void should_partial_fill_array() {
        int s1 = solution.partialFillArray(1, 1, 2);
        assertThat(s1).isEqualTo(2);
        int s2 = solution.partialFillArray(1, 2, 2);
        assertThat(s2).isEqualTo(3);
        int s3 = solution.partialFillArray(1, 2, 3);
        assertThat(s3).isEqualTo(6);
        int s4 = solution.partialFillArray(1, 3, 2);
        assertThat(s4).isEqualTo(4);
    }
}
编辑于 2021-11-16 11:36:31 回复(0)
牛客664026885号头像 牛客664026885号
//使用JS写的，类比了路径算法，示例中都能跑出来，但是提交运行的结果却不对，请求大佬指点
function FillArray( a ,  k ) {
    // write code herelet record = [];
    let record = [];
            let init = 0;
            while (a.indexOf(0, init) != -1) {
                let temp = a.indexOf(0, init);
                record.push(temp);
                init = temp + 1;
            }

            let set = [];
            let temp = [];
            let length = record.length;
            for (let i = 0; i < length; i++) {
                if (temp.length == 0) {
                    temp.push(record[i]);
                } else if (record[i] - record[i - 1] == 1) {
                    temp.push(record[i]);
                }

                if (record[i + 1] - record[i] > 1 || i == length - 1) {
                    let t = temp.slice();
                    set.push(t);
                    temp = [];
                }
            }

            function allPath(range, length) {
                let arr = [];
                for (let i = 0; i < length; i++) {
                    arr.push([1]);
                }
                for (let i = 0; i < range - 1; i++) {
                    arr[0].push(1);
                }
                for (let i = 1; i < length; i++) {
                    for (let j = 1; j < range; j++) {
                        arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
                    }
                }
                let sum = 0;
                for (let i = 0; i < range; i++) {
                    sum += arr[arr.length - 1][i];
                }
                return sum;
            }
            let total = 1;
            const setLength = set.length
            for (let i = 0; i < setLength; i++) {
                let tempArr = set[i];
                let start, end, tlength = tempArr.length;
                if (tempArr[0] == 0) {
                    start = 1;
                } else {
                    start = a[tempArr[0] - 1];
                }
                if (tempArr[tlength - 1] == a.length - 1) {
                    end = k;
                } else {
                    end = a[tempArr[tlength - 1] + 1] < k ? a[tempArr[tlength - 1] + 1] : k;
                }
                let range = end - start + 1;
                let sum = allPath(range, tlength);
                total *= sum;
            }
            return total % (10e8 + 7);
}
发表于 2021-10-30 14:51:29 回复(2)
iyzs头像 iyzs 

import java.math.BigInteger;
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int FillArray (int[] a, int k) {
        // write code here
            Long m = 1000000007l;
        int n = a.length;
        BigInteger res = BigInteger.valueOf(1);
        for (int i = 0; i < n; i++) {
            while (a[i++] != 0) {
            }
            int start = i - 1;
            while (i < a.length && a[i] == 0) {
                i++;
            }
            int end = i - 1;
 
            int zero = end - start + 1;
            int min = 1;
            if (start > 0) min = a[start - 1];
            int max = k;
            if (end < n - 1) max = a[end + 1];
            res = res.multiply(BigInteger.valueOf(f1(min, max, zero))).remainder(BigInteger.valueOf(m));
        }
        return res.intValue();
    }
        public long f1(long min, int max, int zero) {
        if (zero == 1) {
            return max - min + 1;
        }
        long res = 0;
        long temp = f1(min, max, zero - 1);
        for (long i = 0; i < temp; i++) {
            res += f1(min + i, max, zero - 1);
        }
        return res;
    }
}
发表于 2021-10-20 14:13:07 回复(0)
普调的布莱克头像 普调的布莱克
def num_fillings(a, k):
    mod = 1000000007
    n = len(a)

    # 初始化动态规划数组
    dp = [[0] * (k + 1) for _ in range(n)]

    # 填充边界条件
    if a[0] == 0:
        for i in range(1, k + 1):
            dp[0][i] = 1
    else:
        dp[0][a[0]] = 1

    # 动态规划递推
    for i in range(1, n):
        prefix_sum = 0
        for j in range(1, k + 1):
            prefix_sum = (prefix_sum + dp[i - 1][j]) % mod
            if a[i] == 0 or a[i] == j:
                dp[i][j] = prefix_sum
            else:
                dp[i][j] = 0

    # 计算最终结果
    ans = sum(dp[n - 1]) % mod
    return ans
#这个解法的时间复杂度为O(n * k^2)，对于较大的输入可能会很慢。
发表于 2023-03-29 17:31:04 回复(0)
只想打球头像 只想打球 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param a int整型一维数组 
# @param k int整型 
# @return int整型
#
class Solution:
    def FillArray(self, a: List[int], k: int) -> int:
        # write code here
        mod = 10 ** 9 + 7
        n = len(a)
        dp = [[0] * (k + 1) for _ in range(n + 1)]

        # 填充迭代表，用于记录
        # 第一行用于表示常数时表示的个数为1，是为了35行的代码能与是连续0的情况保持一致而使用的
        for j in range(0, k + 1):
            dp[0][j] = 1
        for j in range(1, k + 1):
            dp[1][j] = j
        for i in range(2, n + 1):
            for j in range(1, k + 1):
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j]

        ans = 1
        num = 0  # 对连续0计数
        start = 1  # 左边界值
        i = 0
        while (i < n):
            if a[i] == 0:
                num += 1
                i += 1
            else:
                ans = ans * dp[num][a[i] - start + 1]
                start = a[i]
                num = 0
                i += 1
        # 处理最后一次如果不是常数结尾的情况
        if num!=0:
            ans = ans * dp[num][k - start + 1]


        return ans % mod
        

发表于 2023-02-14 00:09:49 回复(0)
hqw11头像 hqw11
其实就是简单结合排列组合和大数计算 

package main
import "math/big"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param a int整型一维数组
 * @param k int整型
 * @return int整型
 */
func FillArray(a []int, k int) int {
	// write code here
	startNum, count := 1, 0
	res := int64(1)
	for i := 0; i < len(a); i++ {
		if a[i] == 0 {
			count++
			continue
		}
		if count != 0 {
			res = (res * getSection(a[i]-startNum, count)) % 1000000007
		}
		startNum = a[i]
		count = 0
	}
	if count != 0 {
		res = (res * getSection(k-startNum, count)) % 1000000007
	}
	return int(res)
}

func getSection(inter, num int) int64 {
	if num == 0 || inter < 0 {
		return 0
	}
	if inter == 0 {
		return 1
	}
	res := big.NewInt(1)
	for i := num + inter; i > num; i-- {
		res.Mul(res, big.NewInt(int64(i)))
	}
	for i := 1; i <= inter; i++ {
		res.Div(res, big.NewInt(int64(i)))
	}
	return res.Mod(res, big.NewInt(1000000007)).Int64()
}


发表于 2023-02-05 08:30:31 回复(0)
Python 3
牛客139289501号头像 牛客139289501号 
class Solution:
    def FillArray(self , a , k ):
        len1 = len(a)
        dp = [[1]*(len1+1) for _ in range(k+1)]
        for i in range(1, k+1):
            dp[i][1] = i
        for j in range(1, len1+1):
            dp[1][j] = 1

        for i in range(2, k+1):
            for j in range(2, len1+1):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]

        nums = [1]+a+[k]
        len2 = len(nums)
        start = []
        end = []
        for i in range(1, len2-1):
            if nums[i] == 0 and nums[i-1] >0:
                start.append(i)
            if nums[i] == 0 and nums[i+1] >0:
                end.append(i)

        ans = 1       
        for s, e in zip(start, end):
            ans *= dp[min(nums[e+1],k) - nums[s-1]+1][e-s+1]
        return ans%(10**9 + 7)    

发表于 2022-09-07 20:41:17 回复(0)
刻苦的大熊猫在度假头像 刻苦的大熊猫在度假
java 95% 
int mod = 1000000007;
    public int FillArray (int[] a, int k) {
        // write code here
        int n = a.length;
        long ans = 1;
        for(int i=0;i<n;){
            if(a[i] == 0){
                int l = i-1, r = i+1;
                int cnt = 1;
                while(l>=0 && a[l] == 0){
                    l--;
                    cnt++;
                }
                while(r<n && a[r] == 0){
                    r++;
                    cnt++;
                }
                int left = l<0?1:a[l], right = r>=n?k:a[r];
                // [l+1, r-1]中可选的数的个数
                System.out.println(left+" "+right);
                int cnt1 = getCnt(cnt, right - left + 1);
                ans =  (ans*getCnt(cnt, right-left+1))%mod;
                i = r;
            }else{
                i++;
            }
        }
        return (int)ans;
    }

    // 将m个数放入到n个位置且保持有序的方案数
    public int getCnt(int n, int m){
        // dp[i][j]将j个数有序的放到i个空位的方案数
        int[][] dp = new int[n+1][m+1];
        dp[0][0] = 0;
        // 将i个数放到一个空位的方案数为i种
        for(int i=1;i<=m;i++){
            dp[1][i] = i;
        }

        for(int i=2;i<=n;i++){
            for(int j=1;j<=m;j++){
                // 选定最后一个数为j，则可以转移为将j个数放到前i-1个位置 即 dp[i][j] = dp[i-1][j];
                // 选定最后一个数为k = [1,j-1], 可以转移为将k个数放到前i-1个位置的方案数, 相当于 dp[i][j] = dp[i-1][j-1];
                /*for(int k=1;k<j;k++){
                    dp[i][j] += dp[i-1][k]; 
                }*/  
                dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod;
            }
        }
        return dp[n][m];
    }


发表于 2022-07-25 11:51:49 回复(0)
牛客218883569号头像 牛客218883569号 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int FillArray (int[] a, int k) {
        // write code here
        int n=a.length;
        int mod=1000000007;
        int[][] f =new int[n+1][k+1];
        f[0][1]=1;
        for(int i=1;i<=n;i++){
            if(a[i-1]==0){
                int re=0;
                for(int j=1;j<=k;j++){
                    re=(re+f[i-1][j])%mod;
                    f[i][j]=re;
                   
                }
            }else{
                for(int t=1;t<=a[i-1];t++){
                        f[i][a[i-1]]=(f[i][a[i-1]]+f[i-1][t])%mod;
                    }
            }
        }
        if(a[n-1]>0){
            return f[n][a[n-1]];
        }else{
            int ans=0;
            for(int i=1;i<=k;i++){
                ans=(ans+f[n][i])%mod;
            }
            return ans;
        }
        
        
    }
}
动态规划f[i][j]:表示填充前i个数为j时的方案数
f[i][j]=f[i-1][1]+f[i-1][2]+...+f[i-1][j]
然后优化一下就OK
发表于 2022-04-27 18:00:24 回复(0)
JavaScript
JessieeeBoom头像 JessieeeBoom
为什么这题没有js v8环境？
发表于 2022-04-06 18:32:54 回复(0)
287274349头像 287274349 
import java.util.*;
import java.math.*;

public class Solution {

    public int FillArray (int[] a, int k) {
      long b[][] = new long[k+1][a.length+1];
		for(int i = 0 ; i <= a.length ;i++) {
			b[0][i] = 1;
		}
		for(int i = 0 ; i <= k ;i++) {
			b[i][0] = 1;
		}
		for(int i = 1 ; i <= k ;i++) {
			for(int j = 1 ; j < a.length+1 ;j++) {
				b[i][j] = (b[i-1][j]+ b[i][j-1]) % 1000000007;
			}
		}
		int t = 0;
		int min = 1;
		long sum = 1;
		if(a[0] == 0) {t++;}else {min = min > a[0] ? min : a[0];}
		for(int i = 1 ; i < a.length;i++) {
			if(a[i] == 0) {
				t++;
				continue;
			}else {
				if(t == 0) {
					min = min > a[i] ? min : a[i];
					continue;
				}
				sum *= b[(a[i] - min)][t];
				sum %=1000000007;
				min = min > a[i] ? min : a[i]; 
				t = 0;
			}
		}
		if(t != 0) {sum *= b[k - min][t];}
		return (int)(sum %1000000007);
    }
}

发表于 2022-04-05 09:41:12 回复(1)
Java
李橙子头像 李橙子
import java.util.*;
import java.math.BigInteger;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int FillArray (int[] a, int k) {
        long answer = 1;
         
        int index = 0;
        while(index < a.length) {
            int zero_num = 0;
            int min = 1;
            int max = k;
            if(index-1>=0)
                min = a[index-1];
            if(a[index] == 0) {
                while(a[index] == 0) {
                    zero_num++;
                    index++;
                    if(index >= a.length)
                        break;
                }
                if(index < a.length)
                    max = a[index];
                int[] list = new int[max-min+1];
                for (int i = 0; i < list.length; i++) {
                    list[i] = 1;
                }
                for (int i = 1; i < zero_num; i++) {
                    for (int j = 0; j < list.length; j++) {
                        for (int j2 = j+1; j2 < list.length; j2++) {
                            list[j] = (list[j]+list[j2]) % (int)(Math.pow(10, 9)+7);
                        }
                    }
                }
                int sum = 0;
                for (int i = 0; i < list.length; i++) {
                    sum = (sum+list[i]) % (int)(Math.pow(10, 9)+7);
                }
                answer = (answer*sum) % (int)(Math.pow(10, 9)+7);
            }else {
                index++;
            }
        }
        return (int)answer;
    }
}
发表于 2022-03-07 18:11:05 回复(0)
提交观点

问题信息

动态规划 数组
上传者：小小
难度：
16条回答 6641浏览

热门推荐

通过挑战的用户

查看代码

相关试题

填充数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号