PHP | LeetCode

Задача: 1231. Divide Chocolate
Сложность: hard

У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.

Пример:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

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

1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить.

2⃣Двоичный поиск:
Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.

3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.

😎 Решение:

function maximizeSweetness($sweetness, $k) {
    $canDivide = function($minSweetness) use ($sweetness, $k) {
        $currentSum = 0;
        $cuts = 0;
        foreach ($sweetness as $sweet) {
            $currentSum += $sweet;
            if ($currentSum >= $minSweetness) {
                $cuts++;
                $currentSum = 0;
            }
        }
        return $cuts >= $k + 1;
    };

    $left = min($sweetness);
    $right = intdiv(array_sum($sweetness), $k + 1);

    while ($left < $right) {
        $mid = intdiv($left + $right + 1, 2);
        if ($canDivide($mid)) {
            $left = $mid;
        } else {
            $right = $mid - 1;
        }
    }

    return $left;
}

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

Задача: 278. First Bad Version
Сложность: easy

Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими.
Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.
Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.

Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

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

1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.

2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.

3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.

😎 Решение:

class Solution {
    public function firstBadVersion($n) {
        $left = 1;
        $right = $n;
        while ($left < $right) {
            $mid = $left + (int)(($right - $left) / 2);
            if ($this->isBadVersion($mid)) {
                $right = $mid;
            } else {
                $left = $mid + 1;
            }
        }
        return $left;
    }
}

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

Задача: 821. Shortest Distance to a Character
Сложность: easy

Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.

Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.

Пример:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

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

1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.

2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.

3⃣Мы берем минимальное значение из этих двух ответов для создания нашего окончательного ответа.

😎 Решение:

class Solution {
    function shortestToChar($S, $C) {
        $N = strlen($S);
        $ans = array_fill(0, $N, PHP_INT_MAX);
        $prev = -$N;

        for ($i = 0; $i < $N; ++$i) {
            if ($S[$i] == $C) {
                $prev = $i;
            }
            $ans[$i] = $i - $prev;
        }

        $prev = 2 * $N;
        for ($i = $N - 1; $i >= 0; --$i) {
            if ($S[$i] == $C) {
                $prev = $i;
            }
            $ans[$i] = min($ans[$i], $prev - $i);
        }

        return $ans;
    }
}

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.

Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

1⃣Использование рекурсивного подхода:
Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов.
Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки.
Если не можем, пропускаем текущую строку и переходим к следующей.

2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.

3⃣Поиск максимальной длины:
На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины.

😎 Решение:

function maxLength($arr) {
    function isUnique($s) {
        return count(array_unique(str_split($s))) === strlen($s);
    }

    function backtrack($arr, $index, $current) {
        if (!isUnique($current)) {
            return 0;
        }
        $maxLength = strlen($current);
        for ($i = $index; $i < count($arr); $i++) {
            $maxLength = max($maxLength, backtrack($arr, $i + 1, $current . $arr[$i]));
        }
        return $maxLength;
    }

    return backtrack($arr, 0, "");
}

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

Задача: 1033. Moving Stones Until Consecutive
Сложность: medium

На оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть.

Пример:

Input: a = 3, b = 5, c = 1
Output: [1,2]

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

1⃣Сортировка позиций:
Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z.

2⃣Вычисление минимальных ходов:
Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0.
Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1.
В остальных случаях минимальное количество ходов равно 2.

3⃣Вычисление максимальных ходов:
Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1).

😎 Решение:

function numMovesStones($a, $b, $c) {
    $stones = [$a, $b, $c];
    sort($stones);
    list($x, $y, $z) = $stones;
    $minMoves = ($y - $x <= 2 || $z - $y <= 2) ? (($y - $x == 1 && $z - $y == 1) ? 0 : 1) : 2;
    $maxMoves = ($y - $x - 1) + ($z - $y - 1);
    return [$minMoves, $maxMoves];
}

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

Задача: 362. Design Hit Counter
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.

Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

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

1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.

2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.

3⃣Верните размер очереди как количество попаданий за последние 5 минут.

😎 Решение:

class HitCounter {
    private $hits;

    public function __construct() {
        $this->hits = [];
    }

    public function hit($timestamp) {
        array_push($this->hits, $timestamp);
    }

    public function getHits($timestamp) {
        while (!empty($this->hits) && $timestamp - $this->hits[0] >= 300) {
            array_shift($this->hits);
        }
        return count($this->hits);
    }
}

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

Задача: 60. Permutation Sequence
Сложность: hard

Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.
Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.

Пример:

Input: n = 3, k = 3
Output: "213"

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

1⃣Сгенерируйте входной массив nums чисел от 1 до N.

2⃣Вычислите все факториальные основы от 0 до (N−1)!.

3⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1).
Используйте коэффициенты факториалов для построения перестановки.
Верните строку перестановки.

😎 Решение:

class Solution {
    public function getPermutation($n, $k) {
        $factorials = array_fill(0, $n, 1);
        $nums = [];
        for ($i = 1; $i < $n; $i++) {
            $factorials[$i] = $factorials[$i - 1] * $i;
            $nums[] = strval($i + 1);
        }
        $k--;
        $result = "";
        for ($i = $n - 1; $i >= 0; $i--) {
            $idx = intdiv($k, $factorials[$i]);
            $k -= $idx * $factorials[$i];
            $result .= $nums[$idx];
            array_splice($nums, $idx, 1);
        }
        return $result;
    }
}

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

Задача: 59. Spiral Matrix II
Сложность: medium

Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке.

Пример:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

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

1⃣Определение направлений движения:
Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1).

2⃣Перемещение по матрице:
Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений.

3⃣Изменение направления:
Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4.

😎 Решение:

class Solution {
    // Helper function to handle negative indices in modulo operations
    private function floorMod($x, $y) {
        return (($x % $y) + $y) % $y;
    }

    // Function to generate an n x n matrix in spiral order
    public function generateMatrix($n) {
        $result = array_fill(0, $n, array_fill(0, $n, 0));
        $cnt = 1;
        $dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];
        $d = 0;
        $row = 0;
        $col = 0;

        while ($cnt <= $n * $n) {
            $result[$row][$col] = $cnt;
            $cnt++;
            $r = $this->floorMod($row + $dir[$d][0], $n);
            $c = $this->floorMod($col + $dir[$d][1], $n);

            if ($result[$r][$c] != 0) {
                $d = ($d + 1) % 4;
            }
            
            $row += $dir[$d][0];
            $col += $dir[$d][1];
        }

        return $result;
    }
}

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

Задача: 45. Jump Game II
Сложность: medium

Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].
Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:
0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].

Пример:

Input: nums = [2,3,0,1,4]
Output: 2

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

1⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0.

2⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]).

3⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2.

😎 Решение:

function jump($nums) {
    $answer = 0;
    $n = count($nums);
    $curEnd = 0;
    $curFar = 0;
    for ($i = 0; $i < $n - 1; ++$i) {
        $curFar = max($curFar, $i + $nums[$i]);
        if ($i === $curEnd) {
            ++$answer;
            $curEnd = $curFar;
        }
    }
    return $answer;
}

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

Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium

Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.

Пример:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]

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

1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y).

2⃣Перемещение указателей:
Если 𝑓(𝑥,𝑦)=𝑧
f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x.

3⃣Повторяем шаги до тех пор, пока
𝑥≤1000 x≤1000 и 𝑦≥1y≥1.

😎 Решение:

class CustomFunction {
    public function f($x, $y) {}
}

function findSolution($customfunction, $z) {
    $result = [];
    $x = 1;
    $y = 1000;
    
    while ($x <= 1000 && $y >= 1) {
        $value = $customfunction->f($x, $y);
        if ($value == $z) {
            $result[] = [$x, $y];
            $x++;
        } else if ($value < $z) {
            $x++;
        } else {
            $y--;
        }
    }
    
    return $result;
}

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

Задача: 88. Merge Sorted Array
Сложность: easy

Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.

Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.

Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.

Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

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

1⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1.

2⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1.
Инициализируйте указатель для чтения p1 в начале nums1Copy.
Инициализируйте указатель для чтения p2 в начале nums2.

3⃣Инициализируйте указатель для записи p в начале nums1.
Пока p все еще находится внутри nums1:
Если nums1Copy[p1] существует и меньше или равно nums2[p2]:
Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1.
Иначе
Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1.
Увеличьте p на 1.

😎 Решение:

class Solution {

    public function merge(&$nums1, $m, $nums2, $n) {
        $nums1Copy = array_slice($nums1, 0, $m);
        $p1 = 0;
        $p2 = 0;
        
        for ($p = 0; $p < $n + $m; $p++) {
            if ($p2 >= $n || ($p1 < $m && $nums1Copy[$p1] <= $nums2[$p2])) {
                $nums1[$p] = $nums1Copy[$p1];
                $p1++;
            } else {
                $nums1[$p] = $nums2[$p2];
                $p2++;
            }
        }
    }
}

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

Задача: 913. Cat and Mouse4
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

1⃣Использовать динамическое программирование с мемоизацией для хранения результатов игры для каждой комбинации позиций мыши, кота и текущего игрока.

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

