Задача: 1233. Remove Sub-Folders from the Filesystem
Сложность: medium

Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.

Пример:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

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

1⃣Сортировка папок:
Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками.

2⃣Фильтрация вложенных папок:
Будем использовать переменную для отслеживания текущей родительской папки.

3⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список.

😎 Решение:

function removeSubfolders($folder) {
    sort($folder);
    $result = [];
    $parent = "";
    
    foreach ($folder as $path) {
        if (empty($parent) || strpos($path, $parent . "/") !== 0) {
            $parent = $path;
            $result[] = $path;
        }
    }
    
    return $result;
}

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

Задача: 999. Available Captures for Rook
Сложность: easy

Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.

Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

1⃣Поиск ладьи:
Найдите координаты белой ладьи "R" на шахматной доске.

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

3⃣Подсчет атакованных пешек:
Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек.
Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении.

😎 Решение:

class Solution {
    function numRookCaptures($board) {
        $countPawns = function($x, $y, $dx, $dy) use ($board) {
            while ($x >= 0 && $x < 8 && $y >= 0 && $y < 8) {
                if ($board[$x][$y] == 'B') break;
                if ($board[$x][$y] == 'p') return 1;
                $x += $dx;
                $y += $dy;
            }
            return 0;
        };

        for ($i = 0; $i < 8; $i++) {
            for ($j = 0; $j < 8; $j++) {
                if ($board[$i][$j] == 'R') {
                    return $countPawns($i, $j, -1, 0) + $countPawns($i, $j, 1, 0) +
                           $countPawns($i, $j, 0, -1) + $countPawns($i, $j, 0, 1);
                }
            }
        }
        return 0;
    }
}

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

Задача: 67. Add Binary
Сложность: easy

Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки.

Пример:

Input: a = "11", b = "1"
Output: "100"

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

1⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10).

2⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит.

3⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена.

😎 Решение:

function addBinary($a, $b) {
    $n = strlen($a);
    $m = strlen($b);
    if ($n < $m) return addBinary($b, $a);

    $result = [];
    $carry = 0;
    $j = $m - 1;
    for ($i = $n - 1; $i >= 0; --$i) {
        if ($a[$i] === "1") ++$carry;
        if ($j >= 0 && $b[$j] === "1") ++$carry;

        array_push($result, strval($carry % 2));
        $carry = intdiv($carry, 2);
        $j--;
    }
    if ($carry === 1) array_push($result, "1");
    return implode("", array_reverse($result));
}

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

Задача: 89. Gray Code
Сложность: medium

Последовательность Грея с n-битами — это последовательность из 2^n целых чисел, где:

1. Каждое число находится в включающем диапазоне от 0 до 2^n - 1,
2. Первое число равно 0,
3. Каждое число встречается в последовательности не более одного раза,
4. Двоичное представление каждой пары соседних чисел отличается ровно на один бит,
5. Двоичное представление первого и последнего чисел отличается ровно на один бит.

Для заданного числа n возвращается любая допустимая последовательность Грея с n-битами.

Пример:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

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

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

2⃣Инициализируйте множество visited. Это позволяет отслеживать числа, присутствующие в текущей последовательности, чтобы избежать повторения.
Начните с числа 0.
В функции grayCodeHelper() используйте цикл for, чтобы найти каждое возможное число (next), которое может быть сгенерировано путем изменения одного бита последнего числа в списке результатов (current). Делайте это, переключая i-ый бит на каждой итерации. Поскольку максимально возможное количество битов в любом числе последовательности равно n, необходимо переключить n битов.

3⃣Если next не присутствует в множестве использованных чисел (isPresent), добавьте его в список результатов и множество isPresent.
Продолжайте поиск с next.
Если grayCodeHelper(next) возвращает true, это означает, что допустимая последовательность найдена. Дальнейший поиск не требуется (ранняя остановка). Это раннее завершение улучшает время выполнения.
Если с next не найдена допустимая последовательность, удаляем его из списка результатов и множества isPresent и продолжаем поиск.
При достижении базового условия, когда длина текущей последовательности равна 2^n, возвращаем true.
Выход из цикла for означает, что с current в качестве последнего числа не найдена допустимая последовательность кода Грея. Поэтому возвращаем false.

