399.除法求值
399.除法求值
题解
题目：给一个字符串除法数组，比如a/b=1,b/c=2的数组，再给一个查询数组，比如a/c b/a,返回查询数组的值，如果出现不存在的字符串，返回-1，如果根据已有条件查询不到值的，也返回-1
思路：本题可以看作带权有向图，a到b的距离是1，b到c 的距离的2，但是本题是除法，也就是说a/b b/c ---->a/c = a/b * b/c，即更新边距离的时候，不是以往的算最小，而是相乘
图论一般可以用dfs，bfs，Floyd，这里给出bfs和floyd的算法
代码
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 { id := make(map[string]int) cnt := 1 //做映射 for _, val := range equations { u, v := val[0], val[1] if _, ok := id[u]; !ok { id[u] = cnt cnt++ } if _, ok := id[v]; !ok { id[v] = cnt cnt++ } } graph := make([][]float64, cnt) for i := range graph { graph[i] = make([]float64, cnt) } //建图 存边 for i, val := range equations { u, v, w := val[0], val[1], values[i] graph[id[u]][id[v]] = w graph[id[v]][id[u]] = 1 / w } for k := range graph { for i := range graph { for j := range graph { if graph[i][k] > 0 && graph[k][j] > 0 { graph[i][j] = graph[i][k] * graph[k][j] } } } } ans := make([]float64, len(queries)) for i, val := range queries { u, v := val[0], val[1] //如果u或v没出现过，返回-1 if id[u] == 0 || id[v] == 0 || graph[id[u]][id[v]] == 0 { ans[i] = -1 continue } ans[i] = graph[id[u]][id[v]] } return ans }
func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 { type pair struct { v string val float64 } e := make(map[string][]pair) //建图 存边 for i, val := range equations { u, v, w := val[0], val[1], values[i] e[u] = append(e[u], pair{v, w}) e[v] = append(e[v], pair{u, 1 / w}) } var bfs func(st, ed string) float64 bfs = func(st, ed string) float64 { dis := make(map[string]float64) vis := make(map[string]bool) dis[st] = 1 vis[st] = true queue := make([]pair, 0) queue = append(queue, pair{st, 0}) for len(queue) > 0 { u := queue[0].v queue = queue[1:] if u == ed { return dis[u] } for _, allV := range e[u] { v, w := allV.v, allV.val dis[v] = dis[u] * w // a/b b/c ---->a/c = a/b * b/c if !vis[v] { vis[v] = true queue = append(queue, pair{v, dis[v]}) } } } if dis[ed] == 0 { return -1 } return dis[ed] } ans := make([]float64, len(queries)) for i, val := range queries { u, v := val[0], val[1] //如果u或v没出现过，返回-1 if e[u] == nil || e[v] == nil { ans[i] = -1 continue } ans[i] = bfs(u, v) } return ans }
