1. 題目

給出方程式 A / B = k, 其中 A 和 B 均為用字符串表示的變量， k 是一個浮點型數字。
根據已知方程式求解問題，并返回計算結果。如果結果不存在，則返回 -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 ]輸入為: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式結果，問題方程式)， 其中 equations.size() == values.size()， 即方程式的長度與方程式結果長度相等（程式與結果一一對應），并且結果值均為正數。 以上為方程式的描述。 返回vector<double>類型。基于上述例子，輸入如下： equations(方程式) = [ ["a", "b"], ["b", "c"] ], values(方程式結果) = [2.0, 3.0], queries(問題方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 輸入總是有效的。你可以假設除法運算中不會出現除數為0的情況，且不存在任何矛盾的結果。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/evaluate-division
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution {unordered_map<string,unordered_map<string,double>> m;//圖的矩陣表示unordered_set<string> visited;vector<double> ans;bool found;int idx = 0; public:vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {for(int i = 0; i < equations.size(); ++i){m[equations[i][0]][equations[i][1]] = values[i];//正向m[equations[i][1]][equations[i][0]] = 1.0/values[i];//反向}ans.resize(queries.size());for(int i = 0; i < queries.size(); ++i){if(queries[i][0] == queries[i][1])//分子分母一樣{if(m.count(queries[i][0]))ans[idx++] = 1.0;elseans[idx++] = -1.0;continue;}else if(m.count(queries[i][0]) && m[queries[i][0]].count(queries[i][1])){ans[idx++] = m[queries[i][0]][queries[i][1]];//存在通路，直接讀取continue;}found = false;visited.insert(queries[i][0]);//訪問標記dfs(queries[i][0], queries[i][0], queries[i][1], 1.0);if(!found)ans[idx++] = -1.0;visited.erase(queries[i][0]);//回溯}return ans;}void dfs(string& from, string mid, string &to, double v){if(found)return;if(mid == to)//找到了{ans[idx++] = v;m[from][to] = v;//存取起來，方便后面直接讀取m[to][from] = 1.0/v;found = true;return;}for(auto it = m[mid].begin(); it != m[mid].end(); ++it){if(!visited.count(it->first))//沒訪問過到達點{visited.insert(it->first);//訪問標記dfs(from, it->first, to, v*m[mid][it->first]);//一路上value相乘visited.erase(it->first);//回溯}}} };

8 ms 7.9 MB

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 399. 除法求值（图的DFS搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

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