PHP | LeetCode

Задача: 202. Happy Number Сложность: easy Напишите алгоритм для определения, является ли число n счастливым Счастливое число определяется следующим процессом: Начиная с любого положительного целого числа, замените число суммой квадратов его цифр. Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1. Те числа, для которых этот процесс завершается 1, являются счастливыми. Верните true, если n является счастливым числом, и false, если нет. Пример:

Input: n = 2
Output: false

👨‍💻 Алгоритм: 1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач. 2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet. 3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач. 😎 Решение:

function getNext($n) {
    $totalSum = 0;
    while ($n > 0) {
        $digit = $n % 10;
        $n = floor($n / 10);
        $totalSum += $digit * $digit;
    }
    return $totalSum;
}

function isHappy($n) {
    $seen = [];
    while ($n != 1 && !in_array($n, $seen)) {
        $seen[] = $n;
        $n = getNext($n);
    }
    return $n == 1;
}
echo isHappy(19) ? "true" : "false";

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

🐍💩👩‍💻👩‍💻🧑‍💻🧑‍💻🐧👩‍💻🧑‍💻👩‍💻👩‍💻 В сети начали массово сливать курсы и книги известных онлайн школ по айти Вот отсортированная база с тонной материала (постепенно пополняется): (363 видео, 87 книги) — Python (415 видео, 68 книги) — Frontend (143 видео, 33 книги) — ИБ/Хакинг (352 видео, 89 книги) — С/С++/C# (343 видео, 87 книги) — Java/QA (176 видео, 32 книги) — Git/Linux (174 видео, 91 книги) — DevOps (167 видео, 53 книги) — PHP/1С (227 видео, 83 книги) — SQL/БД (114 видео, 77 книги) — Сисадмин (107 видео, 43 книги) — BA/SA (181 видео, 32 книги) — Go/Rust (167 видео, 43 книги) — Kotlin/Swift (112 видео, 24 книги) — Flutter (137 видео, 93 книги) — DS/ML (113 видео, 82 книги) — GameDev (183 видео, 37 книги) — Дизайн (136 видео, 33 книги) — PM/HR Скачивать ничего не нужно — все выложили в Telegram

Задача: 213. House Robber II Сложность: medium Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь. Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию. Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

👨‍💻 Алгоритм: 1⃣Обработка базовых случаев: Если массив nums пуст, возвращаем 0. Если в массиве nums только один дом, возвращаем значение этого дома. 2⃣Разделение задачи на две подзадачи: Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и count($nums) - 2. Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и count($nums) - 1. 3⃣Сравнение результатов и возврат максимального значения: Вернуть максимальное значение из двух полученных результатов. 😎 Решение:

class Solution {
    public function rob($nums) {
        if (count($nums) == 0) return 0;
        if (count($nums) == 1) return $nums[0];

        $max1 = $this->rob_simple($nums, 0, count($nums) - 2);
        $max2 = $this->rob_simple($nums, 1, count($nums) - 1);

        return max($max1, $max2);
    }

    private function rob_simple($nums, $start, $end) {
        $t1 = 0;
        $t2 = 0;

        for ($i = $start; $i <= $end; $i++) {
            $temp = $t1;
            $current = $nums[$i];
            $t1 = max($current + $t2, $t1);
            $t2 = $temp;
        }

        return $t1;
    }
}

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

Задача: 739. Daily Temperatures Сложность: medium Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0. Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

👨‍💻 Алгоритм: 1⃣Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день. 2⃣Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек. 3⃣Возвращайте массив ответов. 😎 Решение:

function dailyTemperatures($T) {
    $n = count($T);
    $answer = array_fill(0, $n, 0);
    $stack = [];
    
    for ($i = 0; $i < $n; $i++) {
        while (!empty($stack) && $T[$i] > $T[end($stack)]) {
            $j = array_pop($stack);
            $answer[$j] = $i - $j;
        }
        $stack[] = $i;
    }
    
    return $answer;
}

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

