本文主要是介绍leetcode-鸡蛋掉落,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
categories: [计算机通识,数据结构与算法]
thumbnail: /images/fe/leetcode.jpg
toc: true
鸡蛋掉落(难度:困难)
你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再使用它,否则可以继续丢,鸡蛋的性能不会随着丢的次数增加而有所损耗。
假设存在一个中间楼层F,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?
示例 1:
输入:K = 1, N = 2
输出:2
解释:
鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
如果它没碎,那么我们肯定知道 F = 2 。
因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2:
输入:K = 2, N = 6
输出:3
示例 3:
输入:K = 3, N = 14
输出:4
动态规划
这个方法可以观看李永乐的视频,比较好理解
复工复产找工作?先来看看这道面试题:双蛋问题
维护一个状态数组dp,dp[i][j]
代表一共有 i 层楼的情况下,使用 j 个鸡蛋的最少实验的次数。
说明:
i 表示的是楼层的大小相对,不是绝对高度(第几层)的意思,例如楼层区间 [8, 9, 10] 的大小为 3。
j 表示可以使用的鸡蛋的个数,它是约束条件。
对于这个数组,我们可以对它的一些特殊情况进行初始化
只有一个鸡蛋:最少移动数就是楼层数。只有一层楼:永远只需要移动一次
那么接下来对于每一个高度i
我们就需要进行枚举,在0到i
之间选一个楼层k开始试验,k从1开始直到i
,就可以依次填写这个数组
对于当前的楼层k,k >= 1 且 k <= i:
如果鸡蛋破碎,实验就得在 k 层以下做(不包括 k 层),这里已经使用了一个鸡蛋,简单来说就是楼层数减一,鸡蛋数减一,即求:dp[k - 1][j - 1]
;
如果鸡蛋完好,那么就要去k楼层以上进行试验。那么对于表中的i
层楼,剩下的楼层数就是i- k
,所以这个时候即求:dp[i - k][j])
那么对于同一个k取值时存在摔碎与没摔碎两种情况,我们要去求最差情况,也就是两者之间的最大值
对于不同k之间的取值,我们需要取两者之间的最小值
代码如下:
var superEggDrop = function(K, N) {let dp = new Array(N + 1)for(let i = 0; i <= N; i++){dp[i] = new Array(K + 1).fill(i)}for(let i = 2; i <= N; i++){for(let j = 2; j <= K; j++){for (let k = 1; k <= i; k++) {dp[i][j] = Math.min(dp[i][j], Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1);}}}return dp[N][K]
};
在上述解法中,由于开辟了一个二维数组dp,所以空间复杂度为O(NK)。填表本身的时间复杂度为O(NK), 但是对于表中的每一项(也就是每一个高度),都要对从哪里开始实验进行枚举,所以时间复杂度变为O(KN^2)
所以不出意外,这道题提交直接TLE
动态规划(重写状态转移方程)
这道题可以进行一下逆行思维,将状态转移方程dp[i][j]
看成,当你有j和鸡蛋,最多可以走i步,你最多可以验证dp[i][j]
高的楼层
那么对于dp[i][j]
来说,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1
dp[i][j]
:如果你还剩 j 个蛋,且只能操作 i 次了,所能确定的楼层。
dp[i - 1][j]
:蛋没碎,因此该部分决定了所操作楼层的上面所能容纳的楼层最大值
dp[i-1][j-1]
:蛋碎了,因此该部分决定了所操作楼层的下面所能容纳的楼层最大值
那么最终dp数组中最后一列中刚刚大于楼层数N的那一个数所在的行数就是最小操作数
代码如下:
var superEggDrop = function(K, N) {let dp = new Array(N)for(let i = 0; i < N; i++){if(i === 0){dp[i] = new Array(K).fill(1)}else{dp[i] = new Array(K).fill(i + 1)}}for(let i = 1; i < N; i++){for(let j = 1; j < K; j++){dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + 1}if(dp[i][K - 1] >= N){return i + 1}}return dp[0][K - 1]
};
再优化
对于上述的dp数组我们发现,第 f 次操作结果只和第 f-1 次操作结果相关,因此我们可以把dp压缩成为一个一维数组,我们发现纵向最多允许操作数是顺序增长的,所以我们可以把纵向最大操作数取消,使用一个变量count递增来代替,保留鸡蛋数,dp[i]
代表有i个鸡蛋时,当前count次操作后可以确认的楼层数。.
代码如下:
var superEggDrop = function(K, N) {let dp = new Array(K + 1).fill(0)let count = 0while(dp[K] < N){for(let i = K; i > 0; i--){dp[i] = dp[i] + dp[i - 1] + 1}count ++}return count
};
这篇关于leetcode-鸡蛋掉落的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!