面试题刷题每日小结-2
1.google经典面试题,两个鸡蛋,100楼,测出鸡蛋的耐摔指数(从哪一层摔下来就pia ji 碎了),要求给出最少次数方案的次数
其实这道题在2018年蓝桥杯的初赛有见过,当时看到的想法就是二分法,但是后面查阅资料发现其实是很巧妙的这道题
这里给出两种解释
(1)动态规划法
f(n)= min( 1+ max( i-1, f(n-i) ) ) i =1,2,...,n
上面的丑陋的图就是我的理解,首先n楼 2个鸡蛋要求最少次数为f(n) , 考虑第一个动作Action, 也就是第一个鸡蛋可以从第一楼扔,第二楼扔,。。。第n楼扔,分别对应上面的 A(1) 到 A(n), 对于每一个动作,都会有两种结果,碎与不碎,如果在i楼碎了的话,那么只能用第二个鸡蛋从1楼开始慢慢爬往上试,所以需要的次数是 i-1,如果比较lucky, 鸡蛋在第i楼没有碎,那么就转化成两个鸡蛋,n-i楼的问题,也就是 f(n-i), 因为要考虑最坏的情况,所以碎与不碎两种情况要取次数最大的,也就是
max( i-1, f(n-i)) 表达式的由来,对于每一个A(i) 动作,都能求出一个次数,接着只需要看看所有的次数中最少的那个,就是最佳的方案,所以这里用的是min, 之所以要加1 ,是因为执行A(i)这个动作本身就算一次。
所以最终的表达式就是 f(n)= min( 1+ max( i-1, f(n-i) ) )
代码:
public class Test {
public static void main(String[] args) {
new Test().f();
}
private void f() {
int []a=new int[101];
a[1]=1;
int best = 0,temp=0;
for(int i=2;i<101;i++)
{
best=Integer.MAX_VALUE;
for(int j=1;j<i;j++)
{
temp=Math.max(j-1, a[i-j])+1;
best=best<temp?best:temp;
}
a[i]=best;
}
System.out.println(a[100]);
}
}
(2)数学方法
假设最少的次数是 x , 那么第一次最高在x层扔下,这是为了防止鸡蛋碎了,剩下的一颗鸡蛋能够用剩下的 (x-1)次机会找出答案;如果没摔的话,第二次最高在 x+(x+1) 层扔下,同理,这是为了防止如果这次鸡蛋碎了,剩下的一颗鸡蛋能够用剩下的(x-2)次机会在【x, x+(x-1)-1】楼层区间中找到答案;依次类推。
然后再反过来思考,就是x次能够测出多高的楼呢,答案是 x+(x-1)+(x-2)+...+1=x(x+1)/2
然后再代进去楼的高度,比如说100层的楼,两个鸡蛋,最少多少次? x(x+1)/2 >=100
可以得到最后答案是 x=14次
上一篇: vector查找指定元素并删除
下一篇: ArrayList去除重复的字符串