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

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

Задача: 1244. Design A Leaderboard
Сложность: medium

Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста.

Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

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

1⃣addScore(playerId, score):
Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение.
Если игрок не существует, добавляем его с заданным счетом.

2⃣top(K):
Сортируем игроков по их счету в порядке убывания.
Возвращаем сумму очков K лучших игроков.

3⃣reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Leaderboard {
    private $scores;

    public function __construct() {
        $this->scores = [];
    }

    public function addScore($playerId, $score) {
        if (isset($this->scores[$playerId])) {
            $this->scores[$playerId] += $score;
        } else {
            $this->scores[$playerId] = $score;
        }
    }

    public function top($K) {
        arsort($this->scores);
        return array_sum(array_slice($this->scores, 0, $K));
    }

    public function reset($playerId) {
        $this->scores[$playerId] = 0;
    }
}

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

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

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    function balanceBST($root) {
        if (!$root) return null;

        $vineHead = new TreeNode(0);
        $vineHead->right = $root;
        $current = $vineHead;

        while ($current->right) {
            if ($current->right->left) {
                $this->rightRotate($current, $current->right);
            } else {
                $current = $current->right;
            }
        }

        $nodeCount = 0;
        $current = $vineHead->right;
        while ($current) {
            $nodeCount++;
            $current = $current->right;
        }

        $m = pow(2, floor(log($nodeCount + 1, 2))) - 1;
        $this->makeRotations($vineHead, $nodeCount - $m);
        while ($m > 1) {
            $m /= 2;
            $this->makeRotations($vineHead, $m);
        }

        return $vineHead->right;
    }

    private function rightRotate($parent, $node) {
        $tmp = $node->left;
        $node->left = $tmp->right;
        $tmp->right = $node;
        $parent->right = $tmp;
    }

    private function leftRotate($parent, $node) {
        $tmp = $node->right;
        $node->right = $tmp->left;
        $tmp->left = $node;
        $parent->right = $tmp;
    }

    private function makeRotations($vineHead, $count) {
        $current = $vineHead;
        for ($i = 0; $i < $count; $i++) {
            $tmp = $current->right;
            $this->leftRotate($current, $tmp);
            $current = $current->right;
        }
    }
}

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

Задача №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]

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

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

2⃣Если еще можно открыть скобку — добавляем ( и уменьшаем счетчик открытых.

3⃣Если есть закрытые скобки, которые можно закрыть — добавляем ).

😎 Решение:

class Solution { 

    private array $answer = []; 
    private string $current = ''; 

    function generateParenthesis($n) { 
        $this->generateParentheses($n, 0); 
        return $this->answer; 
    } 

    function generateParentheses($toOpen, $toClose) { 
        if ($toOpen == 0 && $toClose == 0) { 
            $this->answer[] = $this->current; 
            return; 
        } 

        if ($toOpen > 0) { 
            $this->current .= '('; 
            $this->generateParentheses($toOpen - 1, $toClose + 1); 
            $this->current = substr($this->current, 0, -1); 
        } 

        if ($toClose > 0) { 
            $this->current .= ')'; 
            $this->generateParentheses($toOpen, $toClose - 1); 
            $this->current = substr($this->current, 0, -1); 
        }         
    } 
}

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

Задача: 237. Delete Node in a Linked List
Сложность: medium

Дан односвязный список, требуется удалить конкретный узел, не имея доступа к head.
Гарантируется, что node не последний.

Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

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

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка.

😎 Решение:

class Solution {
    function deleteNode($node) {
        $node->val = $node->next->val;
        $node->next = $node->next->next;
    }
}

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

Задача: 205. Isomorphic Strings
Сложность: easy

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

        return true;
    }
}

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