Задача: CodeTestcaseTest ResultTest Result1523. Count Odd Numbers in an Interval Range
Сложность: easy

### Условие задачи

Даны два неотрицательных целых числа low и high. Верните количество нечётных чисел между low и high (включительно).

Пример:

Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].

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

1⃣Проверьте, является ли число low нечётным. Это можно легко сделать с помощью оператора %, но мы используем побитовый оператор &, так как он более эффективен.

2⃣Если low нечётное, увеличьте его на 1.

3⃣Верните (high - low) / 2 + 1. Важный момент здесь - проверить, не стало ли low больше, чем high после увеличения. Это произойдёт, если low = high, и в этом случае следует вернуть 0.

😎 Решение:

class Solution {
    function countOdds($low, $high) {
        if (($low & 1) == 0) {
            $low++;
        }
        return $low > $high ? 0 : intdiv($high - $low, 2) + 1;
    }
}

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

Задача: 131. Palindrome Partitioning
Сложность: Medium

Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.

Пример:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

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

1⃣Инициация рекурсивного обхода:
В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start.
Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки.

2⃣Проверка на палиндром и продолжение поиска:
Для каждой сгенерированной подстроки проверяем, является ли она палиндромом.
Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова.

3⃣Возврат (Backtracking) и сохранение результатов:
Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат.

😎 Решение:

class Solution {
    public function partition($s) {
        $res = [];
        $this->dfs($s, [], $res);
        return $res;
    }

    private function dfs($s, $path, &$res) {
        if ($s === '') {
            $res[] = $path;
            return;
        }
        for ($i = 0; $i < strlen($s); $i++) {
            $cur = substr($s, 0, $i + 1);
            if ($this->isPalindrome($cur)) {
                $newPath = $path;
                array_push($newPath, $cur);
                $this->dfs(substr($s, $i + 1), $newPath, $res);
            }
        }
    }

    private function isPalindrome($s) {
        $lo = 0;
        $hi = strlen($s) - 1;
        while ($lo < $hi) {
            if ($s[$lo++] != $s[$hi--]) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 939. Minimum Area Rectangle
Сложность: medium

Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0.

Пример:

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

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

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

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

3⃣Если минимальная площадь остается бесконечной, вернуть 0. Иначе вернуть минимальную площадь.

😎 Решение:

function minAreaRect($points) {
    $pointSet = [];
    foreach ($points as $point) {
        $pointSet["{$point[0]},{$point[1]}"] = true;
    }
    
    $minArea = PHP_INT_MAX;
    $len = count($points);
    for ($i = 0; $i < $len; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            $x1 = $points[$i][0];
            $y1 = $points[$i][1];
            $x2 = $points[$j][0];
            $y2 = $points[$j][1];
            if ($x1 != $x2 && $y1 != $y2 && isset($pointSet["$x1,$y2"]) && isset($pointSet["$x2,$y1"])) {
                $minArea = min($minArea, abs($x2 - $x1) * abs($y2 - $y1));
            }
        }
    }
    
    return $minArea == PHP_INT_MAX ? 0 : $minArea;
}

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

Задача: 225. Implement Stack using Queues
Сложность: easy

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).
Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.
Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.

Пример:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.

2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

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

😎 Решение:

class MyStack {
    private $q1;
    private $q2;
    private $topElement;

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

    public function push($x) {
        array_push($this->q2, $x);
        $this->topElement = $x;
        while (!empty($this->q1)) {
            array_push($this->q2, array_shift($this->q1));
        }
        $temp = $this->q1;
        $this->q1 = $this->q2;
        $this->q2 = $temp;
    }

    public function pop() {
        $result = array_shift($this->q1);
        if (!empty($this->q1)) {
            $this->topElement = $this->q1[0];
        }
        return $result;
    }

    public function top() {
        return $this->topElement;
    }

