Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

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

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

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

😎 Решение:

class Solution {
    private function storeFirstOptions($s, $startPos, &$firstOptions) {
        if ($s[$startPos] != '{') {
            $firstOptions[] = $s[$startPos];
        } else {
            $startPos++;
            while ($s[$startPos] != '}') {
                if ($s[$startPos] >= 'a' && $s[$startPos] <= 'z') {
                    $firstOptions[] = $s[$startPos];
                }
                $startPos++;
            }
            sort($firstOptions);
        }
        return $startPos + 1;
    }

    private function findAllWords($s, $startPos) {
        if ($startPos == strlen($s)) {
            return [""];
        }

        $firstOptions = [];
        $remStringStartPos = $this->storeFirstOptions($s, $startPos, $firstOptions);
        $wordsWithRemString = $this->findAllWords($s, $remStringStartPos);

        $expandedWords = [];
        foreach ($firstOptions as $c) {
            foreach ($wordsWithRemString as $word) {
                $expandedWords[] = $c . $word;
            }
        }
        return $expandedWords;
    }

    public function expand($s) {
        return $this->findAllWords($s, 0);
    }
}

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

Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium

Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.

Пример:

Input: preorder = [5,2,1,3,6]
Output: true

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

1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек.

2⃣Итерируйте по массиву preorder. Для каждого num:
Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit.
Если num <= minLimit, верните false.
Добавьте num в стек.

3⃣Верните true, если удалось пройти весь массив.

😎 Решение:

class Solution {
    function verifyPreorder($preorder) {
        $minLimit = -PHP_INT_MAX;
        $stack = [];
        
        foreach ($preorder as $num) {
            while (!empty($stack) && end($stack) < $num) {
                $minLimit = array_pop($stack);
            }
            
            if ($num <= $minLimit) {
                return false;
            }
            
            $stack[] = $num;
        }
        
        return true;
    }
}

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

Задача: 389. Find the Difference
Сложность: easy

Даны две строки s и t.
Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.
Верните букву, которая была добавлена в t.

Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

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

1⃣Отсортируйте строки s и t.

2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.

3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.

😎 Решение:

var findTheDifference = function(s, t) {
    let sortedS = s.split('').sort();
    let sortedT = t.split('').sort();

    for (let i = 0; i < sortedS.length; i++) {
        if (sortedS[i] !== sortedT[i]) {
            return sortedT[i];
        }
    }

    return sortedT[sortedS.length];
};

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

Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

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

1⃣Определите количество возможных двоичных кодов длины k.

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

3⃣Возвращайте true, если все возможные коды найдены, иначе false.

😎 Решение:

