剑指 Offer II 111. 计算除法

---

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20111.%20%E8%AE%A1%E7%AE%97%E9%99%A4%E6%B3%95/README.md

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

解法

方法一

Python3

深度优先搜索
图可以用来表示物体与物体之间的关系，节点代变物体，而边代变两物体之间的关系。在本问题中可以把变量看作是节点，若存在两变量之间的除法，那么这两变量对应的节点之间有一条边相连。**一个除法等式中存在被除数、除数以及商，被除数和除数用节点表示，用边的权值表示两者之间的商。**因为被除数与除数位置不同，最后的商的结果也不同，所以这个图是有向有权图。如 equations = [[“a”,“b”],[“b”,“c”]], values = [2.0,3.0] 可以用下图表示

由数学知识可得 a / b = a / x * x / b，这种关系在图中的表示就是，节点 a 到节点 b 之间是存在通路的，并且 a / b 等于通路各边的权重之积。因此本题本质上来说还是一个图的搜索问题，由于需要记录一条通路，所以使用深度优先搜索算法比较合适。完整代码如下，如果图中节点数量为 v，边的数量为 e，那么计算每个 queries[i] 的时间复杂度为 O(v + e)。

from collections import defaultdictclass Solution:def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:# 建双向有权图graph=defaultdict(list)st=set()for (a,b),val in zip(equations,values):graph[a].append((b,val))graph[b].append((a,1/val))st.add(a)st.add(b)#搜索路径，并计算权值累乘def dfs(st,ed):nonlocal pathif st==ed:return path #这里要return path，否则会会回溯成原始1for nx,val in graph[st]:if nx in used:continuepath*=valused.add(nx)c=dfs(nx,ed)if c!=-1: #【注意】如果存在某个无法确定的答案，则用 -1.0 替代这个答案return c  path/=valused.remove(nx)return -1  #【注意】如果存在某个无法确定的答案（也就是前面一直if st!=ed,没return path），则用 -1.0 替代这个答案res=[]for (a,b) in queries:if a not in st or b not in st:res.append(-1)continuepath=1used = {a}res.append(dfs(a, b))return res

Java

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

C++

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

Go

var p []int
var w []float64func 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] = iw[i] = 1.0}mp := make(map[string]int)idx := 1for i, e := range equations {a, b := e[0], e[1]if mp[a] == 0 {mp[a] = idxidx++}if mp[b] == 0 {mp[b] = idxidx++}pa, pb := find(mp[a]), find(mp[b])if pa == pb {continue}p[pa] = pbw[pa] = w[mp[b]] * values[i] / w[mp[a]]}var res []float64for _, 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]
}

Swift

class Solution {private var parent = [Int]()private var weight = [Double]()func calcEquation(_ equations: [[String]],_ values: [Double],_ queries: [[String]]) -> [Double] {let n = equations.countparent = Array(0..<(n * 2))weight = Array(repeating: 1.0, count: n * 2)var map = [String: Int]()var index = 0for i in 0..<n {let a = equations[i][0]let b = equations[i][1]if map[a] == nil {map[a] = indexindex += 1}if map[b] == nil {map[b] = indexindex += 1}let pa = find(map[a]!)let pb = find(map[b]!)if pa != pb {parent[pa] = pbweight[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]}
}