PHP | LeetCode

Задача: 311. Sparse Matrix Multiplication
Сложность: medium

Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно.

Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

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

1⃣Инициализация результирующей матрицы
Создайте результирующую матрицу result размером m x n, заполненную нулями.

2⃣Хранение ненулевых элементов
Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map.

3⃣Вычисление произведения
Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j].

😎 Решение:

class Solution {
    function multiply($mat1, $mat2) {
        $n = count($mat1);
        $k = count($mat1[0]);
        $m = count($mat2[0]);
        
        $ans = array_fill(0, $n, array_fill(0, $m, 0));
        
        for ($rowIndex = 0; $rowIndex < $n; $rowIndex++) {
            for ($elementIndex = 0; $elementIndex < $k; $elementIndex++) {
                if ($mat1[$rowIndex][$elementIndex] != 0) {
                    for ($colIndex = 0; $colIndex < $m; $colIndex++) {
                        $ans[$rowIndex][$colIndex] += $mat1[$rowIndex][$elementIndex] * $mat2[$elementIndex][$colIndex];
                    }
                }
            }
        }
        
        return $ans;
    }
}

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

Задача: 252. Meeting Rooms
Сложность: easy

Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

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

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

2⃣Проверьте каждый интервал с каждым другим интервалом:
Если найдено перекрытие, верните false.

3⃣Если все интервалы проверены и перекрытий не найдено, верните true.

😎 Решение:

class Solution {
    function overlap($interval1, $interval2) {
        return ($interval1[0] >= $interval2[0] && $interval1[0] < $interval2[1]) ||
               ($interval2[0] >= $interval1[0] && $interval2[0] < $interval1[1]);
    }
    
    function canAttendMeetings($intervals) {
        for ($i = 0; $i < count($intervals); $i++) {
            for ($j = $i + 1; $j < count($intervals); $j++) {
                if ($this->overlap($intervals[$i], $intervals[$j])) {
                    return false;
                }
            }
        }
        return true;
    }
}

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

Задача: 1493. Longest Subarray of 1's After Deleting One Element
Сложность: medium

Дан бинарный массив nums, из которого следует удалить один элемент.

Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует.

Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

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

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

2⃣Итерация по массиву:
При каждом элементе увеличиваем zeroCount, если это ноль.
Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1.
Обновляем longestWindow текущей длиной окна i - start.

3⃣Возврат результата:
Вернуть longestWindow.

😎 Решение:

class Solution {
    function longestSubarray($nums) {
        $zeroCount = 0;
        $longestWindow = 0;
        $start = 0;

        for ($i = 0; $i < count($nums); $i++) {
            if ($nums[$i] == 0) {
                $zeroCount++;
            }

            while ($zeroCount > 1) {
                if ($nums[$start] == 0) {
                    $zeroCount--;
                }
                $start++;
            }

            $longestWindow = max($longestWindow, $i - $start);
        }

        return $longestWindow;
    }
}

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

Задача: 1006. Clumsy Factorial
Сложность: medium

