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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// @Title: 除法求值 (Evaluate Division)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 0 ms
// @Memory: 2.2 MB
/*
 * @lc app=leetcode.cn id=399 lang=golang
 *
 * [399] 除法求值
 *
 * https://leetcode-cn.com/problems/evaluate-division/description/
 *
 * algorithms
 * Medium (49.93%)
 * Likes:    52
 * Dislikes: 0
 * Total Accepted:    1.9K
 * Total Submissions: 3.8K
 * Testcase Example:  '[["a","b"],["b","c"]]\n[2.0,3.0]\n[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]'
 *
 * 给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量, k
 * 是一个浮点型数字。根据已知方程式求解问题,并返回计算结果。如果结果不存在,则返回 -1.0。
 *
 * 示例 :
 * 给定 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 ]
 *
 * 输入为:  vector<pair<string, string>> equations, vector<double>& values,
 * vector<pair<string, string>> queries(方程式,方程式结果,问题方程式), 其中 equations.size()
 * == values.size(),即方程式的长度与方程式结果长度相等(程式与结果一一对应),并且结果值均为正数。以上为方程式的描述。
 * 返回vector<double>类型。
 *
 * 基于上述例子,输入如下:
 *
 *
 * equations(方程式) = [ ["a", "b"], ["b", "c"] ],
 * values(方程式结果) = [2.0, 3.0],
 * queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x",
 * "x"] ].
 *
 *
 * 输入总是有效的。你可以假设除法运算中不会出现除数为0的情况,且不存在任何矛盾的结果。
 *
 */

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	// 建立变量之间的转换关系
	m := make(map[string]map[string]float64)
	for i, e := range equations {
		a, b := e[0], e[1]
		v := values[i]
		// 添加 a / b 的记录
		if _, ok := m[a]; !ok {
			m[a] = make(map[string]float64)
		}
		m[a][b] = 1.0 / v
		// 添加 b / a 的记录
		if _, ok := m[b]; !ok {
			m[b] = make(map[string]float64)
		}
		m[b][a] = v
	}

	// 逐个搜索 queries 的结果
	res := make([]float64, len(queries))
	for i, q := range queries {
		res[i] = bfs(m, q[0], q[1])
	}

	return res
}

type entry struct {
	s string
	f float64
}

func bfs(m map[string]map[string]float64, a, b string) float64 {
	_, ok := m[a]
	if !ok {
		return -1.0
	}
	_, ok = m[b]
	if !ok {
		return -1.0
	}

	if a == b {
		return 1.0
	}

	isVisited := make(map[string]bool)
	queue := []entry{{a, 1.0}}

	for len(queue) > 0 {
		e := queue[0]
		queue = queue[1:]
		if e.s == b {
			// 找到了 b
			return 1.0 / e.f
		}

		if isVisited[e.s] {
			continue
		}

		isVisited[e.s] = true

		for k, v := range m[e.s] {
			queue = append(queue, entry{k, v * e.f})
		}
	}
	//没有找到 b
	return -1.0
}