google phone screen

题目：backjack / 21 点， 给你一堆牌，从1到10，每张牌被抽的概率为1/10，问你deal

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

y(int sum)的方法，返回输掉概率。sum是当前点数。求大米，谢谢！

1. public class BlackJack {
   
2.     public static void main(String[] args) {
   
3.         double res= lostPro(0);
   
4.         System.out.println(res);
   
5.     }
   
6.     public static double lostPro(int sum) {
   
7.         if (sum >=17 && sum <= 21) return 0;
   
8.         if (sum > 21) return 1;
   
9.         double T = 0;
   
10.         for (int i = 1; i <= 10; ++ i) {
    
11.             T += lostPro(sum + i) * 0.1;
    
12.         }
    
13.         return T;
    
14.     }
    
15. }
    

复制代码

1. public class BlackJack {
   
2.     public static void main(String[] args) {
   
3.         long start=System.currentTimeMillis();   //获取开始时间
   
4.         test();
   
5.         long end=System.currentTimeMillis(); //获取结束时间
   
6.         System.out.println((end-start)+"ms");
   
7.     }
   
8. 
   
9.     public static void test() {
   
10.         Double[] mm = new Double[17];
    
11. //        lostProMM(0, mm); // 0ms
    
12.         lostPro(0); // 4ms
    
13.     }
    
14. 
    
15.     public static double lostProMM(int sum, Double[] mm) {
    
16.         if (sum >=17 && sum <= 21) return 0;
    
17.         if (sum > 21) return 1;
    
18.         if (mm[sum] != null) return mm[sum];
    
19.         double T = 0;
    
20.         for (int i = 1; i <= 10; ++ i)
    
21.             T += lostProMM(sum + i, mm) * 0.1;
    
22.         return mm[sum] = T;
    
23.     }
    
24. 
    
25.     public static double lostPro(int sum) {
    
26.         if (sum >=17 && sum <= 21) return 0;
    
27.         if (sum > 21) return 1;
    
28.         double T = 0;
    
29.         for (int i = 1; i <= 10; ++ i) {
    
30.             T += lostPro(sum + i) * 0.1;
    
31.         }
    
32.         return T;
    
33.     }
    
34. }
    

复制代码

一个简单的方法就是recursion进去，但是感觉复杂度有点难想。。。

然后如果对时间要求提速的话，可以recursion+memorization.

楼主的思路是怎样的？

楼主DP解的吗？
电面就考概率真头疼

dsf 发表于 2018-5-10 07:56

请教一下，这个是一张牌可以抽到多次的吧，感觉题目是抽到不放回的。

谢谢分享

dsf 发表于 2018-5-10 07:56

对，应该就是这个答案，我当时脑抽了，写了个更复杂的。

Barbados 发表于 2018-5-10 08:04
请教一下，这个是一张牌可以抽到多次的吧，感觉题目是抽到不放回的。

对，无限牌堆

Barbados 发表于 2018-5-10 08:04
请教一下，这个是一张牌可以抽到多次的吧，感觉题目是抽到不放回的。

嗯嗯，应该无限大