Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

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

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

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

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

😎 Решение:

class Solution {
    function findRoot($tree) {
        $seen = [];

        foreach ($tree as $node) {
            foreach ($node->children as $child) {
                $seen[$child->val] = true;
            }
        }

        foreach ($tree as $node) {
            if (!isset($seen[$node->val])) {
                return $node;
            }
        }

        return null;
    }
}

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

Задача: 641. Design Circular Deque
Сложность: medium

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

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

2⃣Операции вставки
Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

3⃣Операции удаления
Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class MyCircularDeque {
    private $deque;
    private $front;
    private $rear;
    private $size;
    private $capacity;

    function __construct($k) {
        $this->capacity = $k;
        $this->deque = array_fill(0, $k, 0);
        $this->front = 0;
        $this->rear = 0;
        $this->size = 0;
    }

    function insertFront($value) {
        if ($this->isFull()) return false;
        $this->front = ($this->front - 1 + $this->capacity) % $this->capacity;
        $this->deque[$this->front] = $value;
        $this->size++;
        return true;
    }

    function insertLast($value) {
        if ($this->isFull()) return false;
        $this->deque[$this->rear] = $value;
        $this->rear = ($this->rear + 1) % $this->capacity;
        $this->size++;
        return true;
    }

    function deleteFront() {
        if ($this->isEmpty()) return false;
        $this->front = ($this->front + 1) % $this->capacity;
        $this->size--;
        return true;
    }

    function deleteLast() {
        if ($this->isEmpty()) return false;
        $this->rear = ($this->rear - 1 + $this->capacity) % $this->capacity;
        $this->size--;
        return true;
    }

    function getFront() {
        if ($this->isEmpty()) return -1;
        return $this->deque[$this->front];
    }

    function getRear() {
        if ($this->isEmpty()) return -1;
        return $this->deque[($this->rear - 1 + $this->capacity) % $this->capacity];
    }

    function isEmpty() {
        return $this->size == 0;
    }

    function isFull() {
        return $this->size == $this->capacity;
    }
}

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

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

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

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

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

function numPermsDISequence($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, array_fill(0, $n + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $n; $i++) {
        for ($j = 0; $j <= $i; $j++) {
            if ($s[$i - 1] == 'D') {
                for ($k = $j; $k < $i; $k++) {
                    $dp[$i][$j] = ($dp[$i][$j] + $dp[$i - 1][$k]) % $MOD;
                }
            } else {
                for ($k = 0; $k < $j; $k++) {
                    $dp[$i][$j] = ($dp[$i][$j] + $dp[$i - 1][$k]) % $MOD;
                }
            }
        }
    }

    $result = 0;
    for ($j = 0; $j <= $n; $j++) {
        $result = ($result + $dp[$n][$j]) % $MOD;
    }

    return $result;
}

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

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

Дана голова связного списка и значение x. Разделите его так, чтобы все узлы с значениями меньше x находились перед узлами с значениями, равными или большими x.

Необходимо сохранить исходный относительный порядок узлов в каждой из двух частей.

Пример:

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

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

1⃣Инициализация указателей: Создайте два указателя before и after, каждый из которых инициализирован временным (dummy) узлом. Это упрощает управление границами списка, минимизируя необходимость проверок условий в коде.

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

3⃣Соединение списков: После обработки всех узлов исходного списка, соедините списки before и after. Удалите временные узлы в начале каждого списка перед их соединением, чтобы исключить их из итогового связного списка.

😎 Решение:

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

function partition($head, $x) {
    $before_head = new ListNode(0);
    $before = $before_head;
    $after_head = new ListNode(0);
    $after = $after_head;
    
    while ($head != null) {
        if ($head->val < $x) {
            $before->next = $head;
            $before = $before->next;
        } else {
            $after->next = $head;
            $after = $after->next;
        }
        $head = $head->next;
    }
    $after->next = null;
    $before->next = $after_head->next;
    
    return $before_head->next;
}

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

2⃣Пройти по каждому слову в предложении и найти все возможные синонимы.
Сгенерировать все возможные комбинации предложений.

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

class Solution {
    function generateSentences($synonyms, $text) {
        $graph = [];

        foreach ($synonyms as $pair) {
            $graph[$pair[0]][] = $pair[1];
            $graph[$pair[1]][] = $pair[0];
        }

        $words = explode(' ', $text);
        $synonymGroups = [];
        foreach ($words as $word) {
            $synonymGroups[] = $this->findSynonyms($graph, $word);
        }

        $sentences = [];
        $this->generate($sentences, $synonymGroups, "", 0);
        sort($sentences);
        return $sentences;
    }

