evaluate division

topic
1.5k 词
  • 问题来源
  • 问题简介

    给出一系列式子 a / b = k（k为非零小数），要求算出指定的算式，如:
    给出 a / b = 2.0, b / c = 3.0；
    则求 a / c。
    结果: 6.0
    若求不出，则为 -1。

解题思路

时间复杂度 空间复杂度
O(未知) O(未知)

Code

class Solution {
public:
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        unordered_map<string, unordered_map<string, double>> next;
        unordered_set<string> all;
        pair<string, string> cur;
        double val;
        for (int i = 0, len = equations.size(); i < len; i++) {
            cur = equations[i];
            val = values[i];
            next[cur.first][cur.second] = val;
            next[cur.second][cur.first] = 1 / val;
            all.insert(cur.first);
            all.insert(cur.second);
        }
        vector<double> rs(queries.size(), -1.0);
        auto it = rs.begin();
        for (auto &i : queries) {
            auto a_c = all;
            if (next.find(i.first) == next.end() || next.find(i.second) == next.end()) {
                *it++ = -1;
            } else {
                *it++ = dfs(i.first, i.second, next, a_c);
            }
        }
        return rs;
    }

double dfs(const string &amp;cur, const string &amp;goal,
           unordered_map&lt;string, unordered_map&lt;string, double&gt;&gt; &amp;next,
          unordered_set&lt;string&gt; &amp;all) {
    if (cur == goal) {
        return next.find(cur) != next.end() ? !!(next[cur].begin() -&gt; second) : -1;
    }
    if (next[cur].find(goal) != next[cur].end()) {
        return next[cur][goal];
    }
    all.erase(cur);
    auto &amp;next_set = next[cur];
    double nextVal = -1;
    for (auto &amp;i : next_set) {
        if (all.find(i.first) == all.end()) {
            continue;
        }
        nextVal = dfs(i.first, goal, next, all);
        if (nextVal != -1) {
            return nextVal * i.second;
        }
    }
    return -1;
}



};

运行结果

Evaluate Division