airbnb 电面

han4011 发表于 2016-11-23 01:41
楼主把 code 贴上来看看 怎么回事

我写了一下，但是输出结果很奇怪，比如说2.57的话，
输出结果是
Combination 0:
0.32, 0.95, 1.3,
但是prices里有0.65 and 1.3,按说结果还得有
0.32, 0.65, 0.65, 0.95才对啊，不知道问题在哪儿

1.   public static void main(String[] args) {
   
2.     double[] prices = {0.32, 1.30, 3.37, 0.65, 0.95,2.30};
   
3.     List<List<Double>> result = combineSum(prices, 2.57);
   
4.     for(int i = 0; i < result.size();i++){
   
5.       System.out.println("Combination "+i+":");
   
6.       for(int j = 0; j < result.get(i).size();j++)
   
7.           System.out.print(result.get(i).get(j)+", ");
   
8.       System.out.println();
   
9.     }
   
10.   }
    
11.   private static List<List<Double>> combineSum(double[] prices, double target){
    
12.     List<List<Double>> result = new ArrayList<>();
    
13.     Arrays.sort(prices);
    
14.     dfs(prices, 0, target, new ArrayList<Double>(), result);
    
15.     return result;
    
16.   }
    
17.   private static void dfs(double[] prices, int index, double target, List<Double> sol, List<List<Double>> res){
    
18.     if(Double.compare(target, 0.0) == 0){
    
19.       res.add(new ArrayList<Double>(sol));
    
20.       return;
    
21.     }
    
22.     if(target < 0)
    
23.       return;
    
24.     for(int i = index; i < prices.length;i++){
    
25.       sol.add(prices[i]);
    
26.       dfs(prices, i, target-prices[i], sol, res);
    
27.       sol.remove(sol.size()-1);
    
28.     }
    
29.   }

复制代码

lfzh123 发表于 2016-12-4 12:11
我写了一下，但是输出结果很奇怪，比如说2.57的话，
输出结果是
Combination 0:

这题貌似有两种思路：
1是把每个数都乘以100 免去double类型的比较
2是用一个小量来表示趋于接近

SiyaoZhu 发表于 2016-12-4 14:19
这题貌似有两种思路：
1是把每个数都乘以100 免去double类型的比较
2是用一个小量来表示趋于接近

嗯，我刚试了一下，变成int然后计算是正确的，谢谢~

请问楼主，这个题为什么要sort?没有太明白

楼主有没有考虑不同菜名但是价格相同呢，请问这种情况怎么办呢

不sort可能会有重复

李大牛 发表于 2017-2-8 00:15
不sort可能会有重复

请问这个地方的重复体现在那里呢？是不同的菜有相同的价格吗，这样的话，重复的话也ok呀

请问他家是用什么网站做题啊？

f1371342385 发表于 2017-5-1 03:48
请问这个地方的重复体现在那里呢？是不同的菜有相同的价格吗，这样的话，重复的话也ok呀

同问 请问您现在知道了吗？