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  // @Title: 除法求值 (Evaluate Division) // @Author: 15816537946@163.com // @Date: 2021-01-09 16:52:47 // @Runtime: 0 ms // @Memory: 2.2 MB 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] if _, ok := m[a]; !ok { m[a] = make(map[string]float64) } m[a][b] = 1.0 / v if _, ok := m[b]; !ok { m[b] = make(map[string]float64) } m[b][a] = v } 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 { 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}) } } return -1.0 }