刀大师电面新题？

刷面经没在地里看到过貌似是个新题，有点像幺儿三无

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

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

贴个自己写的

1.     public static int maxCalories(int[] calories, double[] prices, double budget) {
   
2.         int budget_int = (int)(budget * 100);
   
3.         int[] prices_int = new int[prices.length];
   
4.         for(int i = 0; i < prices.length; i++) {
   
5.             prices_int[i] = (int)(prices[i] * 100);
   
6.         }
   
7. 
   
8.         List<Food> foods = new ArrayList<>();
   
9.         for(int i = 0; i < calories.length; i++) {
   
10.             foods.add(new Food(prices_int[i], calories[i]));
    
11.         }
    
12. 
    
13.         foods.sort((a, b) -> a.price - b.price);
    
14. 
    
15.         TreeMap<Integer, Integer> dp = new TreeMap<>();
    
16.         dp.put(0, 0);
    
17. 
    
18.         for(int can_buy = 1; can_buy <= budget_int; can_buy++) {
    
19.             for(Food food : foods) {
    
20.                 if(food.price > can_buy) break;
    
21. 
    
22.                 int calorie_with_food = food.calorie + dp.floorEntry(can_buy - food.price).getValue();
    
23.                 if(calorie_with_food > dp.lastEntry().getValue()) {
    
24.                     dp.put(food.price + dp.floorEntry(can_buy - food.price).getKey(), calorie_with_food);
    
25.                 }
    
26.             }
    
27.         }
    
28.         return dp.lastEntry().getValue();
    
29.     }
    
30. 
    
31. 
    
32. class Food {
    
33.     int price;
    
34.     int calorie;
    
35.     Food(int price, int calorie) {
    
36.         this.price = price;
    
37.         this.calorie = calorie;
    
38.     }
    
39. }

复制代码

写了一个Memo + dfs：

1. class Solution {
   
2.    
   
3.     //输入是一个总budget，一些dish的price和calorie，要求算出这个budget能买到的最大的calories，可以重复的选择同一种dish
   
4. // calories [40, 10, 30]
   
5. // prices [8.0, 5.00, 2.15]
   
6. // budget 20.00
   
7.     Map<Integer, Integer> dp = new HashMap<>();
   
8.     public int maxCalorie(int[] calories, int[] prices, int budget) {
   
9.         if (budget== 0) {
   
10.             return 0;
    
11.         }
    
12.         
    
13.         dp[0] = 0;
    
14.         int[][] food = new int[calories.length][2];
    
15.         for (int i = 0; i < food.length; i++) {
    
16.             food[i] = new int[]{prices[i], calories[i]};
    
17.         }
    
18.         
    
19.         Arrays.sort(food, (a, b) -> (a[0] - b[0]));
    
20.         return dfs(budget, food);
    
21.     }
    
22.    
    
23.     private int dfs(int budget, int[][] food) {
    
24.         if (budget == 0) {
    
25.             return 0;
    
26.         }
    
27.         if (dp.containsKey(budget)) {
    
28.             return dp.get(budget);
    
29.         }
    
30.         
    
31.         int cur_max = 0;
    
32.         for (int i = 0; i < food.length; i++) {
    
33.             if (budget < food[i][0]) {
    
34.                 break;
    
35.             }
    
36.             cur_max = Math.max(cur_max, food[i][1] + dfs(budget - food[i][0], food));
    
37.         }
    
38.         
    
39.         dp.put(budget, cur_max);
    
40.         return cur_max;
    
41.     }
    
42. }

复制代码

这题用DFS做面试官认可吗？

DFS比较好？

wtcupup 发表于 2021-11-9 21:49
这题用DFS做面试官认可吗？

说了下dfs+memo，面试官黑脸不太交流，心虚最后写了dp

f1371342385 发表于 2021-11-9 22:21
DFS比较好？

求问dfs的话复杂度是什么？

Knapsack Problem?

mstc123 发表于 2021-11-17 20:51
写了一个Memo + dfs：

prices 和budget是double， 不是int

匿名者 发表于 2021-11-12 09:26
Knapsack Problem?

看起来像完全背包