class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_set<string> node;//记录所有节点
unordered_map<string,unordered_map<string,double>> g;//存储图
int n=equations.size(),m=queries.size();
for(int i=0;i<n;i++)
{
string a=equations[i][0],b=equations[i][1];
double c=values[i];
//a->b的权值为c
node.insert(a);node.insert(b);
g[a][b]=c;g[b][a]=1/c;
}
vector<double> res;
for(int i=0;i<m;i++)//处理询问
{
string a=queries[i][0],b=queries[i][1];
if(node.find(a)==node.end()||node.find(b)==node.end())
res.push_back(-1);
else
{
double path=1;
unordered_map<string,bool> st;
st[a]=true;
if(!dfs(a,b,g,path,st)) path=-1;
res.push_back(path);
}
}
return res;
}
bool dfs(string a,string b,unordered_map<string,unordered_map<string,double>> &g,double &sum,unordered_map<string,bool> &st)
{
if(a==b)
return true;
for(auto item:g[a])
{
string t=item.first;
if(!st[t])
{
st[t]=true;
if(dfs(t,b,g,sum,st))
{
sum*=item.second;
return true;
}
}
}
return false;
}
};
LeetCode 399. 除法求值
发布时间 2023-07-24 12:32:27作者: 穿过雾的阴霾