function catMouseGame($graph) {
    $n = count($graph);
    $DRAW = 0; $MOUSE = 1; $CAT = 2;
    $dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2, $DRAW)));
    $queue = [];

    for ($i = 1; $i < $n; $i++) {
        $dp[0][$i][0] = $MOUSE;
        $dp[0][$i][1] = $MOUSE;
        $dp[$i][$i][0] = $CAT;
        $dp[$i][$i][1] = $CAT;
        $queue[] = [0, $i, 0, $MOUSE];
        $queue[] = [0, $i, 1, $MOUSE];
        $queue[] = [$i, $i, 0, $CAT];
        $queue[] = [$i, $i, 1, $CAT];
    }

    function parents($graph, $mouse, $cat, $turn) {
        $res = [];
        if ($turn == 1) {
            foreach ($graph[$mouse] as $m) {
                $res[] = [$m, $cat, 0];
            }
        } else {
            foreach ($graph[$cat] as $c) {
                if ($c > 0) $res[] = [$mouse, $c, 1];
            }
        }
        return $res;
    }

    while (!empty($queue)) {
        list($mouse, $cat, $turn, $winner) = array_shift($queue);
        foreach (parents($graph, $mouse, $cat, $turn) as list($m, $c, $t)) {
            if ($dp[$m][$c][$t] == $DRAW) {
                if (($t == 0 && $winner == $MOUSE) || ($t == 1 && $winner == $CAT)) {
                    $dp[$m][$c][$t] = $winner;
                    $queue[] = [$m, $c, $t, $winner];
                } else {
                    $degrees = 0;
                    foreach (parents($graph, $m, $c, $t) as $_) $degrees++;
                    if ($degrees == 0) {
                        $dp[$m][$c][$t] = $winner;
                        $queue[] = [$m, $c, $t, $winner];
                    }
                }
            }
        }
    }

    return $dp[1][2][0];
}

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

Задача: 990. Satisfiability of Equality Equations
Сложность: medium

Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.

Верните true, если возможно назначить целые числа именам переменных таким образом, чтобы удовлетворить всем заданным уравнениям, или false в противном случае.

Пример:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

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

1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.

2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.

3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.

😎 Решение:

class UnionFind {
    private $parent;

    public function __construct($size) {
        $this->parent = range(0, $size - 1);
    }

    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        if ($rootX != $rootY) {
            $this->parent[$rootX] = $rootY;
        }
    }

    public function connected($x, $y) {
        return $this->find($x) == $this->find($y);
    }
}

class Solution {
    function equationsPossible($equations) {
        $uf = new UnionFind(26);
        
        foreach ($equations as $eq) {
            if ($eq[1] == '=') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                $uf->union($x, $y);
            }
        }
        
        foreach ($equations as $eq) {
            if ($eq[1] == '!') {
                $x = ord($eq[0]) - ord('a');
                $y = ord($eq[3]) - ord('a');
                if ($uf->connected($x, $y)) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

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

Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
    private $inorderNodes = [];
    
    private function inorderTraversal($root) {
        if ($root === null) {
            return;
        }
        
        $this->inorderTraversal($root->left);
        $this->inorderNodes[] = $root->val;
        $this->inorderTraversal($root->right);
    }
    
    public function minDiffInBST($root) {
        $this->inorderTraversal($root);
        
        $minDistance = PHP_INT_MAX;
        for ($i = 1; $i < count($this->inorderNodes); $i++) {
            $minDistance = min($minDistance, $this->inorderNodes[$i] - $this->inorderNodes[$i - 1]);
        }
        
        return $minDistance;
    }
}

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

Задача: 563. Binary Tree Tilt
Сложность: easy

Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.
Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

1⃣Определите рекурсивную функцию, которая вычисляет сумму значений узлов поддерева и наклон текущего узла.

2⃣Для каждого узла вычислите сумму значений левого и правого поддерева, а также их наклон, добавляя наклон к общей сумме.

3⃣Верните общую сумму наклонов всех узлов.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private $totalTilt = 0;
    
    function findTilt($root) {
        $this->sumAndTilt($root);
        return $this->totalTilt;
    }
    
    private function sumAndTilt($node) {
        if ($node === null) {
            return 0;
        }
        $leftSum = $this->sumAndTilt($node->left);
        $rightSum = $this->sumAndTilt($node->right);
        $nodeTilt = abs($leftSum - $rightSum);
        $this->totalTilt += $nodeTilt;
        return $node->val + $leftSum + $rightSum;
    }
}

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

Задача: 244. Shortest Word Distance II
Сложность: medium

Создайте структуру данных, которая будет инициализироваться массивом строк, а затем должна отвечать на запросы о наименьшем расстоянии между двумя разными строками из массива.
Реализуйте класс WordDistance:
WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

1⃣В конструкторе класса переберите заданный список слов и создайте словарь, сопоставляя слово с его позициями в массиве. Поскольку мы обрабатываем слова слева направо, индексы будут по умолчанию отсортированы для всех слов.

2⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

// PHP
class WordDistance {
    private $locations;

