关于亚麻OA2 Nearest City和Smallest Negative Balance

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

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

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

[quote]匿名者 发表于 2020-12-16 09:02
第一题最近城市，用TreeMap：

1. String[] findNearestCities(String[] ns,          ...[/quote]
   
2. 终于搞定第一题：
   
3. 
   
4. [code]  public String[] findNearestCities(int numOfPoints,
   
5.                                  String[] ns,
   
6.                                  int[] xs,
   
7.                                  int[] ys,
   
8.                                  int numOfQueries,
   
9.                                  String[] qs) {
   
10.         TreeMap<Integer,TreeMap<Integer, List<String>>> xyMap=new TreeMap<>();
    
11.         TreeMap<Integer,TreeMap<Integer,List<String>>> yxMap=new TreeMap<>();
    
12.         Map<String,int[]> npMap=new HashMap<>();
    
13.         int size=ns.length;
    
14.         for(int i=0;i<size;i++){
    
15.             int x=xs[i];
    
16.             int y=ys[i];
    
17.             String n=ns[i];
    
18.             TreeMap<Integer,List<String>> yMap=xyMap.getOrDefault(x,new TreeMap<>());
    
19.             List<String> tmp1=yMap.getOrDefault(y,new ArrayList<>());
    
20.             tmp1.add(n);
    
21.             yMap.put(y,tmp1);
    
22.             xyMap.put(x,yMap);
    
23.             TreeMap<Integer,List<String>> xMap=yxMap.getOrDefault(y,new TreeMap<>());
    
24.             List<String> tmp2=xMap.getOrDefault(x,new ArrayList<>());
    
25.             tmp2.add(n);
    
26.             xMap.put(x,tmp2);
    
27.             yxMap.put(y,xMap);
    
28.             npMap.put(n,new int[]{x,y});
    
29.         }
    
30.         String[] dest=new String[qs.length];
    
31.         for(int i=0;i<qs.length;i++) {
    
32.             String n=qs[i];
    
33.             int[] p=npMap.get(n);
    
34.             if(p==null) continue;
    
35. 
    
36.             // check the same x
    
37.             TreeMap<Integer,List<String>> yMap=xyMap.get(p[0]);
    
38.             List<String> same=yMap.get(p[1]);
    
39.             if (same.size()>1) {
    
40.                 for(String str:same) {
    
41.                     if(str.equals(n)) continue;
    
42.                     if(dest[i]==null||str.compareTo(dest[i])<0) dest[i]=str;
    
43.                 }
    
44.                 continue;
    
45.             }
    
46. 
    
47.             int min=Integer.MAX_VALUE;
    
48.             List<String> cities=new ArrayList<>();
    
49. 
    
50.             Map.Entry<Integer,List<String>> lowerY=yMap.lowerEntry(p[1]);
    
51.             if(lowerY!=null) {
    
52.                 min=p[1]-lowerY.getKey();
    
53.                 cities.addAll(lowerY.getValue());
    
54.             }
    
55. 
    
56.             Map.Entry<Integer,List<String>> higherY=yMap.higherEntry(p[1]);
    
57.             if(higherY!=null) {
    
58.                 if(higherY.getKey()-p[1]<min) {
    
59.                     min=higherY.getKey()-p[1];
    
60.                     cities.clear();
    
61.                     cities.addAll(higherY.getValue());
    
62.                 } else if(higherY.getKey()-p[1]==min) {
    
63.                     cities.addAll(higherY.getValue());
    
64.                 }
    
65.             }
    
66. 
    
67.             // check the same y
    
68.             TreeMap<Integer,List<String>> xMap=yxMap.get(p[1]);
    
69. 
    
70.             Map.Entry<Integer,List<String>> lowerX=xMap.lowerEntry(p[0]);
    
71.             if(lowerX!=null) {
    
72.                 if(p[0]- lowerX.getKey()<min) {
    
73.                     min=p[0]- lowerX.getKey();
    
74.                     cities.clear();
    
75.                     cities.addAll(lowerX.getValue());
    
76.                 } else if(p[0]- lowerX.getKey()==min) {
    
77.                     cities.addAll(lowerX.getValue());
    
78.                 }
    
79.             }
    
80. 
    
81.             Map.Entry<Integer,List<String>> higherX=xMap.higherEntry(p[0]);
    
82.             if(higherX!=null) {
    
83.                 if(higherX.getKey()-p[0]<min) {
    
84.                     min=higherX.getKey()-p[0];
    
85.                     cities.clear();
    
86.                     cities.addAll(higherX.getValue());
    
87.                 } else if (higherX.getKey()-p[0]==min) {
    
88.                     cities.addAll(higherX.getValue());
    
89.                 }
    
90.             }
    
91. 
    
92.             if(!cities.isEmpty()) {
    
93.                 dest[i]=cities.get(0);
    
94.                 for(String city:cities){
    
95.                     if(dest[i].compareTo(city)>0) dest[i]=city;
    
96.                 }
    
97.             }
    
98.         }
    
99.         return dest;
    
100.     }
     

复制代码

[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

第二题看错题了。最小负债和我们中文的理解不一样。应该是最大负债。汗一个。而且忘了最后排序。更新后的代码如下：

1.     List<String> minimumDebtMembers(List<debtRecord> records) {
   
2.         Map<String,Integer> debts=new HashMap<>();
   
3.         for(debtRecord record:records) {
   
4.             String borrower=record.borrower;
   
5.             String lender=record.lender;
   
6.             int amount=record.amount;
   
7.             debts.put(borrower, debts.getOrDefault(borrower,0)-amount);
   
8.             debts.put(lender, debts.getOrDefault(lender,0)+amount);
   
9.         }
   
10.         List<String> dest=new ArrayList<>();
    
11.         int minDebt=Integer.MAX_VALUE;
    
12.         for(Map.Entry<String,Integer> entry:debts.entrySet()) {
    
13.             if (entry.getValue()>=0||entry.getValue()>minDebt) continue;
    
14.             if(entry.getValue()<minDebt) {
    
15.                 minDebt=entry.getValue();
    
16.                 dest.clear();
    
17.             }
    
18.             dest.add(entry.getKey());
    
19.         }
    
20.         Collections.sort(dest);
    
21.         if (dest.isEmpty()) dest.add("Nobody has a negative balance");
    
22.         return dest;
    
23.     }

复制代码

Zbeeee 发表于 2020-12-16 10:59
我也觉得第二题可以Heap和HashMap, 但你看下面的同学给的方法，好像不排序，直接O(N)也可以？就是再遍历 ...

nearest cities 后来有runtime error 那道题我放弃了

匿名者 发表于 2020-12-16 12:29
第二题看错题了。最小负债和我们中文的理解不一样。应该是最大负债。汗一个。而且忘了最后排序。更新后的代 ...

1. import java.util.*;
   
2. import java.io.*;
   
3. import java.lang.*;
   
4. 
   
5. public class Solution {
   
6.     List<String> minimumDebtMembers(List<debtRecord> records){
   
7.         if(records == null) return new ArrayList<>();
   
8.         
   
9.         HashMap<String, Integer> map = new HashMap<>();
   
10.         
    
11.         for(debtRecord record : records){
    
12.             String borrower = record.borrower;
    
13.             String lender = record.lender;
    
14.             int amount = record.amount;
    
15.             map.put(borrower, map.getOrDefault(borrower, 0)-amount);
    
16.             map.put(lender, map.getOrDefault(lender, 0)+amount);
    
17.         }
    
18.         
    
19.         PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>((a,b) -> a.getValue()==b.getValue() ?
    
20.             a.getKey().compareTo(b.getKey()) : a.getValue()-b.getValue());
    
21.             
    
22.         for(Map.Entry<String, Integer> entry : map.entrySet()){
    
23.             if(entry.getValue()<0){
    
24.                 heap.add(entry);
    
25.             }
    
26.         }
    
27.         
    
28.         List<String> result = new ArrayList<>();
    
29.         if(!heap.isEmpty()){
    
30.             int min = heap.peek().getValue();
    
31.             while(!heap.isEmpty() && heap.peek().getValue() == min){
    
32.                 result.add(heap.poll().getKey());
    
33.             }
    
34.         }
    
35.         if(result.size()==0) result.add("Nobody has a negative balance");
    
36.         
    
37.         return result;
    
38.     }
    
39. }

复制代码

我是这么写的，这个逻辑难道有问题？

cerealkiller 发表于 2020-12-16 15:34
[mw_shl_code=java,true]import java.util.*;
import java.io.*;
import java.lang.*;

这个用了排序，时间复杂度太高了。问题就在于O（N）的题被答成O(NLogN)。

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

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

cerealkiller 发表于 2020-12-17 06:55
能不能解释一下如何O(N)? 如果用只用ArrayList， 那一步 Collections.sort(list) 也是O(NLogN)了呀，这道 ...

一个Arraylist找最大，只要从头到尾撸一遍，看看哪个最大就好了，不需要排序，O(N)