leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0399.cpp (1583B)

0 class Solution { 1 const int SIZE = 26 * 5; 2 3 int hash(const string &st) { 4 static int index = 0; 5 static unordered_map<string, int> um; 6 if (!um.count(st)) um[st] = index++; 7 return um[st]; 8 } 9 10 double dfs(vector<vector<pair<int, double>>> &adj, int start, int goal) { 11 stack<pair<int, double>> st; 12 vector<bool> visited(SIZE, false); 13 14 st.push({start, 1}); 15 visited[start] = true; 16 while (!st.empty()) { 17 auto [root, value] = st.top(); 18 st.pop(); 19 if (root == goal) return value; 20 visited[root] = true; 21 for (auto &v : adj[root]) 22 if (!visited[v.first]) st.push({v.first, value * v.second}); 23 } 24 return -1; 25 } 26 27 public: 28 vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, 29 vector<vector<string>> &queries) { 30 vector<vector<pair<int, double>>> adj(SIZE, vector<pair<int, double>>()); 31 for (int i = 0; i < values.size(); i++) { 32 adj[hash(equations[i][0])].push_back({hash(equations[i][1]), values[i]}); 33 adj[hash(equations[i][1])].push_back({hash(equations[i][0]), 1 / values[i]}); 34 } 35 36 vector<double> res(queries.size(), -1); 37 for (int i = 0; i < queries.size(); i++) { 38 int start = hash(queries[i][0]), goal = hash(queries[i][1]); 39 if (adj[start].empty() || adj[goal].empty()) continue; 40 res[i] = dfs(adj, start, goal); 41 } 42 return res; 43 } 44 };