天津建设协会网站,程序员培训机构出来找工作好找吗,网站编程入门,邵阳市城乡建设厅网站问题简介
给定一些由变量组成的等式组#xff0c;然后根据这些等式推算出所闻的等式的结果#xff0c;如果无法推算#xff0c;则返回-1.0。 比如#xff1a;
给定等式组
a / b 2.0, b / c 3.0
求出
a / c ?, b / a ?, a / e ?, a / a ?, x / x ?
返回结果为…问题简介
给定一些由变量组成的等式组然后根据这些等式推算出所闻的等式的结果如果无法推算则返回-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/b2.0 a/b=2.0 这样的等式时同时也保存了b/a0.5 b/a=0.5 。
// 构造一个结构体
struct 节点{是否访问过;unordered_map除数, 结果;
};// 构造稀疏图
unordered_map变量, 节点;
然后根据询问的内容做深度优先遍历即可。
源代码
struct Node{bool visited;unordered_mapstring, double children;Node(){visited false;}
};class Solution {
private:vectordouble res;private:bool dfs(unordered_mapstring, Node* mp, pairstring, 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){pairstring, 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:vectordouble calcEquation(vectorpairstring, string equations, vectordouble values, vectorpairstring, string queries) {// 构造图unordered_mapstring, 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;}
};