Факториал целого положительного числа n - это произведение всех целых положительных чисел, меньших или равных n. Например, факториал(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
Мы составляем неуклюжий факториал, используя целые числа в порядке убывания, заменяя операции умножения на фиксированную последовательность операций с умножением "*", делением "/", сложением "+" и вычитанием "-" в этом порядке. Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка операций арифметики. Мы выполняем все шаги умножения и деления перед шагами сложения и вычитания, а шаги умножения и деления выполняются слева направо. Кроме того, деление, которое мы используем, является делением с полом, так что 10 * 9 / 8 = 90 / 8 = 11. Учитывая целое число n, верните неуклюжий факториал n.

Пример:

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

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

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

2⃣Выполнение операций в цикле:
Создайте цикл, который будет обрабатывать числа от n до 1 в порядке убывания.
В цикле выполняйте операции *, /, +, и - последовательно.
Обновляйте текущий результат на каждом шаге в зависимости от остатка от деления текущего индекса на 4.

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

😎 Решение:

class Solution {
    function clumsy($n) {
        if ($n == 0) return 0;
        if ($n == 1) return 1;
        if ($n == 2) return 2 * 1;
        if ($n == 3) return 3 * 2 / 1;
        
        $res = $n * ($n - 1) / ($n - 2);
        $n -= 3;
        if ($n > 0) $res += $n--;
        
        while ($n > 0) {
            $res -= $n * ($n - 1) / ($n - 2);
            $n -= 3;
            if ($n > 0) $res += $n--;
        }
        
        return $res;
    }
}

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

Задача: 611. Valid Triangle Number
Сложность: medium

Если задан целочисленный массив nums, верните количество выбранных из массива троек, которые могут образовывать треугольники, если принять их за длины сторон треугольника.

Пример:

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

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

1⃣Отсортируйте массив nums.

2⃣Используйте три вложенных цикла: для каждого фиксированного третьего элемента, используйте два указателя для поиска подходящих первых двух элементов, которые удовлетворяют неравенству треугольника.

3⃣Увеличивайте счетчик на количество подходящих пар для каждого третьего элемента.

😎 Решение:

function triangleNumber($nums) {
    sort($nums);
    $n = count($nums);
    $count = 0;
    
    for ($k = $n - 1; $k >= 2; $k--) {
        $i = 0;
        $j = $k - 1;
        while ($i < $j) {
            if ($nums[$i] + $nums[$j] > $nums[$k]) {
                $count += $j - $i;
                $j--;
            } else {
                $i++;
            }
        }
    }
    
    return $count;
}

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

Задача: 261. Graph Valid Tree
Сложность: medium

У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.
Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

1⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    function validTree($n, $edges) {
        if (count($edges) != $n - 1) {
            return false;
        }
        
        $adjList = array_fill(0, $n, []);
        foreach ($edges as $edge) {
            $adjList[$edge[0]][] = $edge[1];
            $adjList[$edge[1]][] = $edge[0];
        }
        
        $parent = [0 => -1];
        $queue = [0];
        
        while (!empty($queue)) {
            $node = array_shift($queue);
            foreach ($adjList[$node] as $neighbor) {
                if ($neighbor == $parent[$node]) {
                    continue;
                }
                if (isset($parent[$neighbor])) {
                    return false;
                }
                $parent[$neighbor] = $node;
                $queue[] = $neighbor;
            }
        }
        
        return count($parent) == $n;
    }
}

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

Задача: 543. Diameter of Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.

Пример:

Input: root = [1,2]
Output: 1

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

1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.

2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.

3⃣Вызвать longestPath с root.

😎 Решение:

class Solution {
    private $diameter;
    
    function diameterOfBinaryTree($root) {
        $this->diameter = 0;
        $this->longestPath($root);
        return $this->diameter;
    }
    
    private function longestPath($node) {
        if ($node === null) return 0;
        
        $leftPath = $this->longestPath($node->left);
        $rightPath = $this->longestPath($node->right);
        
        $this->diameter = max($this->diameter, $leftPath + $rightPath);
        
        return max($leftPath, $rightPath) + 1;
    }
}

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

Задача: 628. Maximum Product of Three Numbers
Сложность: medium

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

Input: nums = [1,2,3]
Output: 6

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

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

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

😎 Решение:

function maximumProduct($nums) {
    sort($nums);
    $n = count($nums);
    $max1 = $nums[$n - 1] * $nums[$n - 2] * $nums[$n - 3];
    $max2 = $nums[0] * $nums[1] * $nums[$n - 1];
    return max($max1, $max2);
}

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

Задача: 1054. Distant Barcodes
Сложность: medium

На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.

Пример:

Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

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

1⃣Подсчитай частоту каждого штрих-кода.
Помести все штрих-коды в максимальную кучу на основе их частоты.

2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми.

3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.

😎 Решение:

function rearrangeBarcodes($barcodes) {
    $count = array_count_values($barcodes);
    $maxHeap = new SplPriorityQueue();
    foreach ($count as $barcode => $freq) {
        $maxHeap->insert($barcode, $freq);
    }

    $result = [];
    $prevFreq = 0;
    $prevBarcode = null;

    while (!$maxHeap->isEmpty()) {
        $barcode = $maxHeap->extract();
        $freq = $count[$barcode];
        $result[] = $barcode;
        if ($prevFreq > 0) {
            $maxHeap->insert($prevBarcode, $prevFreq);
        }
        $prevFreq = $freq - 1;
        $prevBarcode = $barcode;
    }

    return $result;
}

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

