Задача: 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 {
    function calcEquation($equations, $values, $queries) {
        $graph = [];
        
        for ($i = 0; $i < count($equations); $i++) {
            $A = $equations[$i][0];
            $B = $equations[$i][1];
            $value = $values[$i];
            if (!isset($graph[$A])) $graph[$A] = [];
            if (!isset($graph[$B])) $graph[$B] = [];
            $graph[$A][$B] = $value;
            $graph[$B][$A] = 1.0 / $value;
        }
        
        function bfs($start, $end, $graph) {
            if (!isset($graph[$start]) || !isset($graph[$end])) return -1.0;
            $queue = [[$start, 1.0]];
            $visited = [];
            
            while (!empty($queue)) {
                list($current, $curProduct) = array_shift($queue);
                if ($current == $end) return $curProduct;
                $visited[$current] = true;
                foreach ($graph[$current] as $neighbor => $value) {
                    if (!isset($visited[$neighbor])) {
                        array_push($queue, [$neighbor, $curProduct * $value]);
                    }
                }
            }
            return -1.0;
        }
        
        $results = [];
        foreach ($queries as $query) {
            $C = $query[0];
            $D = $query[1];
            $results[] = bfs($C, $D, $graph);
        }
        return $results;
    }
}

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