class Solution {
    function hasAllCodes($s, $k) {
        $need = 1 << $k;
        $got = array_fill(0, $need, false);
        $allOne = $need - 1;
        $hashVal = 0;
        
        for ($i = 0; $i < strlen($s); $i++) {
            $hashVal = (($hashVal << 1) & $allOne) | ($s[$i] - '0');
            if ($i >= $k - 1 && !$got[$hashVal]) {
                $got[$hashVal] = true;
                $need--;
                if ($need == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

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

Задача: 681. Next Closest Time
Сложность: medium

Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.

Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.

Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

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

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

2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60.

3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д.

😎 Решение:

class Solution {
    function nextClosestTime($time) {
        $cur = 60 * intval(substr($time, 0, 2)) + intval(substr($time, 3));
        $allowed = [];
        foreach (str_split($time) as $c) if ($c != ':') {
            $allowed[$c] = true;
        }

        while (true) {
            $cur = ($cur + 1) % (24 * 60);
            $digits = [intval($cur / 60 / 10), intval($cur / 60 % 10), intval($cur % 60 / 10), intval($cur % 60 % 10)];
            $isValid = true;
            foreach ($digits as $d) {
                if (!isset($allowed[$d])) {
                    $isValid = false;
                    break;
                }
            }
            if ($isValid) {
                return sprintf("%02d:%02d", intval($cur / 60), intval($cur % 60));
            }
        }
    }
}

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

Задача: 763. Partition Labels
Сложность: medium

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

Пример:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]

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

1⃣Создайте словарь для хранения последней позиции каждой буквы в строке.

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

3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую.

😎 Решение:

function partitionLabels($s) {
    $lastPos = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $lastPos[$s[$i]] = $i;
    }
    
    $partitions = [];
    $j = 0;
    $anchor = 0;
    for ($i = 0; $i < strlen($s); $i++) {
        $j = max($j, $lastPos[$s[$i]]);
        if ($i == $j) {
            $partitions[] = $i - $anchor + 1;
            $anchor = $i + 1;
        }
    }
    return $partitions;
}

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

Задача: 32. Longest Valid Parentheses
Сложность: hard

Дана строка, содержащая только символы ( и ). Нужно найти длину самой длинной допустимой (правильно сформированной) подстроки круглых скобок.

Пример:

Input: s = "(()"  
Output: 2  

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

1⃣Используем массив dp, где dp[i] хранит длину самой длинной правильной подстроки, заканчивающейся в i.

2⃣Если s[i] == ')' и перед ней есть (, обновляем dp[i] на основе dp[i-1] и dp[i-dp[i-1]-2].

3⃣Возвращаем максимальное значение из dp.

😎 Решение:

class Solution {
    function longestValidParentheses($s) {
        $s2 = ')'.$s;
        $n = strlen($s2);
        $dp = array_fill(0, $n, 0);

        for ($i = 1; $i < $n; $i++) {
            if ($s2[$i] === ')' && $s2[$i - $dp[$i - 1] - 1] === '(') {
                $dp[$i] = $dp[$i - 1] + $dp[$i - $dp[$i - 1] - 2] + 2;
            }
        }

        return max($dp);
    }
}

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

function reachTarget($target) {
    $target = abs($target);
    $position = 0;
    $steps = 0;
    while ($position < $target || ($position - $target) % 2 != 0) {
        $steps += 1;
        $position += $steps;
    }
    return $steps;
}

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

Задача: 412. Fizz Buzz
Сложность: easy

Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.

Пример:

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

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

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

2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку.

3⃣Верните полученный список.

😎 Решение:

function fizzBuzz($n) {
    $answer = [];
    for ($i = 1; $i <= $n; $i++) {
        if ($i % 3 == 0 && $i % 5 == 0) {
            $answer[] = "FizzBuzz";
        } elseif ($i % 3 == 0) {
            $answer[] = "Fizz";
        } elseif ($i % 5 == 0) {
            $answer[] = "Buzz";
        } else {
            $answer[] = (string)$i;
        }
    }
    return $answer;
}

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

Задача: 859. Buddy Strings
Сложность: easy

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

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

class Solution {
    function buddyStrings($s, $goal) {
        if (strlen($s) != strlen($goal)) return false;
        if ($s == $goal) {
            $freq = array_fill(0, 26, 0);
            foreach (str_split($s) as $ch) {
                if (++$freq[ord($ch) - ord('a')] > 1) return true;
            }
            return false;
        }

        $firstIndex = -1;
        $secondIndex = -1;
        for ($i = 0; $i < strlen($s); ++$i) {
            if ($s[$i] != $goal[$i]) {
                if ($firstIndex == -1) $firstIndex = $i;
                else if ($secondIndex == -1) $secondIndex = $i;
                else return false;
            }
        }

        return $secondIndex != -1 &&
               $s[$firstIndex] == $goal[$secondIndex] &&
               $s[$secondIndex] == $goal[$firstIndex];
    }
}

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

Задача: 482. License Key Formatting
Сложность: Easy

Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.
Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные.
Верните переформатированный лицензионный ключ.

Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

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

1⃣Инициализация
Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата.

2⃣Итерация по входной строке в обратном порядке
Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count.

3⃣Завершение
Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её.

😎 Решение:

class Solution {
    function licenseKeyFormatting($s, $k) {
        $count = 0;
        $ans = [];

        for ($i = strlen($s) - 1; $i >= 0; $i--) {
            if ($s[$i] != '-') {
                $ans[] = strtoupper($s[$i]);
                $count++;
                if ($count == $k) {
                    $ans[] = '-';
                    $count = 0;
                }
            }
        }

        if (end($ans) == '-') {
            array_pop($ans);
        }

        return implode('', array_reverse($ans));
    }
}

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

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

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

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
    function arraysIntersection($arr1, $arr2, $arr3) {
        $counter = array();
        
        foreach ($arr1 as $e) {
            if (isset($counter[$e])) $counter[$e]++;
            else $counter[$e] = 1;
        }
        
        foreach ($arr2 as $e) {
            if (isset($counter[$e])) $counter[$e]++;
            else $counter[$e] = 1;
        }
        
        foreach ($arr3 as $e) {
            if (isset($counter[$e])) $counter[$e]++;
            else $counter[$e] = 1;
        }

        $ans = array();
        foreach ($counter as $key => $value) {
            if ($value == 3) array_push($ans, $key);
        }

        return $ans;
    }
}

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

Задача: 865. Smallest Subtree with all the Deepest Nodes
Сложность: medium

Дан корень бинарного дерева, глубина каждого узла — это кратчайшее расстояние до корня.

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

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

Поддерево узла — это дерево, состоящее из этого узла и всех его потомков.

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

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

1⃣В первой фазе используем поиск в глубину (DFS), чтобы аннотировать узлы. Каждый узел будет хранить информацию о своей глубине и о самой большой глубине среди его потомков.

2⃣Во второй фазе также используем DFS для функции answer(node), которая возвращает наименьшее поддерево, содержащее все самые глубокие узлы. Функция сравнивает глубины левых и правых поддеревьев узла для определения наименьшего поддерева.

3⃣Функция answer(node) возвращает поддерево, которое содержит все самые глубокие узлы всего дерева, а не только рассматриваемого поддерева.

😎 Решение:

class Solution {
    private $depth = [];
    private $maxDepth = -1;

    function subtreeWithAllDeepest($root) {
        $this->depth[null] = -1;
        $this->dfs($root, null);
        $this->maxDepth = max($this->depth);
        return $this->answer($root);
    }

    private function dfs($node, $parent) {
        if ($node !== null) {
            $this->depth[$node->val] = $this->depth[$parent->val] + 1;
            $this->dfs($node->left, $node);
            $this->dfs($node->right, $node);
        }
    }

    private function answer($node) {
        if ($node === null || $this->depth[$node->val] == $this->maxDepth) return $node;
        $L = $this->answer($node->left);
        $R = $this->answer($node->right);
        if ($L !== null && $R !== null) return $node;
        return $L !== null ? $L : $R;
    }
}

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

Задача: 742. Closest Leaf in a Binary Tree
Сложность: medium

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

Пример:

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

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

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

2⃣Найдите все листья и минимальное расстояние до них, используя BFS, начиная с найденного узла k.

3⃣Верните значение ближайшего листа.

😎 Решение:

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

function findClosestLeaf($root, $k) {
    $path = [];
    $leaves = [];
    
    function findPath($node, $k, &$path) {
        if (!$node) return false;
        $path[] = $node;
        if ($node->val == $k) return true;
        if (findPath($node->left, $k, $path) || findPath($node->right, $k, $path)) return true;
        array_pop($path);
        return false;
    }
    
    function findLeaves($node, &$leaves) {
        if (!$node) return;
        if (!$node->left && !$node->right) $leaves[spl_object_hash($node)] = 0;
        findLeaves($node->left, $leaves);
        findLeaves($node->right, $leaves);
    }
    
    findPath($root, $k, $path);
    findLeaves($root, $leaves);
    
    $queue = [[end($path), 0]];
    $visited = [];
    
    while ($queue) {
        list($node, $dist) = array_shift($queue);
        if (isset($leaves[spl_object_hash($node)])) return $node->val;
        $visited[spl_object_hash($node)] = true;
        if ($node->left && !isset($visited[spl_object_hash($node->left)])) $queue[] = [$node->left, $dist + 1];
        if ($node->right && !isset($visited[spl_object_hash($node->right)])) $queue[] = [$node->right, $dist + 1];
        if (count($path) > 1) $queue[] = [array_pop($path), $dist + 1];
    }
    return -1;
}

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

Задача: 35. Search Insert Position
Сложность: easy

Дан отсортированный массив различных целых чисел nums и число target. Необходимо вернуть индекс target, если он найден. Если target отсутствует, вернуть индекс, куда он должен быть вставлен, чтобы сохранить порядок.
Алгоритм должен работать за O(log n).

Пример:

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

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

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

2⃣сли nums[mid] == target, возвращаем mid.

3⃣Если nums[mid] < target, продолжаем поиск справа, иначе — слева.

😎 Решение:

class Solution {
    function searchInsert($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = intdiv($left + $right, 2);
            if ($nums[$mid] == $target) {
                return $mid;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return $left;
    }
}

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

Задача: 174. Dungeon Game
Сложность: hard

Демоны захватили принцессу и заточили её в правом нижнем углу подземелья. Подземелье состоит из m x n комнат, расположенных в виде двумерной сетки. Наш отважный рыцарь изначально находится в левом верхнем углу и должен пробиться через подземелье, чтобы спасти принцессу.
У рыцаря есть начальное количество очков здоровья, представленное положительным целым числом. Если в какой-то момент его очки здоровья упадут до 0 или ниже, он немедленно умрёт.
Некоторые комнаты охраняются демонами (представлены отрицательными числами), поэтому рыцарь теряет здоровье, заходя в эти комнаты; другие комнаты либо пусты (представлены как 0), либо содержат магические шары, увеличивающие здоровье рыцаря (представлены положительными числами).
Чтобы как можно быстрее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге.
Верните минимальное начальное количество здоровья рыцаря, чтобы он мог спасти принцессу.
Учтите, что любая комната может содержать угрозы или усиления, включая первую комнату, в которую входит рыцарь, и последнюю комнату, где заточена принцесса.

Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

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

1⃣Определяем матрицу dp[row][col], где элемент dp[row][col] указывает минимальное количество очков здоровья, которое потребуется рыцарю, начиная с соответствующей ячейки подземелья dungeon[row][col], чтобы добраться до цели.

2⃣Для расчета значений матрицы dp начинаем с правого нижнего угла подземелья и идем в порядке справа-налево и снизу-вверх. Для каждой ячейки подземелья рассчитываем соответствующее значение dp[row][col].

3⃣Значение dp[row][col] определяется следующими условиями:
Если возможно, сделав шаг вправо из текущей ячейки подземелья, рыцарь может нуждаться в right_health очках здоровья.
Если возможно, сделав шаг вниз из текущей ячейки подземелья, рыцарь может нуждаться в down_health очках здоровья.
Если существует хотя бы одна из вышеуказанных альтернатив, берём минимальное значение из них для dp[row][col].
Если ни одна из вышеуказанных альтернатив не существует, то есть мы находимся в целевой ячейке, возможны два случая:
Если текущая ячейка содержит магический шар, то достаточно одного очка здоровья.
Если текущая ячейка содержит демона, то рыцарь должен иметь одно очко здоровья плюс очки урона, которые нанесет демон.

😎 Решение:

function calculateMinimumHP($dungeon) {
    $rows = count($dungeon);
    $cols = count($dungeon[0]);
    $dp = array_fill(0, $rows, array_fill(0, $cols, PHP_INT_MAX));

    function get_min_health($dp, $currCell, $nextRow, $nextCol, $rows, $cols) {
        if ($nextRow >= $rows || $nextCol >= $cols) {
            return PHP_INT_MAX;
        }
        $nextCell = $dp[$nextRow][$nextCol];
        return max(1, $nextCell - $currCell);
    }

    for ($row = $rows - 1; $row >= 0; --$row) {
        for ($col = $cols - 1; $col >= 0; --$col) {
            $currCell = $dungeon[$row][$col];

            $right_health = get_min_health($dp, $currCell, $row, $col + 1, $rows, $cols);
            $down_health = get_min_health($dp, $currCell, $row + 1, $col, $rows, $cols);
            $next_health = min($right_health, $down_health);

            if ($next_health != PHP_INT_MAX) {
                $min_health = $next_health;
            } else {
                $min_health = $currCell >= 0 ? 1 : 1 - $currCell;
            }

            $dp[$row][$col] = $min_health;
        }
    }

    return $dp[0][0];
}

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

Задача: 1004. Max Consecutive Ones III
Сложность: medium

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    function longestOnes($nums, $k) {
        $left = 0;
        $maxOnes = 0;
        $zeroCount = 0;

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

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

            $maxOnes = max($maxOnes, $right - $left + 1);
        }

        return $maxOnes;
    }
}

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

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

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

3⃣Объединить массивы, созданные для четных и нечетных индексов, в результирующий массив.

😎 Решение:

function beautifulArray($n) {
    return construct($n);
}

function construct($n) {
    if ($n == 1) return [1];
    $odd = array_map(fn($x) => 2 * $x - 1, construct(($n + 1) / 2));
    $even = array_map(fn($x) => 2 * $x, construct($n / 2));
    return array_merge($odd, $even);
}

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

Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium

Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.

Пример:

Input: nums = [3,6,5,1,8]
Output: 18

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

1⃣Найдите сумму всех элементов массива.

2⃣Если сумма делится на 3, то она и есть ответ.

3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2).
Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2).

