-
Notifications
You must be signed in to change notification settings - Fork 123
Expand file tree
/
Copy pathEvaluate Division.js
More file actions
80 lines (57 loc) · 2.07 KB
/
Copy pathEvaluate Division.js
File metadata and controls
80 lines (57 loc) · 2.07 KB
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
78
79
80
var calcEquation = function(equations, values, queries) {
const res = []
for(let i = 0; i < queries.length; i++) {
const currQuery = queries[i]
const [currStart, currDestination] = currQuery
const adj = {}
const additionalEdges = []
const additionalValues = []
const visited = new Set()
equations.forEach((el,idx) => {
const [to, from] = el
const val = values[idx]
additionalEdges.push([from, to])
additionalValues.push(1/val)
})
values = [...values, ...additionalValues]
let idx = 0
for(const [from, to] of [...equations, ...additionalEdges]) {
if(!(from in adj)) adj[from] = []
adj[from].push([to, values[idx]])
idx++
}
if(!(currStart in adj) || !(currDestination in adj)) {
res.push(-1)
continue
}
if(currStart === currDestination) {
res.push(1)
continue
}
let currEvaluation = 1
let found = false
const subResult = dfs(currStart)
if(!found) res.push(-1)
function dfs(node) {
if(!node) return null
if(node === currDestination) {
return true
}
const children = adj[node] // [ [to, val] ]
if(!children) return false
for(const child of children) {
if(visited.has(node)) continue
visited.add(node)
currEvaluation = currEvaluation*child[1]
if(dfs(child[0]) === true) {
!found && res.push(currEvaluation)
found = true
return
}
visited.delete(node)
currEvaluation /= child[1]
}
}
}
return res
};