Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 399. Evaluate Division

---

參考資訊：
https://blog.csdn.net/fuxuemingzhu/article/details/82591165
https://samiulmushfik.medium.com/leetcode-399-evaluate-division-6bcd7ffff05c

題目：


方法(向量圖概念)：


解答：

#define MAX_SIZE 128
 
double dfs(int a, int b, double **q, int *visit)
{
    int i = 0;
    double r = 0;
 
    if (a == b) {
        return 1.0;
    }
 
    visit[a] = 1;
    for (i = 0; i < MAX_SIZE; i++) {
        if ((q[a][i] > 0) && (visit[i] == 0)) {
            r = dfs(i, b, q, visit);
            if (r > 0.0) {
                return r * q[a][i];
            }
        }
    }
 
    return -1.0;
}
 
int str2idx(const char *s)
{
    int i = 0;
    static char **q = NULL;
 
 
    if (q == NULL) {
        q = calloc(MAX_SIZE, sizeof(char *));
    }
 
    for (i = 0; i < MAX_SIZE; i++) {
        if (q[i] == NULL) {
            break;
        }
         
        if (!strcmp(q[i], s)) {
            return i;
        }
    }
 
    q[i] = calloc(strlen(s) + 1, sizeof(char));
    strcpy(q[i], s);
 
    return i;
}
 
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
double* calcEquation(
    char ***equations,
    int equationsSize,
    int *equationsColSize,
    double *values,
    int valuesSize,
    char ***queries,
    int queriesSize,
    int *queriesColSize,
    int *returnSize)
{
    int i = 0;
    int c1 = 0;
    int *exist = NULL;
    int *visit = NULL;
    double *r = NULL;
    double **q = NULL;
 
    q = calloc(MAX_SIZE, sizeof(double));
    for (i = 0; i < MAX_SIZE; i++) {
        q[i] = calloc(MAX_SIZE, sizeof(double));
    }
 
    exist = calloc(MAX_SIZE, sizeof(int));
    for (i = 0; i < equationsSize; i++) {
        int a = str2idx(equations[i][0]);
        int b = str2idx(equations[i][1]);
 
        q[a][b] = values[i];
        q[b][a] = 1.0 / values[i];
 
        exist[a] |= 1;
        exist[b] |= 1;
    }
 
    r = calloc(queriesSize, sizeof(double));
    visit = calloc(MAX_SIZE, sizeof(int));
    for (i = 0; i < queriesSize; i++) {
        int a = str2idx(queries[i][0]);
        int b = str2idx(queries[i][1]);
 
        if ((exist[a] && exist[b]) == 0) {
            r[i] = -1.0;
            continue;
        }
 
        memset(visit, 0, sizeof(int) * MAX_SIZE);
        r[i] = dfs(a, b, q, visit);
    }
 
    *returnSize = queriesSize;
    return r;
}