😎 Решение:

function maxSumDivThree($nums) {
    $totalSum = array_sum($nums);
    if ($totalSum % 3 == 0) {
        return $totalSum;
    }
    
    $mod1 = [];
    $mod2 = [];
    foreach ($nums as $num) {
        if ($num % 3 == 1) {
            $mod1[] = $num;
        } elseif ($num % 3 == 2) {
            $mod2[] = $num;
        }
    }
    
    sort($mod1);
    sort($mod2);
    
    if ($totalSum % 3 == 1) {
        $remove1 = empty($mod1) ? PHP_INT_MAX : $mod1[0];
        $remove2 = count($mod2) < 2 ? PHP_INT_MAX : $mod2[0] + $mod2[1];
        return $totalSum - min($remove1, $remove2);
    } else {
        $remove2 = empty($mod2) ? PHP_INT_MAX : $mod2[0];
        $remove1 = count($mod1) < 2 ? PHP_INT_MAX : $mod1[0] + $mod1[1];
        return $totalSum - min($remove2, $remove1);
    }
}

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

class Solution {
    function fixedPoint($arr) {
        $left = 0;
        $right = count($arr) - 1;
        $answer = -1;
        
        while ($left <= $right) {
            $mid = intdiv($left + $right, 2);
            
            if ($arr[$mid] == $mid) {
                $answer = $mid;
                $right = $mid - 1;
            } else if ($arr[$mid] < $mid) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        
        return $answer;
    }
}

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

Задача: 1266. Minimum Time Visiting All Points
Сложность: easy

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7

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

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

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

3⃣Суммируйте время переходов для получения общего минимального времени.

😎 Решение:

class Solution {
    function minTimeToVisitAllPoints($points) {
        $time = 0;
        for ($i = 0; $i < count($points) - 1; $i++) {
            $time += $this->distance($points[$i], $points[$i + 1]);
        }
        return $time;
    }

    private function distance($p1, $p2) {
        return max(abs($p1[0] - $p2[0]), abs($p1[1] - $p2[1]));
    }
}

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