Задача: 143. Reorder List
Сложность: medium

Вам дана голова односвязного списка. Список можно представить в следующем виде:
L0 → L1 → … → Ln - 1 → Ln
Переупорядочите список так, чтобы он принял следующую форму:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы.

Пример:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

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

1⃣Нахождение середины списка и разделение его на две части:
Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине.
Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка.

2⃣Реверс второй половины списка:
Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка.
Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка.

3⃣Слияние двух частей списка в заданном порядке:
Начните с головы первой части списка (first) и головы реверсированной второй части (second).
Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки.
Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся.

😎 Решение:

function reorderList($head) {
    if ($head === null) return;
    $slow = $head;
    $fast = $head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    $prev = null;
    $curr = $slow;
    while ($curr !== null) {
        $tmp = $curr->next;
        $curr->next = $prev;
        $prev = $curr;
        $curr = $tmp;
    }
    $first = $head;
    $second = $prev;
    while ($second->next !== null) {
        $tmp = $first->next;
        $first->next = $second;
        $first = $tmp;
        $tmp = $second->next;
        $second->next = $first;
        $second = $tmp;
    }
}

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

Задача: 1102. Path With Maximum Minimum Value
Сложность: medium

Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.

Значение пути определяется минимальным числом на этом пути.

Пример:

Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. 

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

1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.

2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore:
Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore.
Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди.
Если успешно достигли правой нижней ячейки, значит путь существует.
Если очередь опустела до достижения правой нижней ячейки, пути не существует.

3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.

😎 Решение:

class Solution {
    private $dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]];

    function maximumMinimumPath($grid) {
        $R = count($grid);
        $C = count($grid[0]);
        $curScore = min($grid[0][0], $grid[$R - 1][$C - 1]);

        while ($curScore >= 0) {
            if ($this->pathExists($grid, $curScore)) {
                return $curScore;
            }
            $curScore--;
        }
        return -1;
    }

    private function pathExists($grid, $curScore) {
        $R = count($grid);
        $C = count($grid[0]);
        $visited = array_fill(0, $R, array_fill(0, $C, false));
        $dq = [[0, 0]];
        $visited[0][0] = true;

        while (!empty($dq)) {
            [$curRow, $curCol] = array_shift($dq);
            if ($curRow == $R - 1 && $curCol == $C - 1) {
                return true;
            }
            foreach ($this->dirs as $dir) {
                $newRow = $curRow + $dir[0];
                $newCol = $curCol + $dir[1];
                if ($newRow >= 0 && $newCol >= 0 && $newRow < $R && $newCol < $C && !$visited[$newRow][$newCol] && $grid[$newRow][$newCol] >= $curScore) {
                    $dq[] = [$newRow, $newCol];
                    $visited[$newRow][$newCol] = true;
                }
            }
        }
        return false;
    }
}

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

Задача: 398. Random Pick Index
Сложность: medium

Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.

Пример:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

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

1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.

2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.

3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.

😎 Решение:

class Solution {
    private $nums;

    function __construct($nums) {
        $this->nums = $nums;
    }

    function pick($target) {
        $count = 0;
        $result = -1;
        foreach ($this->nums as $i => $num) {
            if ($num == $target) {
                $count++;
                if (rand(1, $count) == $count) {
                    $result = $i;
                }
            }
        }
        return $result;
    }
}

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

Задача: 516. Longest Palindromic Subsequence
Сложность: medium

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

Пример:

Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте двумерный массив memo размером n на n, где memo[i][j] содержит длину самой длинной палиндромной подпоследовательности подстроки, сформированной от индекса i до j в s.

2⃣Верните lps(s, 0, n - 1, memo), где lps — это рекурсивный метод с четырьмя параметрами: s, начальный индекс подстроки как i, конечный индекс подстроки как j и memo. Если memo[i][j] != 0, это означает, что мы уже решили эту подзадачу, поэтому возвращаем memo[i][j]. Если i > j, строка пуста, возвращаем 0. Если i == j, это подстрока, содержащая один символ, возвращаем 1.

