Задача: 160. Intersection of Two Linked Lists
Сложность: easy

Даны головы двух односвязных списков headA и headB. Верните узел, в котором эти два списка пересекаются. Если два связанных списка не имеют пересечений, верните null.
Например, следующие два связанных списка начинают пересекаться в узле c1.

Пример:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

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

1⃣Сохранение ссылок из списка B:
Проходим по всем узлам списка B и сохраняем ссылки (адреса) каждого узла в хеш-таблицу. Это позволит нам быстро проверять, содержится ли узел из списка A в списке B.

2⃣Проверка узлов списка A:
Далее, для каждого узла из списка A проверяем, существует ли такой узел в хеш-таблице, созданной на предыдущем шаге. Если такой узел найден, то он является точкой пересечения, и мы возвращаем этот узел.

3⃣Обработка отсутствия пересечения:
Если до конца списка A не найдено ни одного узла, который бы совпал с узлами из хеш-таблицы, возвращаем null, указывая на отсутствие пересечения между списками.

😎 Решение:

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

class Solution {
    function getIntersectionNode($headA, $headB) {
        $nodesInB = [];
        
        while ($headB !== null) {
            $nodesInB[spl_object_hash($headB)] = $headB;
            $headB = $headB->next;
        }
        
        while ($headA !== null) {
            if (isset($nodesInB[spl_object_hash($headA)])) {
                return $headA;
            }
            $headA = $headA->next;
        }
        
        return null;
    }
}

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

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

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

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

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution {
    private $maxTime = -PHP_INT_MAX;
    
    function DFS($adjList, $informTime, $curr, $time) {
        $this->maxTime = max($this->maxTime, $time);
        foreach ($adjList[$curr] as $adjacent) {
            $this->DFS($adjList, $informTime, $adjacent, $time + $informTime[$curr]);
        }
    }
    
    function numOfMinutes($n, $headID, $manager, $informTime) {
        $adjList = array_fill(0, $n, []);
        for ($i = 0; $i < $n; $i++) {
            if ($manager[$i] != -1) {
                $adjList[$manager[$i]][] = $i;
            }
        }
        $this->DFS($adjList, $informTime, $headID, 0);
        return $this->maxTime;
    }
}

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

Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

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

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

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

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

3⃣Подсчет квадратных перестановок:
Подсчитайте количество перестановок, которые являются квадратными, и верните это значение.

😎 Решение:

class Solution {
    function numSquarefulPerms($nums) {
        sort($nums);
        $used = array_fill(0, count($nums), false);
        $result = [];
        $path = [];
        $this->backtrack($nums, $used, $path, $result);
        return count($result);
    }
    
    private function backtrack($nums, &$used, &$path, &$result) {
        if (count($path) == count($nums)) {
            if ($this->isSquareful($path)) {
                $result[implode(',', $path)] = true;
            }
            return;
        }
        
        for ($i = 0; $i < count($nums); $i++) {
            if ($used[$i] || ($i > 0 && $nums[$i] == $nums[$i - 1] && !$used[$i - 1])) continue;
            $path[] = $nums[$i];
            $used[$i] = true;
            $this->backtrack($nums, $used, $path, $result);
            array_pop($path);
            $used[$i] = false;
        }
    }
    
    private function isSquareful($perm) {
        for ($i = 0; $i < count($perm) - 1; $i++) {
            $sum = $perm[$i] + $perm[$i + 1];
            $root = (int)sqrt($sum);
            if ($root * $root != $sum) return false;
        }
        return true;
    }
}

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

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

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

class Solution {
    function fib($N) {
        if ($N <= 1) return $N;
        $current = 0;
        $prev1 = 1;
        $prev2 = 0;

        for ($i = 2; $i <= $N; $i++) {
            $current = $prev1 + $prev2;
            $prev2 = $prev1;
            $prev1 = $current;
        }
        return $current;
    }
}

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

Задача: 331. Verify Preorder Serialization of a Binary Tree
Сложность: medium

Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.
Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.
Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.

Пример:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

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

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

2⃣Итерация по элементам и проверка:
Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1.
Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию.
Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота.

3⃣Проверка завершения:
После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false.

😎 Решение:

class Solution {
    function isValidSerialization($preorder) {
        $slots = 1;
        $nodes = explode(',', $preorder);
        
        foreach ($nodes as $node) {
            $slots--;
            if ($slots < 0) {
                return false;
            }
            if ($node !== "#") {
                $slots += 2;
            }
        }
        
        return $slots == 0;
    }
}

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

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

2⃣Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.

