腾讯音乐笔试题：
给一个单调不减的数组（也就是其中有相等的数字）总体趋势是增也不一定可能是一条直线，但是其中有些位置被替换成了0，我们需要求出所有的把0替换的方案数量：满足的是填充的每一个数可以大于等于前一个数，小于等于后一个数 且不能超过k，最后的结果需要模1000000007。
比如 1 0 3 我们可以填的就有把0替换为 1 2 3 就有三种方案
核心思路
- 我们总的来说就是要找到数组中连续0的个数，并得到可选择的范围 根据这两个值我们来计算有多少种可能
- 我们可以使用暴力搜索 但是最坏情况的时间复杂度是幂次
- 所以我们使用动态规划
- dp[i][j]代表长度为i，j个取值范围的方案数
- 递推公式dp[i][j]=dp[i-1][j]+dp[i][j-1]
- 递推公式是dp[i][j]=dp[i-1][j] + dp[i-1][j-1] +dp[i-1][j-2]+-----+dp[i-1][1] 也就是前i个长度取值范围为j的方案数 是等于 前i-1个长度 取值范围为j 一直加到 1的方案数
- 又dp[i][j-1]=dp[i-1][j-1] +dp[i-1][j-2]+-----+dp[i-1][1]
- 所以dp[i][j]=dp[i-1][j]+dp[i][j-1];也就是我们可以理解为在二维矩阵中每一个位置的方案数就等于它上一行到同一列的方案数之和
- 那换个思路是不是dp[i][j-1]也是由其上一行得到 + dp[i-1][j]也就是跟定义意思完全相同了
- 然后其他的部分就比较简单了
不知道讲清楚没，大佬们也可以讲一下自己的思路
public int solution(int nums[],int k) {
// dp[i][j]代表的是填充的数量为i个、值的范围为j个的方案数是
// dp[i-1][j] + dp[i-1][j-1] +dp[i-1][j-2]+-----+dp[i-1][1]
int n=nums.length;
int [][]dp=new int[n+1][k+1];
for (int i=1;i<n+1;i++) {
dp[i][1]=1;
}
for (int i=1;i<k+1;i++) {
dp[1][i]=i;
}
for (int i = 2 ; i <=n ; i++) {
for (int j = 2 ; j <=k ; j++) {
dp[i][j]=dp[i-1][j]+dp[i][j-1];
dp[i][j]%=1000000007;
}
}
long res=1;
int j=0;
while (j<nums.length) {
while (j<nums.length&&nums[j]!=0){
j++;
}
if (j==n) break;
int i=j;
int left=j>0?nums[j-1] :1;
while (j<nums.length&&nums[j]==0){
j++;
}
int right=j<n?nums[j]:k;
res=(res*dp[j-i][right-left+1])%1000000007;
}
return (int)res;
}评论 (12)