Задача: 774. Minimize Max Distance to Gas Station Сложность: hard Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k. Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию. Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций. Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

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

👨‍💻 Алгоритм: 1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x. 2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов. 3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций. 😎 Решение:

class Solution {
    function minmaxGasDist($stations, $K) {
        $N = count($stations);
        $deltas = array_fill(0, $N-1, 0);
        for ($i = 0; $i < $N-1; ++$i)
            $deltas[$i] = $stations[$i+1] - $stations[$i];

        $dp = array_fill(0, $N-1, array_fill(0, $K+1, 0));
        for ($i = 0; $i <= $K; ++$i)
            $dp[0][$i] = $deltas[0] / ($i+1);

        for ($p = 1; $p < $N-1; ++$p)
            for ($k = 0; $k <= $K; ++$k) {
                $bns = 999999999;
                for ($x = 0; $x <= $k; ++$x)
                    $bns = min($bns, max($deltas[$p] / ($x+1), $dp[$p-1][$k-$x]));
                $dp[$p][$k] = $bns;
            }

        return $dp[$N-2][$K];
    }
}

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

Задача: 465. Optimal Account Balancing Сложность: medium Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi. Верните минимальное количество транзакций, необходимых для урегулирования долгов. Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

👨‍💻 Алгоритм: 1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека. 2⃣Собрать все ненулевые чистые балансы в массив balance_list. 3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]: Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1. Если cur = n, вернуть 0. В противном случае установить cost на большое значение, например, inf. Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0, Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur]. Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1). Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат). Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации. Вернуть cost, когда итерация завершена. Вернуть dfs(0). 😎 Решение:

class Solution {
    private $creditList;
    
    function minTransfers($transactions) {
        $creditMap = [];
        foreach ($transactions as $t) {
            if (!isset($creditMap[$t[0]])) $creditMap[$t[0]] = 0;
            if (!isset($creditMap[$t[1]])) $creditMap[$t[1]] = 0;
            $creditMap[$t[0]] += $t[2];
            $creditMap[$t[1]] -= $t[2];
        }
        
        $this->creditList = [];
        foreach ($creditMap as $amount) {
            if ($amount != 0) {
                $this->creditList[] = $amount;
            }
        }
        
        $n = count($this->creditList);
        return $this->dfs(0, $n);
    }
    
    private function dfs($cur, $n) {
        while ($cur < $n && $this->creditList[$cur] == 0) {
            $cur++;
        }
    
        if ($cur == $n) {
            return 0;
        }
        
        $cost = PHP_INT_MAX;
        for ($nxt = $cur + 1; $nxt < $n; $nxt++) {
            if ($this->creditList[$nxt] * $this->creditList[$cur] < 0) {
                $this->creditList[$nxt] += $this->creditList[$cur];
                $cost = min($cost, 1 + $this->dfs($cur + 1, $n));
                $this->creditList[$nxt] -= $this->creditList[$cur];
            }
        }
        
        return $cost;
    }
}

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

Задача: 423. Reconstruct Original Digits from English Сложность: medium Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания. Пример:

Input: s = "owoztneoer"
Output: "012"

👨‍💻 Алгоритм: 1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа. 2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры. 3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат. 😎 Решение:

class Solution {
    function originalDigits($s) {
        $count = array_fill(0, 26, 0);
        foreach (str_split($s) as $letter) {
            $count[ord($letter) - ord('a')]++;
        }

        $out = array_fill(0, 10, 0);
        $out[0] = $count[ord('z') - ord('a')];
        $out[2] = $count[ord('w') - ord('a')];
        $out[4] = $count[ord('u') - ord('a')];
        $out[6] = $count[ord('x') - ord('a')];
        $out[8] = $count[ord('g') - ord('a')];
        $out[3] = $count[ord('h') - ord('a')] - $out[8];
        $out[5] = $count[ord('f') - ord('a')] - $out[4];
        $out[7] = $count[ord('s') - ord('a')] - $out[6];
        $out[9] = $count[ord('i') - ord('a')] - $out[5] - $out[6] - $out[8];
        $out[1] = $count[ord('n') - ord('a')] - $out[7] - 2 * $out[9];

        $output = '';
        for ($i = 0; $i < 10; $i++) {
            for ($j = 0; $j < $out[$i]; $j++) {
                $output .= $i;
            }
        }
        return $output;
    }
}

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