3⃣Если первый и последний символы совпадают, т.е. s[i] == s[j], включаем эти два символа в палиндромную подпоследовательность и добавляем её к самой длинной палиндромной подпоследовательности, сформированной с использованием подстроки от индекса i + 1 до j - 1. Выполняем memo[i][j] = lps(s, i + 1, j - 1, memo) + 2. Если первый и последний символы не совпадают, рекурсивно ищем самую длинную палиндромную подпоследовательность в обеих подстроках, сформированных после игнорирования первого и последнего символов. Выбираем максимум из этих двух и выполняем memo[i][j] = max(lps(s, i + 1, j, memo), lps(s, i, j - 1, memo)). Возвращаем memo[i][j].

😎 Решение:

class Solution {
    function longestPalindromeSubseq($s) {
        $n = strlen($s);
        $memo = [];
        
        function lps($s, $l, $r, &$memo) {
            $key = $l . "," . $r;
            if (isset($memo[$key])) return $memo[$key];
            if ($l > $r) return 0;
            if ($l == $r) return 1;
            
            if ($s[$l] == $s[$r]) {
                $memo[$key] = lps($s, $l + 1, $r - 1, $memo) + 2;
            } else {
                $memo[$key] = max(lps($s, $l, $r - 1, $memo), lps($s, $l + 1, $r, $memo));
            }
            return $memo[$key];
        }
        
        return lps($s, 0, $n - 1, $memo);
    }
}

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

Задача: 1530. Number of Good Leaf Nodes Pairs
Сложность: medium

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

Верните количество хороших пар листовых узлов в дереве.

Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

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

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

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

3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.

😎 Решение:

class Solution {
    function countPairs($root, $distance) {
        $graph = [];
        $leafNodes = new SplObjectStorage();
        $this->traverseTree($root, null, $graph, $leafNodes);
        $ans = 0;
        foreach ($leafNodes as $leaf) {
            $bfsQueue = new SplQueue();
            $seen = new SplObjectStorage();
            $bfsQueue->enqueue($leaf);
            $seen->attach($leaf);
            for ($i = 0; $i <= $distance; $i++) {
                $size = $bfsQueue->count();
                for ($j = 0; $j < $size; $j++) {
                    $currNode = $bfsQueue->dequeue();
                    if ($leafNodes->contains($currNode) && $currNode !== $leaf) {
                        $ans++;
                    }
                    if (isset($graph[spl_object_hash($currNode)])) {
                        foreach ($graph[spl_object_hash($currNode)] as $neighbor) {
                            if (!$seen->contains($neighbor)) {
                                $bfsQueue->enqueue($neighbor);
                                $seen->attach($neighbor);
                            }
                        }
                    }
                }
            }
        }
        return $ans / 2;
    }

    private function traverseTree($currNode, $prevNode, &$graph, $leafNodes) {
        if ($currNode === null) {
            return;
        }
        if ($currNode->left === null && $currNode->right === null) {
            $leafNodes->attach($currNode);
        }
        if ($prevNode !== null) {
            $graph[spl_object_hash($prevNode)][] = $currNode;
            $graph[spl_object_hash($currNode)][] = $prevNode;
        }
        $this->traverseTree($currNode->left, $currNode, $graph, $leafNodes);
        $this->traverseTree($currNode->right, $currNode, $graph, $leafNodes);
    }
}

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

Задача: 521. Longest Uncommon Subsequence I
Сложность: easy

Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности между a и b. Если такой несообщей подпоследовательности не существует, верните -1.
Несообщая подпоследовательность между двумя строками — это строка, которая является подпоследовательностью только одной из них.

Пример:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

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

1⃣Если строка a равна строке b, верните -1, так как не существует несообщей подпоследовательности.

2⃣В противном случае: Вычислите длины строк a и b. Верните длину более длинной строки.

3⃣Вернуть длину более длинной строки — она точно не может быть подпоследовательностью другой.

😎 Решение:

class Solution {
    function findLUSlength($a, $b) {
        if ($a == $b) {
            return -1;
        } else {
            return max(strlen($a), strlen($b));
        }
    }
}

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

Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium

Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.

