给出一些等式,求给定表达式的结果


描述

方程式以A/B=k格式给出,其中A和B是用字符串表示的变量,k是实数(浮点数)。给定一些查询,返回答案。如果答案不存在,返回-1。

比如给定: A / B = 2.0,B / C = 3.0。
要求: A / C = ? B / A = ? A / E = ?A / A = ?,X / X = ? …

样例

1
2
输入: [ ["a", "b"], ["b", "c"] ],[2.0, 3.0],[ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]
输出: [6.0, 0.5, -1.0, 1.0, -1.0 ]

思路

初期想直接按照实体数字,比如将 a 设定成 1 ,就可以求出 b , 递推求出其他的字母,后来发现这样做之后遇到之前两个字母都没有记录的数字会很麻烦,于是想用一个 rest 集合先保存这些两个字母都没被记录的,等第一轮结束后再进行 rest 集合的处理,后来发现这样也不行,原因在于 rest 集合中也会有两个同时没有出现的,难道再创建一个 rest 2 号吗 ? 显然这样十分的不合理。参考了一份代码,采用的是深度优先搜索,很厉害。注意对集合map<string,<string,map> >的理解。

代码

代码来自
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
class  {
private:
bool dfs(unordered_map<string, unordered_map<string, double> > &m,
string startvalue, string endvalue, unordered_map<string,bool> &visited, double & res) {
if (m.find(startvalue) == m.end() || m.find(endvalue) == m.end()) { return false;}
if (startvalue == endvalue) { return true; }

for (auto iter = m[startvalue].begin(); iter != m[startvalue].end(); iter++) {
if (visited.find(iter->first) != visited.end()) { continue; }
visited[iter->first] = true;
double old = res;
res *= m[startvalue][iter->first];
if (dfs(m, iter->first, endvalue, visited, res)) { return true; }
visited.erase(iter->first);
res = old;
}

return false;
}

public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
vector<double> result;
unordered_map<string, unordered_map<string, double> > m;
for (int i = 0; i < equations.size();i++) {
string first = equations[i].first;
string second = equations[i].second;
m[first][second] = values[i];
m[second][first] = 1.0 / values[i];
}

for (int i = 0; i < queries.size(); i++) {
string start = queries[i].first;
string end = queries[i].second;
double res = 1.0;
unordered_map<string, bool> visited;
visited[start] = true;

if (dfs(m, start, end, visited, res)) { result.push_back(res);}
else { result.push_back(-1.0);}

}
return result;
}
};

参考

原题链接