Advertisement
TrickmanOff

399. Evaluate Division

Jan 16th, 2022
793
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
  3.  
  4.  You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
  5.  
  6.  Return the answers to all queries. If a single answer cannot be determined, return -1.0.
  7.  
  8. Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
  9.  
  10.  
  11. constraints:
  12.     0 < values[i]
  13.  
  14.  
  15. - example:
  16.   input:
  17.     equations = [["a","b"],["b","c"]]
  18.     values    = [2.0,3.0]
  19.     queries   = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
  20.   output:
  21.     [6.00000,0.50000,-1.00000,1.00000,-1.00000]
  22. */
  23.  
  24. /*
  25. notes:
  26.  
  27. if the graph is stored as a map<string, string>
  28. for each query the algorithm might go through all the names
  29. so it's better to map all the names to number at first
  30.  
  31. building a graph:
  32.   time:     O(#equations)
  33.   memory:   O(#equations)  
  34.  
  35. offline:
  36.   precalcute all the possible results
  37.   precalc time: O(#equations * #variables) - DFS for each vertex
  38.   query time:   O(1)
  39.   space:        O(#variables^2)
  40.  
  41. online:
  42.   calculate each answer
  43.   precalc time: O(#equations)
  44.   query time:   O(#equations)
  45.   space:        O(#equations)
  46. */
  47.  
  48. /*
  49. tricky tests:
  50.     going backwards
  51.     same variable (A/A = ?)
  52.     X/X where X wasn't in equations: -1.
  53. */
  54.  
  55. class Solution {
  56. public:
  57.     /*
  58.     approach:
  59.         store equations as a weighted oriented graph (map<string, Edge>)
  60.         for each equations add two edges (special cases with loops)
  61.        
  62.         make a DFS for the source vertex until we reach the target one
  63.     */
  64.    
  65.     unordered_map<string, int> var_code;
  66.     vector<unordered_map<int, double>> g;
  67.    
  68.     double v_div_target(int v, int target, vector<bool>& visited) {
  69.         if (visited[v]) {
  70.             return -1.;
  71.         }
  72.         visited[v] = true;
  73.        
  74.         if (v == target) {
  75.             return 1.;
  76.         }
  77.        
  78.         for (auto [to, val] : g[v]) {
  79.             double to_div_target = v_div_target(to, target, visited);
  80.             if (to_div_target != -1.) {
  81.                 // v / to = val
  82.                 // to / target = to_div_target
  83.                 // -> v / target = val * to_div_target
  84.                 return val * to_div_target;
  85.             }
  86.         }
  87.         return -1.;
  88.     }
  89.    
  90.     vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
  91.         for (int i = 0; i < equations.size(); ++i) {
  92.             auto& eq = equations[i];
  93.             for (int j = 0; j < 2; ++j) {
  94.                 const string& var_name = eq[j];
  95.                 if (!var_code.count(var_name)) {
  96.                     int var_i = var_code.size();
  97.                     var_code[var_name] = var_i;
  98.                 }
  99.             }
  100.            
  101.             double val = values[i];
  102.             int code1 = var_code[eq[0]];
  103.             int code2 = var_code[eq[1]];
  104.             if (code1 == code2) {
  105.                 continue;
  106.             }
  107.             g.resize(var_code.size());
  108.             g[code1][code2] = val;
  109.             g[code2][code1] = 1. / val;
  110.         }
  111.        
  112.         vector<double> res;
  113.         vector<bool> visited(var_code.size(), false);
  114.         for (auto& query : queries) {
  115.             int v = (var_code.count(query[0]) ? var_code[query[0]] : -1);
  116.             int t = (var_code.count(query[1]) ? var_code[query[1]] : -1);
  117.             visited.assign(visited.size(), false);
  118.            
  119.             double cur_res = ((v == -1 || t == -1) ? -1. : v_div_target(v, t, visited));
  120.             res.push_back(cur_res);
  121.         }
  122.         return res;
  123.     }
  124. };
  125.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement