算法——鸡蛋掉落

2019年7月11日 0 条评论 13 次阅读 1 人点赞

来源

leetcode 第 887 号问题,经典面试题

题目

你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

提示:
1 <= K <= 100
1 <= N <= 10000

解法思路

实话说,博主第一次没能把题看懂(hhh)。所以还没看懂题目的小朋友请先把题目看懂,此处省略,再来看解答吧。

提示:最小移动次数指的是扔鸡蛋的次数

首先,这是道动态规划的题目,故我们需要列出状态转移方程。

两个思路:

  • 已知层数 N 和鸡蛋数 K ,求最少扔鸡蛋次数 X
  • 已知鸡蛋数 K 和 扔鸡蛋次数 X ,求最多能测的层数 N

看懂的同学举个爪,算了我也看不见,接着解答。。。

两个思路下的状态转移方程:

  • 思路一

    Xn = max(F(n - 1, K - 1), F(N - n, K)) + 1
    X = min(Xn), 1 <= n <= N
    假设在第 n 层开始扔鸡蛋,没碎,则从 n + 1 层到 N 层继续扔鸡蛋;碎了,则从第 1 层到 n - 1 层继续扔鸡蛋。 n 可以从 1 到 N 层任意取,max可以理解为最坏情况,算出对应的最少扔鸡蛋次数为 Xn ,最后我们取其中的最小值。

  • 思路二

    N = F(K, X - 1) + F(K - 1, X - 1) + 1
    既然能测出 N 层,那么假设在第 n 层扔鸡蛋时,没碎,那么往上可测 F(K, X - 1) 层;碎了,那么往下可测 F(K - 1, X - 1) 层。再加上 n 这一层,结果便为最多能测的层数。

思路一的代码此处省略,直接写还是会存在复杂度问题,需要优化,有兴趣的同学自己上网查,博主很懒------

下面给出思路二的代码,比较简单,一看就懂。。。。。。

参考代码

class Solution {
public:
    int superEggDrop(int K, int N) {
        //初始化为移动一次的基于鸡蛋数的数组,值为能测的层数
        vector<int> r(K+1, 1);
        int ans = 1;
        r[0] = 0;//零个鸡蛋,无论多少次移动都测不了层数,故为零
        //不断增加移动次数,直至能测出的层数大于题目给出的层数 N
        while(r[K] < N){
            ans++;//移动一次
            for(int i = K; i >= 1; i--){
                r[i] = r[i] + r[i-1] + 1;//动态规划,转移方程式
            }
        }
        return ans;
    }
};
头像

didi

这个人太懒什么东西都没留下

文章评论(0)