부문 평가

난이도 중급
자주 묻는 질문 아마존 블룸버그 게시물에서 Facebook 구글 Microsoft 동네 짱
Graph 유니온 찾기조회수 53

나눗셈 문제를 평가할 때 A / B = k 형식으로 몇 가지 방정식을 제공했습니다. 여기서 A와 B는 문자열이고 k는 실수입니다. 답변이 존재하지 않으면 -1을 반환합니다.

입력:
방정식 : a / b = 2.0 및 b / c = 3.0
쿼리 : a / c =?, b / a =?, a / e =?, a / a =?, x / x =?
출력:
{6.0, 0.5, -1.0, 1.0, -1.0}

방정식은 목록의 목록으로 표시됩니다. 문자열, 값은 다음과 같이 표시됩니다. 정렬 이중 및 쿼리는 list_of_list_of 문자열로도 표시됩니다. 즉, 위의 예에서 입력은 다음과 같이 표시됩니다.

방정식 = {{“a”,“b”}, {“a”,“c”}}
값 = {2.0, 3.0}
검색어 = {{ "a", "c"}, { "b", "a"}, { "a", "e"}, { "a", "a"}, { "x", "x ”}}

나눗셈 평가를위한 알고리즘

위의 문제는 그래프를 나타냅니다.
방정식의 변수는 노드이고 방정식의 값은 모서리의 가중치입니다.
꼭지점 x에서 꼭지점 y까지의 가장자리는 x / y와 같은 가중치를 갖습니다.
위 예의 그래프는 다음과 같습니다.

부문 평가

쿼리에 대한 응답은 다음을 수행하여 찾을 수 있습니다. DFS 에서 검색 그래프.

  1. 위에서 언급 한대로 그래프를 작성하십시오.
  2. 각 쿼리는 소스와 대상의 형태이므로 소스에서 시작하여 대상에 도달해야합니다.
  3. 모든 쿼리에 대해 소스에서 시작하고 소스가 없으면 -1을 반환합니다.
  4. 소스에 필요한 대상에 대한 직접 에지가있는 경우 에지 값을 반환합니다.
  5. 그렇지 않으면 소스를 방문으로 표시하고 아직 방문하지 않은 소스의 모든 인접 항목에 대해 반복하면 인접 항목이 소스가되고 대상은 동일하게 유지됩니다. 인접 항목의 응답이 -1이 아닌 경우 소스에서 인접 항목으로 에지 가중치를 반환합니다. 더하기 이웃의 대답.

평가 부문을위한 JAVA 코드

import java.util.*;

public class EvaluateDivision {
    private static double[] calcEquation(List<List<String>> equations, double[] values,
                                         List<List<String>> queries) {
        // Build the graph
        HashMap<String, HashMap<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String from = equations.get(i).get(0);
            String to = equations.get(i).get(1);

            // From source to destination the weight of edge is values[i]
            if (graph.containsKey(from)) {
                graph.get(from).put(to, values[i]);
            } else {
                HashMap<String, Double> map = new HashMap<>();
                map.put(to, values[i]);
                graph.put(from, map);
            }

            // From destination to source the weight of edge is (1 / values[i])
            if (graph.containsKey(to)) {
                graph.get(to).put(from, 1 / values[i]);
            } else {
                HashMap<String, Double> map = new HashMap<>();
                map.put(from, 1 / values[i]);
                graph.put(to, map);
            }
        }

        // Solve queries
        double ans[] = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            // Visited set
            HashSet<String> visited = new HashSet<>();
            ans[i] = dfs(graph, queries.get(i).get(0), queries.get(i).get(1), visited);
        }

        return ans;
    }

    private static double dfs(HashMap<String, HashMap<String, Double>> graph, String from, String to,
                              HashSet<String> visited) {
        // Source not found
        if (!graph.containsKey(from)) {
            return -1.0;
        }

        // Direct edge
        if (graph.get(from).containsKey(to)) {
            return graph.get(from).get(to);
        }

        // Mark source as visited
        visited.add(from);

        for (Map.Entry<String, Double> entry : graph.get(from).entrySet()) {
            if (!visited.contains(entry.getKey())) {
                // For all unvisited neighbors of source do dfs
                // neighbor becomes the source and destination remains same
                double ans = dfs(graph, entry.getKey(), to, visited);
                if (ans != -1.0) {
                    // If ans of any neighbor is not -1, return (edge weight * ans of neighbor)
                    return (ans * entry.getValue());
                }
            }
        }

        // All neighbors returned -1, return -1
        return -1.0;
    }

    public static void main(String[] args) {
        // Example
        List<List<String>> equations = new ArrayList<>();
        ArrayList<String> eq1 = new ArrayList<>();
        eq1.add("a");
        eq1.add("b");
        equations.add(eq1);
        ArrayList<String> eq2 = new ArrayList<>();
        eq2.add("b");
        eq2.add("c");
        equations.add(eq2);

        double values[] = new double[2];
        values[0] = 2.0;
        values[1] = 3.0;

        List<List<String>> queries = new ArrayList<>();
        ArrayList<String> q1 = new ArrayList<>();
        q1.add("a");
        q1.add("c");
        queries.add(q1);
        ArrayList<String> q2 = new ArrayList<>();
        q2.add("b");
        q2.add("a");
        queries.add(q2);
        ArrayList<String> q3 = new ArrayList<>();
        q3.add("a");
        q3.add("e");
        queries.add(q3);
        ArrayList<String> q4 = new ArrayList<>();
        q4.add("a");
        q4.add("a");
        queries.add(q4);
        ArrayList<String> q5 = new ArrayList<>();
        q5.add("x");
        q5.add("x");
        queries.add(q5);

        double ans[] = calcEquation(equations, values, queries);
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}

Evaluate Division을위한 C ++ 코드

#include<bits/stdc++.h>
using namespace std;

double dfs(unordered_map<string, unordered_map<string, double>> &graph, 
    string from, string to, unordered_set<string> &visited) {
    // Source not found
    if (graph.find(from) == graph.end()) {
        return -1.0;
    }
    
    // Direct edge
    if (graph[from].find(to) != graph[from].end()) {
        return graph[from][to];
    }
    
    // Mark source as visited
    visited.insert(from);
    
    for (auto i : graph[from]) {
        if (visited.find(i.first) == visited.end()) {
            // For all unvisited neighbors of source do dfs
            double ans = dfs(graph, i.first, to, visited);
            if (ans != -1.0) {
                // If ans of any neighbor is not -1, return (edge weight * ans of neighbor)
                return (ans * i.second);
            }
        }
    }
    
    // All neighbors returned -1, return -1
    return -1.0;
}

vector<double> calcEquation(vector<vector<string>>& equations, 
                vector<double>& values, 
                vector<vector<string>>& queries) {
  // Build the graph
  unordered_map<string, unordered_map<string, double>> graph;
  for (int i = 0; i < equations.size(); i++) {
      string from = equations[i][0];
      string to = equations[i][1];
      
      // From source to destination the weight of edge is values[i]
      if (graph.find(from) == graph.end()) {
          unordered_map<std::string, double> m;
          m.insert(make_pair(to, values[i]));
          graph.insert(make_pair(from, m));
      } else {
          graph[from].insert(make_pair(to, values[i]));
      }
      
      // From destination to source the weight of edge is (1 / values[i])
      if (graph.find(to) == graph.end()) {
          unordered_map<std::string, double> m;
          m.insert(make_pair(from, 1 / values[i]));
          graph.insert(make_pair(to, m));
      } else {
          graph[to].insert(make_pair(from, 1 / values[i]));
      }
  }
  
  // Solve queries
  vector<double> ans;
  for (int i = 0; i < queries.size(); i++) {
      unordered_set<string> visited;
      ans.push_back(dfs(graph, queries[i][0], queries[i][1], visited));
  }
  return ans;
}

int main() {
    // Example
    vector<vector<string>> equations;
    vector<string> eq1;
    eq1.push_back("a");
    eq1.push_back("b");
    equations.push_back(eq1);
    vector<string> eq2;
    eq2.push_back("b");
    eq2.push_back("c");
    equations.push_back(eq2);
    
    vector<double> values;
    values.push_back(2.0);
    values.push_back(3.0);
    
    vector<vector<string>> queries;
    vector<string> q1;
    q1.push_back("a");
    q1.push_back("c");
    queries.push_back(q1);
    vector<string> q2;
    q2.push_back("b");
    q2.push_back("a");
    queries.push_back(q2);
    vector<string> q3;
    q3.push_back("a");
    q3.push_back("e");
    queries.push_back(q3);
    vector<string> q4;
    q4.push_back("a");
    q4.push_back("a");
    queries.push_back(q4);
    vector<string> q5;
    q5.push_back("x");
    q5.push_back("x");
    queries.push_back(q5);
    
    vector<double> ans = calcEquation(equations, values, queries);
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    
    return 0;
}
6 0.5 -1 1 -1

복잡성 분석

시간 복잡성 = O (q * (V + E))어디로
q –> 쿼리 수
V –> 그래프의 꼭지점 수 (또는 변수 수)
E –> 그래프의 모서리 수 (또는 방정식 수)

참조

Translate »