😎 Решение:

class Solution {
    public function grayCode($n) {
        $result = [0];
        $isPresent = [0 => true];
        $this->grayCodeHelper($result, $n, $isPresent);
        return $result;
    }

    private function grayCodeHelper(&$result, $n, &$isPresent) {
        if (count($result) === (1 << $n)) {
            return true;
        }
        $current = $result[count($result) - 1];
        for ($i = 0; $i < $n; $i++) {
            $nextNum = $current ^ (1 << $i);
            if (!isset($isPresent[$nextNum])) {
                $isPresent[$nextNum] = true;
                array_push($result, $nextNum);
                if ($this->grayCodeHelper($result, $n, $isPresent)) {
                    return true;
                }
                unset($isPresent[$nextNum]);
                array_pop($result);
            }
        }
        return false;
    }
}

$solution = new Solution();
$n = 2; 
$result = $solution->grayCode($n);
print_r($result);

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

Задача: 317. Shortest Distance from All Buildings
Сложность: hard

Дана сетка m x n, содержащая значения 0, 1 или 2, где:
каждое 0 обозначает пустую землю, по которой можно свободно проходить,
каждое 1 обозначает здание, через которое нельзя пройти,
каждое 2 обозначает препятствие, через которое нельзя пройти.
Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо.
Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1.
Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи.

Пример:

Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7

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

1⃣Инициализация и запуск BFS
Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки.

2⃣Обработка BFS и обновление расстояний
При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX.

3⃣Обновление и возврат минимального расстояния
Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1.

😎 Решение:

class Solution {
    private function bfs(&$grid, $row, $col, $totalHouses) {
        $dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        $rows = count($grid);
        $cols = count($grid[0]);
        $distanceSum = 0;
        $housesReached = 0;
        $steps = 0;
        $q = [[$row, $col]];
        $vis = array_fill(0, $rows, array_fill(0, $cols, false));
        $vis[$row][$col] = true;

        while (!empty($q) && $housesReached != $totalHouses) {
            $size = count($q);
            while ($size-- > 0) {
                list($r, $c) = array_shift($q);
                if ($grid[$r][$c] == 1) {
                    $distanceSum += $steps;
                    $housesReached++;
                    continue;
                }
                foreach ($dirs as $dir) {
                    $nr = $r + $dir[0];
                    $nc = $c + $dir[1];
                    if ($nr >= 0 && $nc >= 0 && $nr < $rows && $nc < $cols && !$vis[$nr][$nc] && $grid[$nr][$nc] != 2) {
                        $vis[$nr][$nc] = true;
                        array_push($q, [$nr, $nc]);
                    }
                }
            }
            $steps++;
        }

        if ($housesReached != $totalHouses) {
            for ($r = 0; $r < $rows; $r++) {
                for ($c = 0; $c < $cols; $c++) {
                    if ($grid[$r][$c] == 0 && $vis[$r][$c]) {
                        $grid[$r][$c] = 2;
                    }
                }
            }
            return PHP_INT_MAX;
        }
        return $distanceSum;
    }

    public function shortestDistance($grid) {
        $minDistance = PHP_INT_MAX;
        $rows = count($grid);
        $cols = count($grid[0]);
        $totalHouses = 0;

        foreach ($grid as $row) {
            foreach ($row as $cell) {
                if ($cell == 1) {
                    $totalHouses++;
                }
            }
        }

        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] == 0) {
                    $minDistance = min($minDistance, $this->bfs($grid, $r, $c, $totalHouses));
                }
            }
        }

        return $minDistance == PHP_INT_MAX ? -1 : $minDistance;
    }
}

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

