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

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

傷城~ 2022-06-04 06:46 297阅读 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;
        }
    }
};