牛妹给了牛牛一个长度为 的下标从
开始的正整型数组
，粗心的牛牛不小心把其中的一些数字删除了。
假如被删除了，则
。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：
-
且对于所有的
满足
。
函数传入一个下标从开始的数组
和一个正整数
，请返回合法的填充方案数对
取模的值,保证不存在方案数为0的数据。
[编程题]填充数组
- 热度指数：4080 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例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
备注:
数组
满足
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)
双指针+一维数组优化+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)
运行时间70ms
占用内存14716KB
1.必须要使用BigInteger,不然会溢出;
2.方案数拆开来其实是个简单的数列自增问题
3.fillZero方法是关键(不要递归,递归效率会崩)因为太久不做数学题导致敏感性下降,结果很简单的问题本来看懂了规律却没想出来公式,只能套递归,崩了,参考了评论里的第一条才想明白公式原来这么简单,看来人已经废了...
public int FillArray (int[] a, int k) {
// write code herereturn 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)
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)
通过全部用例
运行时间 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)
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
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)
其实就是简单结合排列组合和大数计算
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)
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)
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)
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)
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;
}
}
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)
//使用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)
问题信息
通过挑战的用户
查看代码-
2023-03-08 01:13:55
-
2023-02-14 00:02:48
-
2022-12-17 22:44:39 -
2022-12-17 17:57:14
-
2022-11-25 15:34:30
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
