力扣399. 除法求值

广度优先搜索

• 思路：
  • 题目梳理
    • 输入信息里包含 A / B = val；
    • 输入一堆 A'?/ B' 需要求出它们的比值；
  • 以操作数为节点，构建权重图，节点对应了关联节点及其比值；
  • 可以进行简单的处理，将代数变量映射为整数数值，着上述图可以的节点键值转化为数组的下标；

    • for (int i = 0; i < size; ++i) {
          if (variables.find(equations[i][0]) == variables.end()) {
              variables[equations[i][0]] = nvars++;
          }
          if (variables.find(equations[i][1]) == variables.end()) {
             variables[equations[i][1]] = nvars++;
          }
      }
      
      std::vector<std::vector<std::pair<int, double>>> digraph(nvars);
      for (int i = 0; i < size; ++i) {
          int nodeA = variables[equations[i][0]];
          int nodeB = variables[equations[i][1]];
          digraph[nodeA].push_back(std::make_pair(nodeB, values[i]));
          digraph[nodeB].push_back(std::make_pair(nodeA, 1.0 /values[i]));
      }

  • 遍历求解的代数式：
    • 如果变量不在已知的哈希表中，则结果为 -1.0；
    • 如果两个变量相等，则结果为 1.0；
    • 否则就可以从起点出发，通过广度优先搜索的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止；

      • // bfs
        std::queue<int> qu;
        qu.push(na);
        // result for search ratio
        std::vector<double> ratio(nvars, -1.0);
        ratio[na] = 1.0;
        while (!qu.empty() && ratio[nb] < 0) {
            int x = qu.front();
            qu.pop();
        
            for (const auto [y, v] : digraph[x]) {
                if (ratio[y] < 0) {
                    ratio[y] = ratio[x] * v;
                    qu.push(y);
                }
            }
        }
        
        val = ratio[nb];

• 完整代码

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int nvars = 0;
        std::unordered_map<std::string, int> variables;

        int size = equations.size();
        for (int i = 0; i < size; ++i) {
            if (variables.find(equations[i][0]) == variables.end()) {
                variables[equations[i][0]] = nvars++;
            }
            if (variables.find(equations[i][1]) == variables.end()) {
                variables[equations[i][1]] = nvars++;
            }
        }

        std::vector<std::vector<std::pair<int, double>>> digraph(nvars);
        for (int i = 0; i < size; ++i) {
            int nodeA = variables[equations[i][0]];
            int nodeB = variables[equations[i][1]];
            digraph[nodeA].push_back(std::make_pair(nodeB, values[i]));
            digraph[nodeB].push_back(std::make_pair(nodeA, 1.0 /values[i]));
        }

        std::vector<double> result;
        for (const auto & q : queries) {
            double val = -1.0;
            // all of the var exist
            if (variables.find(q[0]) != variables.end() &&
                variables.find(q[1]) != variables.end()) {
                // node value from the graph
                int na = variables[q[0]];
                int nb = variables[q[1]];
                if (na == nb) {
                    val = 1.0;
                } else {
                    // bfs
                    std::queue<int> qu;
                    qu.push(na);
                    // 
                    std::vector<double> ratio(nvars, -1.0);
                    ratio[na] = 1.0;
                    while (!qu.empty() && ratio[nb] < 0) {
                        int x = qu.front();
                        qu.pop();

                        for (const auto [y, v] : digraph[x]) {
                            if (ratio[y] < 0) {
                                ratio[y] = ratio[x] * v;
                                qu.push(y);
                            }
                        }
                    }

                    val = ratio[nb];
                }
            }
            result.push_back(val);
        }

        return result;
    }
};