酷炫网站,最新新闻热点事件今天,织梦猫html5高端网络服务机构网站模板,深圳网站制作公司深圳app开发1. 题目
给出方程式 A / B k, 其中 A 和 B 均为用字符串表示的变量#xff0c; k 是一个浮点型数字。 根据已知方程式求解问题#xff0c;并返回计算结果。如果结果不存在#xff0c;则返回 -1.0。
示例 :
给定 a / b 2.0, b / c 3.0
问题: a / c ?, b / a ?, a / …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 ]输入为:
vectorpairstring, string equations,
vectordouble values,
vectorpairstring, string queries(方程式方程式结果问题方程式)
其中 equations.size() values.size()
即方程式的长度与方程式结果长度相等程式与结果一一对应并且结果值均为正数。
以上为方程式的描述。 返回vectordouble类型。基于上述例子输入如下
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_mapstring,unordered_mapstring,double m;//图的矩阵表示unordered_setstring visited;vectordouble ans;bool found;int idx 0;
public:vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring 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