Задача: 623. Add One Row to Tree
Сложность: medium

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

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

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎 Решение:

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 addOneRow($root, $val, $depth) {
    if ($depth == 1) {
        return new TreeNode($val, $root);
    }
    
    $queue = [$root];
    $currentDepth = 1;
    
    while (!empty($queue)) {
        if ($currentDepth == $depth - 1) {
            foreach ($queue as $node) {
                $node->left = new TreeNode($val, $node->left);
                $node->right = new TreeNode($val, null, $node->right);
            }
            break;
        }
        $currentDepth++;
        $nextQueue = [];
        foreach ($queue as $node) {
            if ($node->left !== null) {
                $nextQueue[] = $node->left;
            }
            if ($node->right !== null) {
                $nextQueue[] = $node->right;
            }
        }
        $queue = $nextQueue;
    }
    
    return $root;
}

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

Задача: 1535. Find the Winner of an Array Game
Сложность: medium

Дан целочисленный массив arr из различных целых чисел и целое число k.

Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.

Верните число, которое выиграет игру.

Гарантируется, что у игры будет победитель.

Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

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

1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.

2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.

3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.

😎 Решение:

class Solution {
    function getWinner($arr, $k) {
        $maxElement = $arr[0];
        $queue = array_slice($arr, 1);
        for ($i = 1; $i < count($arr); $i++) {
            $maxElement = max($maxElement, $arr[$i]);
        }
        
        $curr = $arr[0];
        $winstreak = 0;
        
        while (!empty($queue)) {
            $opponent = array_shift($queue);
            
            if ($curr > $opponent) {
                array_push($queue, $opponent);
                $winstreak++;
            } else {
                array_push($queue, $curr);
                $curr = $opponent;
                $winstreak = 1;
            }
            
            if ($winstreak == $k || $curr == $maxElement) {
                return $curr;
            }
        }
        
        return -1;
    }
}

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

Задача: 505. The Maze II
Сложность: medium

Дан лабиринт, где 0 — пустая ячейка, 1 — стена.
Мячик может катиться по пустым клеткам, пока не упадёт в стену.
Нужно найти минимальное количество шагов, чтобы добраться от start до destination, где шаг — это каждое пустое пространство. Если добраться нельзя — вернуть -1.

Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

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

1⃣Инициализация
Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.

2⃣Обход лабиринта
Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов.

3⃣Обновление расстояний
Если достигнутая новая позиция может быть достигнута меньшим числом шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода верните минимальное расстояние до пункта назначения или -1, если его нельзя достичь.

😎 Решение:

class Solution {
    function shortestDistance($maze, $start, $destination) {
        $m = count($maze);
        $n = count($maze[0]);
        $distance = array_fill(0, $m, array_fill(0, $n, PHP_INT_MAX));
        $distance[$start[0]][$start[1]] = 0;
        $directions = [[0, 1], [0, -1], [-1, 0], [1, 0]];
        $queue = [[$start[0], $start[1]]];
        
        while (!empty($queue)) {
            list($sx, $sy) = array_shift($queue);
            foreach ($directions as list($dx, $dy)) {
                $x = $sx + $dx;
                $y = $sy + $dy;
                $count = 0;
                while ($x >= 0 && $y >= 0 && $x < $m && $y < $n && $maze[$x][$y] == 0) {
                    $x += $dx;
                    $y += $dy;
                    $count++;
                }
                $x -= $dx;
                $y -= $dy;
                if ($distance[$sx][$sy] + $count < $distance[$x][$y]) {
                    $distance[$x][$y] = $distance[$sx][$sy] + $count;
                    array_push($queue, [$x, $y]);
                }
            }
        }
        
        return $distance[$destination[0]][$destination[1]] == PHP_INT_MAX ? -1 : $distance[$destination[0]][$destination[1]];
    }
}

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

Задача: 445. Add Two Numbers II
Сложность: medium

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

Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

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

