Задача: 270. Closest Binary Search Tree Value
Сложность: easy

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

Пример:

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

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

1⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

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

😎 Решение:

class Solution {
    function closestValue($root, $target) {
        $closest = $root->val;
        while ($root) {
            if (abs($root->val - $target) < abs($closest - $target)) {
                $closest = $root->val;
            } else if (abs($root->val - $target) == abs($closest - $target)) {
                $closest = min($root->val, $closest);
            }
            $root = $target < $root->val ? $root->left : $root->right;
        }
        return $closest;
    }
}

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

Задача: 1232. Check If It Is a Straight Line
Сложность: easy

Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.

Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

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

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

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

3⃣Если все наклоны совпадают, то все точки лежат на одной прямой.

😎 Решение:

function checkStraightLine($coordinates) {
    list($x0, $y0) = $coordinates[0];
    list($x1, $y1) = $coordinates[1];
    
    foreach ($coordinates as $coord) {
        list($x, $y) = $coord;
        if (($x1 - $x0) * ($y - $y0) !== ($y1 - $y0) * ($x - $x0)) {
            return false;
        }
    }
    return true;
}

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

Задача: 1119. Remove Vowels from a String
Сложность: easy

Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.

Пример:

Input: s = "leetcodeisacommunityforcoders"
Output: "ltcdscmmntyfrcdrs"

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

1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае.

2⃣Инициализируйте пустую строку ans.

3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans.

😎 Решение:

class Solution {
    function removeVowels($s) {
        $ans = '';
        for ($i = 0; $i < strlen($s); $i++) {
            if (!$this->isVowel($s[$i])) {
                $ans .= $s[$i];
            }
        }
        return $ans;
    }

    private function isVowel($c) {
        return $c == 'a' || $c == 'e' || $c == 'i' || $c == 'o' || $c == 'u';
    }
}

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

Задача: 1042. Flower Planting With No Adjacent
Сложность: medium

У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует.

Пример:

Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

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

1⃣Создайте граф из садов и путей между ними.

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

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

😎 Решение:

function gardenNoAdj($n, $paths) {
    $graph = array_fill(0, $n, []);
    foreach ($paths as $path) {
        $graph[$path[0] - 1][] = $path[1] - 1;
        $graph[$path[1] - 1][] = $path[0] - 1;
    }
    
    $answer = array_fill(0, $n, 0);
    for ($garden = 0; $garden < $n; $garden++) {
        $used = [];
        foreach ($graph[$garden] as $neighbor) {
            $used[$answer[$neighbor]] = true;
        }
        for ($flower = 1; $flower <= 4; $flower++) {
            if (!isset($used[$flower])) {
                $answer[$garden] = $flower;
                break;
            }
        }
    }
    
    return $answer;
}

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

Задача: 314. Binary Tree Vertical Order Traversal
Сложность: medium

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

Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

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

😎 Решение:

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 {
    function verticalOrder($root) {
        $output = [];
        if ($root === null) {
            return $output;
        }

        $columnTable = [];
        $queue = [[$root, 0]];

        while (!empty($queue)) {
            list($node, $col) = array_shift($queue);

            if ($node !== null) {
                if (!isset($columnTable[$col])) {
                    $columnTable[$col] = [];
                }
                $columnTable[$col][] = $node->val;

                $queue[] = [$node->left, $col - 1];
                $queue[] = [$node->right, $col + 1];
            }
        }

        ksort($columnTable);
        foreach ($columnTable as $col => $vals) {
            $output[] = $vals;
        }

        return $output;
    }
}

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

Задача: 904. Fruit Into Baskets
Сложность: medium

Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.

Пример:

Input: fruits = [1,2,1]
Output: 3

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

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

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

3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге.

😎 Решение:

function totalFruit($fruits) {
    $basket = [];
    $left = 0;
    $maxFruits = 0;

    for ($right = 0; $right < count($fruits); $right++) {
        if (!isset($basket[$fruits[$right]])) {
            $basket[$fruits[$right]] = 0;
        }
        $basket[$fruits[$right]]++;
        while (count($basket) > 2) {
            $basket[$fruits[$left]]--;
            if ($basket[$fruits[$left]] == 0) {
                unset($basket[$fruits[$left]]);
            }
            $left++;
        }
        $maxFruits = max($maxFruits, $right - $left + 1);
    }

    return $maxFruits;
}

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

Задача: 1019. Next Greater Node In Linked List
Сложность: medium

Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.

Пример:

Input: head = [2,1,5]
Output: [5,5,0]

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

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

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

3⃣Заполнение оставшихся значений:
Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

class Solution {
    function nextLargerNodes($head) {
        $values = [];
        while ($head != null) {
            $values[] = $head->val;
            $head = $head->next;
        }
        
        $answer = array_fill(0, count($values), 0);
        $stack = [];
        
        for ($i = 0; $i < count($values); $i++) {
            while (!empty($stack) && $values[end($stack)] < $values[$i]) {
                $answer[array_pop($stack)] = $values[$i];
            }
            $stack[] = $i;
        }
        
        return $answer;
    }
}

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

Задача: 1254. Number of Closed Islands
Сложность: medium

Дана двумерная сетка, состоящая из 0 (земля) и 1 (вода).Остров - это максимальная 4-направленно связная группа из 0s, а закрытый остров - это остров, полностью (слева, сверху, справа, снизу) окруженный 1s. Верните количество закрытых островов.

Пример:

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

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

1⃣Пройдите по границам сетки и с помощью поиска в глубину (DFS) или поиска в ширину (BFS) замените все связанные земли (0) на воду (1).

2⃣Пройдите по всей сетке, используя DFS или BFS для поиска всех оставшихся островов (групп 0)

3⃣Подсчитайте количество таких островов.

😎 Решение:

class Solution {
    function closedIsland($grid) {
        $m = count($grid);
        $n = count($grid[0]);

        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if (($i == 0 || $i == $m - 1 || $j == 0 || $j == $n - 1) && $grid[$i][$j] == 0) {
                    $this->dfs($grid, $i, $j);
                }
            }
        }

        $count = 0;
        for ($i = 1; $i < $m - 1; $i++) {
            for ($j = 1; $j < $n - 1; $j++) {
                if ($grid[$i][$j] == 0) {
                    $this->dfs($grid, $i, $j);
                    $count++;
                }
            }
        }

        return $count;
    }

    private function dfs(&$grid, $x, $y) {
        if ($x < 0 || $y < 0 || $x >= count($grid) || $y >= count($grid[0]) || $grid[$x][$y] == 1) {
            return;
        }
        $grid[$x][$y] = 1;
        $this->dfs($grid, $x + 1, $y);
        $this->dfs($grid, $x - 1, $y);
        $this->dfs($grid, $x, $y + 1);
        $this->dfs($grid, $x, $y - 1);
    }
}

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

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

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