Difficulty: Medium
Link: https://leetcode.com/problems/evaluate-division/
Problem
Explanation
- 其實(shí)這道題的核心思想就是圖推汽，尋找兩個(gè)點(diǎn)在該無向圖中是否是聯(lián)通的颖御。我在此解法中采用了hash表來存儲(chǔ)汪诉，提高了搜索效率，然后是DFS（深度優(yōu)先遍歷查找）耀石。
- 提交了一次wrong answer。中途遇到兩個(gè)問題：
- 標(biāo)記路徑的
used[i]必須要對(duì)稱，即使用了used[i] = true溉痢，必須要有一個(gè)used[i] = false與之對(duì)應(yīng)塘揣。（在不符合條件的情況下正嘲福回溯查找） - 在搜索完成之后，對(duì)于沒有查找到結(jié)果的要將其設(shè)置為-1.0亲铡。
- 標(biāo)記路徑的
cpp solution
class Solution {
public:
unordered_map<string, unordered_map<string, double>> hash;
unordered_map<string, bool> used;
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
int size = queries.size();
vector<double> res(size, 0.0);
for (int i = 0; i < equations.size(); i++) {
auto p = equations[i];
hash[p.first][p.second] = values[i];
hash[p.second][p.first] = 1 / values[i];
}
for (int i = 0; i < size; i++) {
if (hash.find(queries[i].first) == hash.end() || hash.find(queries[i].second) == hash.end()) {
res[i] = -1.0;
continue;
}
find(1.0, res, queries[i].first, queries[i].second, i);
if (res[i] == 0) {
res[i] = -1.0; // 發(fā)現(xiàn)第二個(gè)問題后添加的代碼
}
}
return res;
}
void find(double cur, vector<double> &res, string s, string t, int i) {
if (res[i] != 0) {
return;
}
if (hash.find(s) == hash.end() ) {
res[i] = -1.0;
return;
} else {
if (s == t) {
res[i] = cur;
return;
} else {
auto tmp = hash[s];
used[s] = true;
for (auto &p : hash[s] ) {
if (used.find(p.first) == used.end() || used[p.first] == false) {
used[p.first] = true;
find(cur * p.second, res, p.first, t, i);
used[p.first] = false;
}
}
used[s] = false; // 發(fā)現(xiàn)第一個(gè)問題后添加的代碼
}
}
}
};
