399. Evaluate Division

using System;
using System.Collections.Generic;
public class Solution {
    public double[] CalcEquation(IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        var graph = new Dictionary<string, Dictionary<string, double>>();
        for (int i = 0; i < equations.Count; i++) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            if (!graph.ContainsKey(A)) graph[A] = new Dictionary<string, double>();
            if (!graph.ContainsKey(B)) graph[B] = new Dictionary<string, double>();
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }
        double Bfs(string start, string end) {
            if (!graph.ContainsKey(start) || !graph.ContainsKey(end)) return -1.0;
            var q = new Queue<(string, double)>();
            q.Enqueue((start, 1.0));
            var visited = new HashSet<string>();
            
            while (q.Count > 0) {
                var (current, curProduct) = q.Dequeue();
                if (current == end) return curProduct;
                visited.Add(current);
                foreach (var neighbor in graph[current]) {
                    if (!visited.Contains(neighbor.Key)) {
                        q.Enqueue((neighbor.Key, curProduct * neighbor.Value));
                    }
                }
            }
            return -1.0;
        }
        var results = new double[queries.Count];
        for (int i = 0; i < queries.Count; i++) {
            string C = queries[i][0], D = queries[i][1];
            results[i] = Bfs(C, D);
        }
        return results;
    }
}

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public double[] CalcEquation(IList<vector<string>> equations, double[] values, IList<vector<string>> queries) {
        var graph = new unordered_map<string, Dictionary<string, double>>();
        for (int i = 0; i < equations.size(); i++) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            if (!graph.count(A)) graph[A] = new unordered_map<string, double>();
            if (!graph.count(B)) graph[B] = new unordered_map<string, double>();
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }
        double Bfs(string start, string end) {
            if (!graph.count(start) || !graph.count(end)) return -1.0;
            var q = new queue<(string, double)>();
            q.Enqueue((start, 1.0));
            var visited = new HashSet<string>();
            
            while (q.size() > 0) {
                var (current, curProduct) = q.Dequeue();
                if (current == end) return curProduct;
                visited.push_back(current);
                foreach (var neighbor in graph[current]) {
                    if (!visited.Contains(neighbor.Key)) {
                        q.Enqueue((neighbor.Key, curProduct * neighbor.Value));
                    }
                }
            }
            return -1.0;
        }
        var results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            string C = queries[i][0], D = queries[i][1];
            results[i] = Bfs(C, D);
        }
        return results;
    }
}

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values,
            List<List<String>> queries) {

        HashMap<String, HashMap<String, Double>> graph = new HashMap<>();

        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String dividend = equation.get(0), divisor = equation.get(1);
            double quotient = values[i];

            if (!graph.containsKey(dividend))
                graph.put(dividend, new HashMap<String, Double>());
            if (!graph.containsKey(divisor))
                graph.put(divisor, new HashMap<String, Double>());

            graph.get(dividend).put(divisor, quotient);
            graph.get(divisor).put(dividend, 1 / quotient);
        }

        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String dividend = query.get(0), divisor = query.get(1);

            if (!graph.containsKey(dividend) || !graph.containsKey(divisor))
                results[i] = -1.0;
            else if (dividend == divisor)
                results[i] = 1.0;
            else {
                HashSet<String> visited = new HashSet<>();
                results[i] = backtrackEvaluate(graph, dividend, divisor, 1, visited);
            }
        }

        return results;
    }

    private double backtrackEvaluate(HashMap<String, HashMap<String, Double>> graph, String currNode, String targetNode, double accProduct, Set<String> visited) {

        visited.add(currNode);
        double ret = -1.0;

        Map<String, Double> neighbors = graph.get(currNode);
        if (neighbors.containsKey(targetNode))
            ret = accProduct * neighbors.get(targetNode);
        else {
            for (Map.Entry<String, Double> pair : neighbors.entrySet()) {
                String nextNode = pair.getKey();
                if (visited.contains(nextNode))
                    continue;
                ret = backtrackEvaluate(graph, nextNode, targetNode,
                        accProduct * pair.getValue(), visited);
                if (ret != -1.0)
                    break;
            }
        }

        visited.remove(currNode);
        return ret;
    }
}

