2022-04-30 Daily-Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 30

Description

Evaluate Division

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.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

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.

 

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

 

Constraints:

  • 1 <= equations.length <= 20
  • equations[i].length == 2
  • 1 <= Ai.length, Bi.length <= 5
  • values.length == equations.length
  • 0.0 < values[i] <= 20.0
  • 1 <= queries.length <= 20
  • queries[i].length == 2
  • 1 <= Cj.length, Dj.length <= 5
  • Ai, Bi, Cj, Dj consist of lower case English letters and digits.

Solution

class Solution {
public:
  vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    unordered_map<string, unordered_map<string, double>> fractions;
    queue<pair<string, string>> q;
    int len = equations.size();
    for(int i = 0; i < len; ++i) {
      if(equations[i][0] == equations[i][1]) continue;
      fractions[equations[i][0]][equations[i][1]] = values[i];
      fractions[equations[i][1]][equations[i][0]] = 1.0 / values[i];
      fractions[equations[i][0]][equations[i][0]] = 1.0;
      fractions[equations[i][1]][equations[i][1]] = 1.0;
      // (a / b) * (b / c) = a / c
      // (a / b) / (c / b) = a / c
      // add both fraction itself and its reciprocal so
      // we don't need to concern about so much case
      q.push({equations[i][0], equations[i][1]});
      q.push({equations[i][1], equations[i][0]});
    }
    while(q.size()) {
      const auto [numerator1, denominator1] = q.front();
      q.pop();
      // numerator2 == denominator1
      for(const auto &[denominator2, value] : fractions[denominator1]) {
        if(fractions[numerator1].count(denominator2)) continue;
        fractions[numerator1][denominator2] = value * fractions[numerator1][denominator1];
        q.push({numerator1, denominator2});
      }
    }
    vector<double> answer;
    answer.reserve(queries.size());
    for(const auto &query : queries) {
      if(fractions.count(query[0]) && fractions[query[0]].count(query[1])) {
        answer.push_back(fractions[query[0]][query[1]]);
      } else {
        answer.push_back(-1);
      }
    }
    return answer;
  }
};

// Accepted
// 24/24 cases passed (4 ms)
// Your runtime beats 51.34 % of cpp submissions
// Your memory usage beats 18.38 % of cpp submissions (8.6 MB)
Algorithm