Задача: 1512. Number of Good Pairs Сложность: easy Дан массив целых чисел nums, верните количество хороших пар. Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j. Пример:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ans значением 0. 2⃣Итерируйте i от 0 до nums.length: Итерируйте j от i + 1 до nums.length: Если nums[i] == nums[j], увеличьте ans на 1. 3⃣Верните ans. 😎 Решение:

class Solution {
    function numIdenticalPairs($nums) {
        $ans = 0;
        for ($i = 0; $i < count($nums); $i++) {
            for ($j = $i + 1; $j < count($nums); $j++) {
                if ($nums[$i] == $nums[$j]) {
                    $ans++;
                }
            }
        }
        return $ans;
    }
}

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

Задача: 101. Symmetric Tree Сложность: easy Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра). Пример:

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

👨‍💻 Алгоритм: 1⃣Дерево симметрично, если левое поддерево является зеркальным отражением правого поддерева. 2⃣Два дерева являются зеркальным отражением друг друга, если: Их корни имеют одинаковое значение. Правое поддерево каждого дерева является зеркальным отражением левого поддерева другого дерева. 3⃣Это похоже на человека, смотрящего в зеркало. Отражение в зеркале имеет ту же голову, но правая рука отражения соответствует левой руке настоящего человека и наоборот. Вышеописанное объяснение естественным образом превращается в рекурсивную функцию. 😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

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

class Solution {
    function isSymmetric($root) {
        return $this->isMirror($root, $root);
    }

    function isMirror($t1, $t2) {
        if ($t1 === null && $t2 === null) {
            return true;
        }
        if ($t1 === null || $t2 === null) {
            return false;
        }
        return ($t1->val == $t2->val) && $this->isMirror($t1->right, $t2->left) && $this->isMirror($t1->left, $t2->right);
    }
}

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

Задача: 731. My Calendar II Сложность: medium Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь. Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

👨‍💻 Алгоритм: 1⃣Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей. 2⃣При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями. 3⃣Если пересечение не обнаружено, добавьте новое событие и обновите список пересечений при необходимости. 😎 Решение:

class MyCalendarTwo {
    private $events;
    private $overlaps;

    function __construct() {
        $this->events = [];
        $this->overlaps = [];
    }

    function book($start, $end) {
        foreach ($this->overlaps as $overlap) {
            if ($start < $overlap[1] && $end > $overlap[0]) {
                return false;
            }
        }
        foreach ($this->events as $event) {
            if ($start < $event[1] && $end > $event[0]) {
                $this->overlaps[] = [max($start, $event[0]), min($end, $event[1])];
            }
        }
        $this->events[] = [$start, $end];
        return true;
    }
}

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

Задача: 965. Univalued Binary Tree Сложность: medium Дан список слов, и нам нужно реализовать проверку орфографии, которая преобразует слово запроса в правильное слово. Для данного слова запроса, проверка орфографии обрабатывает две категории ошибок правописания: Заглавные буквы: если запрос совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и в списке слов. Пример: wordlist = ["yellow"], query = "YellOw": correct = "yellow" Пример: wordlist = ["Yellow"], query = "yellow": correct = "Yellow" Пример: wordlist = ["yellow"], query = "yellow": correct = "yellow" Ошибки гласных: если после замены гласных ('a', 'e', 'i', 'o', 'u') в слове запроса на любую гласную по отдельности оно совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и совпадающее слово в списке слов. Пример: wordlist = ["YellOw"], query = "yollow": correct = "YellOw" Пример: wordlist = ["YellOw"], query = "yeellow": correct = "" (нет совпадения) Пример: wordlist = ["YellOw"], query = "yllw": correct = "" (нет совпадения) Кроме того, проверка орфографии работает по следующим правилам приоритета: Когда запрос точно совпадает со словом в списке слов (с учетом регистра), вы должны вернуть это же слово. Когда запрос совпадает со словом за исключением регистра, вы должны вернуть первое такое совпадение в списке слов. Когда запрос совпадает со словом за исключением ошибок гласных, вы должны вернуть первое такое совпадение в списке слов. Если запрос не имеет совпадений в списке слов, вы должны вернуть пустую строку. Дан массив запросов, верните список слов answer, где answer[i] — правильное слово для query = queries[i]. Пример:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

