狗家上门

jrou 发表于 2018-7-31 05:36
请问楼主，第二题那个tree是directed还是undirected 呢？

谢谢

directed 因为输入是root 抱歉 应该更类似蠡口楼巴舞

xiaozhi1017 发表于 2018-8-1 01:07
我第一反应直接用HashMap 没想到从hashcode写起 不然还要处理collision挺麻烦的 类比Min Stack我也是直接 ...

好的，谢谢楼主

贴一个第一题C++的解答。如果有bug还请指正。如果觉得有帮助，还请点赞加点米。谢谢大家。
[hide=130]

1. #include <iostream>
   
2. #include <bits/stdc++.h>
   
3. 
   
4. class CSolution
   
5. {   
   
6.     int K;
   
7.     set<pair<int,int>> Set;  // ordered {freq, key}
   
8.     unordered_map<int,int>Map;  // key->freq
   
9. 
   
10.     public:
    
11.     void add(int key, int freq);
    
12.     void printTopK();   
    
13.     CSolution(int _K) { K = _K;}
    
14. };
    
15. 
    
16. void CSolution::add(int key, int freq)
    
17. {
    
18.     if (Set.find({Map[key],key})==Set.end())
    
19.     {
    
20.         Map[key] += freq;
    
21.         Set.insert({Map[key],key});
    
22.         if (Set.size()>K)        
    
23.             Set.erase(Set.begin());        
    
24.     }
    
25.     else
    
26.     {
    
27.         auto iter = Set.find({Map[key],key});
    
28.         Set.erase(iter);
    
29.         Map[key]+=freq;
    
30.         Set.insert({Map[key],key});
    
31.     }
    
32. }
    
33. 
    
34. void CSolution::printTopK()
    
35. {   
    
36.     for (auto a: Set)
    
37.     {
    
38.         cout<<"[freq "<<a.first<<", key "<<a.second<<"]  ";        
    
39.     }
    
40.     cout<<endl;
    
41. }
    
42. 
    
43. int main()
    
44. {
    
45.     CSolution solution(3);   
    
46.     solution.add(1,2);
    
47.     solution.add(2,3);
    
48.     solution.printTopK();
    
49.     solution.add(3,4);
    
50.     solution.add(4,5);
    
51.     solution.printTopK();
    
52.    
    
53.     solution.add(1,8);
    
54.     solution.add(5,9);   
    
55.     solution.printTopK();
    
56.     solution.add(2,1);
    
57.     solution.printTopK();   
    
58. }

复制代码

[\hide]

第三题，贴一个我的解法。我理解的题意是买卖股票的间隔必须恰好是K，那样的话基本的DFS即可。

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

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

多谢lz分享