    private function findSynonyms($graph, $word) {
        $synonyms = [];
        $stack = [$word];
        while (!empty($stack)) {
            $w = array_pop($stack);
            if (!isset($synonyms[$w])) {
                $synonyms[$w] = true;
                if (isset($graph[$w])) {
                    foreach ($graph[$w] as $neighbor) {
                        $stack[] = $neighbor;
                    }
                }
            }
        }
        $result = array_keys($synonyms);
        sort($result);
        return $result;
    }

    private function generate(&$sentences, $groups, $sentence, $index) {
        if ($index == count($groups)) {
            $sentences[] = trim($sentence);
            return;
        }
        foreach ($groups[$index] as $word) {
            $this->generate($sentences, $groups, $sentence . " " . $word, $index + 1);
        }
    }
}

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

function minSubsequences($source, $target) {
    $subsequencesCount = 0;
    $targetIndex = 0;

    while ($targetIndex < strlen($target)) {
        $sourceIndex = 0;
        $subsequencesCount++;
        $startIndex = $targetIndex;

        while ($sourceIndex < strlen($source) && $targetIndex < strlen($target)) {
            if ($source[$sourceIndex] === $target[$targetIndex]) {
                $targetIndex++;
            }
            $sourceIndex++;
        }

        if ($targetIndex === $startIndex) {
            return -1;
        }
    }

    return $subsequencesCount;
}

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

Задача: 354. Russian Doll Envelopes
Сложность: hard

Вам дан двумерный массив целых чисел envelopes, где envelopes[i] = [wi, hi] представляет ширину и высоту конверта.
Один конверт может поместиться в другой, если и только если ширина и высота одного конверта больше ширины и высоты другого конверта.
Верните максимальное количество конвертов, которые вы можете вложить друг в друга (т.е. поместить один в другой).
Примечание: Вы не можете поворачивать конверт.

Пример:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

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

1⃣Отсортируйте массив конвертов по возрастанию по первой размерности (ширине) и по убыванию по второй размерности (высоте).

2⃣Извлеките вторую размерность (высоты) отсортированного массива.

3⃣Найдите длину наибольшей возрастающей подпоследовательности в массиве высот.

😎 Решение:

class Solution {
    function lengthOfLIS($nums) {
        $dp = [];
        foreach ($nums as $num) {
            $i = $this->binarySearch($dp, $num);
            if ($i < 0) $i = -($i + 1);
            $dp[$i] = $num;
        }
        return count($dp);
    }