1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎 Решение:

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;
        $temp = null;
        while ($head != null) {
            $temp = $head->next;
            $head->next = $prev;
            $prev = $head;
            $head = $temp;
        }
        return $prev;
    }

    function addTwoNumbers($l1, $l2) {
        $r1 = $this->reverseList($l1);
        $r2 = $this->reverseList($l2);

        $totalSum = 0;
        $carry = 0;
        $ans = new ListNode(0);
        while ($r1 != null || $r2 != null) {
            if ($r1 != null) {
                $totalSum += $r1->val;
                $r1 = $r1->next;
            }
            if ($r2 != null) {
                $totalSum += $r2->val;
                $r2 = $r2->next;
            }

            $ans->val = $totalSum % 10;
            $carry = intdiv($totalSum, 10);
            $head = new ListNode($carry);
            $head->next = $ans;
            $ans = $head;
            $totalSum = $carry;
        }

        return $carry == 0 ? $ans->next : $ans;
    }
}

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

Задача: 554. Brick Wall
Сложность: medium

Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.
Нарисуйте вертикальную линию от верха до низа, пересекающую наименьшее количество кирпичей. Если ваша линия проходит по краю кирпича, то кирпич не считается пересеченным. Вы не можете нарисовать линию прямо по одному из двух вертикальных краев стены, так как в этом случае линия очевидно не пересечет ни одного кирпича.
Дан двумерный массив wall, содержащий информацию о стене, верните минимальное количество пересеченных кирпичей после проведения такой вертикальной линии.

Пример:

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

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

1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду.

2⃣Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите массив pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i].

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

😎 Решение:

class Solution {
    function leastBricks($wall) {
        $pos = array_fill(0, count($wall), 0);
        $sum = array_sum($wall[0]);
        $res = PHP_INT_MAX;

        while ($sum != 0) {
            $count = 0;
            foreach ($wall as $i => &$row) {
                if ($row[$pos[$i]] != 0) {
                    $count++;
                } else {
                    $pos[$i]++;
                }
                $row[$pos[$i]]--;
            }
            $sum--;
            $res = min($res, $count);
        }

        return $res;
    }
}

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

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

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
    private $count = 0;

    function dfs($node, $parent, $adj) {
        if (!isset($adj[$node])) return;
        foreach ($adj[$node] as $nei) {
            list($neighbor, $sign) = $nei;
            if ($neighbor != $parent) {
                $this->count += $sign;
                $this->dfs($neighbor, $node, $adj);
            }
        }
    }

    function minReorder($n, $connections) {
        $adj = [];
        foreach ($connections as $connection) {
            $adj[$connection[0]][] = [$connection[1], 1];
            $adj[$connection[1]][] = [$connection[0], 0];
        }
        $this->dfs(0, -1, $adj);
        return $this->count;
    }
}

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

Задача: 1125. Smallest Sufficient Team
Сложность: hard

В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.

Рассмотрим достаточную команду: набор людей, такой что для каждого необходимого навыка из req_skills, есть по крайней мере один человек в команде, который обладает этим навыком. Мы можем представить эти команды индексами каждого человека.

Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.

Гарантируется, что ответ существует.

Пример:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [["algorithms","math","java"],["algorithms","math","reactjs"],
["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

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

1⃣Инициализация и создание масок навыков:
Определите количество людей n и количество необходимых навыков m.
Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.
Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.

2⃣Динамическое программирование (DP):
Создайте массив dp размера 2^m и заполните его значениями (1 << n) - 1.
Установите dp[0] в 0 (базовый случай).
Для каждого skillsMask от 1 до 2^m - 1:
- для каждого человека i:
- вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i].
- если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов).

3⃣Формирование ответа:
Извлеките ответ из dp и верните массив индексов людей, составляющих минимальную достаточную команду.

😎 Решение:

class Solution {
    function smallestSufficientTeam($req_skills, $people) {
        $n = count($people);
        $m = count($req_skills);
        $skillId = array_flip($req_skills);
        $skillsMaskOfPerson = array_fill(0, $n, 0);

        foreach ($people as $i => $person) {
            foreach ($person as $skill) {
                if (isset($skillId[$skill])) {
                    $skillsMaskOfPerson[$i] |= 1 << $skillId[$skill];
                }
            }
        }

        $dp = array_fill(0, 1 << $m, (1 << $n) - 1);
        $dp[0] = 0;

        for ($skillsMask = 1; $skillsMask < (1 << $m); $skillsMask++) {
            foreach ($skillsMaskOfPerson as $i => $mask) {
                $smallerSkillsMask = $skillsMask & ~$mask;
                if ($smallerSkillsMask != $skillsMask) {
                    $peopleMask = $dp[$smallerSkillsMask] | (1 << $i);
                    if (substr_count(decbin($peopleMask), '1') < substr_count(decbin($dp[$skillsMask]), '1')) {
                        $dp[$skillsMask] = $peopleMask;
                    }
                }
            }
        }

        $answerMask = $dp[(1 << $m) - 1];
        $result = [];
        for ($i = 0; $i < $n; $i++) {
            if (($answerMask >> $i) & 1) {
                $result[] = $i;
            }
        }
        return $result;
    }
}

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