3⃣Вернуть count.

😎 Решение:

function minDeletionSize($strs) {
    $count = 0;
    $rows = count($strs);
    $cols = strlen($strs[0]);
    for ($col = 0; $col < $cols; $col++) {
        for ($row = 1; $row < $rows; $row++) {
            if ($strs[$row][$col] < $strs[$row - 1][$col]) {
                $count++;
                break;
            }
        }
    }
    return $count;
}

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

Задача: 789. Escape The Ghosts
Сложность: medium

Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами.

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

Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом.

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

Пример:

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

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

1⃣Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели.

2⃣Если это так, мы можем гарантированно добраться до цели раньше любого привидения.

3⃣Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен.

😎 Решение:

class Solution {
    function escapeGhosts($ghosts, $target) {
        $taxi = function($P, $Q) {
            return abs($P[0] - $Q[0]) + abs($P[1] - $Q[1]);
        };

        $playerDistance = $taxi([0, 0], $target);
        foreach ($ghosts as $ghost) {
            if ($taxi($ghost, $target) <= $playerDistance) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 935. Knight Dialer
Сложность: medium

Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

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

2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

function knightDialer($n) {
    $MOD = 1000000007;
    $moves = [
        0 => [4, 6],
        1 => [6, 8],
        2 => [7, 9],
        3 => [4, 8],
        4 => [0, 3, 9],
        5 => [],
        6 => [0, 1, 7],
        7 => [2, 6],
        8 => [1, 3],
        9 => [2, 4]
    ];
    
    $dp = array_fill(0, 10, 1);
    
    for ($step = 1; $step < $n; $step++) {
        $newDp = array_fill(0, 10, 0);
        foreach ($dp as $i => $count) {
            foreach ($moves[$i] as $move) {
                $newDp[$move] = ($newDp[$move] + $count) % $MOD;
            }
        }
        $dp = $newDp;
    }
    
    return array_reduce($dp, function($acc, $val) use ($MOD) {
        return ($acc + $val) % $MOD;
    }, 0);
}

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

Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard

Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.

Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.

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

Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.

Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

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

1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.

2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.

3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.

😎 Решение:

class Solution {
    private $memo;
    private $done;
    private $n;
    private $MOD = 1000000007;
    private $hatsToPeople;

    function numberWays($hats) {
        $this->n = count($hats);
        $this->hatsToPeople = [];

        foreach ($hats as $i => $personHats) {
            foreach ($personHats as $hat) {
                if (!isset($this->hatsToPeople[$hat])) {
                    $this->hatsToPeople[$hat] = [];
                }
                $this->hatsToPeople[$hat][] = $i;
            }
        }

        $this->done = pow(2, $this->n) - 1;
        $this->memo = array_fill(0, 41, array_fill(0, $this->done, -1));

        return $this->dp(1, 0);
    }

    private function dp($hat, $mask) {
        if ($mask == $this->done) {
            return 1;
        }

        if ($hat > 40) {
            return 0;
        }

        if ($this->memo[$hat][$mask] != -1) {
            return $this->memo[$hat][$mask];
        }

        $ans = $this->dp($hat + 1, $mask);

        if (isset($this->hatsToPeople[$hat])) {
            foreach ($this->hatsToPeople[$hat] as $person) {
                if (($mask & (1 << $person)) == 0) {
                    $ans = ($ans + $this->dp($hat + 1, $mask | (1 << $person))) % $this->MOD;
                }
            }
        }

        $this->memo[$hat][$mask] = $ans;
        return $ans;
    }
}

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

Задача: 779. K-th Symbol in Grammar
Сложность: medium

Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10.

Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110.
Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк.

Пример:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

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

1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal.

2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal).

3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal).

😎 Решение:

class Solution {
    private function depthFirstSearch(int $n, int $k, int $rootVal): int {
        if ($n === 1) return $rootVal;
        $totalNodes = 1 << ($n - 1);
        if ($k > $totalNodes / 2) {
            $nextRootVal = $rootVal === 0 ? 1 : 0;
            return $this->depthFirstSearch($n - 1, $k - $totalNodes / 2, $nextRootVal);
        } else {
            $nextRootVal = $rootVal === 0 ? 0 : 1;
            return $this->depthFirstSearch($n - 1, $k, $nextRootVal);
        }
    }