Пример:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15

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

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

2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц.

😎 Решение:

function countSquares($matrix) {
    $m = count($matrix);
    $n = count($matrix[0]);
    $dp = array_fill(0, $m, array_fill(0, $n, 0));
    $count = 0;

    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($matrix[$i][$j] == 1) {
                if ($i == 0 || $j == 0) {
                    $dp[$i][$j] = 1;
                } else {
                    $dp[$i][$j] = min($dp[$i-1][$j], min($dp[$i][$j-1], $dp[$i-1][$j-1])) + 1;
                }
                $count += $dp[$i][$j];
            }
        }
    }

    return $count;
}

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

Задача: 1673. Find the Most Competitive Subsequence
Сложность: medium

Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k.

Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива.

Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.

Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

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

1⃣Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность.

2⃣Переберите массив nums, выбирая наиболее конкурентоспособные элементы и добавляя их в очередь. Сравнивайте последний элемент в очереди с текущим элементом, удаляя из очереди более крупные элементы, если можно удалить больше элементов, чем необходимо для достижения размера k.

3⃣В конце получите первые k элементов из очереди и создайте результирующий массив.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function mostCompetitive($nums, $k) {
        $queue = [];
        $additionalCount = count($nums) - $k;
        
        foreach ($nums as $num) {
            while (!empty($queue) && end($queue) > $num && $additionalCount > 0) {
                array_pop($queue);
                $additionalCount--;
            }
            $queue[] = $num;
        }
        
        return array_slice($queue, 0, $k);
    }
}

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

Задача: 523. Continuous Subarray Sum
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае.
Хороший подмассив — это подмассив, который:
имеет длину не менее двух, и
сумма элементов подмассива является кратной k.
Учтите:
Подмассив — это непрерывная часть массива.
Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k.

Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

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

1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod.

2⃣Итеративно пройдите по всем элементам массива nums.

3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false.

😎 Решение:

class Solution {
    function checkSubarraySum($nums, $k) {
        $prefixMod = 0;
        $modSeen = [0 => -1];
        
        for ($i = 0; $i < count($nums); $i++) {
            $prefixMod = ($prefixMod + $nums[$i]) % $k;
            
            if (array_key_exists($prefixMod, $modSeen)) {
                if ($i - $modSeen[$prefixMod] > 1) {
                    return true;
                }
            } else {
                $modSeen[$prefixMod] = $i;
            }
        }
        
        return false;
    }
}

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

Задача: 846. Hand of Straights
Сложность: medium

У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.

Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.

Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

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

1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.

2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.

3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $hand
     * @param Integer $groupSize
     * @return Boolean
     */
    function isNStraightHand($hand, $groupSize) {
        if (count($hand) % $groupSize != 0) {
            return false;
        }

        $cardCount = [];
        foreach ($hand as $card) {
            if (!isset($cardCount[$card])) {
                $cardCount[$card] = 0;
            }
            $cardCount[$card]++;
        }

        sort($hand);

        foreach ($hand as $card) {
            if ($cardCount[$card] == 0) {
                continue;
            }

            for ($nextCard = $card; $nextCard < $card + $groupSize; $nextCard++) {
                if (!isset($cardCount[$nextCard]) || $cardCount[$nextCard] == 0) {
                    return false;
                }
                $cardCount[$nextCard]--;
            }
        }

        return true;
    }
}

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

Задача: 279. Perfect Squares
Сложность: medium

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.
Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

class Solution {
    function numSquares($n) {
        $dp = array_fill(0, $n + 1, PHP_INT_MAX);
        $dp[0] = 0;
        
        $maxSquareIndex = floor(sqrt($n)) + 1;
        $squareNums = array_fill(0, $maxSquareIndex, 0);
        for ($i = 1; $i < $maxSquareIndex; ++$i) {
            $squareNums[$i] = $i * $i;
        }
        
        for ($i = 1; $i <= $n; ++$i) {
            for ($s = 1; $s < $maxSquareIndex; ++$s) {
                if ($i < $squareNums[$s]) break;
                $dp[$i] = min($dp[$i], $dp[$i - $squareNums[$s]] + 1);
            }
        }
        
        return $dp[$n];
    }
}

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