算法练习——除法求值

2021年1月6日,LeetCode每日一题为399. 除法求值,这一题定义的难度为中等,但是对于数据结构学的不是特别好,算法思维还没有建立成体的玩家来说,这个难度还是有点高的,刚看题目的时候第一个想法是先将已知的用map建立起映射,然后通过查询的值来用克鲁斯卡尔算法那种思想来进行求解,a除b,b除c就等于a除c,找一条路径,也就是图的结构和算法。但是到后面却无从下手,可能是对图不够熟悉,看了题解后,也不是特别好理解,花了点时间。下面附上题解代码以及题解地址题解

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
class Solution {

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int nvars = 0;
Map<String, Integer> variables = new HashMap<String, Integer>();

int n = equations.size();
for (int i = 0; i < n; i++) {
if (!variables.containsKey(equations.get(i).get(0))) {
variables.put(equations.get(i).get(0), nvars++);
}
if (!variables.containsKey(equations.get(i).get(1))) {
variables.put(equations.get(i).get(1), nvars++);
}
}

List<Pair>[] edges = new List[nvars];
for (int i = 0; i < nvars; i++) {
edges[i] = new ArrayList<Pair>();
}
for (int i = 0; i < n; i++) {
int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
edges[va].add(new Pair(vb, values[i]));
edges[vb].add(new Pair(va, 1.0 / values[i]));
}

int queriesCount = queries.size();
double[] ret = new double[queriesCount];
for (int i = 0; i < queriesCount; i++) {
List<String> query = queries.get(i);
double result = -1.0;
if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
int ia = variables.get(query.get(0)), ib = variables.get(query.get(1));
if (ia == ib) {
result = 1.0;
} else {
Queue<Integer> points = new LinkedList<Integer>();
points.offer(ia);
double[] ratios = new double[nvars];
Arrays.fill(ratios, -1.0);
ratios[ia] = 1.0;

while (!points.isEmpty() && ratios[ib] < 0) {
int x = points.poll();
for (Pair pair : edges[x]) {
int y = pair.index;
double val = pair.value;
if (ratios[y] < 0) {
ratios[y] = ratios[x] * val;
points.offer(y);
}
}
}
result = ratios[ib];
}
}
ret[i] = result;
}
return ret;
}
}

class Pair {
int index;
double value;

Pair(int index, double value) {
this.index = index;
this.value = value;
}
}

虽然能想到图,但是对于广度优先和深度优先的熟练度不够,同时也是因为基础不够扎实,导致不够自信,想到图之后,就卡壳了,因此对于基础的数据结构与算法还需要跟进扎实一下。