leetcode 문제 풀이: 399 번 Evaluate Division

https://leetcode-cn.com/problems/evaluate-division/
글 목록

분석

해법 1. 그림 옮 겨 다 니 기

코드

해법 2. 병 찰 집

코드

분석 하 다.
이 문 제 는 목적 이 명확 하고 논리 도 이해 하기 쉬 우 며 사람 은 이런 방정식 의 결 과 를 쉽게 계산 할 수 있 지만 어떻게 이런 방정식 을 프로그램 에서 표시 하 느 냐 가 어 려 운 문제 이다.방정식 을 정확하게 표시 하면 처리 하기 어 려 울 것 같은 이 문 제 를 쉽게 해결 할 수 있 는 문제 로 바 꿀 수 있다 는 얘 기다.
해법
힌트 를 주면 이 문 제 를 그림 과 연결 시 켜 해결 방법 을 빨리 찾 을 수 있 을 까?우 리 는 입력 한 모든 방정식 을 띠 권 도 로 표시 할 수 있다 는 것 을 자 연 스 럽 게 생각 할 수 있다. a / b = value 는 두 변 을 나타 낸다. a->b, 가중치 value 와 b->a, 가중치 1.0 / value.조회 한 문제 방정식 x / y 에 대해 문 제 는 이 대역 권 도 에서 x 에서 y 까지 의 경 로 를 찾 고 경로 상의 가중치 곱 하기 로 전환 할 수 있다.
몇 개의 인 코딩 세부 사항

그림 의 표현 방법 을 어떻게 선택 합 니까?인접 표.노드 a 는 string 유형 이기 때문에 해시 표 로 노드 a 를 모든 변 의 맵 에 저장 해 야 합 니 다.vector 로 a 가 가리 키 는 모든 노드, 즉 a 에서 나 간 변 의 집합

을 저장 합 니 다.

가중치 의 변 을 어떻게 표시 합 니까?구조 체 의 가중 변 은 가리 키 는 노드 를 갖 추 는 것 외 에 도 가중치 가 필요 하기 때문에 구조 체 를 정의 하 는 것 이 좋 은 선택

이다.

어떻게 x 에서 y 까지 의 경 로 를 찾 습 니까?BFS 나 DFS 에서 흔히 말 하 는 화 제 는 가중치 의 곱 하기 와 이미 옮 겨 다 니 는 노드 를 옮 겨 다 니 지 않도록 주의해 야 한다.

코드

class Solution {
     
public:
    struct edge {
     
        string node;
        double weight;
        edge (string node, double weight): node(node), weight(weight) {
     }
    };
    
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
     
        unordered_map<string, vector<edge>> edges;
        int n = equations.size();
        //        
        for (int i = 0; i < n; ++i) {
     
            string x = equations[i][0], y = equations[i][1];
            edges[x].push_back(edge(y, values[i]));
            edges[y].push_back(edge(x, 1 / values[i]));
        }
        vector<double> ans;
        for (auto& query : queries) {
     
            string x = query[0], y = query[1];
            bool flag = false;
            //        x y     
            unordered_map<string, int> used;
            queue<pair<string, double>> q;
            if (edges.count(x)) {
     
                q.push({
     x, 1.0});
                used[x] = 1;
            }
            while (!q.empty()) {
     
                auto [node, weight] = q.front();
                q.pop();
                if (node == y) {
     
                    ans.push_back(weight);
                    flag = true;
                    break;
                }
                for (edge& e : edges[node]) {
     
                    if (used[e.node] == 0) {
     
                        q.push({
     e.node, weight * e.weight});
                        used[e.node] = 1;
                    }
                }
            }
            //     query  
            if (!flag) ans.push_back(-1.0);
        }
        return ans;
    }
};

해법
가중치 변 을 가 진 집합 을 구축 하고 계산 할 방정식 x / y:

만약 x 과 y 이 연 결 된 서브 집중 에 없 으 면 풀 리 지 않 는 다

그렇지 않 으 면 각각 계산 x / root 과 y / root 을 하여 구 해 x / y

이러한 병렬 집합 을 실현 하려 면 두 개의 변 수 를 정의 해 야 한다. parents[a] 는 존재 a / parents[a] 를 대표 하고 값 은 weights[a] 이다.
코드

class Solution {
     
public:
    unordered_map<string, string> parents; //   a / parents[a]
    unordered_map<string, double> weights; // weights[a]: a / parents[a]

    pair<string, double> MyFind(string& x) {
     
        if (!parents.count(x)) return {
     "", -1.0};
        double weight = 1.0;
        while (x != parents[x]) {
     
            weight *= weights[x];
            x = parents[x];
        }
        return {
     x, weight}; //x   root, weight  x / root  
    }

    void MyUnion(string& a, string& b, double value) {
     
        pair<string, double> root1 = MyFind(a);
        pair<string, double> root2 = MyFind(b);
        if (root1.first == root2.first) return;
        parents[root1.first] = root2.first;
        // root1.second: a / root1, value: a / b, root2.second: b / root2
        weights[root1.first] = 1.0 / root1.second * value * root2.second;
    }

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
     
        int n = equations.size();
        for (int i = 0; i < n; ++i) {
     
            string x = equations[i][0], y = equations[i][1];
            //    
            if (!parents.count(x)) parents[x] = x, weights[x] = 1.0;
            if (!parents.count(y)) parents[y] = y, weights[y] = 1.0;
            MyUnion(x, y, values[i]);
        }
        vector<double> ans;
        for (auto& query : queries) {
     
            string x = query[0], y = query[1];
            pair<string, double> root1 = MyFind(x);
            pair<string, double> root2 = MyFind(y);
            if (root1.first != root2.first || root1.first == "" || root2.first == "") ans.push_back(-1.0);
            else ans.push_back(root1.second / root2.second);
        }
        return ans;
    }
};