#easy
Задача: 203. Remove Linked List Elements

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

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

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

1️⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2️⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3️⃣Верните sentinel.next.

😎 Решение:

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

function deleteNode($head, $value) {
    $sentinel = new ListNode(0);
    $sentinel->next = $head;
    $prev = $sentinel;
    $curr = $head;

    while ($curr !== null) {
        if ($curr->val === $value) {
            $prev->next = $curr->next;
        } else {
            $prev = $curr;
        }
        $curr = $curr->next;
    }
    return $sentinel->next;
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 204. Count Primes

Дано целое число n, верните количество простых чисел, которые строго меньше n.

Пример:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

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

1️⃣Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу.

2️⃣Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само число p должно быть простым). Найдите наименьшее число в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2.

3️⃣Когда алгоритм завершится, все оставшиеся числа, которые не отмечены, являются простыми.

😎 Решение:

class Solution {
    function countPrimes($n) {
        if ($n <= 2) {
            return 0;
        }

        $numbers = array_fill(0, $n, true);
        for ($p = 2; $p <= sqrt($n); ++$p) {
            if ($numbers[$p]) {
                for ($j = $p * $p; $j < $n; $j += $p) {
                    $numbers[$j] = false;
                }
            }
        }

        $numberOfPrimes = 0;
        for ($i = 2; $i < $n; $i++) {
            if ($numbers[$i]) {
                ++$numberOfPrimes;
            }
        }

        return $numberOfPrimes;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 205. Isomorphic Strings

Даны две строки s и t, определите, являются ли они изоморфными.

Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.

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

Пример:

Input: s = "egg", t = "add"
Output: true

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

1️⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2️⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3️⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

class Solution {
    function isIsomorphic($s, $t) {
        $mappingStoT = [];
        $mappingTtoS = [];

        for ($i = 0; $i < strlen($s); ++$i) {
            $c1 = $s[$i];
            $c2 = $t[$i];

            if (!isset($mappingStoT[$c1]) && !isset($mappingTtoS[$c2])) {
                $mappingStoT[$c1] = $c2;
                $mappingTtoS[$c2] = $c1;
            } else if (($mappingStoT[$c1] ?? null) !== $c2 || ($mappingTtoS[$c2] ?? null) !== $c1) {
                return false;
            }
        }

        return true;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 206. Reverse Linked List

Дан односвязный список, разверните этот список и верните развернутый список.

Пример:

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

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

1️⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.

2️⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.

3️⃣После завершения цикла верните prev как новую голову развернутого списка.

😎 Решение:

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

class Solution {
    function reverseList($head) {
        $prev = null;
        $curr = $head;
        while ($curr !== null) {
            $nextTemp = $curr->next;
            $curr->next = $prev;
            $prev = $curr;
            $curr = $nextTemp;
        }
        return $prev;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 207. Course Schedule

Всего у вас есть numCourses курсов, которые нужно пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.

Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните true, если вы можете завершить все курсы. В противном случае верните false.

Пример:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

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

1️⃣Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1.

2️⃣Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов.

3️⃣Пока очередь не пуста:
Извлеките первый узел из очереди.
Увеличьте nodesVisited на 1.
Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor.
Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь.
Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses.

😎 Решение:

class Solution {
    function canFinish($numCourses, $prerequisites) {
        $indegree = array_fill(0, $numCourses, 0);
        $adj = array_fill(0, $numCourses, []);

        foreach ($prerequisites as $prerequisite) {
            $adj[$prerequisite[1]][] = $prerequisite[0];
            $indegree[$prerequisite[0]]++;
        }

        $q = [];
        for ($i = 0; $i < $numCourses; $i++) {
            if ($indegree[$i] == 0) {
                $q[] = $i;
            }
        }

        $nodesVisited = 0;
        while (!empty($q)) {
            $node = array_shift($q);
            $nodesVisited++;

            foreach ($adj[$node] as $neighbor) {
                $indegree[$neighbor]--;
                if ($indegree[$neighbor] == 0) {
                    $q[] = $neighbor;
                }
            }
        }

        return $nodesVisited == $numCourses;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 208. Implement Trie (Prefix Tree)

Trie (произносится как "трай") или префиксное дерево — это древовидная структура данных, используемая для эффективного хранения и поиска ключей в наборе строк. Существует множество применений этой структуры данных, таких как автозаполнение и проверка орфографии.

Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

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

1️⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2️⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3️⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎 Решение:

class TrieNode {
    private $links;
    private $isEnd;

    public function __construct() {
        $this->links = array_fill(0, 26, null);
        $this->isEnd = false;
    }

    public function containsKey($ch) {
        return $this->links[ord($ch) - ord('a')] !== null;
    }

    public function get($ch) {
        return $this->links[ord($ch) - ord('a')];
    }

    public function put($ch, $node) {
        $this->links[ord($ch) - ord('a')] = $node;
    }

    public function setEnd() {
        $this->isEnd = true;
    }

    public function isEndNode() {
        return $this->isEnd;
    }
}

class Trie {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function insert($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!$node->containsKey($ch)) {
                $node->put($ch, new TrieNode());
            }
            $node = $node->get($ch);
        }
        $node->setEnd();
    }

    private function searchPrefix($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if ($node->containsKey($ch)) {
                $node = $node->get($ch);
            } else {
                return null;
            }
        }
        return $node;
    }

    public function search($word) {
        $node = $this->searchPrefix($word);
        return $node !== null && $node->isEndNode();
    }

    public function startsWith($prefix) {
        return $this->searchPrefix($prefix) !== null;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 209. Minimum Size Subarray Sum

Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1️⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2️⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3️⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

class Solution {
    public function minSubArrayLen($target, $nums) {
        $left = 0;
        $sumOfCurrentWindow = 0;
        $res = PHP_INT_MAX;

        for ($right = 0; $right < count($nums); $right++) {
            $sumOfCurrentWindow += $nums[$right];

            while ($sumOfCurrentWindow >= $target) {
                $res = min($res, $right - $left + 1);
                $sumOfCurrentWindow -= $nums[$left];
                $left++;
            }
        }

        return $res == PHP_INT_MAX ? 0 : $res;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 210. Course Schedule II

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1️⃣ Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2️⃣ Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

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

😎 Решение:

class Solution {
    const WHITE = 1;
    const GRAY = 2;
    const BLACK = 3;

    public function findOrder($numCourses, $prerequisites) {
        $isPossible = true;
        $color = array_fill(0, $numCourses, self::WHITE);
        $adjList = [];
        $topologicalOrder = [];

        foreach ($prerequisites as $relation) {
            list($dest, $src) = $relation;
            if (!isset($adjList[$src])) {
                $adjList[$src] = [];
            }
            $adjList[$src][] = $dest;
        }

        for ($i = 0; $i < $numCourses && $isPossible; $i++) {
            if ($color[$i] == self::WHITE) {
                $this->dfs($i, $color, $adjList, $isPossible, $topologicalOrder);
            }
        }

        if ($isPossible) {
            $order = array_reverse($topologicalOrder);
            return $order;
        } else {
            return [];
        }
    }

    private function dfs($node, &$color, &$adjList, &$isPossible, &$topologicalOrder) {
        if (!$isPossible) return;
        $color[$node] = self::GRAY;

        if (isset($adjList[$node])) {
            foreach ($adjList[$node] as $neighbor) {
                if ($color[$neighbor] == self::WHITE) {
                    $this->dfs($neighbor, $color, $adjList, $isPossible, $topologicalOrder);
                } else if ($color[$neighbor] == self::GRAY) {
                    $isPossible = false;
                }
            }
        }

        $color[$node] = self::BLACK;
        $topologicalOrder[] = $node;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 252. Meeting Rooms

Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

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

1️⃣Создайте функцию для проверки перекрытия двух интервалов:
Возвращайте true, если начало одного интервала находится внутри другого интервала.

2️⃣Проверьте каждый интервал с каждым другим интервалом:
Если найдено перекрытие, верните false.

3️⃣Если все интервалы проверены и перекрытий не найдено, верните true.

😎 Решение:

class Solution {
    function overlap($interval1, $interval2) {
        return ($interval1[0] >= $interval2[0] && $interval1[0] < $interval2[1]) ||
               ($interval2[0] >= $interval1[0] && $interval2[0] < $interval1[1]);
    }
    
    function canAttendMeetings($intervals) {
        for ($i = 0; $i < count($intervals); $i++) {
            for ($j = $i + 1; $j < count($intervals); $j++) {
                if ($this->overlap($intervals[$i], $intervals[$j])) {
                    return false;
                }
            }
        }
        return true;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 253. Meeting Rooms II

Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

1️⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

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

3️⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.

😎 Решение:

class Solution {
    function minMeetingRooms($intervals) {
        usort($intervals, function($a, $b) {
            return $a[0] - $b[0];
        });
        $heap = new SplMinHeap();
        $heap->insert($intervals[0][1]);
        
        for ($i = 1; $i < count($intervals); $i++) {
            if ($intervals[$i][0] >= $heap->top()) {
                $heap->extract();
            }
            $heap->insert($intervals[$i][1]);
        }
        return $heap->count();
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 254. Factor Combinations

Числа можно рассматривать как произведение их множителей.

Например, 8 = 2 x 2 x 2 = 2 x 4.
Дано целое число n, верните все возможные комбинации его множителей. Вы можете вернуть ответ в любом порядке.

Обратите внимание, что множители должны быть в диапазоне [2, n - 1].

Пример:

Input: n = 1
Output: []

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

1️⃣Определите вспомогательную функцию backtracking, которая принимает два параметра: factors (список множителей) и ans (список списков для сохранения всех комбинаций множителей). Начните вызов backtracking с factors, содержащим только n, и пустым списком ans.

2️⃣Основная логика функции backtracking:
Если размер factors больше 1, добавьте его копию в ans, так как это одно из желаемых решений.
Получите последний элемент factors (lastFactor) и удалите его из factors.
Если factors пуст, итерируйте i от 2. В противном случае, итерируйте i от последнего значения в factors. Итерируйте, пока i <= lastFactor / i.
Для каждого i, если lastFactor % i == 0, добавьте i и lastFactor / i в factors и вызовите backtracking(factors, ans).
Восстановите список (откат) factors, удалив последние два элемента из factors.
Восстановите список (откат) factors, добавив обратно lastFactor.

3️⃣В конце выполнения, ans будет содержать все возможные комбинации множителей числа n.

😎 Решение:

class Solution {
    private function backtracking(&$factors, &$ans) {
        if (count($factors) > 1) {
            $ans[] = $factors;
        }
        $lastFactor = array_pop($factors);
        $start = empty($factors) ? 2 : end($factors);
        for ($i = $start; $i * $i <= $lastFactor; ++$i) {
            if ($lastFactor % $i == 0) {
                $factors[] = $i;
                $factors[] = $lastFactor / $i;
                $this->backtracking($factors, $ans);
                array_pop($factors);
                array_pop($factors);
            }
        }
        $factors[] = $lastFactor;
    }

    public function getFactors($n) {
        $ans = [];
        $factors = [$n];
        $this->backtracking($factors, $ans);
        return $ans;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 255. Verify Preorder Sequence in Binary Search Tree

Дан массив уникальных целых чисел 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;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 211. Design Add and Search Words Data Structure

Спроектируйте структуру данных, которая поддерживает добавление новых слов и проверку, соответствует ли строка любому ранее добавленному слову.

Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1️⃣ Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2️⃣ Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3️⃣ Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

class TrieNode {
    public $children;
    public $isWord;

    public function __construct() {
        $this->children = [];
        $this->isWord = false;
    }
}

class WordDictionary {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function addWord($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!isset($node->children[$ch])) {
                $node->children[$ch] = new TrieNode();
            }
            $node = $node->children[$ch];
        }
        $node->isWord = true;
    }

    private function searchInNode($word, $node) {
        for ($i = 0; $i < strlen($word); $i++) {
            $ch = $word[$i];
            if (!isset($node->children[$ch])) {
                if ($ch === '.') {
                    foreach ($node->children as $child) {
                        if ($this->searchInNode(substr($word, $i + 1), $child)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                $node = $node->children[$ch];
            }
        }
        return $node->isWord;
    }

    public function search($word) {
        return $this->searchInNode($word, $this->root);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 212. Word Search II

Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1️⃣ Построение Trie:
Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.

2️⃣ Запуск обхода в глубину (Backtracking) с каждой ячейки:
Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3️⃣ Обход соседних ячеек:
В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎

class TrieNode {
    public $children;
    public $word;

    public function __construct() {
        $this->children = [];
        $this->word = null;
    }
}

class Solution {
    private $board;
    private $result;

    public function findWords($board, $words) {
        $root = $this->buildTrie($words);
        $this->board = $board;
        $this->result = [];

        for ($row = 0; $row < count($board); ++$row) {
            for ($col = 0; $col < count($board[0]); ++$col) {
                if (isset($root->children[$board[$row][$col]])) {
                    $this->backtrack($row, $col, $root);
                }
            }
        }
        return $this->result;
    }

    private function buildTrie($words) {
        $root = new TrieNode();
        foreach ($words as $word) {
            $node = $root;
            for ($i = 0; $i < strlen($word); ++$i) {
                $letter = $word[$i];
                if (!isset($node->children[$letter])) {
                    $node->children[$letter] = new TrieNode();
                }
                $node = $node->children[$letter];
            }
            $node->word = $word;
        }
        return $root;
    }

    private function backtrack($row, $col, $parent) {
        $letter = $this->board[$row][$col];
        $currNode = $parent->children[$letter];

        if ($currNode->word !== null) {
            $this->result[] = $currNode->word;
            $currNode->word = null;
        }

        $this->board[$row][$col] = '#';

        $rowOffset = [-1, 0, 1, 0];
        $colOffset = [0, 1, 0, -1];
        for ($i = 0; $i < 4; ++$i) {
            $newRow = $row + $rowOffset[$i];
            $newCol = $col + $colOffset[$i];
            if (
                $newRow >= 0 && $newRow < count($this->board) &&
                $newCol >= 0 && $newCol < count($this->board[0])
            ) {
                if (isset($currNode->children[$this->board[$newRow][$newCol]])) {
                    $this->backtrack($newRow, $newCol, $currNode);
                }
            }
        }

        $this->board[$row][$col] = $letter;

        if (empty($currNode->children)) {
            unset($parent->children[$letter]);
        }
    }
}

// Example usage:
$solution = new Solution();
$board = [
    ['o', 'a', 'a', 'n'],
    ['e', 't', 'a', 'e'],
    ['i', 'h', 'k', 'r'],
    ['i', 'f', 'l', 'v']
];
$words = ["oath", "pea", "eat", "rain"];
print_r($solution->findWords($board, $words));

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 256. Paint House

Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.

Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.

Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.

Пример:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

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

1️⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2].

2️⃣Для каждого дома i от 1 до n-1 обновите значения массива dp:
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

3️⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).

😎 Решение:

class Solution {
    function minCost($costs) {
        $n = count($costs);
        $dp = array_fill(0, $n, array_fill(0, 3, 0));
        $dp[0] = $costs[0];
        
        for ($i = 1; $i < $n; $i++) {
            $dp[$i][0] = $costs[$i][0] + min($dp[$i-1][1], $dp[$i-1][2]);
            $dp[$i][1] = $costs[$i][1] + min($dp[$i-1][0], $dp[$i-1][2]);
            $dp[$i][2] = $costs[$i][2] + min($dp[$i-1][0], $dp[$i-1][1]);
        }
        
        return min($dp[$n-1][0], $dp[$n-1][1], $dp[$n-1][2]);
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 257. Binary Tree Paths

Дано корневое дерево, верните все пути от корня до листа в любом порядке.

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

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1️⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2️⃣Начните с корневого узла, пустого пути и пустого списка путей.

3️⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    function construct_paths($root, $path, &$paths) {
        if ($root !== null) {
            $path .= $root->val;
            if ($root->left === null && $root->right === null) {
                $paths[] = $path;
            } else {
                $path .= "->";
                $this->construct_paths($root->left, $path, $paths);
                $this->construct_paths($root->right, $path, $paths);
            }
        }
    }

    function binaryTreePaths($root) {
        $paths = [];
        $this->construct_paths($root, "", $paths);
        return $paths;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 258. Add Digits

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1️⃣Инициализируйте переменную digital_root значением 0.

2️⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3️⃣Верните значение digital_root.

😎 Решение:

class Solution {
    function addDigits($num) {
        $digital_root = 0
        while ($num > 0) {
            $digital_root += $num % 10
            $num = intdiv($num, 10)
            if ($num == 0 && $digital_root > 9) {
                $num = $digital_root
                $digital_root = 0
            }
        }
        return $digital_root
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 259. 3Sum Smaller

Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.

Пример:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

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

1️⃣Отсортируйте массив nums.

2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.

3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.

😎 Решение:

class Solution {
    public function threeSumSmaller($nums, $target) {
        sort($nums);
        $sum = 0;
        for ($i = 0; $i < count($nums) - 2; $i++) {
            $sum += $this->twoSumSmaller($nums, $i + 1, $target - $nums[$i]);
        }
        return $sum;
    }

    private function twoSumSmaller($nums, $startIndex, $target) {
        $sum = 0;
        for ($i = $startIndex; $i < count($nums) - 1; $i++) {
            $j = $this->binarySearch($nums, $i, $target - $nums[$i]);
            $sum += $j - $i;
        }
        return $sum;
    }

    private function binarySearch($nums, $startIndex, $target) {
        $left = $startIndex;
        $right = count($nums) - 1;
        while ($left < $right) {
            $mid = intval(($left + $right + 1) / 2);
            if ($nums[$mid] < $target) {
                $left = $mid;
            } else {
                $right = $mid - 1;
            }
        }
        return $left;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 260. Single Number III

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

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

Пример:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

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

1️⃣Выполните XOR для всех элементов массива nums. Это даст результат, который является XOR двух уникальных чисел.

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

3️⃣Выполните XOR для каждой группы, чтобы найти два уникальных числа.

😎 Решение:

class Solution {
    public function singleNumber($nums) {
        $xor = 0;
        foreach ($nums as $num) {
            $xor ^= $num;
        }
        $diff = $xor & -$xor;
        $res = [0, 0];
        foreach ($nums as $num) {
            if (($num & $diff) == 0) {
                $res[0] ^= $num;
            } else {
                $res[1] ^= $num;
            }
        }
        return $res;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 261. Graph Valid Tree

У вас есть граф из n узлов, помеченных от 0 до n - 1. Вам даны целое число n и список рёбер, где edges[i] = [ai, bi] указывает на то, что существует неориентированное ребро между узлами ai и bi в графе.

Верните true, если рёбра данного графа образуют допустимое дерево, и false в противном случае.

Пример:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

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

1️⃣Проверьте, что количество рёбер равно n - 1. Если нет, верните false.

2️⃣Используйте итеративный обход в глубину (DFS) для проверки связности графа и отсутствия циклов. Создайте стек для хранения узлов для посещения и множество для отслеживания посещённых узлов. Начните с узла 0.

3️⃣Если все узлы посещены и циклы не обнаружены, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    function validTree($n, $edges) {
        if (count($edges) != $n - 1) {
            return false;
        }
        
        $adjList = array_fill(0, $n, []);
        foreach ($edges as $edge) {
            $adjList[$edge[0]][] = $edge[1];
            $adjList[$edge[1]][] = $edge[0];
        }
        
        $parent = [0 => -1];
        $queue = [0];
        
        while (!empty($queue)) {
            $node = array_shift($queue);
            foreach ($adjList[$node] as $neighbor) {
                if ($neighbor == $parent[$node]) {
                    continue;
                }
                if (isset($parent[$neighbor])) {
                    return false;
                }
                $parent[$neighbor] = $node;
                $queue[] = $neighbor;
            }
        }
        
        return count($parent) == $n;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ


🔒 База собесов | 🔒 База тестовых

#easy
Задача: 263. Ugly Number

Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.

Дано целое число n, верните true, если n является уродливым числом.

Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

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

1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.

2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.

3️⃣Если после всех делений n равно 1, верните true, иначе верните false.

😎 Решение:

class Solution {
    function isUgly($n) {
        if ($n <= 0) {
            return false;
        }
        foreach ([2, 3, 5] as $factor) {
            $n = $this->keepDividingWhenDivisible($n, $factor);
        }
        return $n == 1;
    }

    private function keepDividingWhenDivisible($dividend, $divisor) {
        while ($dividend % $divisor == 0) {
            $dividend /= $divisor;
        }
        return $dividend;
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых