难度: Hard
Submission
运行时间: 35 ms
内存: 16.4 MB
from collections import defaultdict, deque
from typing import List
class Solution:
def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:
"""
:param equations:
:param values:
:return:
"""
s1 = set()
m1 = {}
for k, v in enumerate(equations):
s1.add(v[0])
s1.add(v[1])
ll1 = list(s1)
for k, v in enumerate(ll1):
m1[v] = k
ll1 = list(s1)
for k,v in enumerate(ll1):
m1[v] = k
factorM = defaultdict(list)
for k,v in enumerate(equations):
v[0] = m1[v[0]]
v[1] = m1[v[1]]
factorM[v[0]].append((v[1], values[k]))
factorM[v[1]].append((v[0], 1 / values[k]))
def check_ok(startnode, factor_map):
dq = deque()
dq.append(startnode)
assign_map = {}
used = set()
while dq:
cur = dq.popleft()
if cur in used:
continue
used.add(cur)
anchorv = 1
if cur in assign_map:
anchorv = assign_map[cur]
linkednode = factor_map.get(cur, [])
for i in linkednode:
if i[0] not in assign_map:
assign_map[i[0]] = i[1] * anchorv
else:
if abs(i[1] * anchorv - assign_map[i[0]]) > 10**-4:
return False, used
dq.append(i[0])
return True, used
u1 = set()
for i in s1:
cur = m1[i]
if cur in u1:
continue
ret, used = check_ok(cur, factorM)
if ret is False:
return True
u1 = u1.union(used)
return False
a = Solution()
print(a.checkContradictions(equations = [["a","b"],["b","c"],["a","c"]], values = [3,0.5,1.5]))
print(a.checkContradictions( equations = [["le","et"],["le","code"],["code","et"]], values = [2,5,0.5]))
print(a.checkContradictions([["sml","gf"],["sml","myt"],["d","gf"],["myt","rlpk"],["d","gf"],["rlpk","rlpk"]],
[9.44,4.25,8.63,6.07,8.63,1]))
Explain
此题解利用图的理论来解决方程组的矛盾检查问题。首先，构建了每个变量到其索引的映射，然后将方程转化为有向图的形式，其中边的权重表示方程中两个变量的比值。接着使用广度优先搜索（BFS）检查图中是否存在矛盾。矛盾的定义是在图的遍历过程中，同一个变量计算得到的值不一致（在允许的误差范围内）。具体地，如果从一个节点出发，经过一系列转换后返回该节点时，比值乘积与1的差值大于设定的阈值，则判定为存在矛盾。
时间复杂度: O(N)
空间复杂度: O(N)
from collections import defaultdict, deque
from typing import List
class Solution:
def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:
# 创建变量到索引的映射
variable_to_index = {}
variables = set(sum(equations, []))
for index, variable in enumerate(variables):
variable_to_index[variable] = index
# 构建图表示方程
graph = defaultdict(list)
for (var1, var2), value in zip(equations, values):
index1 = variable_to_index[var1]
index2 = variable_to_index[var2]
graph[index1].append((index2, value))
graph[index2].append((index1, 1 / value))
# 检查图中的矛盾
def bfs_check(index):
queue = deque([index])
assigned_values = {}
visited = set()
while queue:
current = queue.popleft()
if current in visited:
continue
visited.add(current)
current_value = assigned_values.get(current, 1)
for neighbor, factor in graph[current]:
calculated_value = factor * current_value
if neighbor not in assigned_values:
assigned_values[neighbor] = calculated_value
elif abs(calculated_value - assigned_values[neighbor]) > 1e-4:
return False
queue.append(neighbor)
return True
visited_nodes = set()
for index in variables:
if index not in visited_nodes:
if not bfs_check(index):
return True
visited_nodes.update(visited)
return False
Explore
在构建图的过程中，选择使用有向图是因为每个方程表示的是一个方向性的比值关系，例如方程表示 a = k * b（其中 k 是一定的比值），这意味着从 a 到 b 的关系是乘以 k，而从 b 到 a 的关系则是乘以 1/k。这种比值的方向性使得有向图成为表示这类问题的自然选择。在无向图中，边缘并不区分方向，这将使得方程的比值关系难以准确表示。
阈值1e-4的设定是为了处理计算中的浮点数精度问题。在实际的计算中，由于浮点数的存储和运算特性，可能会引入极小的误差。设定一个小的阈值可以帮助算法区分这些微小的误差和真正的逻辑矛盾。这个值的选择通常是基于经验和具体应用场景的需要，可以根据实际情况调整。在不同的应用中，这个阈值可能需要根据方程的敏感度和精度需求进行调整。
在实现中，通过维护一个已访问节点集合来处理环的问题。在BFS过程中，每次从队列中取出一个节点时，会检查这个节点是否已经被访问过。如果已访问，则跳过该节点，这样可以防止算法重复遍历同一节点并导致无限循环。此外，通过对每个节点分配一个计算得到的值，并在遍历其相邻节点时检查新计算的值与已分配值的一致性，来检测是否存在矛盾。
在BFS遍历时选择初始节点的值为1是因为这提供了一个基准值，以便于从该节点出发计算其他节点的值。选择1作为起始值是因为1是乘法运算的单位元素，任何数与1相乘都不会改变其值，这使得从任何一个节点开始计算都是等价的。这种选择不会影响算法的正确性，因为最终检测矛盾的是比值之间的一致性而不是绝对值。此外，这也不会影响算法的效率，因为所有节点的初始值选择是相同的，不会增加额外的计算负担。