    function binarySearch($arr, $target) {
        $left = 0;
        $right = count($arr);
        while ($left < $right) {
            $mid = intdiv($left + $right, 2);
            if ($arr[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        return ($left < count($arr) && $arr[$left] == $target) ? $left : -($left + 1);
    }

    function maxEnvelopes($envelopes) {
        usort($envelopes, function($a, $b) {
            return $a[0] == $b[0] ? $b[1] - $a[1] : $a[0] - $b[0];
        });
        $secondDim = array_map(function($envelope) {
            return $envelope[1];
        }, $envelopes);
        return $this->lengthOfLIS($secondDim);
    }
}

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

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

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

Задача: 568. Maximum Vacation Days
Сложность: hard

LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения.

Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.

Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

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

1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i].

2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1).

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

😎 Решение:

function maxVacationDays($flights, $days) {
    $n = count($flights);
    $k = count($days[0]);
    $memo = array_fill(0, $n, array_fill(0, $k, -1));
    
    function dfs($flights, $days, &$memo, $curCity, $weekNo) {
        $n = count($flights);
        $k = count($days[0]);
        if ($weekNo == $k) return 0;
        if ($memo[$curCity][$weekNo] != -1) return $memo[$curCity][$weekNo];
        $maxVac = 0;
        for ($nextCity = 0; $nextCity < $n; $nextCity++) {
            if ($curCity == $nextCity || $flights[$curCity][$nextCity] == 1) {
                $maxVac = max($maxVac, $days[$nextCity][$weekNo] + dfs($flights, $days, $memo, $nextCity, $weekNo + 1));
            }
        }
        $memo[$curCity][$weekNo] = $maxVac;
        return $maxVac;
    }

    return dfs($flights, $days, $memo, 0, 0);
}

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

Задача: 345. Reverse Vowels of a String
Сложность: easy

Дана строка s, переверните только все гласные в строке и верните её.

Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры.

Пример:

Input: s = "hello"
Output: "holle"

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

1⃣Инициализация указателей и гласных:
Создайте набор гласных для быстрой проверки.
Установите два указателя: один на начало строки (left), другой на конец строки (right).

2⃣Перестановка гласных:
Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные.
Обменивайте найденные гласные и продолжайте сдвигать указатели.

3⃣Завершение работы:
Когда указатели пересекутся, остановите процесс и верните строку.

😎 Решение:

class Solution {
    function reverseVowels($s) {
        $vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
        $s = str_split($s);
        $left = 0;
        $right = count($s) - 1;
        
        while ($left < $right) {
            if (!in_array($s[$left], $vowels)) {
                $left++;
            } else if (!in_array($s[$right], $vowels)) {
                $right--;
            } else {
                $temp = $s[$left];
                $s[$left] = $s[$right];
                $s[$right] = $temp;
                $left++;
                $right--;
            }
        }
        
        return implode('', $s);
    }
}

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

Задача: 112. Path Sum
Сложность: easy

Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum.

Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

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

1⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val.

2⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом.

3⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами.

😎 Решение:

$hasPathSum = function ($root, $sum) {
    if (!$root) return false;
    $nodeStack = [];
    $sumStack = [];
    array_push($nodeStack, $root);
    array_push($sumStack, $sum - $root->val);
    while (count($nodeStack) > 0) {
        $currentNode = array_pop($nodeStack);
        $currSum = array_pop($sumStack);
        if (!$currentNode->left && !$currentNode->right && $currSum === 0)
            return true;
        if ($currentNode->right) {
            array_push($nodeStack, $currentNode->right);
            array_push($sumStack, $currSum - $currentNode->right->val);
        }
        if ($currentNode->left) {
            array_push($nodeStack, $currentNode->left);
            array_push($sumStack, $currSum - $currentNode->left->val);
        }
    }
    return false;
};

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

Задача: 1302. Deepest Leaves Sum
Сложность: medium

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

Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

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

1⃣Поместите корень в стек.

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

3⃣Верните deepest_sum.

😎 Решение:

class Solution {
    function deepestLeavesSum($root) {
        $deepestSum = 0;
        $depth = 0;
        $stack = [[$root, 0]];

        while (!empty($stack)) {
            list($node, $currDepth) = array_pop($stack);

            if ($node->left === null && $node->right === null) {
                if ($depth < $currDepth) {
                    $deepestSum = $node->val;
                    $depth = $currDepth;
                } elseif ($depth == $currDepth) {
                    $deepestSum += $node->val;
                }
            } else {
                if ($node->right !== null) {
                    $stack[] = [$node->right, $currDepth + 1];
                }
                if ($node->left !== null) {
                    $stack[] = [$node->left, $currDepth + 1];
                }
            }
        }
        return $deepestSum;
    }
}

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

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

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

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

class Solution {
    public function kidsWithCandies($candies, $extraCandies) {
        $maxCandies = max($candies);
        $result = [];
        foreach ($candies as $candy) {
            $result[] = $candy + $extraCandies >= $maxCandies;
        }
        return $result;
    }
}

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

Задача: 407. Trapping Rain Water II
Сложность: hard

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

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

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

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

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

3⃣Повторите процесс, пока все ячейки не будут обработаны.

😎 Решение:

function trapRainWater($heightMap) {
    $m = count($heightMap);
    $n = count($heightMap[0]);
    if ($m <= 2 || $n <= 2) return 0;
    $visited = array_fill(0, $m, array_fill(0, $n, false));
    $heap = new SplPriorityQueue();
    for ($i = 0; $i < $m; $i++) {
        for ($j of [0, $n-1]) {
            $heap->insert([$heightMap[$i][$j], $i, $j], -$heightMap[$i][$j]);
            $visited[$i][$j] = true;
        }
    }
    for ($j = 0; $j < $n; $j++) {
        for ($i of [0, $m-1]) {
            $heap->insert([$heightMap[$i][$j], $i, $j], -$heightMap[$i][$j]);
            $visited[$i][$j] = true;
        }
    }
    $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    $water = 0;
    while (!$heap->isEmpty()) {
        list($height, $x, $y) = $heap->extract();
        foreach ($directions as $direction) {
            $nx = $x + $direction[0];
            $ny = $y + $direction[1];
            if ($nx >= 0 && $nx < $m && $ny >= 0 && $ny < $n && !$visited[$nx][$ny]) {
                $visited[$nx][$ny] = true;
                $water += max(0, $height - $heightMap[$nx][$ny]);
                $heap->insert([max($height, $heightMap[$nx][$ny]), $nx, $ny], -max($height, $heightMap[$nx][$ny]));
            }
        }
    }
    return $water;
}

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

Задача: 199. Binary Tree Right Side View
Сложность: medium

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

Пример:

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

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

1⃣Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel.

2⃣Пока очередь nextLevel не пуста:
Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel.
Пока очередь текущего уровня не пуста:
Извлеките узел из очереди текущего уровня.
Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel.
Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside.

3⃣Верните rightside.

😎 Решение:

class Solution {
    public function rightSideView($root) {
        if ($root === null) return [];

        $nextLevel = [$root];
        $rightside = [];

        while (!empty($nextLevel)) {
            $currLevel = $nextLevel;
            $nextLevel = [];

            foreach ($currLevel as $node) {
                if ($node->left !== null) $nextLevel[] = $node->left;
                if ($node->right !== null) $nextLevel[] = $node->right;
            }

            $rightside[] = end($currLevel)->val;
        }
        return $rightside;
    }
}

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

Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy

Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.

Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.

Пример:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

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

1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.

2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].