👨‍💻 Алгоритм: 1⃣Используйте множество для хранения слов из списка, чтобы проверять точные совпадения. 2⃣Используйте хэш-таблицу для хранения слов в нижнем регистре и соответствующих слов из списка для проверки совпадений без учета регистра. 3⃣Используйте хэш-таблицу для хранения слов в нижнем регистре с замененными гласными символами и соответствующих слов из списка для проверки совпадений с ошибками гласных. 😎 Решение:

class Solution {
    private $wordsPerfect;
    private $wordsCap;
    private $wordsVow;

    /**
     * @param String[] $wordlist
     * @param String[] $queries
     * @return String[]
     */
    function spellchecker($wordlist, $queries) {
        $this->wordsPerfect = array_flip($wordlist);
        $this->wordsCap = [];
        $this->wordsVow = [];

        foreach ($wordlist as $word) {
            $wordlow = strtolower($word);
            if (!isset($this->wordsCap[$wordlow])) {
                $this->wordsCap[$wordlow] = $word;
            }

            $wordlowDV = $this->devowel($wordlow);
            if (!isset($this->wordsVow[$wordlowDV])) {
                $this->wordsVow[$wordlowDV] = $word;
            }
        }

        $result = [];
        foreach ($queries as $query) {
            $result[] = $this->solve($query);
        }
        return $result;
    }

    private function solve($query) {
        if (isset($this->wordsPerfect[$query])) {
            return $query;
        }

        $queryL = strtolower($query);
        if (isset($this->wordsCap[$queryL])) {
            return $this->wordsCap[$queryL];
        }

        $queryLV = $this->devowel($queryL);
        if (isset($this->wordsVow[$queryLV])) {
            return $this->wordsVow[$queryLV];
        }

        return "";
    }

    private function devowel($word) {
        return preg_replace('/[aeiou]/', '*', $word);
    }
}

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

Задача: 487. Max Consecutive Ones II Сложность: medium Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля. Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

👨‍💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:

class Solution {
    function findMaxConsecutiveOnes($nums) {
        $longestSequence = 0;
        for ($left = 0; $left < count($nums); $left++) {
            $numZeroes = 0;
            for ($right = $left; $right < count($nums); $right++) {
                if ($nums[$right] == 0) {
                    $numZeroes++;
                }
                if ($numZeroes <= 1) {
                    $longestSequence = max($longestSequence, $right - $left + 1);
                }
            }
        }
        return $longestSequence;
    }
}

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

Задача: 1074. Number of Submatrices That Sum to Target Сложность: hard Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению. Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2. Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'. Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

👨‍💻 Алгоритм: 1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений. 2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target. 3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count. 😎 Решение:

