力扣399. 除法求值

发布时间:2024年01月14日

广度优先搜索

  • 思路:
    • 题目梳理
      • 输入信息里包含 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;
    }
};

文章来源:https://blog.csdn.net/N_BenBird/article/details/135582645
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。