    function __construct($words) {
        $this->locations = [];
        foreach ($words as $i => $word) {
            if (!isset($this->locations[$word])) {
                $this->locations[$word] = [];
            }
            $this->locations[$word][] = $i;
        }
    }

    function shortest($word1, $word2) {
        $loc1 = $this->locations[$word1];
        $loc2 = $this->locations[$word2];
        $l1 = 0;
        $l2 = 0;
        $minDiff = PHP_INT_MAX;

        while ($l1 < count($loc1) && $l2 < count($loc2)) {
            $minDiff = min($minDiff, abs($loc1[$l1] - $loc2[$l2]));
            if ($loc1[$l1] < $loc2[$l2]) {
                $l1++;
            } else {
                $l2++;
            }
        }
        return $minDiff;

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

Задача: 666. Path Sum IV
Сложность: medium

Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

1⃣Создание структуры дерева:
Пройдите по массиву nums и для каждого элемента создайте узел дерева.
Сохраните узлы в словаре для удобного доступа по их позиции.

2⃣Связывание узлов:
Пройдите по массиву и свяжите узлы друг с другом, исходя из их позиции и глубины.
Найдите левого и правого ребенка для каждого узла и установите соответствующие связи.

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

class Solution {
    function pathSum($nums) {
        $tree = [];
        
        foreach ($nums as $num) {
            $depth = intdiv($num, 100);
            $pos = intdiv($num, 10) % 10;
            $val = $num % 10;
            $tree[$depth * 10 + $pos] = $val;
        }
        
        return $this->dfs($tree, 1, 1, 0);
    }
    
    private function dfs($tree, $depth, $pos, $currentSum) {
        $key = $depth * 10 + $pos;
        if (!isset($tree[$key])) {
            return 0;
        }
        $currentSum += $tree[$key];
        $leftChild = ($depth + 1) * 10 + 2 * $pos - 1;
        $rightChild = ($depth + 1) * 10 + 2 * $pos;
        if (!isset($tree[$leftChild]) && !isset($tree[$rightChild])) {
            return $currentSum;
        }
        return $this->dfs($tree, $depth + 1, 2 * $pos - 1, $currentSum) + $this->dfs($tree, $depth + 1, 2 * $pos, $currentSum);
    }
}

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

Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

2⃣Проверка на коллинеарность:
Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны.

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

function isBoomerang($points) {
    list($x1, $y1) = $points[0];
    list($x2, $y2) = $points[1];
    list($x3, $y3) = $points[2];
    return ($x1 != $x2 || $y1 != $y2) && 
           ($x1 != $x3 || $y1 != $y3) && 
           ($x2 != $x3 || $y2 != $y3) && 
           ($x1 * ($y2 - $y3) + $x2 * ($y3 - $y1) + $x3 * ($y1 - $y2)) != 0;
}

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

Задача: 1065. Index Pairs of a String
Сложность: easy

Дана строка text и массив строк words, верните массив всех пар индексов [i, j], таких что подстрока text[i...j] находится в words.

Верните пары [i, j] в отсортированном порядке (то есть отсортируйте их по первой координате, а в случае совпадения сортируйте их по второй координате).

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Поддерживайте хэш-набор слов.

2⃣Итерируйте i от 0 до text.length-1. Итерируйте j от i до text.length-1. Если подстрока text[i...j] принадлежит хэш-набору слов, добавьте пару [i, j] в ответ.

3⃣Верните ответ.

😎 Решение:

class Solution {
    function indexPairs($text, $words) {
        $wordsSet = array_flip($words);
        $ans = [];
        
        for ($i = 0; $i < strlen($text); $i++) {
            for ($j = $i; $j < strlen($text); $j++) {
                if (isset($wordsSet[substr($text, $i, $j - $i + 1)])) {
                    $ans[] = [$i, $j];
                }
            }
        }
        return $ans;
    }
}

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

Задача: 606. Construct String from Binary Tree
Сложность: medium

Дано бинарное дерево, необходимо вернуть его строковое представление, используя прямой обход (preorder traversal) и правила со скобками:
Скобки для детей обязательны, если есть правый ребёнок
Пропускать пустые скобки, кроме случая, когда отсутствует левый, но есть правый ребёнок

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

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

😎 Решение:

class Solution {
    function tree2str($t) {
        $res = "";
        $this->dfs($t, $res);
        return $res;
    }

    function dfs($t, &$res) {
        if ($t == null)
            return;
        $res .= $t->val;
        if ($t->left == null && $t->right == null)
            return;
        $res .= '(';
        $this->dfs($t->left, $res);
        $res .= ')';
        if ($t->right != null) {
            $res .= '(';
            $this->dfs($t->right, $res);
            $res .= ')';
        }
    }
}

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