-
-
Notifications
You must be signed in to change notification settings - Fork 10
/
399 Evaluate Division.swift
77 lines (60 loc) 路 2.58 KB
/
399 Evaluate Division.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//
// 399 Evaluate Division.swift
// LeetCode-Solutions
//
// Created by Aleksandar Dinic on 27/09/2020.
// Copyright 漏 2020 Aleksandar Dinic. All rights reserved.
//
import Foundation
/// Source: https://leetcode.com/problems/evaluate-division/
class Solution {
/// Evaluates division for given equations.
///
/// - Parameters:
/// - equations: The equations in the format A / B = k.
/// - values: The values.
/// - queries: The queries.
/// - Returns: The answers, if the answer does not exist return -1.0.
///
/// - Complexity:
/// - time: O((n + m) log(n)), where n is the number of equations and m is the number
/// of queries.
/// - space: O(n), where n is the number of equations.
func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
var gidWeight = [String: (key: String, value: Double)]()
for (i, equation) in equations.enumerated() {
union(&gidWeight, dividend: equation[0], divisor: equation[1], value: values[i])
}
var ans = [Double]()
for querie in queries {
if !gidWeight.keys.contains(querie[0]) || !gidWeight.keys.contains(querie[1]) {
ans.append(-1.0)
} else {
let dividendEntry = find(&gidWeight, querie[0])
let divisorEntry = find(&gidWeight, querie[1])
if dividendEntry.key != divisorEntry.key {
ans.append(-1.0)
} else {
ans.append(dividendEntry.value / divisorEntry.value)
}
}
}
return ans
}
private func union(_ gidWeight: inout [String: (key: String, value: Double)], dividend: String, divisor: String, value: Double) {
let dividendEntry = find(&gidWeight, dividend)
let divisorEntry = find(&gidWeight, divisor)
guard dividendEntry.key != divisorEntry.key else { return }
gidWeight[dividendEntry.key] = (divisorEntry.key, divisorEntry.value * value / dividendEntry.value)
}
private func find(_ gidWeight: inout [String: (key: String, value: Double)], _ nodeID: String) -> (key: String, value: Double) {
if !gidWeight.keys.contains(nodeID) {
gidWeight[nodeID] = (nodeID, 1.0)
}
let entry = gidWeight[nodeID] ?? (nodeID, 1.0)
guard entry.key != nodeID else { return entry }
let newEntry = find(&gidWeight, entry.key)
gidWeight[nodeID] = (newEntry.key, entry.value * newEntry.value)
return gidWeight[nodeID] ?? (nodeID, 1.0)
}
}