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

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

function minMalwareSpread($graph, $initial) {
    $n = count($graph);
    $components = [];
    $visited = [];
    
    function dfs($graph, $node, &$component, &$visited) {
        $stack = [$node];
        while (!empty($stack)) {
            $u = array_pop($stack);
            if (!isset($visited[$u])) {
                $visited[$u] = true;
                $component[] = $u;
                foreach ($graph[$u] as $v => $connected) {
                    if ($connected == 1 && !isset($visited[$v])) {
                        $stack[] = $v;
                    }
                }
            }
        }
    }
    
    for ($i = 0; $i < $n; $i++) {
        if (!isset($visited[$i])) {
            $component = [];
            dfs($graph, $i, $component, $visited);
            $components[] = $component;
        }
    }
    
    $infectedInComponent = array_fill(0, count($components), 0);
    $nodeToComponent = array_fill(0, $n, -1);
    
    foreach ($components as $idx => $component) {
        foreach ($component as $node) {
            $nodeToComponent[$node] = $idx;
            if (in_array($node, $initial)) {
                $infectedInComponent[$idx]++;
            }
        }
    }
    
    $minInfected = PHP_INT_MAX;
    $resultNode = min($initial);
    
    foreach ($initial as $node) {
        $componentIdx = $nodeToComponent[$node];
        if ($infectedInComponent[$componentIdx] == 1) {
            $componentSize = count($components[$componentIdx]);
            if ($componentSize < $minInfected || ($componentSize == $minInfected && $node < $resultNode)) {
                $minInfected = $componentSize;
                $resultNode = $node;
            }
        }
    }
    
    return $resultNode;
}

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

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

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

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

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

3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.

😎 Решение:

function longestWord($words) {
    sort($words);
    $validWords = ["" => true];
    $longest = "";
    foreach ($words as $word) {
        if (isset($validWords[substr($word, 0, -1)])) {
            $validWords[$word] = true;
            if (strlen($word) > strlen($longest)) {
                $longest = $word;
            }
        }
    }
    return $longest;
}

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

Задача: 743. Network Delay Time
Сложность: medium

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

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

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

1⃣Представьте граф в виде списка смежности.

2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.

3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎 Решение:

function networkDelayTime($times, $n, $k) {
    $graph = [];
    for ($i = 1; $i <= $n; $i++) {
        $graph[$i] = [];
    }
    foreach ($times as $time) {
        $graph[$time[0]][] = [$time[1], $time[2]];
    }

    $minHeap = new SplPriorityQueue();
    $minHeap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    $minHeap->insert([$k, 0], 0);
    $minTime = array_fill(1, $n, INF);
    $minTime[$k] = 0;

    while (!$minHeap->isEmpty()) {
        $data = $minHeap->extract();
        $time = $data['priority'];
        $node = $data['data'][0];
        foreach ($graph[$node] as $neighbor) {
            $newTime = $time + $neighbor[1];
            if ($newTime < $minTime[$neighbor[0]]) {
                $minTime[$neighbor[0]] = $newTime;
                $minHeap->insert([$neighbor[0], $newTime], -$newTime);
            }
        }
    }

    $maxTime = max($minTime);
    return $maxTime == INF ? -1 : $maxTime;
}

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

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

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

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

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

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

1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

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

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

class Solution {
    function isPossible($nums) {
        $freq = array_count_values($nums);
        $need = [];
        
        foreach ($nums as $num) {
            if ($freq[$num] == 0) continue;

            if (isset($need[$num]) && $need[$num] > 0) {
                $need[$num]--;
                $need[$num + 1] = isset($need[$num + 1]) ? $need[$num + 1] + 1 : 1;
            } elseif (isset($freq[$num + 1]) && $freq[$num + 1] > 0 && isset($freq[$num + 2]) && $freq[$num + 2] > 0) {
                $freq[$num + 1]--;
                $freq[$num + 2]--;
                $need[$num + 3] = isset($need[$num + 3]) ? $need[$num + 3] + 1 : 1;
            } else {
                return false;
            }
            $freq[$num]--;
        }
        
        return true;
    }
}

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

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

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.
Вы ограничены следующими правилами:
Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution {
    function generatePossibleResults($a, $b) {
        $res = [$a + $b, $a - $b, $b - $a, $a * $b];
        if ($a != 0) $res[] = $b / $a;
        if ($b != 0) $res[] = $a / $b;
        return $res;
    }

    function checkIfResultReached($list) {
        if (count($list) == 1) return abs($list[0] - 24) <= 0.1;

        for ($i = 0; $i < count($list); $i++) {
            for ($j = $i + 1; $j < count($list); $j++) {
                $newList = [];
                for ($k = 0; $k < count($list); $k++) {
                    if ($k != $i && $k != $j) $newList[] = $list[$k];
                }
                foreach ($this->generatePossibleResults($list[$i], $list[$j]) as $res) {
                    $newList[] = $res;
                    if ($this->checkIfResultReached($newList)) return true;
                    array_pop($newList);
                }
            }
        }
        return false;
    }

    function judgePoint24($cards) {
        return $this->checkIfResultReached(array_map('floatval', $cards));
    }
}

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

Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard

У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.

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

Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

1⃣ Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов.

2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps.

3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов.

😎 Решение:

class Solution {
    /**
     * @param Integer[][] $graph
     * @return Integer
     */
    function shortestPathLength($graph) {
        $n = count($graph);
        if ($n == 1) return 0;
        
        $endingMask = (1 << $n) - 1;
        $seen = array_fill(0, $n, array_fill(0, $endingMask, false));
        $queue = [];
        
        for ($i = 0; $i < $n; $i++) {
            $queue[] = [$i, 1 << $i];
            $seen[$i][1 << $i] = true;
        }
        
        $steps = 0;
        while (!empty($queue)) {
            $nextQueue = [];
            foreach ($queue as [$node, $mask]) {
                foreach ($graph[$node] as $neighbor) {
                    $nextMask = $mask | (1 << $neighbor);
                    if ($nextMask == $endingMask) return 1 + $steps;
                    if (!$seen[$neighbor][$nextMask]) {
                        $seen[$neighbor][$nextMask] = true;
                        $nextQueue[] = [$neighbor, $nextMask];
                    }
                }
            }
            $steps++;
            $queue = $nextQueue;
        }
        
        return -1;
    }
}

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