Question

剑指 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/

解法

方法一

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

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];
  }
}

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];
  }
};

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]
}