class Solution {
    function numSubmatrixSumTarget($matrix, $target) {
        $r = count($matrix);
        $c = count($matrix[0]);
        $ps = array_fill(0, $r + 1, array_fill(0, $c + 1, 0));
        
        for ($i = 1; $i <= $r; ++$i) {
            for ($j = 1; $j <= $c; ++$j) {
                $ps[$i][$j] = $ps[$i - 1][$j] + $ps[$i][$j - 1] - $ps[$i - 1][$j - 1] + $matrix[$i - 1][$j - 1];
            }
        }
        
        $count = 0;
        
        for ($r1 = 1; $r1 <= $r; ++$r1) {
            for ($r2 = $r1; $r2 <= $r; ++$r2) {
                $h = array();
                $h[0] = 1;
                for ($col = 1; $col <= $c; ++$col) {
                    $currSum = $ps[$r2][$col] - $ps[$r1 - 1][$col];
                    if (isset($h[$currSum - $target])) {
                        $count += $h[$currSum - $target];
                    }
                    if (isset($h[$currSum])) {
                        $h[$currSum]++;
                    } else {
                        $h[$currSum] = 1;
                    }
                }
            }
        }
        
        return $count;
    }
}

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

Задача: 148. Sort List Сложность: Medium Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания. Пример:

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

👨‍💻 Алгоритм: 1⃣Разделение списка (Фаза разделения): Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка. 2⃣Сортировка подсписков и их объединение (Фаза слияния): Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков. 3⃣Иллюстрация процесса сортировки: Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список. 😎 Решение:

