Задача: 1539. Kth Missing Positive Number
Сложность: easy

Дан массив arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение:

class Solution {
    function findKthPositive($arr, $k) {
        if ($k <= $arr[0] - 1) {
            return $k;
        }
        $k -= $arr[0] - 1;
        $n = count($arr);
        for ($i = 0; $i < $n - 1; ++$i) {
            $currMissing = $arr[$i + 1] - $arr[$i] - 1;
            if ($k <= $currMissing) {
                return $arr[$i] + $k;
            }
            $k -= $currMissing;
        }
        return $arr[$n - 1] + $k;
    }
}

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

Задача: 758. Bold Words in String
Сложность: medium

При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом.
Возвращает после добавления тегов, выделенных жирным шрифтом. Возвращаемая строка должна содержать как можно меньшее количество тегов, и теги должны образовывать допустимую комбинацию.

Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

1⃣Создайте массив для хранения флагов, указывающих, какие символы в строке a должны быть выделены жирным шрифтом.

2⃣Пройдите по каждому ключевому слову и отметьте соответствующие позиции в массиве флагов.

3⃣Постройте результирующую строку, добавляя теги <b> и </b> на основе массива флагов.

😎 Решение:

function addBoldTags($keywords, $s) {
    $n = strlen($s);
    $bold = array_fill(0, $n, false);
    
    foreach ($keywords as $word) {
        $start = strpos($s, $word);
        while ($start !== false) {
            for ($i = $start; $i < $start + strlen($word); $i++) {
                $bold[$i] = true;
            }
            $start = strpos($s, $word, $start + 1);
        }
    }
    
    $result = '';
    $i = 0;
    while ($i < $n) {
        if ($bold[$i]) {
            $result .= '<b>';
            while ($i < $n && $bold[$i]) {
                $result .= $s[$i];
                $i++;
            }
            $result .= '</b>';
        } else {
            $result .= $s[$i];
            $i++;
        }
    }
    
    return $result;
}

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

Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

class Solution {
    function isSubsequence($x, $y) {
        $j = 0;
        for ($i = 0; $i < strlen($y) && $j < strlen($x); $i++) {
            if ($x[$j] == $y[$i]) {
                $j++;
            }
        }
        return $j == strlen($x);
    }

    function findLongestWord($s, $d) {
        $max_str = "";
        foreach ($d as $str) {
            if ($this->isSubsequence($str, $s)) {
                if (strlen($str) > strlen($max_str) || (strlen($str) == strlen($max_str) && strcmp($str, $max_str) < 0)) {
                    $max_str = $str;
                }
            }
        }
        return $max_str;
    }
}

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

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

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

Задача: 127. Word Ladder
Сложность: Hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:
Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

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

1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

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

3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

function ladderLength($beginWord, $endWord, $wordList) {
    $L = strlen($beginWord);
    $allComboDict = [];
    foreach ($wordList as $word) {
        for ($i = 0; $i < $L; $i++) {
            $newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
            if (!isset($allComboDict[$newWord])) {
                $allComboDict[$newWord] = [];
            }
            $allComboDict[$newWord][] = $word;
        }
    }

    $queue = [[$beginWord, 1]];
    $visited = [$beginWord => true];
    while (count($queue) > 0) {
        $node = array_shift($queue);
        $word = $node[0];
        $level = $node[1];
        for ($i = 0; $i < $L; $i++) {
            $newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
            if (!isset($allComboDict[$newWord])) {
                $allComboDict[$newWord] = [];
            }
            foreach ($allComboDict[$newWord] as $adjacentWord) {
                if ($adjacentWord === $endWord) {
                    return $level + 1;
                }
                if (!isset($visited[$adjacentWord])) {
                    $visited[$adjacentWord] = true;
                    $queue[] = [$adjacentWord, $level + 1];
                }
            }
        }
    }

    return 0;
}

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

Задача: 320. Generalized Abbreviation
Сложность: medium

Обобщённая аббревиатура слова может быть построена путём замены несмежных и неперекрывающихся подстрок на их длины.
Например, для слова "abcde" возможны сокращения:
"a3e" — "bcd" заменено на "3"
"1bcd1" — "a" и "e" заменены на "1"
"5" — всё слово заменено на длину
"abcde" — без сокращений
Недопустимы:
"23" — замены "ab" и "cde" смежны
"22de" — замены "ab" и "bc" перекрываются
Нужно вернуть все возможные обобщённые аббревиатуры слова word.

