Задача: 277. Find the Celebrity
Сложность: medium

Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.

Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

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

1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.

2⃣Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.

3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.

😎 Решение:

class Solution {
    private $n;
    private $cache = [];

    function findCelebrity($n) {
        $this->n = $n;
        $celebrityCandidate = 0;
        for ($i = 1; $i < $n; $i++) {
            if ($this->cachedKnows($celebrityCandidate, $i)) {
                $celebrityCandidate = $i;
            }
        }
        return $this->isCelebrity($celebrityCandidate) ? $celebrityCandidate : -1;
    }

    private function isCelebrity($i) {
        for ($j = 0; $j < $this->n; $j++) {
            if ($i == $j) continue;
            if ($this->cachedKnows($i, $j) || !$this->cachedKnows($j, $i)) {
                return false;
            }
        }
        return true;
    }

    private function cachedKnows($a, $b) {
        $key = "$a,$b";
        if (!isset($this->cache[$key])) {
            $this->cache[$key] = knows($a, $b);
        }
        return $this->cache[$key];
    }
}

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

Задача: 991. Broken Calculator
Сложность: medium

Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:

Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.

Пример:

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

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

1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.

2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.

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

😎 Решение:

class Solution {
    function brokenCalc($startValue, $target) {
        $operations = 0;
        
        while ($target > $startValue) {
            $operations++;
            if ($target % 2 == 0) {
                $target /= 2;
            } else {
                $target += 1;
            }
        }
        
        return $operations + ($startValue - $target);
    }
}

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

Задача: 513. Find Bottom Left Tree Value
Сложность: medium

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

Пример:

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

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

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

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

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

class Solution {
    private $maxDepth = -1;
    private $bottomLeftValue = 0;
    
    function findBottomLeftValue($root) {
        $this->dfs($root, 0);
        return $this->bottomLeftValue;
    }
    
    private function dfs($current, $depth) {
        if ($current == null) return;
        
        if ($depth > $this->maxDepth) {
            $this->maxDepth = $depth;
            $this->bottomLeftValue = $current->val;
        }
        
        $this->dfs($current->left, $depth + 1);
        $this->dfs($current->right, $depth + 1);
    }
}

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

Задача: 965. Univalued Binary Tree
Сложность: easy

Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.

Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

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

2⃣Проверьте, что все значения в списке одинаковы.

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

class Solution {
    private $vals;
    
    function isUnivalTree($root) {
        $this->vals = [];
        $this->dfs($root);
        foreach ($this->vals as $v) {
            if ($v != $this->vals[0]) {
                return false;
            }
        }
        return true;
    }

    function dfs($node) {
        if ($node != null) {
            $this->vals[] = $node->val;
            $this->dfs($node->left);
            $this->dfs($node->right);
        }
    }
}

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

Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium

В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.

Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.

Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.

Пример:

Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

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

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

2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск":
Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b).
Каждое объединение добавляет новые связи между участниками.

3⃣Следите за количеством групп:
Изначально каждый участник рассматривается как отдельная группа.
Количество групп уменьшается с каждым полезным объединением.
Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени.
Если такого момента не существует, верните -1.

😎 Решение:

class UnionFind {
    private $parent;
    private $rank;

    public function __construct($n) {
        $this->parent = range(0, $n - 1);
        $this->rank = array_fill(0, $n, 1);
    }

    public function find($x) {
        if ($this->parent[$x] != $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        
        if ($rootX != $rootY) {
            if ($this->rank[$rootX] > $this->rank[$rootY]) {
                $this->parent[$rootY] = $rootX;
            } else if ($this->rank[$rootX] < $this->rank[$rootY]) {
                $this->parent[$rootX] = $rootY;
            } else {
                $this->parent[$rootY] = $rootX;
                $this->rank[$rootX]++;
            }
            return true;
        }
        return false;
    }
}

class Solution {
    function earliestAcq($logs, $n) {
        usort($logs, function($a, $b) {
            return $a[0] - $b[0];
        });
        $uf = new UnionFind($n);
        $groupCount = $n;
        
        foreach ($logs as $log) {
            $timestamp = $log[0];
            $friendA = $log[1];
            $friendB = $log[2];
            if ($uf->union($friendA, $friendB)) {
                $groupCount--;
            }
            if ($groupCount == 1) {
                return $timestamp;
            }
        }
        
        return -1;
    }
}

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

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

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