Pocket Gems面经题求助

这两天就要面试第二轮了，在地里看见到面经题毫无思路，求各路大神帮助，在此跪谢！传说中的背包装宝石题目，地理最近好多人电面问到了。

/*
You’re playing your favorite RPG, and your character has just found a room full of treas

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

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

ter has just found a room full of treasure. You have n inventory slots. Luckily, objects of the same type stack together, with the maximum size ...

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

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

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

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

这题就是greedy吧，看面经很多人说用个堆，然后就能转换成top K了，不太能明白。。。我用的最朴素的办法。。。放一个算一下。。。

1. class Tuple{
   
2.     String name;
   
3.     int value;
   
4.     int maximum_stack_size;
   
5.     public Tuple(String name, int value, int maximum_stack_size){
   
6.         this.name = name;
   
7.         this.value = value;
   
8.         this.maximum_stack_size = maximum_stack_size;
   
9.     }
   
10. }
    
11. 
    
12. public class Main {
    
13. 
    
14.     public static int maxValue(int n, String[] items, Tuple[] item_infos){
    
15.         int val = 0;
    
16.         HashMap<String, Integer> maxMap = new HashMap<>();
    
17.         HashMap<String, Integer> valMap = new HashMap<>();
    
18.         HashMap<String, Integer> countMap = new HashMap<>();
    
19.         for (Tuple item_info : item_infos){
    
20.             maxMap.put(item_info.name, item_info.maximum_stack_size);
    
21.             valMap.put(item_info.name, item_info.value);
    
22.         }
    
23.         for(String item : items){
    
24.             countMap.put(item, countMap.getOrDefault(item, 0) + 1);
    
25.         }
    
26.         for(int i = 0; i < n && !countMap.isEmpty(); i++){
    
27.             int max = 0;
    
28.             String select = "";
    
29.             int num = 0;
    
30.             for (String item : countMap.keySet()){
    
31.                 int count = countMap.get(item);
    
32.                 if(count >= maxMap.get(item)){
    
33.                     if(maxMap.get(item) * valMap.get(item) > max) {
    
34.                         select = item;
    
35.                         num = maxMap.get(item);
    
36.                         max = maxMap.get(item) * valMap.get(item);
    
37.                     }
    
38.                 }
    
39.                 else{
    
40.                     if (count * valMap.get(item) > max){
    
41.                         select = item;
    
42.                         num = count;
    
43.                         max = count * valMap.get(item);
    
44.                     }
    
45.                 }
    
46.             }
    
47.             val += max;
    
48.             if(!select.equals("")){
    
49.                 countMap.put(select, countMap.get(select) - num);
    
50.                 if (countMap.get(select) == 0){
    
51.                     countMap.remove(select);
    
52.                 }
    
53.             }
    
54.         }
    
55.         return val;
    
56.     }
    
57. 
    
58.     public static void main(String[] args) {
    
59.         // write your code here
    
60.         Tuple[] tuples = new Tuple[3];
    
61.         tuples[0] = new Tuple("diamond", 10, 5);
    
62.         tuples[1] = new Tuple("ruby", 5, 5);
    
63.         tuples[2] = new Tuple("armor", 25, 1);
    
64.         String[] items = {"diamond", "ruby", "armor", "diamond", "diamond", "ruby", "diamond", "diamond", "diamond", "diamond",
    
65.          "diamond", "armor"};
    
66.         System.out.println(maxValue(3, items, tuples));
    
67. 
    
68.     }
    
69. }

复制代码

上面题目被截断了

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

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

我的理解是，对于每个item，可以用总的个数除以一个stack最多能放的个数，得到放满的stack个数，并算这些stack的value，并且丢到heap里面，然后再算余数对应stack的value，丢到heap里去，最后取top k...我不明白的事....这么算复杂度真的有优化么？假设k很小，item很多...岂不是做了很多没必要的维护堆的操作？sift up/sift down

听你这么一说忽然有点理解了heap做法。

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

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

xiuluoxn 发表于 2016-12-28 17:05
突然想到heap的优化了, 你的code复杂度是O(k*n), 相对于每个slot, worst case要遍历整个items(或余下的) ...

有道理！这样就比朴素方法好了！

我是按每种东西的最大数量打包，不够的也打成一个包。PQ存包，comparator按照包里的总价值，然后就是k largest了。。