leetcode 399. Evaluate Division 等式求解+典型的DFS深度优先遍历

傷城~ 2022-06-04 06:46 156阅读 0赞

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:  
Given a / b = 2.0, b / c = 3.0.  
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .  
return \[6.0, 0.5, -1.0, 1.0, -1.0 \].

The input is: vector （pair（string, string）） equations, vector（double）& values, vector（pair（string, string）） queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = \[ \[“a”, “b”\], \[“b”, “c”\] \],  
values = \[2.0, 3.0\],  
queries = \[ \[“a”, “c”\], \[“b”, “a”\], \[“a”, “e”\], \[“a”, “a”\], \[“x”, “x”\] \].  
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

题意很简单，就是做一个除法的计算，就是一个DFS深度优先遍历的实现

这道题的要点是可以使用**后继结点来保存树结构，使用父亲节点也可以**，别的都没有难点了

**注意这里的set是为了防止陷入死循环**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        map<string, map<string, double>> m;
        vector<double> calcEquation(vector<pair<string, string>> equations,
            vector<double>& values, vector<pair<string, string>> query)
        {
            vector<double> res;
            for (int i = 0; i < values.size(); ++i)
            {
                m[equations[i].first].insert(make_pair(equations[i].second, values[i]));
                if (values[i] != 0)
                    m[equations[i].second].insert(make_pair(equations[i].first, 1 / values[i]));
            }
    
            for (auto i : query)
            {
                set<string> s;
                double tmp = check(i.first, i.second, s);
                res.push_back(tmp);
            }
            return res;
        }
    
        double check(string up, string down, set<string> &s)
        {
            if (m[up].find(down) != m[up].end())
                return m[up][down];
            else
            {
                for (auto i : m[up])
                {
                    if (s.find(i.first) == s.end())
                    {
                        s.insert(i.first);
                        double tmp = check(i.first, down, s);
                        if (tmp != -1)
                            return i.second*tmp;
                    }
                }
                return -1;
            }
        }
    };