亚马逊OA - 订单匹配问题

heronalps 发表于 2018-3-18 13:38
这段写得真棒，我之前也把这个问题想复杂了。有一点小小的改进，用一个start变量剪枝一下，可以减少循环 ...

哈哈 确实 都忘了3sum里面也有这个避免重复的套路

另外我发现我代码里面有个bug，在最后一个函数里面

1.     public static int kindOfCombos(Map<String, Integer> combos) {
   
2.         int count = 0;
   
3.         for(int i = 1; i <= combos.size(); i++) {
   
4.             if (combos.getOrDefault("bom" + i, 0) != 0) {
   
5.                 count++;
   
6.             }
   
7.         }
   
8.         return count;
   
9.     }

复制代码

要遍历传进来的这个Map的话，不应该用int i = 1然后递增的办法，而应该是用combos.keySet()的办法。

您好！
本帖隐藏的内容需要积分高于 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

你好, 我也找朋友在组内找到opening 内推了一下，可以问问你这个是什么组吗?

legendava 发表于 2018-3-19 19:21
你好, 我也找朋友在组内找到opening 内推了一下，可以问问你这个是什么组吗?

RedShift

有利特扣的638感觉有点相似

亚麻又开始抽奖了？

发一个号理解得递归：

1.     public static List<Integer> match(int[] item, Map<Integer,int[]> patterns){
   
2.         List<Integer> bestMatched = new ArrayList<>();
   
3.         matchHelper(bestMatched, item, patterns);
   
4.         return bestMatched;
   
5.     }
   
6. 
   
7.     static int matchHelper(List<Integer> matchedRes, int[] item, Map<Integer, int[]> patterns){
   
8.         //get data from mem.
   
9.         long minCategory = Arrays.stream(item).filter(v->v>0).count();
   
10.         if (minCategory==0){
    
11.             return 0;
    
12.         }
    
13.         List<Integer> bestMatched = new ArrayList<>();
    
14.         for (Map.Entry<Integer, int[]> pt: patterns.entrySet()) {
    
15.             List<Integer> currentMatched = new ArrayList<>();
    
16.             int[] newItem = reduce(item, pt.getValue());
    
17.             if (newItem!=null) {
    
18.                 currentMatched.add(pt.getKey());
    
19.                 int restCategory = matchHelper(currentMatched, newItem, patterns);
    
20.                 if (minCategory>restCategory){
    
21.                     minCategory = restCategory;
    
22.                     bestMatched = new ArrayList<>();
    
23.                     bestMatched.addAll(currentMatched);
    
24.                 }
    
25.                 if (minCategory == restCategory){
    
26.                     if (bestMatched!=null && currentMatched.size()<bestMatched.size()){
    
27.                         bestMatched = new ArrayList<>();
    
28.                         bestMatched.addAll(currentMatched);
    
29.                     }
    
30.                 }
    
31.                 currentMatched.remove(currentMatched.size()-1);
    
32.             }
    
33.         }
    
34.         matchedRes.addAll(bestMatched);
    
35.         //mem result
    
36.         return Long.valueOf(minCategory).intValue();
    
37.     }
    
38. 
    
39.     private static int[] reduce(int[] item, int[] value) {
    
40.         int[] nitem = new int[item.length];
    
41.         for (int i=0;i<item.length;i++){
    
42.             int newval = item[i] - value[i];
    
43.             if (newval<0){
    
44.                 return null;
    
45.             }
    
46.             nitem[i] = newval;
    
47.         }
    
48.         return nitem;
    
49.     }

复制代码