class Solution {
    calcEquation(equations, values, queries) {
        const graph = new Map();

        for (let i = 0; i < equations.length; i++) {
            const [A, B] = equations[i];
            const value = values[i];
            if (!graph.has(A)) graph.set(A, new Map());
            if (!graph.has(B)) graph.set(B, new Map());
            graph.get(A).set(B, value);
            graph.get(B).set(A, 1.0 / value);
        }

        const bfs = (start, end) => {
            if (!graph.has(start) || !graph.has(end)) return -1.0;
            const q = [[start, 1.0]];
            const visited = new Set();
            
            while (q.length) {
                const [current, curProduct] = q.shift();
                if (current === end) return curProduct;
                visited.add(current);
                for (const [neighbor, value] of graph.get(current).entries()) {
                    if (!visited.has(neighbor)) {
                        q.push([neighbor, curProduct * value]);
                    }
                }
            }
            return -1.0;
        };

        return queries.map(([C, D]) => bfs(C, D));
    }
}

from collections import defaultdict, deque

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = defaultdict(dict)

        for (A, B), value in zip(equations, values):
            graph[A][B] = value
            graph[B][A] = 1 / value

        def bfs(start, end):
            if start not in graph or end not in graph:
                return -1.0
            queue = deque([(start, 1.0)])
            visited = set()
            while queue:
                current, cur_product = queue.popleft()
                if current == end:
                    return cur_product
                visited.add(current)
                for neighbor, value in graph[current].items():
                    if neighbor not in visited:
                        queue.append((neighbor, cur_product * value))
            return -1.0

        results = []
        for C, D in queries:
            results.append(bfs(C, D))
        return results

package main

import "container/list"

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    graph := make(map[string]map[string]float64)
    
    for i, equation := range equations {
        A, B := equation[0], equation[1]
        value := values[i]
        if _, ok := graph[A]; !ok {
            graph[A] = make(map[string]float64)
        }
        if _, ok := graph[B]; !ok {
            graph[B] = make(map[string]float64)
        }
        graph[A][B] = value
        graph[B][A] = 1.0 / value
    }
    
    bfs := func(start, end string) float64 {
        if _, ok := graph[start]; !ok {
            return -1.0
        }
        if _, ok := graph[end]; !ok {
            return -1.0
        }
        q := list.New()
        q.PushBack([2]interface{}{start, 1.0})
        visited := make(map[string]bool)
        
        for q.Len() > 0 {
            e := q.Front()
            q.Remove(e)
            cur := e.Value.([2]interface{})
            current, curProduct := cur[0].(string), cur[1].(float64)
            if current == end {
                return curProduct
            }
            visited[current] = true
            for neighbor, value := range graph[current] {
                if !visited[neighbor] {
                    q.PushBack([2]interface{}{neighbor, curProduct * value})
                }
            }
        }
        return -1.0
    }
    
    results := make([]float64, len(queries))
    for i, query := range queries {
        C, D := query[0], query[1]
        results[i] = bfs(C, D)
    }
    return results
}

Algorithm

Создание grapheа:

Представьте каждую переменную как узел в grapheе.

Используйте уравнения для создания ребер между узлами, где каждое edge имеет вес, равный значению уравнения (Ai / Bi = values[i]).

Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

Поиск пути:

Для каждого запроса используйте Depth-first search (DFS) или Breadth-first search (BFS) для поиска пути от Cj до Dj.

Если путь найден, вычислите произведение весов вдоль пути, чтобы find значение Cj / Dj.

Если путь не найден, return -1.0.

Обработка запросов:

Пройдитесь по всем запросам и используйте graphe для вычисления результатов каждого запроса.

😎