FilesExpand file tree

 master

/

EvaluateDivision.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

67 lines (59 loc) · 2.04 KB

 master

/

EvaluateDivision.java

Copy path

Top

File metadata and controls

• Code
• Blame

67 lines (59 loc) · 2.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

/**

* 1, 首先给除的结果都存起来，建立有向图

* 2，用DFS遍历路径

*/

public class EvaluateDivision {

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {

HashMap<String, HashMap<String, Double>> table = new HashMap<>();

for (int i = 0; i < equations.length; i++) {

add(table, equations[i], values[i]);

}

double[] result = new double[queries.length];

HashSet<String> visited = new HashSet<>();

for (int i = 0; i < queries.length; i++) {

visited.clear();

result[i] = calc(table, visited, queries[i][0], queries[i][1]);

}

return result;

}

private double calc(HashMap<String, HashMap<String, Double>> table, HashSet<String> visited, String a, String b) {

HashMap<String, Double> map = table.get(a);

if (map == null) {

return -1.0;

}

if (a.equals(b)) {

return 1.0;

}

for (Map.Entry<String, Double> entry : map.entrySet()) {

String key = entry.getKey();

Double value = entry.getValue();

if (visited.contains(key)) {

continue;

}

visited.add(key);

double t = calc(table, visited, key, b);

if (t != -1.0) {

return value * t;

}

visited.remove(key);

}

return -1.0;

}

private void add(HashMap<String, HashMap<String, Double>> table, String[] equation, double value) {

HashMap<String, Double> map0 = table.get(equation[0]);

HashMap<String, Double> map1 = table.get(equation[1]);

if (map0 == null) {

map0 = new HashMap<>();

table.put(equation[0], map0);

}

if (map1 == null) {

map1 = new HashMap<>();

table.put(equation[1], map1);

}

map0.put(equation[1], value);

map1.put(equation[0], 1 / value);

}

}