Code & Fun

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

今天的题目是Evaluate Division:

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

  1. 利用equationsvalue构造一个图
  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;
}

本文首发于Code & Fun