class ListNode {
    public $val;
    public $next;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {
    public function sortList($head) {
        if ($head === null || $head->next === null) {
            return $head;
        }
        $mid = $this->getMid($head);
        $left = $this->sortList($head);
        $right = $this->sortList($mid);
        return $this->merge($left, $right);
    }

    private function merge($list1, $list2) {
        $dummyHead = new ListNode();
        $tail = $dummyHead;
        while ($list1 !== null && $list2 !== null) {
            if ($list1->val < $list2->val) {
                $tail->next = $list1;
                $list1 = $list1->next;
            } else {
                $tail->next = $list2;
                $list2 = $list2->next;
            }
            $tail = $tail->next;
        }
        $tail->next = $list1 ?? $list2;
        return $dummyHead->next;
    }

    private function getMid($head) {
        $midPrev = null;
        $slow = $head;
        $fast = $head;
        while ($fast !== null && $fast->next !== null) {
            $midPrev = ($midPrev === null) ? $slow : $midPrev->next;
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        $mid = $midPrev->next;
        $midPrev->next = null;
        return $mid;
    }
}

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

Задача: 366. Find Leaves of Binary Tree Сложность: medium Дан корень бинарного дерева, соберите узлы дерева следующим образом: Соберите все листовые узлы. Удалите все листовые узлы. Повторяйте, пока дерево не станет пустым. Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

👨‍💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1. 2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте. 3⃣Организовать узлы по высоте и вернуть результат. 😎 Решение:

class Solution {
    private $pairs = [];

    private function getHeight($node) {
        if ($node === null) return -1;
        $leftHeight = $this->getHeight($node->left);
        $rightHeight = $this->getHeight($node->right);
        $currHeight = max($leftHeight, $rightHeight) + 1;
        $this->pairs[] = [$currHeight, $node->val];
        return $currHeight;
    }

    public function findLeaves($root) {
        $this->getHeight($root);
        usort($this->pairs, function($a, $b) {
            return $a[0] <=> $b[0];
        });
        $solution = [];
        $currentHeight = -1;
        foreach ($this->pairs as $pair) {
            if ($pair[0] !== $currentHeight) {
                $solution[] = [];
                $currentHeight = $pair[0];
            }
            $solution[count($solution) - 1][] = $pair[1];
        }
        return $solution;
    }
}

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

Задача: 908. Smallest Range I Сложность: easy Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем. Пример:

Input: nums = [1], k = 0
Output: 0

👨‍💻 Алгоритм: 1⃣Найти минимальное и максимальное значения массива nums. 2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции. 3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями. 😎 Решение:

function smallestRangeI($nums, $k) {
    $minVal = min($nums);
    $maxVal = max($nums);
    return max(0, ($maxVal - $k) - ($minVal + $k));
}

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

Задача: 358. Rearrange String k Distance Apart Сложность: hard Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "". Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

👨‍💻 Алгоритм: 1⃣Создайте словарь частот для символов строки и определите максимальную частоту. 2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов. 3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку. 😎 Решение:

class Solution {
    function rearrangeString($s, $k) {
        $freqs = [];
        $maxFreq = 0;

        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if (!isset($freqs[$char])) {
                $freqs[$char] = 0;
            }
            $freqs[$char]++;
            $maxFreq = max($maxFreq, $freqs[$char]);
        }

        $mostChars = [];
        $secondChars = [];

        foreach ($freqs as $char => $freq) {
            if ($freq == $maxFreq) {
                $mostChars[] = $char;
            } else if ($freq == $maxFreq - 1) {
                $secondChars[] = $char;
            }
        }

        $segments = array_fill(0, $maxFreq, "");

        for ($i = 0; $i < $maxFreq; $i++) {
            foreach ($mostChars as $char) {
                $segments[$i] .= $char;
            }
            if ($i < $maxFreq - 1) {
                foreach ($secondChars as $char) {
                    $segments[$i] .= $char;
                }
            }
        }

        $segmentId = 0;

        foreach ($freqs as $char => $freq) {
            if (in_array($char, $mostChars) || in_array($char, $secondChars)) {
                continue;
            }

            for ($j = 0; $j < $freq; $j++) {
                $segments[$segmentId] .= $char;
                $segmentId = ($segmentId + 1) % ($maxFreq - 1);
            }
        }

        for ($i = 0; $i < $maxFreq - 1; $i++) {
            if (strlen($segments[$i]) < $k) {
                return "";
            }
        }

        return implode("", $segments);
    }
}

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

Задача: 1044. Longest Duplicate Substring Сложность: hard Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "". Пример:

Input: s = "banana"
Output: "ana"

👨‍💻 Алгоритм: 1⃣Использование двоичного поиска для определения длины дублированной подстроки: Двоичный поиск используется для поиска максимальной длины дублированной подстроки. 2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины: Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок. 3⃣Хеширование с помощью функции rolling hash: Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов. 😎 Решение:

function longestDupSubstring($s) {
    function search($s, $length) {
        $seen = [];
        for ($i = 0; $i <= strlen($s) - $length; $i++) {
            $sub = substr($s, $i, $length);
            if (isset($seen[$sub])) {
                return $sub;
            }
            $seen[$sub] = true;
        }
        return "";
    }

    $left = 1;
    $right = strlen($s);
    $result = "";
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        $dup = search($s, $mid);
        if ($dup !== "") {
            $result = $dup;
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }
    return $result;
}

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

Задача: 189. Rotate Array Сложность: medium Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число. Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

👨‍💻 Алгоритм: 1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива. 2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов. 3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива. 😎 Решение:

class Solution {
    function rotate(&$nums, $k) {
        $n = count($nums);
        $a = array_fill(0, $n, 0);
        for ($i = 0; $i < $n; $i++) {
            $a[($i + $k) % $n] = $nums[$i];
        }
        for ($i = 0; $i < $n; $i++) {
            $nums[$i] = $a[$i];
        }
    }
}

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

Задача: 538. Convert BST to Greater Tree Сложность: medium Дано корень бинарного дерева поиска (BST), преобразуйте его в дерево, в котором каждый ключ исходного BST изменен на исходный ключ плюс сумму всех ключей, больших исходного ключа в BST. Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям: Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла. Правое поддерево узла содержит только узлы с ключами, большими ключа узла. И левое, и правое поддеревья также должны быть бинарными деревьями поиска. Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

👨‍💻 Алгоритм: 1⃣Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево. 2⃣Посещаем текущий узел, обновляем его значение и общую сумму. 3⃣Рекурсивно обрабатываем левое поддерево. 😎 Решение:

class Solution {
    private $sum = 0;

    public function convertBST($root) {
        if ($root !== null) {
            $this->convertBST($root->right);
            $this->sum += $root->val;
            $root->val = $this->sum;
            $this->convertBST($root->left);
        }
        return $root;
    }
}

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