2307：检查方程中的矛盾之处（★★）

力扣第 2307 题

题目

给你一个由字符串二维数组 equations 和实数数组 values ，其中 equations[i] = [Ai, Bi]，values[i] 表示 Ai / Bi = values[i].。

确定方程中是否存在矛盾。如果存在矛盾则返回 true，否则返回 false。

注意:

• 当检查两个数字是否相等时，检查它们的 绝对差值 是否小于 10-5.
• 生成的测试用例没有针对精度的用例，即使用 double 就足以解决问题。

示例 1:

输入: equations = [["a","b"],["b","c"],["a","c"]], values = [3,0.5,1.5]
输出: false
解释:
给定的方程为: a / b = 3, b / c = 0.5, a / c = 1.5
方程中没有矛盾。满足所有方程的一个可能的分配是:
a = 3, b = 1 和 c = 2.

示例 2:

输入: equations = [["le","et"],["le","code"],["code","et"]], values = [2,5,0.5]
输出: true
解释:
给定的方程为: le / et = 2, le / code = 5, code / et = 0.5
根据前两个方程，我们得到 code / et = 0.4.
因为第三个方程是 code / et = 0.5, 所以矛盾。

提示:

• 1 <= equations.length <= 100
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• Ai, Bi 由小写英文字母组成。
• equations.length == values.length
• 0.0 < values[i] <= 10.0
• values[i] 小数点后最多 2 位。

相似问题：

• 0399：除法求值

分析

• 遍历每个连通块，dfs 并赋值，看是否有矛盾即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

eps = 1e-5
class Solution:
    def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:
        g = defaultdict(list)
        for (u,v),w in zip(equations,values):
            g[u].append((v,1/w))
            g[v].append((u,w))
        d = {}
        for u in g:
            if u not in d:
                d[u] = 1
                sk = [u]
                while sk:
                    u = sk.pop()
                    for v,w in g[u]:
                        if v not in d:
                            d[v] = d[u]*w
                            sk.append(v)
                        elif abs(d[v]-d[u]*w)>eps:
                            return True
        return False

0 ms