    public function kthGrammar(int $n, int $k): int {
        return $this->depthFirstSearch($n, $k, 0);
    }
}

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

Задача: 1242. Web Crawler Multithreaded
Сложность: medium

Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.

Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.

Пример:

Input:
urls = [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.google.com",
  "https://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "https://news.yahoo.com/news/topics/"
Output: [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.yahoo.com/us"
]

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

1⃣Извлечь имя хоста из startUrl.
Использовать многопоточность для обработки URL-адресов.

2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения.

3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц.

😎 Решение:

class HtmlParser {
    public function getUrls($url) {
        return [];
    }
}

class Solution extends Threaded {
    private $visited;
    private $hostname;
    private $htmlParser;

    public function __construct($startUrl, $htmlParser) {
        $this->hostname = parse_url($startUrl, PHP_URL_HOST);
        $this->htmlParser = $htmlParser;
        $this->visited = new Volatile();
        $this->visited[$startUrl] = true;
    }

    public function crawl() {
        $pool = new Pool(10);
        $pool->submit(new CrawlTask($this, $this->htmlParser, $this->hostname, array_keys((array) $this->visited)));

        $pool->shutdown();
        return array_keys((array) $this->visited);
    }
}

class CrawlTask extends Collectable {
    private $solution;
    private $htmlParser;
    private $hostname;
    private $urls;

    public function __construct($solution, $htmlParser, $hostname, $urls) {
        $this->solution = $solution;
        $this->htmlParser = $htmlParser;
        $this->hostname = $hostname;
        $this->urls = $urls;
    }

    public function run() {
        foreach ($this->urls as $url) {
            foreach ($this->htmlParser->getUrls($url) as $nextUrl) {
                $nextHostname = parse_url($nextUrl, PHP_URL_HOST);
                if ($nextHostname == $this->hostname && !isset($this->solution->visited[$nextUrl])) {
                    $this->solution->visited[$nextUrl] = true;
                    $this->worker->stack(new CrawlTask($this->solution, $this->htmlParser, $this->hostname, [$nextUrl]));
                }
            }
        }
        $this->setGarbage();
    }
}

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

Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium

Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.

Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.

Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.

Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.

Пример:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

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

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

2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.

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

😎 Решение:

class Solution {
    function getSmallestString($n, $k) {
        $result = array_fill(0, $n, 'a');
        
        for ($position = 0; $position < $n; $position++) {
            $positionsLeft = ($n - $position - 1);
            if ($k > $positionsLeft * 26) {
                $add = $k - ($positionsLeft * 26);
                $result[$position] = chr(97 + $add - 1);
                $k -= $add;
            } else {
                $k -= 1;
            }
        }
        
        return implode('', $result);
    }
}

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.

Пример:

Input: n = 2, start = 3
Output: [3,2,0,1]

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

1⃣Генерация Грей-кода:
Генерация Грей-кода для чисел от 0 до 2𝑛−1

2⃣Определение начальной позиции:
Находим индекс числа start в последовательности Грей-кода.

3⃣Построение перестановки:
Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.

😎 Решение:

function circularPermutation($n, $start) {
    $grayCode = function($n) {
        $result = [];
        for ($i = 0; $i < (1 << $n); $i++) {
            $result[] = $i ^ ($i >> 1);
        }
        return $result;
    };

    $gray = $grayCode($n);
    $startIndex = array_search($start, $gray);
    return array_merge(array_slice($gray, $startIndex), array_slice($gray, 0, $startIndex));
}

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

Задача: 107. Binary Tree Level Order Traversal II
Сложность: medium

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

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

1⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels.

2⃣Добавьте значение узла в последний уровень в levels.

3⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1).

😎 Решение:

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;

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

class Solution {
    private $levels = [];

    private function helper($node, $level) {
        if (!$node) return;
        if (!isset($this->levels[$level])) $this->levels[$level] = [];
        array_push($this->levels[$level], $node->val);
        if ($node->left) $this->helper($node->left, $level + 1);
        if ($node->right) $this->helper($node->right, $level + 1);
    }

    public function levelOrderBottom($root) {
        $this->helper($root, 0);
        return array_reverse($this->levels);
    }
}

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

Задача: 190. Reverse Bits
Сложность: easy

Переверните биты заданного 32-битного беззнакового целого числа.

Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

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

1⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа.

2⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции.

3⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений.

😎 Решение:

class Solution {
    private $cache = [];

    function reverseByte($byte) {
        if (isset($this->cache[$byte])) {
            return $this->cache[$byte];
        }
        $value = ($byte * 0x0202020202 & 0x010884422010) % 1023;
        $this->cache[$byte] = $value;
        return $value;
    }

