跳转至

剑指 Offer II 111. 计算除法

题目描述

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

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

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -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 由小写英文字母与数字组成

 

注意：本题与主站 399 题相同： https://leetcode.cn/problems/evaluate-division/

解法

方法一

 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
class Solution:
    def calcEquation(
        self, equations: List[List[str]], values: List[float], queries: List[List[str]]
    ) -> List[float]:
        n = len(equations)
        p = list(range(n << 1))
        w = [1.0] * (n << 1)

        def find(x):
            if p[x] != x:
                origin = p[x]
                p[x] = find(p[x])
                w[x] *= w[origin]
            return p[x]

        mp = {}
        idx = 0
        for i, e in enumerate(equations):
            a, b = e[0], e[1]
            if a not in mp:
                mp[a] = idx
                idx += 1
            if b not in mp:
                mp[b] = idx
                idx += 1
            pa, pb = find(mp[a]), find(mp[b])
            if pa == pb:
                continue
            p[pa] = pb
            w[pa] = w[mp[b]] * values[i] / w[mp[a]]

        res = []
        for q in queries:
            c, d = q[0], q[1]
            if c not in mp or d not in mp:
                res.append(-1.0)
            else:
                pa, pb = find(mp[c]), find(mp[d])
                res.append(w[mp[c]] / w[mp[d]] if pa == pb else -1.0)
        return res

 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
class Solution {
    private int[] p;
    private double[] w;

    public double[] calcEquation(
        List<List<String>> equations, double[] values, List<List<String>> queries) {
        int n = equations.size();
        p = new int[n << 1];
        w = new double[n << 1];
        for (int i = 0; i < p.length; ++i) {
            p[i] = i;
            w[i] = 1.0;
        }
        Map<String, Integer> mp = new HashMap<>(n << 1);
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            List<String> e = equations.get(i);
            String a = e.get(0), b = e.get(1);
            if (!mp.containsKey(a)) {
                mp.put(a, idx++);
            }
            if (!mp.containsKey(b)) {
                mp.put(b, idx++);
            }
            int pa = find(mp.get(a)), pb = find(mp.get(b));
            if (pa == pb) {
                continue;
            }
            p[pa] = pb;
            w[pa] = w[mp.get(b)] * values[i] / w[mp.get(a)];
        }
        int m = queries.size();
        double[] res = new double[m];
        for (int i = 0; i < m; ++i) {
            String c = queries.get(i).get(0), d = queries.get(i).get(1);
            Integer id1 = mp.get(c), id2 = mp.get(d);
            if (id1 == null || id2 == null) {
                res[i] = -1.0;
            } else {
                int pa = find(id1), pb = find(id2);
                res[i] = pa == pb ? w[id1] / w[id2] : -1.0;
            }
        }
        return res;
    }

    private int find(int x) {
        if (p[x] != x) {
            int origin = p[x];
            p[x] = find(p[x]);
            w[x] *= w[origin];
        }
        return p[x];
    }
}

 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
class Solution {
public:
    vector<int> p;
    vector<double> w;

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int n = equations.size();
        for (int i = 0; i < (n << 1); ++i) {
            p.push_back(i);
            w.push_back(1.0);
        }
        unordered_map<string, int> mp;
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            auto e = equations[i];
            string a = e[0], b = e[1];
            if (mp.find(a) == mp.end()) mp[a] = idx++;
            if (mp.find(b) == mp.end()) mp[b] = idx++;
            int pa = find(mp[a]), pb = find(mp[b]);
            if (pa == pb) continue;
            p[pa] = pb;
            w[pa] = w[mp[b]] * values[i] / w[mp[a]];
        }
        int m = queries.size();
        vector<double> res;
        for (int i = 0; i < m; ++i) {
            string c = queries[i][0], d = queries[i][1];
            if (mp.find(c) == mp.end() || mp.find(d) == mp.end())
                res.push_back(-1.0);
            else {
                int pa = find(mp[c]), pb = find(mp[d]);
                res.push_back(pa == pb ? w[mp[c]] / w[mp[d]] : -1.0);
            }
        }
        return res;
    }

    int find(int x) {
        if (p[x] != x) {
            int origin = p[x];
            p[x] = find(p[x]);
            w[x] *= w[origin];
        }
        return p[x];
    }
};

 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
var p []int
var w []float64

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    n := len(equations)
    p = make([]int, (n<<1)+10)
    w = make([]float64, (n<<1)+10)
    for i := 0; i < (n<<1)+10; i++ {
        p[i] = i
        w[i] = 1.0
    }
    mp := make(map[string]int)
    idx := 1
    for i, e := range equations {
        a, b := e[0], e[1]
        if mp[a] == 0 {
            mp[a] = idx
            idx++
        }
        if mp[b] == 0 {
            mp[b] = idx
            idx++
        }
        pa, pb := find(mp[a]), find(mp[b])
        if pa == pb {
            continue
        }
        p[pa] = pb
        w[pa] = w[mp[b]] * values[i] / w[mp[a]]
    }
    var res []float64
    for _, q := range queries {
        c, d := q[0], q[1]
        if mp[c] == 0 || mp[d] == 0 {
            res = append(res, -1.0)
        } else {
            pa, pb := find(mp[c]), find(mp[d])
            if pa == pb {
                res = append(res, w[mp[c]]/w[mp[d]])
            } else {
                res = append(res, -1.0)
            }
        }
    }
    return res
}

func find(x int) int {
    if p[x] != x {
        origin := p[x]
        p[x] = find(p[x])
        w[x] *= w[origin]
    }
    return p[x]
}

 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
class Solution {
    private var parent = [Int]()
    private var weight = [Double]()

    func calcEquation(
        _ equations: [[String]],
        _ values: [Double],
        _ queries: [[String]]
    ) -> [Double] {
        let n = equations.count
        parent = Array(0..<(n * 2))
        weight = Array(repeating: 1.0, count: n * 2)

        var map = [String: Int]()
        var index = 0

        for i in 0..<n {
            let a = equations[i][0]
            let b = equations[i][1]

            if map[a] == nil {
                map[a] = index
                index += 1
            }
            if map[b] == nil {
                map[b] = index
                index += 1
            }

            let pa = find(map[a]!)
            let pb = find(map[b]!)

            if pa != pb {
                parent[pa] = pb
                weight[pa] = weight[map[b]!] * values[i] / weight[map[a]!]
            }
        }

        var result = [Double]()

        for query in queries {
            let (c, d) = (query[0], query[1])
            if let id1 = map[c], let id2 = map[d], find(id1) == find(id2) {
                result.append(weight[id1] / weight[id2])
            } else {
                result.append(-1.0)
            }
        }

        return result
    }

    private func find(_ x: Int) -> Int {
        if parent[x] != x {
            let origin = parent[x]
            parent[x] = find(parent[x])
            weight[x] *= weight[origin]
        }
        return parent[x]
    }
}

评论