Задача: 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);
    }
}

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

Задача: 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);
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
}

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

Задача: 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);
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 1047. Remove All Adjacent Duplicates In String
Сложность: easy

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

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

1⃣Создай пустой стек для хранения символов строки.

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

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

😎 Решение:

function removeDuplicates($s) {
    $stack = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        if (!empty($stack) && end($stack) === $char) {
            array_pop($stack);
        } else {
            $stack[] = $char;
        }
    }
    return implode('', $stack);
}

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

Задача: 424. Longest Repeating Character Replacement
Сложность: medium

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

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

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.

😎 Решение:

class Solution {
    function characterReplacement
class Solution {
    function characterReplacement($s, $k) {
        $lo = 1;
        $hi = strlen($s) + 1;

        while ($lo + 1 < $hi) {
            $mid = $lo + intval(($hi - $lo) / 2);
            if ($this->canMakeValidSubstring($s, $mid, $k)) {
                $lo = $mid;
            } else {
                $hi = $mid;
            }
        }

        return $lo;
    }

    private function canMakeValidSubstring($s, $substringLength, $k) {
        $freqMap = array_fill(0, 26, 0);
        $maxFrequency = 0;
        $start = 0;

        for ($end = 0; $end < strlen($s); $end++) {
            $freqMap[ord($s[$end]) - ord('A')]++;

            if ($end + 1 - $start > $substringLength) {
                $freqMap[ord($s[$start]) - ord('A')]--;
                $start++;
            }

            $maxFrequency = max($maxFrequency, $freqMap[ord($s[$end]) - ord('A')]);
            if ($substringLength - $maxFrequency <= $k) {
                return true;
            }
        }

        return false;
    }
}

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

Задача: 495. Teemo Attacking
Сложность: easy

Наш герой Тимо атакует врага Эшу ядовитыми атаками! Когда Тимо атакует Эшу, она оказывается отравленной на ровно duration секунд. Более формально, атака в секунду t означает, что Эша будет отравлена в течение интервала времени [t, t + duration - 1] включительно. Если Тимо атакует снова до окончания эффекта яда, таймер для него сбрасывается, и эффект яда закончится через duration секунд после новой атаки.
Вам дано неубывающее целое число timeSeries, где timeSeries[i] обозначает, что Тимо атакует Эшу во вторую timeSeries[i], и целое число duration.
Верните общее количество секунд, в течение которых Эша была отравлена.

Пример:

Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

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

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

2⃣Итерация
Пройдите по всем элементам массива timeSeries, кроме последнего. На каждой итерации добавьте к total минимальное значение между длительностью интервала и временем действия яда duration.

3⃣Возврат результата
Верните сумму total и duration, чтобы учесть последнюю атаку.

😎 Решение:

class Solution {
    function findPoisonedDuration($timeSeries, $duration) {
        $n = count($timeSeries);
        if ($n == 0) return 0;

        $total = 0;
        for ($i = 0; $i < $n - 1; $i++) {
            $total += min($timeSeries[$i + 1] - $timeSeries[$i], $duration);
        }
        return $total + $duration;
    }
}

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

Задача: 227. Basic Calculator II
Сложность: medium

Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение.
Целочисленное деление должно округляться к нулю.
Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval().

Пример:

Input: s = "3+2*2"
Output: 7

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

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

2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации.

3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки.

😎 Решение:

class Solution {
    function calculate($s) {
        $length = strlen($s);
        if ($length == 0) return 0;
        $currentNumber = 0;
        $lastNumber = 0;
        $result = 0;
        $sign = '+';
        
        for ($i = 0; $i < $length; $i++) {
            $currentChar = $s[$i];
            if (ctype_digit($currentChar)) {
                $currentNumber = ($currentNumber * 10) + intval($currentChar);
            }
            if (!ctype_digit($currentChar) && !ctype_space($currentChar) || $i == $length - 1) {
                if ($sign == '+' || $sign == '-') {
                    $result += $lastNumber;
                    $lastNumber = ($sign == '+') ? $currentNumber : -$currentNumber;
                } else if ($sign == '*') {
                    $lastNumber *= $currentNumber;
                } else if ($sign == '/') {
                    $lastNumber /= $currentNumber;
                }
                $sign = $currentChar;
                $currentNumber = 0;
            }
        }
        $result += $lastNumber;
        return $result;  
    }
}

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

Задача: 924. Minimize Malware Spread
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.

2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.

😎 Решение:

function minMalwareSpread($graph, $initial) {
    function dfs($graph, $node, &$infected) {
        for ($neighbor = 0; $neighbor < count($graph); $neighbor++) {
            if ($graph[$node][$neighbor] == 1 && !in_array($neighbor, $infected)) {
                $infected[] = $neighbor;
                dfs($graph, $neighbor, $infected);
            }
        }
    }

    $n = count($graph);
    $initialSet = $initial;
    sort($initial);
    $minInfected = PHP_INT_MAX;
    $bestNode = $initial[0];
    
    foreach ($initial as $node) {
        $infected = $initialSet;
        $infected = array_diff($infected, [$node]);
        foreach ($initialSet as $i) {
            if ($i != $node) {
                dfs($graph, $i, $infected);
            }
        }
        if (count($infected) < $minInfected) {
            $minInfected = count($infected);
            $bestNode = $node;
        }
    }
    
    return $bestNode;
}

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

Задача: 1202. Smallest String With Swaps
Сложность: medium

Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.

Пример:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

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

1⃣Создание списка смежности:
Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source.

2⃣Обход графа и сбор индексов и символов:
Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:
- выполните DFS, если вершина еще не посещена (visited[vertex] = false).
- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

3⃣Сортировка и построение результирующей строки:
Отсортируйте списки indices и characters.
Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.
Верните smallestString.

😎 Решение:

class Solution {
    function smallestStringWithSwaps($s, $pairs) {
        $n = strlen($s);
        $adj = array_fill(0, $n, []);
        foreach ($pairs as $pair) {
            $adj[$pair[0]][] = $pair[1];
            $adj[$pair[1]][] = $pair[0];
        }

        $visited = array_fill(0, $n, false);
        $sArray = str_split($s);

        function dfs($node, &$adj, &$visited, &$sArray, &$indices, &$chars) {
            $visited[$node] = true;
            $indices[] = $node;
            $chars[] = $sArray[$node];
            foreach ($adj[$node] as $neighbor) {
                if (!$visited[$neighbor]) {
                    dfs($neighbor, $adj, $visited, $sArray, $indices, $chars);
                }
            }
        }

        for ($i = 0; $i < $n; $i++) {
            if (!$visited[$i]) {
                $indices = [];
                $chars = [];
                dfs($i, $adj, $visited, $sArray, $indices, $chars);
                sort($indices);
                sort($chars);
                for ($j = 0; $j < count($indices); $j++) {
                    $sArray[$indices[$j]] = $chars[$j];
                }
            }
        }

        return implode('', $sArray);
    }
}

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