@@ -12,62 +12,62 @@ public static class Solution1 {
1212/**
1313 * Credit: https://medium.com/@null00/leetcode-evaluate-division-52a0158488c1
1414 */
15- private Map <String ,String >root ;
16- private Map <String ,Double >rate ;
15+ private Map <String ,String >root ;
16+ private Map <String ,Double >rate ;
1717
18- public double []calcEquation (List <List <String >>equations ,double []values ,List <List <String >>queries ) {
19- root =new HashMap <String , String >();
20- rate =new HashMap <String , Double >();
21- int n =equations .size ();
22- for (int i =0 ;i <n ; ++i ) {
23- String X =equations .get (i ).get (0 );
24- String Y =equations .get (i ).get (1 );
25- root .put (X ,X );
26- root .put (Y ,Y );
27- rate .put (X ,1.0 );
28- rate .put (Y ,1.0 );
29- }
18+ public double []calcEquation (List <List <String >>equations ,double []values ,List <List <String >>queries ) {
19+ root =new HashMap <>();
20+ rate =new HashMap <>();
21+ int n =equations .size ();
22+ for (int i =0 ;i <n ; ++i ) {
23+ String X =equations .get (i ).get (0 );
24+ String Y =equations .get (i ).get (1 );
25+ root .put (X ,X );
26+ root .put (Y ,Y );
27+ rate .put (X ,1.0 );
28+ rate .put (Y ,1.0 );
29+
3030
31- for (int i =0 ;i <n ; ++i ) {
32- String X =equations .get (i ).get (0 );
33- String Y =equations .get (i ).get (1 );
34- union (X ,Y ,values [i ]);
35- }
31+ for (int i =0 ;i <n ; ++i ) {
32+ String X =equations .get (i ).get (0 );
33+ String Y =equations .get (i ).get (1 );
34+ union (X ,Y ,values [i ]);
35+ }
36+
37+ double []result =new double [queries .size ()];
38+ for (int i =0 ;i <queries .size (); ++i ) {
39+ String X =queries .get (i ).get (0 );
40+ String Y =queries .get (i ).get (1 );
41+ if (!root .containsKey (X ) || !root .containsKey (Y )) {
42+ result [i ] = -1 ;
43+ continue ;
44+ }
3645
37- double []result =new double [queries .size ()];
38- for (int i =0 ;i <queries .size (); ++i ) {
39- String X =queries .get (i ).get (0 );
40- String Y =queries .get (i ).get (1 );
41- if (!root .containsKey (X ) || !root .containsKey (Y )) {
42- result [i ] = -1 ;
43- continue ;
46+ String rootx =findRoot (X ,X ,1.0 );
47+ String rooty =findRoot (Y ,Y ,1.0 );
48+ result [i ] =rootx .equals (rooty ) ?rate .get (X ) /rate .get (Y ) : -1.0 ;
4449 }
4550
51+ return result ;
52+ }
53+
54+ private void union (String X ,String Y ,double v ) {
4655String rootx =findRoot (X ,X ,1.0 );
4756String rooty =findRoot (Y ,Y ,1.0 );
48- result [i ] =rootx .equals (rooty ) ?rate .get (X ) /rate .get (Y ) : -1.0 ;
57+ root .put (rootx ,rooty );
58+ double r1 =rate .get (X );
59+ double r2 =rate .get (Y );
60+ rate .put (rootx ,v *r2 /r1 );
4961 }
50-
51- return result ;
52- }
5362
54- private void union (String X ,String Y ,double v ) {
55- String rootx =findRoot (X ,X ,1.0 );
56- String rooty =findRoot (Y ,Y ,1.0 );
57- root .put (rootx ,rooty );
58- double r1 =rate .get (X );
59- double r2 =rate .get (Y );
60- rate .put (rootx ,v *r2 /r1 );
61- }
63+ private String findRoot (String originalX ,String X ,double r ) {
64+ if (root .get (X ).equals (X )) {
65+ root .put (originalX ,X );
66+ rate .put (originalX ,r *rate .get (X ));
67+ return X ;
68+ }
6269
63- private String findRoot (String originalX ,String X ,double r ) {
64- if (root .get (X ).equals (X )) {
65- root .put (originalX ,X );
66- rate .put (originalX ,r *rate .get (X ));
67- return X ;
70+ return findRoot (originalX ,root .get (X ),r *rate .get (X ));
6871 }
69-
70- return findRoot (originalX ,root .get (X ),r *rate .get (X ));
71- }
7272 }
7373}