3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.

😎 Решение:

class Solution {
    function luckyNumbers ($matrix) {
        $N = count($matrix);
        $M = count($matrix[0]);
        
        $rowMin = [];
        for ($i = 0; $i < $N; $i++) {
            $rMin = min($matrix[$i]);
            $rowMin[] = $rMin;
        }
        
        $colMax = [];
        for ($i = 0; $i < $M; $i++) {
            $cMax = PHP_INT_MIN;
            for ($j = 0; $j < $N; $j++) {
                $cMax = max($cMax, $matrix[$j][$i]);
            }
            $colMax[] = $cMax;
        }
        
        $luckyNumbers = [];
        for ($i = 0; $i < $N; $i++) {
            for ($j = 0; $j < $M; $j++) {
                if ($matrix[$i][$j] == $rowMin[$i] && $matrix[$i][$j] == $colMax[$j]) {
                    $luckyNumbers[] = $matrix[$i][$j];
                }
            }
        }
        
        return $luckyNumbers;
    }
}

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

Задача: 631. Design Excel Sum Formula
Сложность: hard

Разработайте базовую функцию Excel и реализуйте функцию формулы суммы. Реализуйте класс Excel: Excel(int height, char width) Инициализирует объект с высотой и шириной листа. Лист представляет собой целочисленную матрицу размером height x width с индексом строки в диапазоне [1, height] и индексом столбца в диапазоне ['A', width]. Все значения должны быть нулевыми изначально. void set(int row, char column, int val) Изменяет значение в mat[row][column] на val. int get(int row, char column) Возвращает значение в mat[row][column]. int sum(int row, char column, List<String> numbers) Устанавливает значение в mat[row][column] как сумму ячеек, представленных числами, и возвращает значение в mat[row][column]. Эта формула суммы должна существовать до тех пор, пока эта ячейка не будет перекрыта другим значением или другой формулой суммы. numbers[i] могут иметь формат: "ColRow", который представляет одну ячейку. Например, "F7" представляет ячейку mat[7]['F']. "ColRow1:ColRow2", который представляет диапазон ячеек. Диапазон всегда будет прямоугольником, где "ColRow1" представляет позицию левой верхней ячейки, а "ColRow2" - позицию правой нижней ячейки.
Например, "B3:F7" представляет ячейки mat[i][j] для 3 <= i <= 7 и 'B' <= j <= 'F'. Примечание: Можно предположить, что не будет никаких ссылок на круговую сумму. Например, mat[1]['A'] == sum(1, "B") и mat[1]['B'] == sum(1, "A").

Пример:

Input
["Excel", "set", "sum", "set", "get"]
[[3, "C"], [1, "A", 2], [3, "C", ["A1", "A1:B2"]], [2, "B", 2], [3, "C"]]
Output
[null, null, 4, null, 6]

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

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

2⃣Метод установки значений
Реализуйте метод set, который будет изменять значение ячейки в матрице.

3⃣Метод вычисления суммы
Реализуйте метод sum, который будет вычислять сумму значений ячеек, указанных в списке numbers. Метод должен поддерживать как одиночные ячейки, так и диапазоны ячеек.

😎 Решение:

class Excel {
    private $mat;
    private $formulas;

    public function __construct($height, $width) {
        $this->mat = array_fill(0, $height, array_fill(0, ord($width) - ord('A') + 1, 0));
        $this->formulas = [];
    }

    public function set($row, $column, $val) {
        $this->mat[$row - 1][ord($column) - ord('A')] = $val;
        unset($this->formulas["$row$column"]);
    }