Пример:

Input: word = "a"
Output: ["1","a"]

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

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

class Solution {
    function generateAbbreviations($word) {
        $result = [];
        $n = strlen($word);
        
        for ($x = 0; $x < (1 << $n); $x++) {
            $result[] = $this->abbr($word, $x);
        }
        
        return $result;
    }

    private function abbr($word, $x) {
        $builder = "";
        $k = 0;
        $n = strlen($word);
        
        for ($i = 0; $i < $n; $i++, $x >>= 1) {
            if (($x & 1) == 0) {
                if ($k != 0) {
                    $builder .= $k;
                    $k = 0;
                }
                $builder .= $word[$i];
            } else {
                $k++;
            }
        }
        
        if ($k != 0) $builder .= $k;
        return $builder;
    }
}

$sol = new Solution();
print_r($sol->generateAbbreviations("word"));

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

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

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

😎 Решение:

class Solution {
    function maxScoreSightseeingPair($values) {
        $maxScore = 0;
        $maxIPlusValue = $values[0];
        
        for ($j = 1; $j < count($values); $j++) {
            $maxScore = max($maxScore, $maxIPlusValue + $values[$j] - $j);
            $maxIPlusValue = max($maxIPlusValue, $values[$j] + $j);
        }
        
        return $maxScore;
    }
}

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

Задача: 940. Distinct Subsequences II4
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет.

Пример:

Input: s = "abc"
Output: 7

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

1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j.

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

3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7.

😎 Решение:

function countSubsequences($s) {
    $MOD = 1000000007;
    $dp = array_fill(0, 26, 0);
    foreach (str_split($s) as $c) {
        $index = ord($c) - ord('a');
        $dp[$index] = (array_sum($dp) + 1) % $MOD;
    }
    return array_sum($dp) % $MOD;
}

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

Задача: 834. Sum of Distances in Tree
Сложность: hard

Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.

Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.

Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.

Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

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

2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева.

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

😎 Решение:

class Solution {
    private $ans;
    private $count;
    private $graph;
    private $N;

    function sumOfDistancesInTree($N, $edges) {
        $this->N = $N;
        $this->graph = array_fill(0, $N, []);
        $this->ans = array_fill(0, $N, 0);
        $this->count = array_fill(0, $N, 1);

        foreach ($edges as $edge) {
            $this->graph[$edge[0]][] = $edge[1];
            $this->graph[$edge[1]][] = $edge[0];
        }

        $this->dfs(0, -1);
        $this->dfs2(0, -1);
        return $this->ans;
    }

    function dfs($node, $parent) {
        foreach ($this->graph[$node] as $child) {
            if ($child != $parent) {
                $this->dfs($child, $node);
                $this->count[$node] += $this->count[$child];
                $this->ans[$node] += $this->ans[$child] + $this->count[$child];
            }
        }
    }

    function dfs2($node, $parent) {
        foreach ($this->graph[$node] as $child) {
            if ($child != $parent) {
                $this->ans[$child] = $this->ans[$node] - $this->count[$child] + $this->N - $this->count[$child];
                $this->dfs2($child, $node);
            }
        }
    }
}

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

Задача: 268. Missing Number
Сложность: easy

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

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

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

3⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число.

😎 Решение:

class Solution {
    function missingNumber($nums) {
        sort($nums);
        if ($nums[count($nums) - 1] != count($nums)) {
            return count($nums);
        } else if ($nums[0] != 0) {
            return 0;
        }
        for ($i = 1; $i < count($nums); $i++) {
            $expectedNum = $nums[$i - 1] + 1;
            if ($nums[$i] != $expectedNum) {
                return $expectedNum;
            }
        }
        return -1;
    }
}

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

Задача: 1029. Two City Scheduling
Сложность: medium

Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.

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

3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.

😎 Решение:

class Solution {
    function twoCitySchedCost($costs) {
        usort($costs, function($a, $b) {
            return ($a[0] - $a[1]) - ($b[0] - $b[1]);
        });
        $totalCost = 0;
        $n = count($costs) / 2;
        for ($i = 0; $i < $n; $i++) {
            $totalCost += $costs[$i][0];
            $totalCost += $costs[$i + $n][1];
        }
        return $totalCost;
    }
}

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

Задача: 664. Strange Printer
Сложность: hard

Существует странный принтер с двумя особыми свойствами:

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

Пример:

Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

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

