题目

给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。

根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -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 <= equations[i][0].length, equations[i][1].length <= 5

values.length == equations.length

0.0 < values[i] <= 20.0

1 <= queries.length <= 20

queries[i].length == 2

1 <= queries[i][0].length, queries[i][1].length <= 5

equations[i][0], equations[i][1], queries[i][0], queries[i][1] 由小写英文字母与数字组成

解题思路分析

1、广度优先搜索；时间复杂度O(n^2),空间复杂度O(n^2)

type Node struct {
   to    int
   value float64
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
   m := make(map[string]int) // 计算对应的id
   for i := 0; i < len(equations); i++ {
      a, b := equations[i][0], equations[i][1]
      if _, ok := m[a]; ok == false {
         m[a] = len(m)
      }
      if _, ok := m[b]; ok == false {
         m[b] = len(m)
      }
   }
   arr := make([][]Node, len(m)) // 邻接表
   for i := 0; i < len(equations); i++ {
      a, b := m[equations[i][0]], m[equations[i][1]]
      arr[a] = append(arr[a], Node{to: b, value: values[i]})
      arr[b] = append(arr[b], Node{to: a, value: 1 / values[i]}) // 除以
   }
   res := make([]float64, len(queries))
   for i := 0; i < len(queries); i++ {
      a, okA := m[queries[i][0]]
      b, okB := m[queries[i][1]]
      if okA == false || okB == false {
         res[i] = -1
      } else {
         res[i] = bfs(arr, a, b) // 广度优先查找
      }
   }
   return res
}

func bfs(arr [][]Node, start, end int) float64 {
   temp := make([]float64, len(arr)) // 结果的比例
   temp[start] = 1
   queue := make([]int, 0)
   queue = append(queue, start)
   for len(queue) > 0 {
      node := queue[0]
      queue = queue[1:]
      if node == end {
         return temp[node]
      }
      for i := 0; i < len(arr[node]); i++ {
         next := arr[node][i].to
         if temp[next] == 0 {
            temp[next] = temp[node] * arr[node][i].value
            queue = append(queue, next)
         }
      }
   }
   return -1
}

2、Floyd；时间复杂度O(n^3),空间复杂度O(n^2)

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
   m := make(map[string]int) // 计算对应的id
   for i := 0; i < len(equations); i++ {
      a, b := equations[i][0], equations[i][1]
      if _, ok := m[a]; ok == false {
         m[a] = len(m)
      }
      if _, ok := m[b]; ok == false {
         m[b] = len(m)
      }
   }
   arr := make([][]float64, len(m)) // 邻接矩阵
   for i := 0; i < len(m); i++ {
      arr[i] = make([]float64, len(m))
   }
   for i := 0; i < len(equations); i++ {
      a, b := m[equations[i][0]], m[equations[i][1]]
      arr[a][b] = values[i]
      arr[b][a] = 1 / values[i]
   }
   for k := 0; k < len(arr); k++ { // Floyd
      for i := 0; i < len(arr); i++ {
         for j := 0; j < len(arr); j++ {
            if arr[i][k] > 0 && arr[k][j] > 0 {
               arr[i][j] = arr[i][k] * arr[k][j]
            }
         }
      }
   }
   res := make([]float64, len(queries))
   for i := 0; i < len(queries); i++ {
      a, okA := m[queries[i][0]]
      b, okB := m[queries[i][1]]
      if okA == false || okB == false || arr[a][b] == 0 {
         res[i] = -1
      } else {
         res[i] = arr[a][b]
      }
   }
   return res
}

3、并查集；时间复杂度O(nlog(n)),空间复杂度O(n)

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
   m := make(map[string]int) // 计算对应的id
   for i := 0; i < len(equations); i++ {
      a, b := equations[i][0], equations[i][1]
      if _, ok := m[a]; ok == false {
         m[a] = len(m)
      }
      if _, ok := m[b]; ok == false {
         m[b] = len(m)
      }
   }
   fa, rank = Init(len(m))
   for i := 0; i < len(equations); i++ {
      a, b := m[equations[i][0]], m[equations[i][1]]
      union(a, b, values[i])
   }
   res := make([]float64, len(queries))
   for i := 0; i < len(queries); i++ {
      a, okA := m[queries[i][0]]
      b, okB := m[queries[i][1]]
      if okA == true && okB == true && find(a) == find(b) {
         res[i] = rank[a] / rank[b]
      } else {
         res[i] = -1
      }
   }
   return res
}

var fa []int
var rank []float64

// 初始化
func Init(n int) ([]int, []float64) {
   arr := make([]int, n)
   r := make([]float64, n)
   for i := 0; i < n; i++ {
      arr[i] = i
      r[i] = 1
   }
   return arr, r
}

// 查询
func find(x int) int {
   // 彻底路径压缩
   if fa[x] != x {
      origin := fa[x]
      fa[x] = find(fa[x])
      rank[x] = rank[x] * rank[origin] // 秩处理是难点
   }
   return fa[x]
}

// 合并
func union(i, j int, value float64) {
   x, y := find(i), find(j)
   rank[x] = value * rank[j] / rank[i] // 秩处理是难点
   fa[x] = y
}

总结

Medium题目，多种解法，并查集带秩方法可以了解一下