    public function get($row, $column) {
        $key = "$row$column";
        if (isset($this->formulas[$key])) {
            return $this->evaluateFormula($key);
        }
        return $this->mat[$row - 1][ord($column) - ord('A')];
    }

    public function sum($row, $column, $numbers) {
        $key = "$row$column";
        $this->formulas[$key] = $numbers;
        return $this->evaluateFormula($key);
    }

    private function evaluateFormula($key) {
        $numbers = $this->formulas[$key];
        $total = 0;
        foreach ($numbers as $number) {
            if (strpos($number, ':') !== false) {
                list($start, $end) = explode(':', $number);
                $startRow = (int)substr($start, 1);
                $startCol = $start[0];
                $endRow = (int)substr($end, 1);
                $endCol = $end[0];
                for ($r = $startRow; $r <= $endRow; $r++) {
                    for ($c = ord($startCol); $c <= ord($endCol); $c++) {
                        $total += $this->get($r, chr($c));
                    }
                }
            } else {
                $r = (int)substr($number, 1);
                $c = $number[0];
                $total += $this->get($r, $c);
            }
        }
        return $total;
    }
}

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

Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy

Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.

2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.

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

😎 Решение:

class Solution {
    function largestSumAfterKNegations($nums, $k) {
        sort($nums);
        
        for ($i = 0; $i < count($nums); $i++) {
            if ($k > 0 && $nums[$i] < 0) {
                $nums[$i] = -$nums[$i];
                $k--;
            }
        }
        
        if ($k % 2 == 1) {
            sort($nums);
            $nums[0] = -$nums[0];
        }
        
        return array_sum($nums);
    }
}

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

Задача: 1335. Minimum Difficulty of a Job Schedule
Сложность: hard

Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i).

Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день.

Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i].

Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1.

Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

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

1⃣Определение состояния:
Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней.

2⃣Функция перехода состояния:
Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i
]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i
]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i
]) для всех j > i.

3⃣Базовый случай:
Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач.

😎 Решение:

class Solution {
    function minDifficulty($jobDifficulty, $d) {
        $n = count($jobDifficulty);
        if ($n < $d) return -1;
        
        $mem = array_fill(0, $n, array_fill(0, $d + 1, -1));
        
        function minDiff($i, $daysRemaining, $jobDifficulty, &$mem) {
            if ($mem[$i][$daysRemaining] != -1) {
                return $mem[$i][$daysRemaining];
            }
            
            if ($daysRemaining == 1) {
                return max(array_slice($jobDifficulty, $i));
            }
            
            $res = PHP_INT_MAX;
            $dailyMaxJobDiff = 0;
            
            for ($j = $i; $j < count($jobDifficulty) - $daysRemaining + 1; $j++) {
                $dailyMaxJobDiff = max($dailyMaxJobDiff, $jobDifficulty[$j]);
                $res = min($res, $dailyMaxJobDiff + minDiff($j + 1, $daysRemaining - 1, $jobDifficulty, $mem));
            }
            
            $mem[$i][$daysRemaining] = $res;
            return $res;
        }
        
        return minDiff(0, $d, $jobDifficulty, $mem);
    }
}

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

Задача: 373. Find K Pairs with Smallest Sums
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.
Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.
Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами.

Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

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

1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар.

2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited.

3⃣Повторяйте до получения k пар и пока minHeap не пуст:
Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2].
Добавьте пару (nums1[i], nums2[j]) в ans.
Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap.
Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap.
Верните ans.

😎 Решение:

class Solution {
    function kSmallestPairs($nums1, $nums2, $k) {
        $m = count($nums1);
        $n = count($nums2);
        $ans = [];
        $visited = [];
        $minHeap = new SplPriorityQueue();
        $minHeap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
        $minHeap->insert([0, 0], -($nums1[0] + $nums2[0]));
        $visited["0,0"] = true;

        while ($k > 0 && !$minHeap->isEmpty()) {
            $top = $minHeap->extract();
            list($i, $j) = $top['data'];
            $ans[] = [$nums1[$i], $nums2[$j]];

            if ($i + 1 < $m && !isset($visited[($i + 1) . ",$j"])) {
                $minHeap->insert([$i + 1, $j], -($nums1[$i + 1] + $nums2[$j]));
                $visited[($i + 1) . ",$j"] = true;
            }

            if ($j + 1 < $n && !isset($visited["$i," . ($j + 1)])) {
                $minHeap->insert([$i, $j + 1], -($nums1[$i] + $nums2[$j + 1]));
                $visited["$i," . ($j + 1)] = true;
            }
            $k--;
        }

        return $ans;
    }
}

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