Skip to content

Commit 0fd5389

Browse files
yanglbmeyanglbme
committed
feat: update solutions to lc problem: No.0399
No.0399.Evaluate Division
1 parent 71ecf3f commit 0fd5389

File tree

6 files changed

+122
-139
lines changed

6 files changed

+122
-139
lines changed

‎solution/0300-0399/0399.Evaluate Division/README.md

Lines changed: 42 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,9 @@
6161

6262
<!-- 这里可写通用的实现逻辑 -->
6363

64-
并查集。
64+
并查集。对于本题，具备等式关系的所有变量构成同一个集合，同时，需要维护一个权重数组 w，初始时 `w[i] = 1`。对于等式关系如 `a / b = 2`，令 `w[a] = 2`。在 `find()` 查找祖宗节点的时候，同时进行路径压缩，并更新节点权重。而在合并节点时，`p[pa] = pb`，同时更新 pa 的权重为 `w[pa] = w[b] * (a / b) / w[a]`。
65+
66+
以下是并查集的几个常用模板。
6567

6668
模板 1——朴素并查集：
6769

@@ -120,8 +122,6 @@ p[find(a)] = find(b)
120122
d[find(a)] = distance
121123
```
122124

123-
对于本题，具备等式关系的所有变量构成同一个集合，同时，需要维护一个权重数组 w，初始时 `w[i] = 1`。对于等式关系如 `a / b = 2`，令 `w[a] = 2`。在 `find()` 查找祖宗节点的时候，同时进行路径压缩，并更新节点权重。
124-
125125
<!-- tabs:start -->
126126

127127
### **Python3**
@@ -131,26 +131,24 @@ d[find(a)] = distance
131131
```python
132132
class Solution:
133133
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
134-
w = defaultdict(lambda: 1)
135-
p = defaultdict()
136-
for a, b in equations:
137-
p[a] = a
138-
p[b] = b
139-
140134
def find(x):
141135
if p[x] != x:
142136
origin = p[x]
143137
p[x] = find(p[x])
144138
w[x] *= w[origin]
145139
return p[x]
146140