    function reverseBits($n) {
        $ret = 0;
        $power = 24;
        while ($n != 0) {
            $ret += $this->reverseByte($n & 0xff) << $power;
            $n = $n >> 8;
            $power -= 8;
        }
        return $ret;
    }
}

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

Задача: 408. Valid Word Abbreviation
Сложность: easy

Строку можно сократить, заменив любое количество не смежных, непустых подстрок их длинами. Длины не должны содержать ведущих нулей.
Например, строка "замена" может быть сокращена следующим образом (но не ограничивается этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("замена") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замены подстрок) Следующие сокращения не являются допустимыми:
"s55n" ("s ubsti tutio n", заменяемые подстроки смежные) "s010n" (содержит ведущие нули) "s0ubstitution" (заменяет пустую подстроку) Если задано строковое слово и аббревиатура abbr, верните, соответствует ли строка заданной аббревиатуре.
Подстрока - это непрерывная непустая последовательность символов в строке.

Пример:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

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

1⃣Инициализируйте два указателя: один для строки word и один для аббревиатуры abbr. Начните сравнение символов строки и аббревиатуры с начала.

2⃣Если символ аббревиатуры - это цифра, вычислите полное число и переместите указатель строки word на это количество символов. Если символ аббревиатуры - это буква, убедитесь, что он совпадает с текущим символом строки.

3⃣Повторяйте шаг 2, пока оба указателя не достигнут конца строки и аббревиатуры соответственно. Если это так, верните true, иначе false.

😎 Решение:

function validWordAbbreviation($word, $abbr) {
    $i = $j = 0;
    while ($i < strlen($word) && $j < strlen($abbr)) {
        if (is_numeric($abbr[$j])) {
            if ($abbr[$j] == '0') {
                return false;
            }
            $num = 0;
            while ($j < strlen($abbr) && is_numeric($abbr[$j])) {
                $num = $num * 10 + (int)$abbr[$j];
                $j++;
            }
            $i += $num;
        } else {
            if ($word[$i] != $abbr[$j]) {
                return false;
            }
            $i++;
            $j++;
        }
    }
    return $i == strlen($word) && $j == strlen($abbr);
}

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

Задача №27. Remove Element
Сложность: easy

Учитывая целочисленный массив nums и целочисленное значение val, удалите все вхождения val в nums на месте. Затем верните количество элементов, которые не равны val.

Пример:

Input: nums = [3,2,2,3], val = 3  
Output: 2, nums = [2,2,_]

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

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

2⃣Перебирать массив, копируя все элементы, не равные val, на позиции k.

3⃣Вернуть k как количество оставшихся элементов.

😎 Решение:

function removeElement(&$nums, $val) {
    $k = 0; 
    for ($i = 0; $i < count($nums); $i++) { 
        if ($nums[$i] != $val) {
            $nums[$k++] = $nums[$i];
        }  
    }  
    return $k;
}

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

Задача: 491. Non-decreasing Subsequences
Сложность: medium

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

Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

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

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

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

😎 Решение:

class Solution {
    function findSubsequences($nums) {
        $result = [];
        $sequence = [];
        $this->backtrack($nums, 0, $sequence, $result);
        return array_values($result);
    }

    private function backtrack($nums, $index, &$sequence, &$result) {
        if ($index == count($nums)) {
            if (count($sequence) >= 2) {
                $key = implode(',', $sequence);
                $result[$key] = $sequence;
            }
            return;
        }
        if (empty($sequence) || end($sequence) <= $nums[$index]) {
            $sequence[] = $nums[$index];
            $this->backtrack($nums, $index + 1, $sequence, $result);
            array_pop($sequence);
        }
        $this->backtrack($nums, $index + 1, $sequence, $result);
    }
}

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

Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

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

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

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

function findHeight($root) {
    if ($root === null) return -1;
    return 1 + max(findHeight($root->left), findHeight($root->right));
}

function fill(&$res, $root, $r, $c, $height) {
    if ($root === null) return;
    $res[$r][$c] = strval($root->val);
    if ($root->left !== null) {
        fill($res, $root->left, $r + 1, $c - (1 << ($height - $r - 1)), $height);
    }
    if ($root->right !== null) {
        fill($res, $root->right, $r + 1, $c + (1 << ($height - $r - 1)), $height);
    }
}

function printTree($root) {
    $height = findHeight($root);
    $m = $height + 1;
    $n = (1 << ($height + 1)) - 1;
    $res = array_fill(0, $m, array_fill(0, $n, ""));
    fill($res, $root, 0, intval(($n - 1) / 2), $height);
    return $res;
}

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

Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium

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;
    }
}

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