Google onsite 新鲜面经 9/10

我靠,竟然考到了quadtree...

第一题 用c++写了段代码 大神们帮忙优化下

1. struct Node{
   
2. char c;
   
3. int count;
   
4. Node(char c1,int c2 ){c=c1;count=c2;}
   
5. }
   
6. struct cmp{
   
7. bool operator()(const Node l,const Node r){
   
8.          return l.count<r.count;}
   
9. }
   
10. 
    
11. string change(string s){
    
12. string res;
    
13. unordered_map<char,int> mp;
    
14. priority_queue<Node,vector<Node>,cmp> que;
    
15.    
    
16.     for(char c:s){
    
17.           mp[c]++;   
    
18.           }
    
19.     for(auto iter=mp.begin();iter!=mp.end();iter++){
    
20.          Node n(iter->first,iter->second);            
    
21.          que.push(n);
    
22.                      }
    
23.      while(!que.empty()){
    
24.       Node n=que.top();
    
25.       que.pop();
    
26.       res+=n.c; n.count--;
    
27.       if(n.count) que.push(n);
    
28. 
    
29.      }
    
30.     return res;
    
31. 
    
32. }

复制代码

第一题是不是一开始就得判断一下，因为有些string本身就不可能refactor成邻字母不能相同的string

请问嗯楼主电面完多久通知on site的

quadtree很牛b，第二题对我来说也是好题，多谢lz。

returning 发表于 2015-10-11 04:01
quadtree很牛b，第二题对我来说也是好题，多谢lz。

请问第二题有想法吗？前面有个人说欧拉回路，不太理解

hj867955629 发表于 2015-10-29 06:57
请问第二题有想法吗？前面有个人说欧拉回路，不太理解

你google下欧拉回路的解法就行了。
通俗来说，先转化为求回路的问题，再者，对欧拉回路，方法是固定的，只要满足条件肯定能找到。

returning 发表于 2015-10-29 12:19
你google下欧拉回路的解法就行了。
通俗来说，先转化为求回路的问题，再者，对欧拉回路，方法是固定的， ...

能给个代码嘛？比如求的是长度为2的字符串，每个字符0～9

第二题 De Bruijn sequence