147-
for i, e in enumerate(equations):
148-
pa, pb = find(e[0]), find(e[1])
141+
w = defaultdict(lambda: 1)
142+
p = defaultdict()
143+
for a, b in equations:
144+
p[a], p[b] = a, b
145+
for i, v in enumerate(values):
146+
a, b = equations[i]
147+
pa, pb = find(a), find(b)
149148
if pa == pb:
150149
continue
151150
p[pa] = pb
152-
w[pa] = w[e[1]] * values[i] / w[e[0]]
153-
151+
w[pa] = w[b] * v / w[a]
154152
return [-1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d] for c, d in queries]
155153
```
156154

@@ -165,8 +163,8 @@ class Solution {
165163

166164
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
167165
int n = equations.size();
168-
p = new HashMap<>(n << 1);
169-
w = new HashMap<>(n << 1);
166+
p = new HashMap<>();
167+
w = new HashMap<>();
170168
for (List<String> e : equations) {
171169
p.put(e.get(0), e.get(0));
172170
p.put(e.get(1), e.get(1));
@@ -184,12 +182,12 @@ class Solution {
184182
w.put(pa, w.get(b) * values[i] / w.get(a));
185183
}
186184
int m = queries.size();
187-
double[] res = new double[m];
185+
double[] ans = new double[m];
188186
for (int i = 0; i < m; ++i) {
189187
String c = queries.get(i).get(0), d = queries.get(i).get(1);
190-
res[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d)) ? - 1.0 : w.get(c) / w.get(d);
188+
ans[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d)) ? - 1.0 : w.get(c) / w.get(d);
191189
}
192-
return res;
190+
return ans;
193191
}
194192

195193
private String find(String x) {
@@ -230,13 +228,13 @@ public:
230228
w[pa] = w[b] * values[i] / w[a];
231229
}
232230
int m = queries.size();
233-
vector<double> res(m);
231+
vector<double> ans(m);
234232
for (int i = 0; i < m; ++i)
235233
{
236234
string c = queries[i][0], d = queries[i][1];
237-
res[i] = p.find(c) == p.end() || p.find(d) == p.end() || find(c) != find(d) ? -1.0 : w[c] / w[d];
235+
ans[i] = p.find(c) == p.end() || p.find(d) == p.end() || find(c) != find(d) ? -1.0 : w[c] / w[d];
238236
}
239-
return res;
237+
return ans;
240238
}
241239

242240
string find(string x) {
@@ -254,46 +252,44 @@ public:
254252
### **Go**
255253

256254
```go
257-
var p map[string]string
258-
var w map[string]float64
259-
260255
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
261-
p = make(map[string]string)
262-
w = make(map[string]float64)
256+
p := make(map[string]string)
257+
w := make(map[string]float64)
263258
for _, e := range equations {
264-
p[e[0]] = e[0]
265-
p[e[1]] = e[1]
266-
w[e[0]] = 1.0
267-
w[e[1]] = 1.0
268-
}
269-
for i, e := range equations {
270259
a, b := e[0], e[1]
260+
p[a], p[b] = a, b
261+
w[a], w[b] = 1.0, 1.0
262+
}
263+
264+
var find func(x string) string
265+
find = func(x string) string {
266+
if p[x] != x {
267+
origin := p[x]
268+
p[x] = find(p[x])
269+
w[x] *= w[origin]
270+
}
271+
return p[x]
272+
}
273+
274+
for i, v := range values {
275+
a, b := equations[i][0], equations[i][1]
271276
pa, pb := find(a), find(b)
272277
if pa == pb {
273278
continue
274279
}
275280
p[pa] = pb
276-
w[pa] = w[b] * values[i] / w[a]
281+
w[pa] = w[b] * v / w[a]
277282
}
278-
var res []float64
283+
var ans []float64
279284
for _, e := range queries {
280285
c, d := e[0], e[1]
281286
if p[c] == "" || p[d] == "" || find(c) != find(d) {
282-
res = append(res, -1.0)
287+
ans = append(ans, -1.0)
283288
} else {
284-
res = append(res, w[c]/w[d])
289+
ans = append(ans, w[c]/w[d])
285290
}
286291
}
287-
return res
288-
}
289-
290-
func find(x string) string {
291-
if p[x] != x {
292-
origin := p[x]
293-
p[x] = find(p[x])
294-
w[x] *= w[origin]
295-
}
296-
return p[x]
292+
return ans
297293
}
298294
```
299295

‎solution/0300-0399/0399.Evaluate Division/README_EN.md

Lines changed: 39 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -64,26 +64,24 @@ Union find.
6464
```python
6565
class Solution:
6666
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
67-
w = defaultdict(lambda: 1)
68-
p = defaultdict()
69-
for a, b in equations:
70-
p[a] = a
71-
p[b] = b
72-
7367
def find(x):
7468
if p[x] != x:
7569
origin = p[x]
7670
p[x] = find(p[x])
7771
w[x] *= w[origin]
7872
return p[x]
7973

