Evaluate Division

LeetCode

第59天，有好几天没做了，太咸鱼了我。

今天的题目是Evaluate Division:

一道写起来比较麻烦，但是总体来看还是比较简单的。就是分为两步走即可：

  1. 利用equations和value构造一个图
  2. 然后通过在图上遍历的方式计算得到queries的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    vector<double> res(queries.size());
    
    // calc elem set
    unordered_map<string, int> smap;
    int index = 0;
    for(auto &vec: equations) {
        auto it = smap.find(vec[0]);
        if (it == smap.end()) smap[vec[0]] = index++;
        it = smap.find(vec[1]);
        if (it == smap.end()) smap[vec[1]] = index++;
    }
    
    // for(auto p: smap) cout << p.second << endl;
    
    // build graph
    vector<vector<double>> graph(index, vector<double>(index, -1.0));
    for(int k = 0, size = equations.size(); k < size; k++) {
        int i = smap[equations[k][0]], j = smap[equations[k][1]];
        graph[i][j] = values[k];
        graph[j][i] = 1 / values[k];
    }

    for(int k = 0, size = queries.size(); k < size; k++) {
        auto it1 = smap.find(queries[k][0]);
        auto it2 = smap.find(queries[k][1]);
        if (it1 == smap.end() || it2 == smap.end()) {
            res[k] = -1.0;
            continue;
        }
            
        if (queries[k][0] == queries[k][1]) {
            res[k] = 1.0;
            continue;
        }
        
        int i = it1->second, j = it2->second;
        vector<bool> visited(index, false);
        if (dfs(graph, visited,i, j, res[k]) == false) {
            res[k] = -1.0;
        }
    }
    return res;
}

bool dfs(vector<vector<double>> &graph, vector<bool> &visited, int s, int e, double &res) {
    if (s == e) { res = 1.0; return true; }
    visited[s] = true;
    for(int i = 0;i < graph.size(); i++) {
        double temp;
        if (visited[i] == false && graph[s][i] > 0 && dfs(graph, visited, i, e, temp)) {
            res = temp * graph[s][i];
            return true;
        }
    }
    return false;
}