C++ 0ms using adjacent matrix


  • 0
    F
    class Solution {
    public:
        unordered_map<string, int> strIdx;
        // aIdx / bIdx
        double dfsGetValue(int aIdx, int bIdx, vector<vector<double>> &vMatrix, vector<char> &visited) {
            if(vMatrix[aIdx][bIdx] > 0.0) return vMatrix[aIdx][bIdx];
            visited[aIdx] = 1;
            for(int i=0; i < vMatrix.size(); ++i) {
                if(visited[i] == 0 && vMatrix[aIdx][i] > 0.0) {
                    double dRet = dfsGetValue(i, bIdx, vMatrix, visited);
                    if(dRet > 0.0) return vMatrix[aIdx][i] * dRet;
                }
            }
            return -1.0;
        }
    
        vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
            int idxCount = 0;
            for(auto &d : equations) {
                if(strIdx.count(d.first) == 0) {
                    strIdx[d.first] = idxCount;
                    ++idxCount;
                }
                if(strIdx.count(d.second) == 0) {
                    strIdx[d.second] = idxCount;
                    ++idxCount;
                }
            }
            vector<vector<double>> vMatrix(idxCount, vector<double>(idxCount, -1.0));
            for(int i=0; i<idxCount; ++i) vMatrix[i][i] = 1.0;
            for(int i=0; i<equations.size(); ++i) {
                auto &d = equations[i];
                vMatrix[strIdx[d.first]][strIdx[d.second]] = values[i];
                vMatrix[strIdx[d.second]][strIdx[d.first]] = 1.0 / values[i];
            }
    
            vector<double> ans;
            for(auto &query : queries) {
                // a/b
                if(strIdx.count(query.first) == 0 || strIdx.count(query.second) == 0) {
                    ans.push_back(-1.0);
                }else{
                    vector<char> visited(vMatrix.size(), 0);
                    ans.push_back( dfsGetValue(strIdx[query.first], strIdx[query.second], vMatrix, visited) );
                }
            }
            return ans;
        }
    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.