google footer level 4，送foobar challenge链接

关于google foobar这个博主介绍得很好： 我有好几题和他重复。贴一个遇到的level4题和我的解法。感觉gg foobar就是加点mathmatics的经典算法，high performance的implementation有难度,没有acm难。之后会贴个level5的新题。另外拿到个foobar challenge链接，想要的加米站内信，先到先得。如果要面试的话内推显然更快，主要是好玩。Free the Bunny Prisoners
========================

You need to free the bunny prisoners before Commander Lambda's space station explodes! Unfortunately, the commander was very careful with her highest-value prisoners - they're all held in separate, maximum-security cells. The cells are opened by putting keys into each console, then pressing the open button on each console simultaneously. When the open button is pressed, each key opens its corresponding lock on the cell. So, the union of the keys in all of the consoles must be all of the keys. The scheme may require multiple copies of one key given to different minions.

The consoles are far enough apart that a separate minion is needed for each one. Fortunately, you have already freed some bunnies to aid you - and even better, you were able to steal the keys while you were working as Commander Lambda's assistant. The problem is, you don't know which keys to use at which consoles. The consoles are programmed to know which keys each minion had, to prevent someone from just stealing all of the keys and using them blindly. There are signs by the consoles saying how many mi

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

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

t-size:12px">    (int) num_required = 3
Output:
    (int) [[0, 1, 2, 3, 4, 5], [0, 1, 2, 6, 7, 8], [0, 3, 4, 6, 7, 9], [1, 3, 5, 6, 8, 9], [2, 4, 5, 7, 8, 9]]

Inputs:
    (int) num_buns = 4
    (int) num_required = 4
Output:
    (int) [[0], [1], [2], [3]]

想法是这个： https://en.wikipedia.org/wiki/Combination

1. public class Answer {
   
2. 
   
3.   public static int[][] answer(int num_buns, int num_required) {
   
4. 
   
5.     if(num_required > num_buns || num_required == 0) return new int[num_buns][0];
   
6. 
   
7.     if(num_required == 1) return new int[num_buns][1];
   
8. 
   
9.    
   
10. 
    
11.     int[] bun_labels = new int[num_buns];
    
12. 
    
13.     int combSize = num_buns - num_required + 1;
    
14. 
    
15.     for(int i = 0; i < num_buns; i++) bun_labels[i] = i;
    
16. 
    
17.     List<List<Integer>> schema = getCombinations(bun_labels, combSize, 0);
    
18. 
    
19.    
    
20. 
    
21.     List<List<Integer>> result = new ArrayList<List<Integer>>();
    
22. 
    
23.     for(int j = 0; j < num_buns; j++) result.add(new ArrayList<Integer>());
    
24. 
    
25.    
    
26. 
    
27.     for(int k = 0; k < schema.size(); k++) {
    
28. 
    
29.         List<Integer> positions = schema.get(k);
    
30. 
    
31.         for(int pos : positions) {
    
32. 
    
33.           result.get(pos).add(k);
    
34. 
    
35.         }
    
36. 
    
37.     }
    
38. 
    
39.    
    
40. 
    
41.     int[][] ans = new int[num_buns][result.get(0).size()];
    
42. 
    
43.     for(int c = 0; c < result.size(); c++) {
    
44. 
    
45.         List<Integer> cur = result.get(c);
    
46. 
    
47.         for(int m = 0; m < cur.size(); m++) ans[c][m] = cur.get(m);
    
48. 
    
49.     }
    
50. 
    
51.     return ans;
    
52. 
    
53. }
    
54. 
    
55. 
    
56. 
    
57. private static List<List<Integer>> getCombinations(int[] items, int combSize, int startIndx) {
    
58. 
    
59.     List<List<Integer>> result = new ArrayList<List<Integer>>();
    
60. 
    
61.     if (combSize == 0) return result;
    
62. 
    
63.     if (combSize == 1) {
    
64. 
    
65.         for(int i = startIndx; i < items.length; i++) {
    
66. 
    
67.             List<Integer> cur = new ArrayList<Integer>();
    
68. 
    
69.             cur.add(items[i]);
    
70. 
    
71.             result.add(cur);
    
72. 
    
73.         }
    
74. 
    
75.     } else {
    
76. 
    
77.         for(int i = startIndx; i <= items.length - combSize; i++){
    
78. 
    
79.             List<List<Integer>> cur = getCombinations(items, combSize-1, i+1);
    
80. 
    
81.             for (List<Integer> ele : cur) {
    
82. 
    
83.                 ele.add(0, i);
    
84. 
    
85.             }
    
86. 
    
87.             result.addAll(cur);
    
88. 
    
89.         }
    
90. 
    
91.     }
    
92. 
    
93.     return result;
    
94. 
    
95. }
    
96. 
    
97. }

复制代码