Google电面挂经 + 求助

今天HR告诉我加面，可能面试官没有fail我，大家加油！

bless 楼主

我也觉得union find应该比较好做：
可以分成两步:
union:
需要三个数据结构：
Edge: src, dest, ratio
HashSet<Edge>：从点到其root的dest，key是src和dest
HashMap<Node, Set<Node>>：点和他的root集，因为某个点可能有很多root，比如说A——C，B——C，c的root就是a和b
然后复杂度是O(n^2)
find：
直接在HashSet里面找就可以，总复杂度是O(N)

dimi 发表于 2016-4-1 10:54
仔細想想這題目不難。bfs+backtracking

求问bfs怎么backtracking？

user123456 发表于 2016-3-29 23:20
有向图 + BFS可行。但在推进的过程中，除了需要像普通的BFS需要存一个queue和一个visited的标记外，visit ...

你好，我想问下bfs在遍历时是怎么保存每条路径上的乘机呢？谢谢

用 DFS 就可以了， 只需要经过一个特定点一次， 这个点上的 value 是不会变化的， 没有必要做sum啊等其他的需要遍历多次的情况

daniel_hl 发表于 2016-3-29 14:03
处理完f1后应该要根据graph来建立一个HashMap来存任意两个string的ratio吧，比如HashMap， 这样在处理f2时 ...

根据f1和f2的size来看， 应该也是先根据f1建立Map<Character, Map<Character, ratio>>，然后从任意一点开始BFS or DFS，能reach到的所有点都直接存到上面的Map中，这样f2每次直接查就好了；

另外一种选择是f1只用neighor建好map, 先不BFS. 等到f2的时候开始BFS, 途中遇到的所有点，都更新上面的map,这样只有前面的f2需要BFS，后面的基本都能直接look up，相当于cache了

leetcode 399
ORZ...ORZ....ORZ

看了解释后直接写一次性跑通

1.        public void addEdge(String sa, String sb, double val, Map<String, Map<String, Double>> graph) {
   
2.             Map<String, Double> vertex = graph.get(sa);
   
3.             if (vertex == null) {
   
4.                 vertex = new HashMap<>();
   
5.                 graph.put(sa, vertex);
   
6.             }
   
7.             vertex.put(sb, val);
   
8.         }
   
9. 
   
10.         public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    
11. 
    
12.             Map<String, Map<String, Double>> graph = new HashMap<>();
    
13. 
    
14.             for (int i  = 0; i < values.length; i++) {
    
15.                 String[] syms = equations[i];
    
16.                 String sym1 = syms[0];
    
17.                 String sym2 = syms[1];
    
18.                 addEdge(sym1, sym2, values[i], graph);
    
19.                 addEdge(sym2, sym1, 1 / values[i], graph);
    
20.             }
    
21. 
    
22. 
    
23.             double[] rt = new double[queries.length];
    
24.             for (int i = 0;i < queries.length; i++) {
    
25.                 String[] syms = queries[i];
    
26.                 String sym1 = syms[0];
    
27.                 String sym2 = syms[1];
    
28.                 Map<String, Double> vertexA = graph.get(sym1);
    
29.                 rt[i] = -1;
    
30.                 if (vertexA == null) {
    
31.                     continue;
    
32.                 }
    
33.                 rt[i] = countRatio(graph, sym1, sym2, new HashSet<>());
    
34.             }
    
35.             return rt;
    
36.         }
    
37. 
    
38.         private double countRatio(Map<String, Map<String, Double>> graph, String syma, String symb, Set<String> visited) {
    
39.             Map<String, Double> vertex = graph.get(syma);
    
40.             visited.add(syma);
    
41.             if (vertex == null) return -1;
    
42.             if (syma.equals(symb)) return 1;
    
43.             for (Map.Entry<String, Double> e : vertex.entrySet()) {
    
44.                 String sb = e.getKey();
    
45.                 Double ratio = e.getValue();
    
46.                 if (!visited.contains(sb)) {
    
47.                     double cr = countRatio(graph, sb, symb, visited);
    
48.                     if (cr != -1) {
    
49.                         double res = ratio * cr;
    
50.                         if (visited.contains(symb)) return res;
    
51.                     }
    
52.                 }
    
53.             }
    
54.             return -1;
    
55.         }

复制代码

这么难？