*leetcode 399 除法求值

题目

给你一个变量对数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1.并查集

在并查集模板写法的基础上加上权值

四边形法则
带权并查集中：考虑x/y=vx/y=v。
结点x，y可能有多种情况，可能x==y, find(x)==x || find(y)==yx==y, find(x)==x || find(y)==y。
我们直接考虑最复杂的情况，即find(x)!=x && find(y)!=yfind(x)!!=x && find(y)!=y，这种情况是最复杂的，其他情况都是该情况的特殊情况

/**
 * @param {string[][]} equations
 * @param {number[]} values
 * @param {string[][]} queries
 * @return {number[]}
 */
//模板写法
class UnionFind {
    constructor() {
        this.parent = {},
            this.value = {}
    }
    find(x) {
        let x_root = x
        let base = 1.0
        while (this.parent[x_root] !== -1) {
            x_root = this.parent[x_root]
            base *= this.value[x_root]
        }
        //路径压缩
        while (x !== x_root) {
            let original_father = this.parent[x]
            //越远倍数越大
            this.value[x] *= base
            base /= this.value[original_father]
            this.parent[x] = x_root
            x = original_father
        }
        return x_root
    }
    merge(x, y, val) {
        let x_root = this.find(x)
        let y_root = this.find(y)
        if (x_root !== y_root) {
            this.parent[x_root] = y_root
            //四边形法则
            this.value[x_root] = this.value[y] * val / this.value[x]
        }
    }
    add(x) {
        if (!this.parent[x]) {
            this.parent[x] = -1
            this.value[x] = 1.0
        }
    }
}
var calcEquation = function (equations, values, queries) {
    const uf = new UnionFind()
    const n = values.length
    const n1 = queries.length
    //初始化 
    for (let i = 0; i < n; i++) {
        uf.add(equations[i][0])
        uf.add(equations[i][1])
        uf.merge(equations[i][0], equations[i][1], values[i])
    }
    const res = new Array(n1).fill(-1.0)
    for (let i = 0; i < n1; i++) {
        const x1 = queries[i][0]
        const x2 = queries[i][1]
        if (uf.value[x1] && uf.value[x2] && uf.find(x1) === uf.find(x2)) {
            res[i] = uf.value[x1] / uf.value[x2]
        }
    }
    return res
};
var calcEquation = function(equations, values, queries) {
    let parentMap = new Map();
    let valueMap = new Map();
    for (let i = 0; i < equations.length; i++) {
        if (!parentMap.has(equations[i][0])) {
            parentMap.set(equations[i][0], equations[i][0]);
        }
        if (!parentMap.has(equations[i][1])) {
            parentMap.set(equations[i][1], equations[i][1]);
        }
        if (!valueMap.has(equations[i][0])) {
            valueMap.set(equations[i][0], 1);
        }
        if (!valueMap.has(equations[i][1])) {
            valueMap.set(equations[i][1], 1);
        }
        union(parentMap, valueMap, equations[i][0], equations[i][1], values[i]);
    }
    const result = [];
    for (let i = 0; i < queries.length; i++) {
        let tmp1 = find(parentMap, valueMap, queries[i][0]);
        let tmp2 = find(parentMap, valueMap, queries[i][1]);
        if (!tmp1 || !tmp2) {
            result.push(-1.0);
            continue;
        }
        if (tmp1.index === tmp2.index) {
            result.push(tmp1.value / tmp2.value);
        }
        else {
            result.push(-1.0);
        }     
    }
    return result;
};
function union(parentMap, valueMap, index1, index2, value) {
    let tmp1 = find(parentMap, valueMap, index1);
    let tmp2 = find(parentMap, valueMap, index2);
    parentMap.set(tmp1.index, tmp2.index);
    valueMap.set(tmp1.index, (value * tmp2.value) / tmp1.value);
}
function find(parentMap, valueMap, index) {
    let value = 1;
    while (parentMap.get(index) && parentMap.get(index) !== index) {
        value *= valueMap.get(index);
        index = parentMap.get(index);
    }
    if (!parentMap.get(index)) {
        return null;
    }
    return {
        index,
        value
    };
}

2.DFS

// 先构造图再dfs
var calcEquation = function(equations, values, queries) {
    const graph = {}, visited = new Set();

    // 构造图，equations的第一项除以第二项等于value里的对应值，第二项除以第一项等于其倒数
    for(let [index, value] of values.entries()) {
        const x = equations[index][0], y = equations[index][1];
        if(graph[x]) {
            graph[x][y] = value;
        } else {
            graph[x] = {[y]: value};
        }

        if(graph[y]) {
            graph[y][x] = 1 / value;
        } else {
            graph[y] = {[x]: 1 / value};
        }
    }

    // dfs找寻从s到t的路径并返回结果叠乘后的边权重即结果
    const dfs = (dividend, divisor) => {
        if(!graph[dividend]) {
            return -1;
        }
        if(dividend === divisor) {
            return 1;
        }
        for(let node of Object.keys(graph[dividend])) {
            if(node === divisor) {
                return graph[dividend][node];
            } else if(!visited.has(node)) {
                visited.add(node); // 添加到已访问避免重复遍历
                const value = dfs(node, divisor);
                visited.delete(node);
                if(value !== -1) {
                    return graph[dividend][node] * value;
                }
            }
        }
        return -1;
    }

    return queries.map(([dividend, divisor]) => dfs(dividend, divisor));
};