Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

👨‍💻 Алгоритм:

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

2⃣Поиск пути
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

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

😎 Решение:

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));
    }
}

Ставь 👍 и забирай 📚 Базу знаний