1⃣Инициализация и подсчет:
Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1].

2⃣Динамическое программирование:
Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим.
В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов.


3⃣Возврат результата:
Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки.

😎 Решение:

class Solution {
    function strangePrinter($s) {
        $n = strlen($s);
        $dp = array_fill(0, $n, array_fill(0, $n, 0));
        
        for ($length = 1; $length <= $n; $length++) {
            for ($i = 0; $i <= $n - $length; $i++) {
                $j = $i + $length - 1;
                $dp[$i][$j] = ($i === $j) ? 1 : $dp[$i][$j - 1] + 1;
                for ($k = $i; $k < $j; $k++) {
                    if ($s[$k] === $s[$j]) {
                        $dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + ($k + 1 <= $j - 1 ? $dp[$k + 1][$j - 1] : 0));
                    }
                }
            }
        }
        return $dp[0][$n - 1];
    }
}

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

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

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

Задача: 421. Maximum XOR of Two Numbers in an Array
Сложность: medium

Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.

Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

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

1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0.

2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0):
Сдвигайте max_xor влево, чтобы освободить следующий бит.
Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы.

3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums:
Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i.
Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите.

😎 Решение:

class Solution {
    function findMaximumXOR($nums) {
        $maxNum = $nums[0];
        foreach ($nums as $num) {
            if ($num > $maxNum) {
                $maxNum = $num;
            }
        }
        $L = strlen(decbin($maxNum));

        $maxXor = 0;
        for ($i = $L - 1; $i >= 0; $i--) {
            $maxXor <<= 1;
            $currXor = $maxXor | 1;
            $prefixes = [];
            foreach ($nums as $num) {
                $prefixes[$num >> $i] = true;
            }
            foreach ($prefixes as $p => $true) {
                if (isset($prefixes[$currXor ^ $p])) {
                    $maxXor = $currXor;
                    break;
                }
            }
        }
        return $maxXor;
    }
}
?>

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

Задача: 988. Smallest String Starting From Leaf
Сложность: medium

Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.

Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.

Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.

Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.

Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

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

1⃣Инициализация и подготовка:
Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк).
Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы.

2⃣Обход дерева:
Если текущий узел пуст (null), просто вернитесь из функции.
Добавьте текущий символ (соответствующий значению узла) в начало строки пути.
Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше.
Рекурсивно вызовите dfs для левого и правого потомков текущего узла.

3⃣Возврат результата:
Вызовите функцию dfs с корневым узлом и пустым путем.
Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня.

😎 Решение:

class Solution {
    private $ans = "~";

    function smallestFromLeaf($root) {
        $this->dfs($root, "");
        return $this->ans;
    }

    private function dfs($node, $path) {
        if ($node === null) return;
        $path = chr($node->val + ord('a')) . $path;
        if ($node->left === null && $node->right === null) {
            if (strcmp($path, $this->ans) < 0) {
                $this->ans = $path;
            }
        }
        $this->dfs($node->left, $path);
        $this->dfs($node->right, $path);
    }
}

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

Задача: 291. Word Pattern II
Сложность: medium

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

class Solution {
    function wordPatternMatch($pattern, $s) {
        $symbolMap = [];
        $wordSet = [];
        return $this->isMatch($s, 0, $pattern, 0, $symbolMap, $wordSet);
    }

    private function isMatch($s, $sIndex, $pattern, $pIndex, &$symbolMap, &$wordSet) {
        if ($pIndex == strlen($pattern)) {
            return $sIndex == strlen($s);
        }
        $symbol = $pattern[$pIndex];
        if (isset($symbolMap[$symbol])) {
            $word = $symbolMap[$symbol];
            if (substr($s, $sIndex, strlen($word)) !== $word) {
                return false;
            }
            return $this->isMatch($s, $sIndex + strlen($word), $pattern, $pIndex + 1, $symbolMap, $wordSet);
        }
        for ($k = $sIndex + 1; $k <= strlen($s); $k++) {
            $newWord = substr($s, $sIndex, $k - $sIndex);
            if (in_array($newWord, $wordSet)) {
                continue;
            }
            $symbolMap[$symbol] = $newWord;
            $wordSet[] = $newWord;
            if ($this->isMatch($s, $k, $pattern, $pIndex + 1, $symbolMap, $wordSet)) {
                return true;
            }
            unset($symbolMap[$symbol]);
            array_pop($wordSet);
        }
        return false;
    }
}
?>

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