Задача: 173. Binary Search Tree Iterator
Сложность: medium

Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order:
BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST.
boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false.
int next(): Перемещает указатель вправо, затем возвращает число на указателе.
Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST.
Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число.

Пример:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

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

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

2⃣Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево.

3⃣Когда у нас будут все узлы в массиве, нам просто нужен указатель или индекс в этом массиве для реализации двух функций next и hasNext. Всякий раз, когда вызывается hasNext, мы просто проверяем, достиг ли индекс конца массива или нет. При вызове функции next мы просто возвращаем элемент, на который указывает индекс. Также, после вызова функции next, мы должны переместить индекс на один шаг вперед, чтобы имитировать прогресс нашего итератора.

😎 Решение:

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

class BSTIterator {
    private $nodesSorted = [];
    private $index = -1;

    function __construct($root) {
        $this->inorder($root);
    }

    private function inorder($root) {
        if ($root === null) {
            return;
        }

        $this->inorder($root->left);
        $this->nodesSorted[] = $root->val;
        $this->inorder($root->right);
    }

    public function next() {
        return $this->nodesSorted[++$this->index];
    }

    public function hasNext() {
        return $this->index + 1 < count($this->nodesSorted);
    }
}

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

Задача: 43. Multiply Strings
Сложность: hard

Даны две строки num1 и num2, представляющие неотрицательные целые числа. Необходимо вернуть их произведение в виде строки.
Запрещено использовать встроенные библиотеки для работы с большими числами (BigInteger) и напрямую преобразовывать строки в числа.

Пример:

  
Input: num1 = "2", num2 = "3"  
Output: "6"  

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

1⃣Перевернуть строки num1 и num2.

2⃣Умножить каждую цифру num2[j] на каждую цифру num1[i], добавляя результаты в массив ans.

3⃣ Обработать переносы (carry), чтобы числа не превышали 9.

😎 Решение:

function multiply($num1, $num2) {
    if ($num1 === "0" || $num2 === "0") {
        return "0";
    }

    $n = strlen($num1);
    $m = strlen($num2);
    $ans = array_fill(0, $n + $m, 0);

    for ($i = $n - 1; $i >= 0; $i--) {
        for ($j = $m - 1; $j >= 0; $j--) {
            $mul = ($num1[$i] - '0') * ($num2[$j] - '0');
            $sum = $mul + $ans[$i + $j + 1];

            $ans[$i + $j + 1] = $sum % 10;
            $ans[$i + $j] += intdiv($sum, 10);
        }
    }

    while (count($ans) > 1 && $ans[0] === 0) {
        array_shift($ans);
    }

    return implode("", $ans);
}

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

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

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

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями.

3⃣Начните обход в глубину (DFS).

😎 Решение:

class Solution {
    function dfs($node, $parent, $adj, $labels, &$ans) {
        $nodeCounts = array_fill(0, 26, 0);
        $nodeCounts[ord($labels[$node]) - ord('a')] = 1;

        if (!isset($adj[$node])) return $nodeCounts;

        foreach ($adj[$node] as $child) {
            if ($child == $parent) continue;
            $childCounts = $this->dfs($child, $node, $adj, $labels, $ans);
            for ($i = 0; $i < 26; $i++) {
                $nodeCounts[$i] += $childCounts[$i];
            }
        }

        $ans[$node] = $nodeCounts[ord($labels[$node]) - ord('a')];
        return $nodeCounts;
    }

