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

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

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

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

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

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

class Solution {
    function isBipartite($graph) {
        $color = [];
        for ($node = 0; $node < count($graph); $node++) {
            if (!isset($color[$node])) {
                $stack = [$node];
                $color[$node] = 0;
                while (!empty($stack)) {
                    $currentNode = array_pop($stack);
                    foreach ($graph[$currentNode] as $neighbor) {
                        if (!isset($color[$neighbor])) {
                            $stack[] = $neighbor;
                            $color[$neighbor] = $color[$currentNode] ^ 1;
                        } elseif ($color[$neighbor] == $color[$currentNode]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

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

Задача: 583. Delete Operation for Two Strings
Сложность: medium

Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.

Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

1⃣Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

2⃣Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

3⃣Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎 Решение:

class Solution {
    function minDistance($word1, $word2) {
        $m = strlen($word1);
        $n = strlen($word2);
        $dp = array_fill(0, $n + 1, 0);

        for ($i = 0; $i <= $m; $i++) {
            $temp = array_fill(0, $n + 1, 0);
            for ($j = 0; $j <= $n; $j++) {
                if ($i == 0 || $j == 0) {
                    $temp[$j] = $i + $j;
                } else if ($word1[$i - 1] == $word2[$j - 1]) {
                    $temp[$j] = $dp[$j - 1];
                } else {
                    $temp[$j] = 1 + min($dp[$j], $temp[$j - 1]);
                }
            }
            $dp = $temp;
        }

        return $dp[$n];
    }
}

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

Задача: 836. Rectangle Overlap
Сложность: easy

Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y.

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

Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false.

Пример:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

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

1⃣Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]).

2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]).

3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $rec1
     * @param Integer[] $rec2
     * @return Boolean
     */
    function isRectangleOverlap($rec1, $rec2) {
        return min($rec1[2], $rec2[2]) > max($rec1[0], $rec2[0]) &&
               min($rec1[3], $rec2[3]) > max($rec1[1], $rec2[1]);
    }
}

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

Задача: 977. Squares of a Sorted Array
Сложность: easy

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

Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

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

1⃣Создайте массив квадратов каждого элемента.

2⃣Отсортируйте массив квадратов.

3⃣Верните отсортированный массив квадратов.

😎 Решение:

class Solution {
    function sortedSquares($nums) {
        $ans = array_map(function($num) {
            return $num * $num;
        }, $nums);
        sort($ans);
        return $ans;
    }
}

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

Задача: 1472. Design Browser History
Сложность: medium

У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории.

Реализуйте класс BrowserHistory:
BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера.
void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд.
string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов.
string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов.

Пример:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

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

1⃣Инициализация:
Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей.

2⃣Посещение URL:
Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future.

3⃣Навигация назад и вперед:
Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым.
Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым.

😎 Решение:

class BrowserHistory {
    private $history;
    private $future;
    private $current;
    
    function __construct($homepage) {
        $this->history = [];
        $this->future = [];
        $this->current = $homepage;
    }
    
    function visit($url) {
        array_push($this->history, $this->current);
        $this->current = $url;
        $this->future = [];
    }
    
    function back($steps) {
        while ($steps > 0 && count($this->history) > 0) {
            array_push($this->future, $this->current);
            $this->current = array_pop($this->history);
            $steps--;
        }
        return $this->current;
    }
    
    function forward($steps) {
        while ($steps > 0 && count($this->future) > 0) {
            array_push($this->history, $this->current);
            $this->current = array_pop($this->future);
            $steps--;
        }
        return $this->current;
    }
}

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