    public function empty() {
        return empty($this->q1);
    }
}

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

Задача: 1491. Average Salary Excluding the Minimum and Maximum Salary
Сложность: easy

Вам дан массив уникальных целых чисел salary, где salary[i] — это зарплата i-го сотрудника.

Верните среднюю зарплату сотрудников, исключая минимальную и максимальную зарплату. Ответы, отличающиеся не более чем на 10^-5 от фактического ответа, будут приняты.

Пример:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

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

1⃣Инициализация переменных:
Установить minSalary в максимально возможное значение, maxSalary в минимально возможное значение и sum в 0.

2⃣Итерация по зарплатам:
Для каждой зарплаты добавить её к переменной sum.
Обновить переменную minSalary, если текущая зарплата меньше её значения.
Обновить переменную maxSalary, если текущая зарплата больше её значения.

3⃣Вычисление среднего значения:
Вернуть значение (sum - minSalary - maxSalary) / (N - 2), предварительно преобразовав числитель и знаменатель в double для точности.

😎 Решение:

class Solution {
    function average($salary) {
        $minSalary = PHP_INT_MAX;
        $maxSalary = PHP_INT_MIN;
        $sum = 0;

        foreach ($salary as $sal) {
            $sum += $sal;
            $minSalary = min($minSalary, $sal);
            $maxSalary = max($maxSalary, $sal);
        }

        return ($sum - $minSalary - $maxSalary) / (count($salary) - 2);
    }
}

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

Задача: 841. Keys and Rooms
Сложность: medium

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

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

class Solution {
    /**
     * @param Integer[][] $rooms
     * @return Boolean
     */
    function canVisitAllRooms($rooms) {
        $seen = array_fill(0, count($rooms), false);
        $seen[0] = true;
        $stack = [0];

        while (!empty($stack)) {
            $node = array_pop($stack);
            foreach ($rooms[$node] as $nei) {
                if (!$seen[$nei]) {
                    $seen[$nei] = true;
                    array_push($stack, $nei);
                }
            }
        }

        return !in_array(false, $seen);
    }
}

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

Задача: 132. Palindrome Partitioning II
Сложность: Hard

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

Пример:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

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

1⃣Определение задачи и начальные условия:
Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end.
Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut.
Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом).

2⃣Генерация подстрок и рекурсивный поиск:
Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки.

3⃣Условие палиндрома и рекурсивное разделение:
Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки

😎 Решение:

class Solution {
    public function minCut($s) {
        return $this->findMinimumCut($s, 0, strlen($s) - 1, strlen($s) - 1);
    }

    private function findMinimumCut($s, $start, $end, $minimumCut) {
        if ($start === $end || $this->isPalindrome($s, $start, $end)) {
            return 0;
        }
        for ($currentEndIndex = $start; $currentEndIndex <= $end; $currentEndIndex++) {
            if ($this->isPalindrome($s, $start, $currentEndIndex)) {
                $minimumCut = min(
                    $minimumCut,
                    1 + $this->findMinimumCut($s, $currentEndIndex + 1, $end, $minimumCut)
                );
            }
        }
        return $minimumCut;
    }