    function countSubTrees($n, $edges, $labels) {
        $adj = [];
        foreach ($edges as $edge) {
            $adj[$edge[0]][] = $edge[1];
            $adj[$edge[1]][] = $edge[0];
        }

        $ans = array_fill(0, $n, 0);
        $this->dfs(0, -1, $adj, $labels, $ans);
        return $ans;
    }
}

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

Задача: 168. Excel Sheet Column Title
Сложность: easy

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.

Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1
Output: "A"

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

1⃣Инициализация пустой строки ans:
Создайте пустую строку ans, которая будет хранить заголовок столбца.

2⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26

3⃣Переворот и возврат результата:
Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке.
Верните полученный заголовок столбца.

😎 Решение:

class Solution {
    function convertToTitle($columnNumber) {
        $ans = "";

        while ($columnNumber > 0) {
            $columnNumber--;
            $ans = chr($columnNumber % 26 + ord('A')) . $ans;
            $columnNumber = intdiv($columnNumber, 26);
        }

        return $ans;
    }
}

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

Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎 Решение:

class Solution {
    function shortestAlternatingPaths($n, $redEdges, $blueEdges) {
        $adj = [];
        foreach ($redEdges as $edge) {
            $adj[$edge[0]][] = [$edge[1], 0];
        }
        foreach ($blueEdges as $edge) {
            $adj[$edge[0]][] = [$edge[1], 1];
        }

        $answer = array_fill(0, $n, -1);
        $visit = array_fill(0, $n, [false, false]);
        $queue = [[0, 0, -1]];
        $answer[0] = 0;
        $visit[0][0] = true;
        $visit[0][1] = true;

        while ($queue) {
            list($node, $steps, $prevColor) = array_shift($queue);
            if (!isset($adj[$node])) continue;
            foreach ($adj[$node] as $nei) {
                list($neighbor, $color) = $nei;
                if (!$visit[$neighbor][$color] && $color != $prevColor) {
                    if ($answer[$neighbor] == -1) {
                        $answer[$neighbor] = $steps + 1;
                    }
                    $visit[$neighbor][$color] = true;
                    $queue[] = [$neighbor, $steps + 1, $color];
                }
            }
        }
        return $answer;
    }
}

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

Задача: 526. Beautiful Arrangement
Сложность: medium

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.

Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

1⃣Инициализация и подготовка массива:
Создайте массив чисел от 1 до N и инициализируйте счетчик красивых перестановок.
Создайте функцию для перестановки элементов массива.

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

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

😎 Решение:

class Solution {
    private $count = 0;
    
    function countArrangement($N) {
        $nums = range(1, $N);
        $this->permute($nums, 0);
        return $this->count;
    }
    
    private function permute(&$nums, $l) {
        if ($l == count($nums)) {
            $this->count++;
        }
        for ($i = $l; $i < count($nums); $i++) {
            $this->swap($nums, $i, $l);
            if ($nums[$l] % ($l + 1) == 0 || ($l + 1) % $nums[$l] == 0) {
                $this->permute($nums, $l + 1);
            }
            $this->swap($nums, $i, $l);
        }
    }
    
    private function swap(&$nums, $x, $y) {
        $temp = $nums[$x];
        $nums[$x] = $nums[$y];
        $nums[$y] = $temp;
    }
}

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

Задача: 409. Longest Palindrome
Сложность: easy

Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.

Пример:

Input: s = "abccccdd"
Output: 7

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

1⃣Создайте словарь для подсчета количества каждого символа в строке.

2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.

3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.

😎 Решение:

function longestPalindrome($s) {
    $charCount = [];
    foreach (str_split($s) as $char) {
        if (isset($charCount[$char])) {
            $charCount[$char]++;
        } else {
            $charCount[$char] = 1;
        }
    }
    $length = 0;
    $oddFound = false;
    foreach ($charCount as $count) {
        if ($count % 2 == 0) {
            $length += $count;
        } else {
            $length += $count - 1;
            $oddFound = true;
        }
    }
    return $oddFound ? $length + 1 : $length;
}

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