题目描述

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

样例

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

算法1

(BFS Flood Fill) $O(M)$

考虑A / B * B / C = A / C，因此可以建模成有向图的问题，A / B = k实际上是A和B两个节点之间有一条从A指向B的权值为k的边，不同于最短路问题的是，这里的边权不是相加而是相乘。

考虑bfs，假设有A / B = k1, B / C = k2，从一个变量出发，例如从A出发，通过权值为k1的边到达B，相当于得到B = 1/k1 * A，然后再通过权值为k2的边从B到达C，相当于C = 1 / k2 * B = 1/k2 * 1/k1 * A，于是与A连通的所有变量都可以用A的值来表示，例如假设M = p * A, N = q * A，于是M / N = p / q。

由于来的query有很多条，因此可以考虑通过bfs的flood fill的方法，把与每个变量连通的所有变量都预处理出来与起始变量的关系，然后对每条query判断是否在同一连通块里并且直接求值即可。

时间复杂度

建图的时候每条边会遍历一遍，bfs中每个变量（就是每个节点）会遍历一遍，所以复杂度为$O(M)$（M为边数）。

Python3 代码

from collections import defaultdict, deque
class Solution:
    def bfs(self, var, edges, var_val): # 求出以变量var起始的所有连通变量的相对自己的值
        q = deque()
        q.append((var, 1.0)) # 起始变量为var, var / var = 1.0
        var_val[var] = (var, 1.0)
        while len(q) > 0:
            point, val = q.popleft()
            if point not in edges:
                continue
            for nxt_point, nxt_val in edges[point]:
                if var_val[nxt_point] == None: # 说明nxt_point没有访问过
                    var_val[nxt_point] = (var, nxt_val * val) # 边权是相乘
                    q.append((nxt_point, nxt_val * val))

    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # var_val记录每个变量在bfs过程中，得到的相对于起始变量的值，key是变量名，value是(起始变量，相对于起始变量的值)
        var_val = {} 
        edges = defaultdict(list) # 将输入的方程式建成有向图中的边
        for i, equation in enumerate(equations):
            if equation[0] not in var_val:
                var_val[equation[0]] = None 
            if equation[1] not in var_val:
                var_val[equation[1]] = None 
            edges[equation[0]].append((equation[1], values[i])) 
            edges[equation[1]].append((equation[0], 1.0 / values[i])) # A / B = k => B / A = 1/k
        for var in var_val: # Flood Fill
            if var_val[var] == None:
                self.bfs(var, edges, var_val)
        res = []
        for query in queries:
            if query[0] in var_val and query[1] in var_val and var_val[query[0]][0] == var_val[query[1]][0]: 
            # 只有query的两个变量都相对于同一个起始变量有值，例如N = p * A, M = q * A时，才能做除法
                res.append(var_val[query[1]][1] / var_val[query[0]][1])
            else:
                res.append(-1.0)
        return res

算法2

(Floyd) $O(N^3)$

在解法1中，我们把这道题看成一个有向图的问题，根据输入的方程式建成了有向图，那么query实际上就是求图中任意两个点的距离，很明显，A / C = A / B * B / C，于是这里的距离不是权值的加和而是相乘而已。求图中多源最短路问题可以考虑Floyd算法，只是把代码里的加法变成乘法。

Floyd算法本质是dp, dp[i][j]表示求到的变量i / 变量j的除法结果。

时间复杂度

三重循环，复杂度为$O(N^3)$，N是变量（即节点）个数。

Python3 代码

from collections import defaultdict, deque
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        var_idx_dict = {} # 建立变量名到点的下标的映射关系，把变量名映射到从0-N的数字
        idx = 0
        for equation in equations:
            for var in equation:
                if var not in var_idx_dict:
                    var_idx_dict[var] = idx
                    idx += 1
        dp = [[-1.0 for i in range(idx)] for j in range(idx)] # dp[i][j]表示 变量i / 变量j = dp[i][j]
        for i, equation in enumerate(equations): # 初始化图
            idx1, idx2 = var_idx_dict[equation[0]], var_idx_dict[equation[1]]
            dp[idx1][idx2] = values[i]
            dp[idx2][idx1] = 1.0 / values[i]
        for i in range(idx):
            dp[i][i] = 1.0
        for k in range(idx): # 注意Floyd的三层循环顺序
            for i in range(idx):
                for j in range(idx):
                    if dp[i][k] >= 0.0 and dp[k][j] >= 0.0: # 考虑第k个变量，i / j = i / k * k / j
                        dp[i][j] = dp[i][k] * dp[k][j]
        res = []
        for query in queries:
            if query[0] in var_idx_dict and query[1] in var_idx_dict:
                idx1, idx2 = var_idx_dict[query[0]], var_idx_dict[query[1]]
                res.append(dp[idx1][idx2])
            else:
                res.append(-1.0)
        return res