    private function isPalindrome($s, $start, $end) {
        while ($start < $end) {
            if ($s[$start++] !== $s[$end--]) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: 305. Number of Islands II
Сложность: hard

Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

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

1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.

3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.

😎 Решение

class UnionFind {
    private $parent, $rank, $count;
    public function __construct($size) { $this->parent = array_fill(0, $size, -1); $this->rank = array_fill(0, $size, 0); $this->count = 0; }
    public function addLand($x) { if ($this->parent[$x] < 0) { $this->parent[$x] = $x; $this->count++; } }
    public function isLand($x) { return $this->parent[$x] >= 0; }
    public function find($x) { if ($this->parent[$x] != $x) $this->parent[$x] = $this->find($this->parent[$x]); return $this->parent[$x]; }
    public function unionSet($x, $y) { $xset = $this->find($x); $yset = $this->find($y);
        if ($xset != $yset) { if ($this->rank[$xset] < $this->rank[$yset]) $this->parent[$xset] = $yset
        else { $this->parent[$yset] = $xset; if ($this->rank[$xset] == $this->rank[$yset]) $this->rank[$xset]++; }; $this->count--; } }
}

class Solution {
    public function numIslands2($m, $n, $positions) {
        $dsu = new UnionFind($m * $n); $x = [-1, 1, 0, 0]; $y = [0, 0, -1, 1]; $answer = [];
        foreach ($positions as $pos) { $land = $pos[0] * $n + $pos[1]; $dsu->addLand($land);
            for ($i = 0; $i < 4; $i++) { $nx = $pos[0] + $x[$i]; $ny = $pos[1] + $y[$i]; $neighbor = $nx * $n + $ny;
                if ($nx >= 0 && $nx < $m && $ny >= 0 && $ny < $n && $dsu->isLand($neighbor)) $dsu->unionSet($land, $neighbor); }
            $answer[] = $dsu->count; }
        return $answer;
    }
}

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

Задача: 285. Inorder Successor in BST
Сложность: medium

Дан корень бинарного дерева поиска и узел p в нем. Верните преемника этого узла в порядке возрастания в бинарном дереве поиска (BST). Если у данного узла нет преемника в порядке возрастания в дереве, верните null.
Преемник узла p — это узел с наименьшим ключом, который больше p.val.

Пример:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

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

1⃣Определение переменных класса:
Определите две переменные класса: previous и inorderSuccessorNode. Переменная previous будет использоваться при обработке второго случая, а inorderSuccessorNode будет содержать результат, который нужно вернуть.

2⃣Обработка двух случаев:
В функции inorderSuccessor сначала проверьте, какой из двух случаев нужно обработать, проверяя наличие правого дочернего элемента.
Правый дочерний элемент существует:
- присвойте правый дочерний элемент узлу leftmost и итерируйтесь, пока не достигнете узла (leftmost), у которого нет левого дочернего элемента. Итерируйте, присваивая leftmost = leftmost.left, пока не получите левый узел в поддереве.
Правый дочерний элемент не существует:
- определите функцию inorderCase2 и передайте ей узел и узел p.
- выполните простой обход в порядке возрастания: сначала рекурсируйте на левый дочерний элемент узла.
- когда рекурсия вернется, проверьте, равна ли переменная класса previous узлу p. Если это так, значит p является предшественником узла, или, другими словами, узел является преемником узла p. Назначьте inorderSuccessorNode узлу и вернитесь из функции.
- наконец, верните inorderSuccessorNode как результат.

3⃣Итерация и обновление:
В функции inorderCase2 обновляйте previous текущим узлом и продолжайте рекурсировать на правый дочерний элемент.

😎 Решение:

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

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

class Solution {
    private $previous = null;
    private $inorderSuccessorNode = null;

    public function inorderSuccessor($root, $p) {
        if ($p->right !== null) {
            $leftmost = $p->right;
            while ($leftmost->left !== null) {
                $leftmost = $leftmost->left;
            }
            $this->inorderSuccessorNode = $leftmost;
        } else {
            $this->inorderCase2($root, $p);
        }
        return $this->inorderSuccessorNode;
    }

    private function inorderCase2($node, $p) {
        if ($node === null) {
            return;
        }

        $this->inorderCase2($node->left, $p);

        if ($this->previous === $p && $this->inorderSuccessorNode === null) {
            $this->inorderSuccessorNode = $node;
            return;
        }

        $this->previous = $node;

        $this->inorderCase2($node->right, $p);
    }
}

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

Задача: 943. Find the Shortest Superstring
Сложность: hard

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

Пример:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

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

1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается.

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

3⃣Вернуть результат.

😎 Решение:

function shortestSuperstring($words) {
    while (count($words) > 1) {
        $maxOverlap = -1;
        $l = 0;
        $r = 0;
        $merged = '';
        for ($i = 0; $i < count($words); $i++) {
            for ($j = 0; $j < count($words); $j++) {
                if ($i != $j) {
                    $ovlp = overlap($words[$i], $words[$j]);
                    if ($ovlp > $maxOverlap) {
                        $maxOverlap = $ovlp;
                        $l = $i;
                        $r = $j;
                        $merged = merge($words[$i], $words[$j], $ovlp);
                    }
                }
            }
        }
        $words[$l] = $merged;
        array_splice($words, $r, 1);
    }
    return $words[0];
}

function overlap($a, $b) {
    $maxOverlap = 0;
    for ($i = 1; $i <= min(strlen($a), strlen($b)); $i++) {
        if (substr($a, -$i) === substr($b, 0, $i)) {
            $maxOverlap = $i;
        }
    }
    return $maxOverlap;
}

function merge($a, $b, $overlapLen) {
    return $a . substr($b, $overlapLen);
}

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

Задача: 1029. Two City Scheduling
Сложность: medium

Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.

2⃣Сортировать по разнице:
Отсортируйте людей по разнице в стоимости перелета в город A и B. Это поможет минимизировать общую стоимость, так как мы сначала будем отправлять тех, для кого разница минимальна.

3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.

😎 Решение:

class Solution {
    function twoCitySchedCost($costs) {
        usort($costs, function($a, $b) {
            return ($a[0] - $a[1]) - ($b[0] - $b[1]);
        });
        $totalCost = 0;
        $n = count($costs) / 2;
        for ($i = 0; $i < $n; $i++) {
            $totalCost += $costs[$i][0];
            $totalCost += $costs[$i + $n][1];
        }
        return $totalCost;
    }
}

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

Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard

Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.
Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева.
Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.

Пример:

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

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

1⃣Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".

2⃣Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").

3⃣Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.

😎 Решение:

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 Codec {
    function rserialize($root, &$str) {
        if ($root === null) {
            $str .= "null,";
        } else {
            $str .= $root->val . ",";
            $this->rserialize($root->left, $str);
            $this->rserialize($root->right, $str);
        }
    }

    function serialize($root) {
        $str = "";
        $this->rserialize($root, $str);
        return $str;
    }

    function rdeserialize(&$data) {
        if ($data[0] === "null") {
            array_shift($data);
            return null;
        }

        $root = new TreeNode(intval(array_shift($data)));
        $root->left = $this->rdeserialize($data);
        $root->right = $this->rdeserialize($data);
        return $root;
    }

    function deserialize($data) {
        $dataArray = explode(",", $data);
        return $this->rdeserialize($dataArray);
    }
}
?>

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

Задача: 1136. Parallel Courses
Сложность: medium

Вам дано целое число n, которое указывает, что есть n курсов, обозначенных от 1 до n. Вам также дан массив relations, где relations[i] = [prevCoursei, nextCoursei], представляющий собой зависимость между курсами: курс prevCoursei должен быть пройден до курса nextCoursei.

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

Пример:

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

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

1⃣Постройте направленный граф из зависимостей (relations).

2⃣Реализуйте функцию dfsCheckCycle для проверки наличия цикла в графе.

3⃣Реализуйте функцию dfsMaxPath для вычисления длины самого длинного пути в графе. Если цикл найден, верните -1. Иначе верните длину самого длинного пути.

😎 Решение:

class Solution {
    function minimumSemesters($N, $relations) {
        $graph = array_fill(0, $N + 1, []);
        foreach ($relations as $relation) {
            $graph[$relation[0]][] = $relation[1];
        }

        $visited = array_fill(0, $N + 1, 0);
        for ($node = 1; $node <= $N; $node++) {
            if ($this->dfsCheckCycle($node, $graph, $visited) === -1) {
                return -1;
            }
        }

        $visitedLength = array_fill(0, $N + 1, 0);
        $maxLength = 1;
        for ($node = 1; $node <= $N; $node++) {
            $length = $this->dfsMaxPath($node, $graph, $visitedLength);
            $maxLength = max($length, $maxLength);
        }
        return $maxLength;
    }

    private function dfsCheckCycle($node, $graph, &$visited) {
        if ($visited[$node] !== 0) {
            return $visited[$node];
        } else {
            $visited[$node] = -1;
        }
        foreach ($graph[$node] as $endNode) {
            if ($this->dfsCheckCycle($endNode, $graph, $visited) === -1) {
                return -1;
            }
        }
        $visited[$node] = 1;
        return 1;
    }

    private function dfsMaxPath($node, $graph, &$visitedLength) {
        if ($visitedLength[$node] !== 0) {
            return $visitedLength[$node];
        }
        $maxLength = 1;
        foreach ($graph[$node] as $endNode) {
            $length = $this->dfsMaxPath($endNode, $graph, $visitedLength);
            $maxLength = max($length + 1, $maxLength);
        }
        $visitedLength[$node] = $maxLength;
        return $maxLength;
    }
}

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

Задача: 1337. The K Weakest Rows in a Matrix
Сложность: easy

Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке.

Строка i слабее строки j, если выполнено одно из следующих условий:

Количество солдат в строке i меньше, чем в строке j.
Обе строки имеют одинаковое количество солдат, но i < j.
Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной.

Пример:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

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

1⃣Вычислите силу каждой строки матрицы и поместите пары сила/индекс в массив. Для каждой строки подсчитайте количество единиц (солдат) до первой нуля (гражданского), чтобы определить силу строки.

2⃣Отсортируйте массив пар по возрастанию силы, а в случае равенства силы — по возрастанию индекса. Для этого потребуется реализовать компаратор, который сравнивает сначала силу, а затем индекс.

3⃣Извлеките первые k индексов из отсортированного массива и верните их. Эти индексы будут соответствовать k самым слабым строкам в порядке от самой слабой к самой сильной.

😎 Решение:

class Solution {
    function kWeakestRows($mat, $k) {
        $m = count($mat);
        $n = count($mat[0]);

        $pairs = [];
        for ($i = 0; $i < $m; $i++) {
            $strength = 0;
            for ($j = 0; $j < $n; $j++) {
                if ($mat[$i][$j] == 0) break;
                $strength++;
            }
            $pairs[] = [$strength, $i];
        }

        usort($pairs, function($a, $b) {
            if ($a[0] == $b[0]) return $a[1] - $b[1];
            return $a[0] - $b[0];
        });

        $indexes = [];
        for ($i = 0; $i < $k; $i++) {
            $indexes[] = $pairs[$i][1];
        }
        return $indexes;
    }
}

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

Задача: 1219. Path with Maximum Gold
Сложность: medium

В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста.

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

Пример:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

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

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

2⃣Функция DFS и обратный трек:
Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека.
Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота.
Пометьте текущую ячейку как посещённую и сохраните её значение.
Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь.
Сбросьте текущую ячейку до её исходного значения для дальнейших исследований.

3⃣Поиск максимального золота:
Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack.
Обновите maxGold при нахождении лучшего пути.
Верните maxGold.

😎 Решение:

class Solution {
    private $directions = [0, 1, 0, -1, 0];

    function getMaximumGold($grid) {
        $rows = count($grid);
        $cols = count($grid[0]);
        $maxGold = 0;

        for ($row = 0; $row < $rows; $row++) {
            for ($col = 0; $col < $cols; $col++) {
                $maxGold = max($maxGold, $this->dfsBacktrack($grid, $rows, $cols, $row, $col));
            }
        }
        return $maxGold;
    }

    private function dfsBacktrack(&$grid, $rows, $cols, $row, $col) {
        if ($row < 0 || $col < 0 || $row >= $rows || $col >= $cols || $grid[$row][$col] == 0) {
            return 0;
        }
        $originalVal = $grid[$row][$col];
        $grid[$row][$col] = 0;
        $maxGold = 0;

        for ($i = 0; $i < 4; $i++) {
            $maxGold = max($maxGold, $this->dfsBacktrack($grid, $rows, $cols, $row + $this->directions[$i], $col + $this->directions[$i + 1]));
        }

        $grid[$row][$col] = $originalVal;
        return $maxGold + $originalVal;
    }
}

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

Задача: 1218. Longest Arithmetic Subsequence of Given Difference
Сложность: medium

Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference.

Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов.

Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

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

1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1.

2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]:
Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference:
- если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference].
- в противном случае, установите before_a = 0.
Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]).

3⃣Верните answer после завершения итерации.

😎 Решение:

class Solution {
    function longestSubsequence($arr, $difference) {
        $dp = [];
        $answer = 1;
        
        foreach ($arr as $a) {
            $beforeA = isset($dp[$a - $difference]) ? $dp[$a - $difference] : 0;
            $dp[$a] = $beforeA + 1;
            $answer = max($answer, $dp[$a]);
        }
        
        return $answer;
    }
}

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

Задача: 1426. Counting Elements
Сложность: easy

Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно.

Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

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

1⃣ Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве.

2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве.

3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика.

😎 Решение:

class Solution {
    function countElements($arr) {
        $count = 0;
        foreach ($arr as $x) {
            if ($this->integerInArray($arr, $x + 1)) {
                $count++;
            }
        }
        return $count;
    }

    function integerInArray($arr, $target) {
        foreach ($arr as $x) {
            if ($x == $target) {
                return true;
            }
        }
        return false;
    }
}

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