当前位置:  首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意:

  1. 已知蛋从F楼丢下会坏
  2. 现在给你K个蛋,在N层楼中,请问最坏情况最少要试验几次才能知道F的精确值
  3. 如果蛋丢下来不会坏,那么可以捡起来继续丢

思路:

  • 又是一个脑筋急转弯的题目,我们来看看K=1的情况。由于只有一个蛋,坏了就没了,所以只能一层一层往下丢。一层丢下,蛋坏了,说明F=1,反之,继续去二层丢,所以K=1时,最坏情况要试验N次
  • 当K>=2时,由于蛋有多余,可以大胆的去中间丢,这样就可以少丢几次
  • 因此,令cache[K][N]表示K个蛋在N层试验最少要试验的次数,假设第一次要在i层丢蛋,那么分成了两个子问题,如果蛋没碎了,那么最少次数等于cache[k][N-i]+1,如果蛋碎了,那么最少次数等于cache[k-1][i-1]+1
  • 那么这个题就变成了cache[k][N] = min[1<=i<=N]{max{cache[k][N-i], cache[k - 1][i - 1] + 1} + 1},时间复杂度是o(kNN)
  • 但是看数据范围,k<=100,N<=10000,o(kNN)肯定是过不了的
  • 注意到,cache[k][N]是非严格递增输了,且递增值不会超过1,即0<=cache[k][i+1]-cache[k][i]<=1
  • 计算过程中令cache[k][N]最优解的i,跟cache[k][N+1]最优解的j,关系是0<=j-i<=1
  • 因此在处理的过程,固定k,递推N,保存上一个最优解i,继续推出下一个最优解

代码:

  1. class Solution {
  2. private static int[][] cache;
  3. private static void init() {
  4. if (cache == null) {
  5. cache = new int[101][10001];
  6. for (int i = 1;i <= 10000;i++) {
  7. cache[1][i] = i;
  8. }
  9. for (int i = 2;i <= 100;i++) {
  10. cache[i][1] = 0;
  11. cache[i][1] = 1;
  12. cache[i][2] = 2;
  13. int idx = 1;
  14. for (int j = 3;j <= 10000;j++) {
  15. while (cache[i - 1][idx + 1] <= cache[i][j - idx - 2]) {
  16. idx++;
  17. }
  18. cache[i][j] = Math.max(cache[i - 1][idx], cache[i][j - idx - 1]) + 1;
  19. }
  20. }
  21. }
  22. }
  23. public int superEggDrop(int K, int N) {
  24. init();
  25. return cache[K][N];
  26. }
  27. }

该分类下的相关小册推荐: