首页 > 试题广场 >

填充数组

[编程题]填充数组
  • 热度指数：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

备注:
数组满足
算法知识视频讲解
开通博客
头像 AimerAimer
发表于 2022-02-06 12:26:49
题意： 方法一： 动态规划 思路：         dp[i][j]表示填充i个数，取值个数是j的方案数。   &nbs 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Minecraft_lbs
发表于 2022-10-16 18:27:17
代码: class Solution { public:     int FillArray(vector<int>& a, int k) {  & 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 CroMarmot
发表于 2022-02-21 14:42:53
填充数组 题意 给定一个数组，把其中为0的位置填上1~k, 求能让数组最终是单调上升的方案数 方法 枚举每个位置的值(TLE) 分析 我们直接对每个位置进行枚举，并在枚举过程中判断是否合法 这样每次一个合法的方案计数+1 最终这个方案数就是要求的答案 代码 class Solution { publ 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 牛客107722044号
发表于 2022-01-25 16:51:08
对每一段零，做动态规划，看有多少方案，最后把所有方案数相乘 例如00035这个数组 以下是声明的一个3*3的数组，横坐标是可以填入的数，纵坐标是0的个数 1 1 1（第一个位置可以填1、2、3） 3 2 1（当一空填1时，二空有1、2、3三种填法；一空填2，二空有2、3两种填法；一空填3，二空有3一 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hqw11
发表于 2023-02-05 08:10:22
其实就是简单结合排列组合和大数计算 package main import "math/big" /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a int整型一维数组 * @param k int整型 * @return 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 认认真真coding
发表于 2022-02-23 15:43:06
填充数组 题目描述 牛妹给了牛牛一个长度为 n的下标从0开始的正整型数组a ，粗心的牛牛不小心把其中的一些数字删除了。 假如aia_{i}ai​被删除了，则aia_{i}ai​=0。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得： a0≤a1≤...≤an−1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 江湖彼
发表于 2024-04-25 09:57:41
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a int整型一维数组 * @param aLen int a数组长度 * @param k int整型 * @return int整型 */ int FillArr 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 江湖彼
发表于 2024-04-25 09:59:21
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a int整型一维数组 * @param aLen int a数组长度 * @param k int整型 * @return int整型 */ int FillArr 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-08-03 16:04:03
import java.util.*; /** * NC173 填充数组 * @author d3y1 */ public class Solution { private final int MOD = 1000000007; /** * 代码中的类名、方法名、 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客362459853号
发表于 2021-11-12 22:17:30
假设n=max-min表示可填数字个数，zero表示连续0的个数， A[i][j]为出现或多次出现0时可填总数，,i为max-min-1，j为zero-1，则：A[I][j]=A[i-1][j]+A[i][j-1]； 测试了下A[15][15]就已经超过1000000007了。 进 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

填充数组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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