80-
for i, e in enumerate(equations):
81-
pa, pb = find(e[0]), find(e[1])
74+
w = defaultdict(lambda: 1)
75+
p = defaultdict()
76+
for a, b in equations:
77+
p[a], p[b] = a, b
78+
for i, v in enumerate(values):
79+
a, b = equations[i]
80+
pa, pb = find(a), find(b)
8281
if pa == pb:
8382
continue
8483
p[pa] = pb
85-
w[pa] = w[e[1]] * values[i] / w[e[0]]
86-
84+
w[pa] = w[b] * v / w[a]
8785
return [-1 if c not in p or d not in p or find(c) != find(d) else w[c] / w[d] for c, d in queries]
8886
```
8987

@@ -96,8 +94,8 @@ class Solution {
9694

9795
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
9896
int n = equations.size();
99-
p = new HashMap<>(n << 1);
100-
w = new HashMap<>(n << 1);
97+
p = new HashMap<>();
98+
w = new HashMap<>();
10199
for (List<String> e : equations) {
102100
p.put(e.get(0), e.get(0));
103101
p.put(e.get(1), e.get(1));
@@ -115,12 +113,12 @@ class Solution {
115113
w.put(pa, w.get(b) * values[i] / w.get(a));
116114
}
117115
int m = queries.size();
118-
double[] res = new double[m];
116+
double[] ans = new double[m];
119117
for (int i = 0; i < m; ++i) {
120118
String c = queries.get(i).get(0), d = queries.get(i).get(1);
121-
res[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d)) ? - 1.0 : w.get(c) / w.get(d);
119+
ans[i] = !p.containsKey(c) || !p.containsKey(d) || !Objects.equals(find(c), find(d)) ? - 1.0 : w.get(c) / w.get(d);
122120
}
123-
return res;
121+
return ans;
124122
}
125123

126124
private String find(String x) {
@@ -161,13 +159,13 @@ public:
161159
w[pa] = w[b] * values[i] / w[a];
162160
}
163161
int m = queries.size();
164-
vector<double> res(m);
162+
vector<double> ans(m);
165163
for (int i = 0; i < m; ++i)
166164
{
167165
string c = queries[i][0], d = queries[i][1];
168-
res[i] = p.find(c) == p.end() || p.find(d) == p.end() || find(c) != find(d) ? -1.0 : w[c] / w[d];
166+
ans[i] = p.find(c) == p.end() || p.find(d) == p.end() || find(c) != find(d) ? -1.0 : w[c] / w[d];
169167
}
170-
return res;
168+
return ans;
171169
}
172170

173171
string find(string x) {
@@ -185,46 +183,44 @@ public:
185183
### **Go**
186184

187185
```go
188-
var p map[string]string
189-
var w map[string]float64
190-
191186
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
192-
p = make(map[string]string)
193-
w = make(map[string]float64)
187+
p := make(map[string]string)
188+
w := make(map[string]float64)
194189
for _, e := range equations {
195-
p[e[0]] = e[0]
196-
p[e[1]] = e[1]
197-
w[e[0]] = 1.0
198-
w[e[1]] = 1.0
199-
}
200-
for i, e := range equations {
201190
a, b := e[0], e[1]
191+
p[a], p[b] = a, b
192+
w[a], w[b] = 1.0, 1.0
193+
}
194+
195+
var find func(x string) string
196+
find = func(x string) string {
197+
if p[x] != x {
198+
origin := p[x]
199+
p[x] = find(p[x])
200+
w[x] *= w[origin]
201+
}
202+
return p[x]
203+
}
204+
205+
for i, v := range values {
206+
a, b := equations[i][0], equations[i][1]
202207
pa, pb := find(a), find(b)
203208
if pa == pb {
204209
continue
205210
}
206211
p[pa] = pb
207-
w[pa] = w[b] * values[i] / w[a]
212+
w[pa] = w[b] * v / w[a]
208213
}
209-
var res []float64
214+
var ans []float64
210215
for _, e := range queries {
211216
c, d := e[0], e[1]
212217
if p[c] == "" || p[d] == "" || find(c) != find(d) {
213-
res = append(res, -1.0)
218+
ans = append(ans, -1.0)
214219
} else {
215-
res = append(res, w[c]/w[d])
220+
ans = append(ans, w[c]/w[d])
216221
}
217222
}
218-
return res
219-
}
220-
221-
func find(x string) string {
222-
if p[x] != x {
223-
origin := p[x]
224-
p[x] = find(p[x])
225-
w[x] *= w[origin]
226-
}
227-
return p[x]
223+
return ans
228224
}
229225
```
230226

‎solution/0300-0399/0399.Evaluate Division/Solution.cpp

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -22,13 +22,13 @@ class Solution {
2222
w[pa] = w[b] * values[i] / w[a];
2323
}
2424
int m = queries.size();
25-
vector<double> res(m);
25+
vector<double> ans(m);
2626
for (int i = 0; i < m; ++i)
2727
{
2828
string c = queries[i][0], d = queries[i][1];
29-
res[i] = p.find(c) == p.end() || p.find(d) == p.end() || find(c) != find(d) ? -1.0 : w[c] / w[d];
29+
ans[i] = p.find(c) == p.end() || p.find(d) == p.end() || find(c) != find(d) ? -1.0 : w[c] / w[d];
3030
}
31-
return res;
31+
return ans;
3232
}
3333

3434
string find(string x) {

0 commit comments

Comments
 (0)