新鲜YouTube Onsite面经

题目都不容易，感觉lz实力挺强的，答得也挺好的,

第二轮啤酒那题，我觉得lz的instinct是对的，应该是要用backtracking来做的，试着写了下，不知道对不对。

1. public class BeerMachineCombination {
   
2. 
   
3.     private static List<List<Integer>> result;
   
4.     private static int lower, higher;
   
5.     public static List<List<Integer>> combination(BeerRange[] buckets, int minVolume, int maxVolume) {
   
6.         result = new ArrayList<List<Integer>>();
   
7.         if (buckets == null || minVolume > maxVolume || buckets.length == 0) return result;
   
8.         lower = minVolume;
   
9.         higher = maxVolume;
   
10.         helper(buckets, 0, 0, 0, new ArrayList<Integer>());
    
11.         boolean found = false;
    
12.         for (List<Integer> list : result) {
    
13.             if (list.size() > 0) {
    
14.                 found = true;
    
15.                 System.out.println("TRUE");
    
16.                 for (int d : list) {
    
17.                     System.out.print(d + " ");
    
18.                 }
    
19.                 System.out.println();
    
20.             }
    
21.         }
    
22.         if (!found) {
    
23.             System.out.println("FALSE");
    
24.         }
    
25.         return result;
    
26.     }
    
27.    
    
28.     private static void helper(BeerRange[] buckets, int start, int preMin, int preMax, List<Integer> temp) {
    
29.         if (preMin >= lower && preMax <= higher) {
    
30.             result.add(new ArrayList<Integer>(temp));
    
31.             return;
    
32.         }
    
33.         for (int i = start; i < buckets.length; i++) {
    
34.             int currMin = buckets[i].min, currMax = buckets[i].max;
    
35.             if (preMin + currMin > higher) continue;
    
36.             if (preMax + currMin > higher) continue;
    
37.             temp.add(i);
    
38.             helper(buckets, i, preMin + currMin, preMax + currMax, temp);
    
39.             temp.remove(temp.size() - 1);
    
40.         }
    
41.     }
    
42.    
    
43.     public static void main(String[] args) {
    
44.        // BeerRange[] beer = {new BeerRange(100,150), new BeerRange(200,250), new BeerRange(300,350)};
    
45.         BeerRange[] beer = {new BeerRange(100,150), new BeerRange(200,300), new BeerRange(300,350)};
    
46.         int minV = 300, maxV = 400;
    
47.         combination(beer, minV, maxV);        
    
48.     }
    
49. }
    
50. 
    
51. class BeerRange {
    
52.     int min, max;
    
53.     BeerRange(int min, int max) {
    
54.         this.min = min;
    
55.         this.max = max;
    
56.     }
    
57. }

复制代码

javaprogrammer 发表于 2016-2-2 12:04
题目都不容易，感觉lz实力挺强的，答得也挺好的,

第二轮啤酒那题，我觉得lz的instinct是对的，应该是要 ...

你好，我想请教一下这段代码。为什么你的helper函数里每次for循环都要从start（上次选择的杯子）开始？谢谢