Задача: 31. Next Permutation
Сложность: medium

Дан массив целых чисел nums, представляющий перестановку его элементов. Нужно изменить nums, чтобы получить его следующую перестановку в лексикографическом порядке. Если это невозможно, преобразовать массив в наименьшую возможную перестановку (отсортировать по возрастанию).
Замена должна происходить на месте, используя только постоянную дополнительную память.

Пример:

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

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

1⃣Найти первую пару чисел, идущих по убыванию справа налево.

2⃣Найти наименьшее число справа, которое больше найденного, и поменять их местами.

3⃣Отсортировать оставшуюся часть массива после измененного элемента.

😎 Решение:

class Solution {
    function nextPermutation(&$nums) {
        if (count($nums) <= 1) return;
        
        $i = count($nums) - 2;
        while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) $i--;
        
        if ($i >= 0) {
            $j = count($nums) - 1;
            while ($nums[$j] <= $nums[$i]) $j--;
            $this->swap($nums, $i, $j);
        }
        
        $this->reverse($nums, $i + 1, count($nums) - 1);
    }
    
    function swap(&$nums, $i, $j) {
        $temp = $nums[$i];
        $nums[$i] = $nums[$j];
        $nums[$j] = $temp;
    }
    
    function reverse(&$nums, $start, $end) {
        while ($start < $end) {
            $this->swap($nums, $start, $end);
            $start++;
            $end--;
        }
    }
}

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

Задача: 322. Coin Change
Сложность: medium

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

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

class Solution {
    public function coinChange($coins, $amount) {
        return $this->coinChangeHelper(0, $coins, $amount);
    }

    private function coinChangeHelper($idxCoin, $coins, $amount) {
        if ($amount == 0) return 0;
        if ($idxCoin < count($coins) && $amount > 0) {
            $maxVal = intdiv($amount, $coins[$idxCoin]);
            $minCost = PHP_INT_MAX;
            for ($x = 0; $x <= $maxVal; $x++) {
                if ($amount >= $x * $coins[$idxCoin]) {
                    $res = $this->coinChangeHelper($idxCoin + 1, $coins, $amount - $x * $coins[$idxCoin]);
                    if ($res != -1) {
                        $minCost = min($minCost, $res + $x);
                    }
                }
            }
            return $minCost == PHP_INT_MAX ? -1 : $minCost;
        }
        return -1;
    }
}

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

Задача: 128. Longest Consecutive Sequence
Сложность: Medium

Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.

Необходимо написать алгоритм, который работает за время O(n).

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

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

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎 Решение:

function arrayContains($arr, $num) {
    foreach ($arr as $item) {
        if ($item === $num) {
            return true;
        }
    }
    return false;
}

function longestConsecutive($nums) {
    $longestStreak = 0;
    foreach ($nums as $num) {
        $currentNum = $num;
        $currentStreak = 1;
        while (arrayContains($nums, $currentNum + 1)) {
            $currentNum += 1;
            $currentStreak += 1;
        }
        if ($currentStreak > $longestStreak) {
            $longestStreak = $currentStreak;
        }
    }
    return $longestStreak;
}

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

Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение:

class Solution {
    private $memo = [];
    private $add = [1 => true, 9 => true, 99 => true];

    function getLengthOfOptimalCompression($s, $k) {
        return $this->dp($s, 0, chr(ord('a') + 26), 0, $k);
    }

    private function dp($s, $idx, $lastChar, $lastCharCount, $k) {
        if ($k < 0) {
            return PHP_INT_MAX / 2;
        }

        if ($idx == strlen($s)) {
            return 0;
        }

        $key = $idx * 101 * 27 * 101 + (ord($lastChar) - ord('a')) * 101 * 101 + $lastCharCount * 101 + $k;

        if (isset($this->memo[$key])) {
            return $this->memo[$key];
        }

        $deleteChar = $this->dp($s, $idx + 1, $lastChar, $lastCharCount, $k - 1);
        if ($s[$idx] == $lastChar) {
            $keepChar = $this->dp($s, $idx + 1, $lastChar, $lastCharCount + 1, $k) + (isset($this->add[$lastCharCount]) ? 1 : 0);
        } else {
            $keepChar = $this->dp($s, $idx + 1, $s[$idx], 1, $k) + 1;
        }

        $res = min($keepChar, $deleteChar);
        $this->memo[$key] = $res;

        return $res;
    }
}

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