热乎乎的Google Onsite面经

bobingmm 发表于 2015-4-9 13:02
请问下第二轮第二道口袋题目，combine的最后是要combine成一个口袋是吗？

补充内容 (2015-4-9 13:05):

这个题应该用hauffman coding idea来搞。 因为要让cost最小，必须是的大的bag被合并的次数少。

补充内容 (2015-5-1 02:16):
我把题目看错了，是合并相邻的两个。这是经典的dp问题了。

stochasticer 发表于 2015-4-8 17:10
问个很弱的问题。LZ的第一道题，我的思路和LZ基本一致，对给的每一个点BFS，然后最终扫描。写了一下code发 ...

用DFS不行么？感觉代码稍微简单点啊。。。

1. 
   
2. void dfs(vector<vector<int>> &matrix, int pos, vector<bool> &visit,unordered_map<int, int> &map) {
   
3.     int i = pos/matrix[0].size();
   
4.     int j = pos%matrix[0].size();
   
5.     if(visit[pos] == true)
   
6.         return;
   
7.     visit[pos] = true;
   
8.     map[pos]++;
   
9.     int val = matrix[i][j];
   
10.     if(i && matrix[i-1][j] > val){
    
11.         int tmp = (i-1)*matrix[0].size() + j;
    
12.         dfs(matrix, tmp, visit,map);
    
13.     }
    
14.     if(j && matrix[i][j-1] > val){
    
15.         int tmp = i*matrix[0].size() + j - 1;
    
16.         dfs(matrix, tmp, visit,map);
    
17.     }
    
18.     if(i < matrix.size()-1 && matrix[i+1][j] > val){
    
19.         int tmp = (i+1)*matrix[0].size() + j;
    
20.         dfs(matrix, tmp, visit,map);
    
21.     }
    
22.     if(j < matrix[0].size()-1 && matrix[i][j+1] > val){
    
23.         int tmp = (i)*matrix[0].size() + j + 1;
    
24.         dfs(matrix, tmp, visit,map);
    
25.     }
    
26.     return;
    
27. }
    
28. int findhighest(vector<vector<int>> &matrix, vector<int> pts){
    
29.     unordered_map<int,int> map;
    
30.     int m = matrix.size();
    
31.     int n = matrix[0].size();
    
32.    
    
33.     for(int k = 0; k < pts.size(); k++) {
    
34.         vector<bool> visit(m*n, false);
    
35.         dfs(matrix, pts[k],visit,map);
    
36.     }
    
37.     int num = 0;
    
38.     int pos = 0;
    
39.     for(auto it:map){
    
40.         if(it.second == pts.size())
    
41.             if(matrix[it.first/n][it.first%n] > num){
    
42.                 num = matrix[it.first/n][it.first%n];
    
43.                 pos = it.first;
    
44.             }
    
45.         
    
46.     }
    
47.     return pos;
    
48. }
    
49. 
    
50. int main(int argc, const char * argv[]) {
    
51.     vector<vector<int>> num{{1, 5, 3, 2}, {9, 3, 8, 2}, {9, 4, 8, 9}, {0, 3, 2, 3}};
    
52.     vector<int> pts{5,7, 14};
    
53.     cout << findhighest(num, pts);
    
54. }

复制代码