Created
September 18, 2016 10:31
-
-
Save eclipselu/2031ceb1f9deece358dc795c489cd82e to your computer and use it in GitHub Desktop.
Evaluate Division
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class ValType { | |
public: | |
double val; | |
string sym; | |
ValType () { | |
this->val = 1.0; | |
this->sym = ""; | |
} | |
ValType (double v, string s) { | |
this->val = v; | |
this->sym = s; | |
} | |
}; | |
class Solution { | |
public: | |
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { | |
set<string> numers, denoms, vars; | |
map<string, ValType> vals; | |
for (auto &p: equations) { | |
vars.insert(p.first); | |
vars.insert(p.second); | |
numers.insert(p.first); | |
denoms.insert(p.second); | |
} | |
// initialize `lone` denominators: only appears as a denominator | |
vector<string> lone_denoms; | |
for (string s: denoms) | |
if (numers.find(s) == numers.end()) | |
lone_denoms.push_back(s); | |
// set vals | |
for (string s: lone_denoms) | |
setVals(vals, equations, values, vars.size(), s); | |
vector<double> results; | |
for (auto &p: queries) { | |
string num = p.first, den = p.second; | |
if (vals.find(num) == vals.end() || vals.find(den) == vals.end() || vals[num].sym != vals[den].sym) | |
results.push_back(-1.0); | |
else | |
results.push_back(vals[num].val / vals[den].val); | |
} | |
return results; | |
} | |
private: | |
void setVals(map<string, ValType> &vals, | |
vector<pair<string, string> > &equations, | |
vector<double> &values, | |
int len, | |
string key) { | |
if (vals.size() == len) | |
return ; | |
if (vals.find(key) == vals.end()) { | |
vals[key] = ValType(1.0, key); | |
setVals(vals, equations, values, len, key); | |
return ; | |
} | |
for (int i = 0; i < equations.size(); ++i) { | |
auto p = equations[i]; | |
ValType v = vals[key]; | |
if (key == p.second && vals.find(p.first) == vals.end()) { | |
vals[p.first] = ValType(v.val * values[i], v.sym); | |
setVals(vals, equations, values, len, p.first); | |
} else if (key == p.first && vals.find(p.second) == vals.end()) { | |
vals[p.second] = ValType(v.val / values[i], v.sym); | |
setVals(vals, equations, values, len, p.second); | |
} | |
} | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## function naming is not very pythonic though :( | |
class ValType(object): | |
def __init__(self, val=1.0, sym=''): | |
self.val = val | |
self.sym = sym | |
class Solution(object): | |
def calcEquation(self, equations, values, queries): | |
""" | |
:type equations: List[List[str]] | |
:type values: List[float] | |
:type queries: List[List[str]] | |
:rtype: List[float] | |
""" | |
numers = {r[0] for r in equations} | |
denoms = {r[1] for r in equations} | |
num_vars = len(numers | denoms) | |
start_vars = denoms - numers | |
vals = dict() | |
# use dfs to set vals for each variable | |
for var in start_vars: | |
self.setVals(vals, var, num_vars, equations, values) | |
# calc result | |
result = [] | |
for q in queries: | |
numer = vals.get(q[0]) | |
denom = vals.get(q[1]) | |
if not (numer and denom) or numer.sym != denom.sym: | |
result.append(-1.0) | |
else: | |
result.append(numer.val / denom.val) | |
return result | |
def setVals(self, vals, var, | |
num_vars, equations, values): | |
if len(vals) == num_vars: | |
return | |
if not vals.get(var): | |
vals[var] = ValType(1.0, var) | |
self.setVals(vals, var, num_vars, equations, values) | |
return | |
for (numer, denom), val in zip(equations, values): | |
if numer == var and not vals.get(denom): | |
vals[denom] = ValType(vals[var].val / val, vals[var].sym) | |
self.setVals(vals, denom, num_vars, equations, values) | |
elif denom == var and not vals.get(numer): | |
vals[numer] = ValType(vals[var].val * val, vals[var].sym) | |
self.setVals(vals, numer, num_vars, equations, values) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment