問題簡介

給定一些由變量組成的等式組，然后根據這些等式推算出所聞的等式的結果，如果無法推算，則返回-1.0。
比如：

給定等式組 a / b = 2.0, b / c = 3.0 求出 a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 返回結果為 [ 6.0, 0.5, -1.0, 1.0, -1.0 ]

注：給定的等式組不存在結果為0的情況。

解題思路

先構造一個數據結構，然后根據給定的等式構造一個map，便于訪問，這其實就相當與是一幅稀疏圖。
要注意的是，這里在保存a/b=2.0這樣的等式時，同時也保存了b/a=0.5。

// 構造一個結構體 struct 節點{是否訪問過;unordered_map<除數, 結果>; };// 構造稀疏圖 unordered_map<變量, 節點>;

然后根據詢問的內容做深度優先遍歷即可。

源代碼

struct Node{bool visited;unordered_map<string, double> children;Node(){visited = false;} };class Solution { private:vector<double> res;private:bool dfs(unordered_map<string, Node*>& mp, pair<string, string>& p, double r){if (mp.find(p.first) != mp.end() && !mp[p.first]->visited){mp[p.first]->visited = true;if (mp[p.first]->children.find(p.second) != mp[p.first]->children.end()){res.push_back(r * mp[p.first]->children[p.second]);mp[p.first]->visited = false;return true;}else{for (auto iter = mp[p.first]->children.begin(); iter != mp[p.first]->children.end(); iter++){pair<string, string> new_p = make_pair(iter->first, p.second);if (dfs(mp, new_p, r * iter->second)){mp[p.first]->visited = false;return true;}}}mp[p.first]->visited = false;}return false;}public:vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {// 構造圖unordered_map<string, Node*> mp;for (int i = 0; i < equations.size(); i++){// 保存a/bif (mp.find(equations[i].first) == mp.end()){mp[equations[i].first] = new Node();}Node* tmp = mp[equations[i].first];if (tmp->children.find(equations[i].second) == tmp->children.end()){tmp->children[equations[i].second] = values[i];}// 保存b/aif (mp.find(equations[i].second) == mp.end()){mp[equations[i].second] = new Node();}tmp = mp[equations[i].second];if (tmp->children.find(equations[i].first) == tmp->children.end()){tmp->children[equations[i].first] = 1.0 / values[i];}}// 開始執行queryfor (int i = 0; i < queries.size(); i++){if (queries[i].first == queries[i].second){if (mp.find(queries[i].first) != mp.end())res.push_back(1.0);elseres.push_back(-1.0);}else{if (!dfs(mp, queries[i], 1.0)){res.push_back(-1.0);}}}return res;} };

總結

以上是生活随笔為你收集整理的利用哈希表和dfs解决LeetCode 399. Evaluate Division的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。