Leetcode-399.除法求值

描述

给出方程式 A / B = k, 其中AB 均为代表字符串的变量, k 是一个浮点型数字。根据已知方程式求解问题,并返回计算结果。如果结果不存在,则返回 -1.0。

示例 :

1
2
3
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式,方程式结果,问题方程式), 其中equations.size() == values.size(),即方程式的长度与方程式结果长度相等(程式与结果一一对应),并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。

基于上述例子,输入如下:

1
2
3
equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

输入总是有效的。你可以假设除法运算中不会出现除数为0的情况,且不存在任何矛盾的结果。

来源:力扣(LeetCode)
链接:399. Evaluate Division

解题思路

这道题主要考察并查集和图这两种数据结构, 目前对这两种结构以及常用的算法掌握欠佳, 解题思路先空着, 等复习完这些基本算法, 理解了相关代码再进行补充.

下面暂时先放一些相关的示意图和各种语言的代码, 其中Java使用的是并查集, C++使用的是图.

并查集

图

代码

解法一: Java语言

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

//child parent
Map<String,String> parents=new HashMap<>();
//child mutiply of parent
Map<String,Double> values=new HashMap<>();

public void add(String x){
if(!parents.containsKey(x)){
parents.put(x,x);
values.put(x,1.0);
}
}
public void union(String parent,String child, double value){

add(parent);
add(child);
String p1=find(parent);
String p2=find(child);
if(p1==p2){
return;
}else{
parents.put(p2,p1);
values.put(p2,value*(values.get(parent)/values.get(child)));
}
}

public String find(String x){
while(parents.get(x)!=x){
x=parents.get(x);
}
return x;
}


public double cal(String x){
// System.out.println("cal x"+x);
double v=values.get(x);
while(parents.get(x)!=x){
x=parents.get(x);
v*=values.get(x);
}

return v;
}
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

//union
for(int i=0;i<equations.size();i++){
//union parent child value
union(equations.get(i).get(0),equations.get(i).get(1),values[i]);

}

//find
double[] ans=new double[queries.size()];
for(int i=0;i<queries.size();i++){
String c1=queries.get(i).get(0);
String c2=queries.get(i).get(1);
if(!parents.containsKey(c1)||!parents.containsKey(c2)){
ans[i]=-1;
continue;
}
if(c1.equals(c2)){
ans[i]=1;
continue;
}
String p1=find(c1);
String p2=find(c2);
if(!p1.equals(p2)){
ans[i]=-1;
continue;
}
ans[i]=cal(c2)/cal(c1);
}

return ans;
}
}

解法二: C++语言

解法三: 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
double DFS(int s, int e, int n, double ** dpf, int ** dpfok, int ** vis) {
if(dpfok[s][e] == 1) {
return dpf[s][e];
}

double ans = -1.0;

vis[s][e] = 1;
vis[e][s] = 1;

for (int i = 0; i < n; i++) {

if (i != s && i != e && vis[e][i] == 0 && dpfok[s][i]) {
double res = DFS(i, e, n,dpf,dpfok,vis);
if(res == -1.0) continue;
ans = dpf[s][i] * res;
break;
}
}
vis[s][e] = 0;
vis[e][s] = 0;
return ans;
}

double* calcEquation(char *** equations, int equationsSize, int* equationsColSize, double* values, int valuesSize, char *** queries, int queriesSize, int* queriesColSize, int* returnSize){
int str[1000] = {0};
char *pstr[1000] = {0};

double **dpf = malloc(equationsSize * 2 * sizeof(double *));
int ** dpfok= malloc(equationsSize * 2 * sizeof(int *));
int ** vis= malloc(equationsSize * 2 * sizeof(int *));

for(int i = 0; i < equationsSize * 2;i++) {
dpf[i] = malloc(equationsSize * 2 * sizeof(double));
dpfok[i] = malloc(equationsSize * 2 * sizeof(int));
vis[i] = malloc(equationsSize * 2 * sizeof(int));
memset(dpf[i],0,equationsSize * 2 * sizeof(double));
memset(dpfok[i],0,equationsSize * 2 * sizeof(int));
memset(vis[i],0,equationsSize * 2 * sizeof(int));
}
int pos = 0;
int dp[1000][2] = {0};

double * res = (double *) malloc(sizeof(double) * queriesSize);
pstr[pos] = equations[0][0];
str[pos] = pos;
pos++;

pstr[pos] = equations[0][1];
str[pos] = pos;
pos++;

dpf[0][1] = values[0];
dpf[1][0] = 1.0/values[0];

dpfok[0][1] = 1;
dpfok[1][0] = 1;

for (int i = 1; i < equationsSize; i++) {
int e[2] = {0};

for (int j = 0; j < 2; j++) {
int k;
for(k = 0; k < pos; k++) {
if(strcmp(equations[i][j],pstr[k]) == 0) {
e[j] = str[k];
break;
}
}
if (k == pos) {
pstr[pos] = equations[i][j];
str[pos] = pos;
e[j] = pos;
pos++;
}
}

dpf[e[0]][e[1]] = values[i];
dpf[e[1]][e[0]] = 1.0/values[i];
dpfok[e[0]][e[1]] = 1;
dpfok[e[1]][e[0]] = 1;
}

for (int i = 0; i < queriesSize; i++) {
int e[2] = {0};
for (int j = 0; j < 2; j++) {
int k;
for(k = 0; k < pos; k++) {

if(strcmp(queries[i][j],pstr[k]) == 0) {
e[j] = str[k];
break;
}
}
dp[i][j] = e[j];
if (k == pos) {
dp[i][j] = -1;
}

}
}
// 将字符串转换为数组,上面都是c语言处理字符串额外做的工作,下面是代码逻辑
for (int i = 0; i < pos; i++) {
dpf[i][i] = 1.0;
dpfok[i][i] = 1;
}

for (int i = 0; i < queriesSize; i++) {

if(dp[i][0] == -1 || dp[i][1] == -1) {
res[i] = -1.0;
continue;
}
res[i] = DFS(dp[i][0],dp[i][1],pos,dpf,dpfok,vis);
}
*returnSize = queriesSize;
return res;

}

参考