LeetCode 399. 除法求值

题目描述

给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量, k 是一个浮点型数字。根据已知方程式求解问题,并返回计算结果。如果结果不存在,则返回 -1.0

输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况,且不存在任何矛盾的结果。

示例1:

输入:equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出:[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释:
给定: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 ]

示例2:

输入:equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出:[3.75000,0.40000,5.00000,0.20000]

示例3:

输入:equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出:[0.50000,2.00000,-1.00000,-1.00000]

提示:

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= equations[i][0].length, equations[i][1].length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= queries[i][0].length, queries[i][1].length <= 5
  • equations[i][0], equations[i][1], queries[i][0], queries[i][1] 由小写英文字母与数字组成

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/evaluate-division

思路解析

深度优先搜索(DFS)

  1. unordered_map<string, unordered_map<string, double>> graph 表示图,可以通过访问graph['a']['b']得到\(a/b\)的结果(如果存在)。
  2. unordered_set<string> visited 表示已经访问过的节点。
  3. 若要计算\(a / b\):
    • 查找是否存在graph['a']['b'],若存在,直接返回结果;
    • 若不存在graph['a']['b'],则查找graph['a']中存在哪些节点,比如存在'c', 'd'...,则分别查找graph['c']['b']graph['d']['b']
    • 倘若从graph['c']['b']中找到了结果,记为t,则返回t * graph['a']['c']
    • 若都没有找到结果,返回-1

代码实现

class Solution {
private:
    unordered_map<string, unordered_map<string, double>> graph;
    double dfs(string src, string dst, unordered_set<string> visited) {
        if(graph[src].count(dst))
            return graph[src][dst];
        for(const auto subequation : graph[src]) {
            if(visited.count(subequation.first))
                continue;
            visited.insert(subequation.first);
            double t = dfs(subequation.first, dst, visited);
            if(t > 0)
                return t * subequation.second;
        }
        return -1;
    }
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for(int i = 0; i < equations.size(); i++) {
            auto e = equations[i];
            graph[e[0]][e[1]] = values[i];
            graph[e[1]][e[0]] = 1.0 / values[i];
        }
        vector<double> result;
        for(auto q : queries) {
            unordered_set<string> visited;
            double res = dfs(q[0], q[1], visited);
            result.push_back(res);
        }
        return result;
    }
};
上一篇:回溯:79、单词搜索


下一篇:矩阵中的路径