LeetCode:399.Evaluate Division 除法求值（C语言）-蒲公英云

LeetCode:399.Evaluate Division 除法求值（C语言）

题目描述：
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回所有问题的答案。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。

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

示例 1：

输入：equations = [[“a”,“b”],[“b”,“c”]], values = [2.0,3.0], queries = [[“a”,“c”],[“b”,“a”],[“a”,“e”],[“a”,“a”],[“x”,“x”]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：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 ]

示例 2：

输入：equations = [[“a”,“b”],[“b”,“c”],[“bc”,“cd”]], values = [1.5,2.5,5.0], queries = [[“a”,“c”],[“c”,“b”],[“bc”,“cd”],[“cd”,“bc”]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：

输入：equations = [[“a”,“b”]], values = [0.5], queries = [[“a”,“b”],[“b”,“a”],[“a”,“c”],[“x”,“y”]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

提示：

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj 由小写英文字母与数字组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答：

typedef struct { 
    char *x;
    char *y;
    double z;
    UT_hash_handle hh;
} Hash;
Hash *hash;
Hash* derive(Hash *p, double *t) { 
    *t = 1;
    while (strcmp(p->x, p->y)) { 
        *t *= p->z;
        char *s = p->y;
        HASH_FIND(hh, hash, s, strlen(s), p);
    }
    return p;
}
void _add(char *x, char *y, double z) { 
    Hash *p1, *p2;
    HASH_FIND(hh, hash, x, strlen(x), p1);
    HASH_FIND(hh, hash, y, strlen(y), p2);
    if (p1 && p2) { 
        //x、y已经出现过，若它们无联系，那么将他们合并关系
        double tx, ty;
        p1 = derive(p1, &tx);
        p2 = derive(p2, &ty);
        if (strcmp(p1->x, p2->x)) { 
            p1->y = p2->x;
            p1->z = ty*z/tx;
        }
    } else if (p1) { 
        double tx;
        p1 = derive(p1, &tx);
        Hash *p = malloc(sizeof(Hash));
        p->x = y; 
        p->y = p1->x;
        p->z = tx/z;
        HASH_ADD_STR(hash, x, p);
    } else if (p2) { 
        double ty;
        p2 = derive(p2, &ty);
        Hash *p = malloc(sizeof(Hash));
        p->x = x;
        p->y = p2->x;
        p->z = z/ty;
        HASH_ADD_STR(hash, x, p);
    } else { 
        p1 = malloc(sizeof(Hash));
        p2 = malloc(sizeof(Hash));
        p1->x = x;
        p1->y = y;
        p1->z = z;
        HASH_ADD_STR(hash, x, p1);
        p2->x = y;
        p2->y = y;
        p2->z = 1;
        HASH_ADD_STR(hash, x, p2);
    }
}
double _div(char *x, char *y) { 
    Hash *p1, *p2;
    HASH_FIND(hh, hash, x, strlen(x), p1);
    HASH_FIND(hh, hash, y, strlen(y), p2);
    if (p1 && p2) { 
        double tx, ty;
        p1 = derive(p1, &tx);
        p2 = derive(p2, &ty);
        if (strcmp(p1->x, p2->x) == 0) { 
            return tx/ty;
        }
    } 
    return -1.0;
}
double* calcEquation(char *** equations, int equationsSize, int* equationsColSize, double* values, int valuesSize, char *** queries, int queriesSize, int* queriesColSize, int* returnSize){ 
    hash = NULL;
    for (int i=0; i<equationsSize; ++i) { 
        _add(equations[i][0], equations[i][1], values[i]);
    }
    double *res = malloc(sizeof(double) * queriesSize);
    for (int i=0; i<queriesSize; ++i) { 
        res[i] = _div(queries[i][0], queries[i][1]);
    }
    *returnSize = queriesSize;
    return res;
}