Задача: 155. Min Stack
Сложность: medium

Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время.
Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.
Вы должны реализовать решение с временной сложностью O(1) для каждой функции.

Пример:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

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

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

2⃣Работа со стеком:
Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.

3⃣Доступ к элементам:
Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.

😎 Решение:

class MinStack {
    private $stack = [];

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

    private function last() {
        return end($this->stack);
    }

    public function push($x) {
        if (empty($this->stack)) {
            array_push($this->stack, [$x, $x]);
            return;
        }

        $currentMin = $this->last()[1];
        array_push($this->stack, [$x, min($currentMin, $x)]);
    }

    public function pop() {
        array_pop($this->stack);
    }

    public function top() {
        $last = $this->last();
        return $last[0];
    }

    public function getMin() {
        $last = $this->last();
        return $last[1];
    }
}

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

Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

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

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

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

😎 Решение:

class Solution {
    private function storeFirstOptions($s, $startPos, &$firstOptions) {
        if ($s[$startPos] != '{') {
            $firstOptions[] = $s[$startPos];
        } else {
            $startPos++;
            while ($s[$startPos] != '}') {
                if ($s[$startPos] >= 'a' && $s[$startPos] <= 'z') {
                    $firstOptions[] = $s[$startPos];
                }
                $startPos++;
            }
            sort($firstOptions);
        }
        return $startPos + 1;
    }

    private function findAllWords($s, $startPos) {
        if ($startPos == strlen($s)) {
            return [""];
        }

        $firstOptions = [];
        $remStringStartPos = $this->storeFirstOptions($s, $startPos, $firstOptions);
        $wordsWithRemString = $this->findAllWords($s, $remStringStartPos);

        $expandedWords = [];
        foreach ($firstOptions as $c) {
            foreach ($wordsWithRemString as $word) {
                $expandedWords[] = $c . $word;
            }
        }
        return $expandedWords;
    }

    public function expand($s) {
        return $this->findAllWords($s, 0);
    }
}

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

Задача: 348. Design Tic-Tac-Toe
Сложность: medium

Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:

Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:

TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.

Пример:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

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

1⃣Инициализация:
Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно.
Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно.
Инициализируйте размер доски n.

2⃣Выполнение хода:
Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода.
Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal.

3⃣Проверка победы:
Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя.
Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода.

😎 Решение:

class TicTacToe {
    private $n;
    private $rows;
    private $cols;
    private $diagonal;
    private $antiDiagonal;

    function __construct($n) {
        $this->n = $n;
        $this->rows = array_fill(0, $n, 0);
        $this->cols = array_fill(0, $n, 0);
        $this->diagonal = 0;
        $this->antiDiagonal = 0;
    }

    function move($row, $col, $player) {
        $add = $player === 1 ? 1 : -1;
        $this->rows[$row] += $add;
        $this->cols[$col] += $add;
        if ($row === $col) {
            $this->diagonal += $add;
        }
        if ($row + $col === $this->n - 1) {
            $this->antiDiagonal += $add;
        }
        if (abs($this->rows[$row]) === $this->n || 
            abs($this->cols[$col]) === $this->n || 
            abs($this->diagonal) === $this->n || 
            abs($this->antiDiagonal) === $this->n) {
            return $player;
        }
        return 0;
    }
}

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

Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium

Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.

Пример:

Input: stones = [7,4,9]
Output: [1,2]

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

1⃣Сортировка:
Сначала отсортируем массив камней.

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

3⃣Минимальное количество ходов:
Минимальное количество ходов можно определить следующим образом:
Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни.
Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0.
В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место).

😎 Решение:

function numMovesStonesII($stones) {
    sort($stones);
    $n = count($stones);
    
    $maxMoves = $stones[$n-1] - $stones[0] + 1 - $n;
    $maxMoves -= min($stones[1] - $stones[0] - 1, $stones[$n-1] - $stones[$n-2] - 1);

    $minMoves = PHP_INT_MAX;
    $j = 0;

    for ($i = 0; $i < $n; $i++) {
        while ($j < $n && $stones[$j] - $stones[$i] + 1 <= $n) {
            $j++;
        }
        $alreadyInWindow = $j - $i;
        if ($alreadyInWindow == $n - 1 && $stones[$j-1] - $stones[$i] + 1 == $n - 1) {
            $minMoves = min($minMoves, 2);
        } else {
            $minMoves = min($minMoves, $n - $alreadyInWindow);
        }
    }

    return [$minMoves, $maxMoves];
}

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

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

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

Задача: 790. Domino and Tromino Tiling
Сложность: medium

У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.

Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет.

Пример:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

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

1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).

2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас.

3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.

😎 Решение:

class Solution {
    private $MOD = 1_000_000_007;
    private $fCache = [];
    private $pCache = [];

    private function p($n) {
        if (isset($this->pCache[$n])) {
            return $this->pCache[$n];
        }
        if ($n == 2) {
            return 1;
        }
        $result = ($this->p($n - 1) + $this->f($n - 2)) % $this->MOD;
        $this->pCache[$n] = $result;
        return $result;
    }

    private function f($n) {
        if (isset($this->fCache[$n])) {
            return $this->fCache[$n];
        }
        if ($n <= 2) {
            return $n;
        }
        $result = ($this->f($n - 1) + $this->f($n - 2) + 2 * $this->p($n - 1)) % $this->MOD;
        $this->fCache[$n] = $result;
        return $result;
    }

    public function numTilings($n) {
        return $this->f($n);
    }
}

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

class Solution {
    function flipLights($n, $m) {
        $seen = [];
        $n = min($n, 6);
        $shift = max(0, 6 - $n);
        for ($cand = 0; $cand < 16; ++$cand) {
            $bcount = substr_count(decbin($cand), '1');
            if ($bcount % 2 == $m % 2 && $bcount <= $m) {
                $lights = 0;
                if ((($cand >> 0) & 1) > 0) $lights ^= 0b111111 >> $shift;
                if ((($cand >> 1) & 1) > 0) $lights ^= 0b010101 >> $shift;
                if ((($cand >> 2) & 1) >

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

Задача: 1463. Cherry Pickup II
Сложность: hard

Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).

У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).

Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.

Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

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

1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2).

2⃣Итеративно заполните dp, начиная с нижней строки, вычисляя для каждой клетки максимальное количество вишен, которое можно собрать с учетом возможных перемещений роботов.
3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов.

😎 Решение:

class Solution {
    function cherryPickup($grid) {
        $m = count($grid);
        $n = count($grid[0]);
        $dp = array_fill(0, $m, array_fill(0, $n, array_fill(0, $n, 0)));
        
        for ($row = $m - 1; $row >= 0; $row--) {
            for ($col1 = 0; $col1 < $n; $col1++) {
                for ($col2 = 0; $col2 < $n; $col2++) {
                    $result = $grid[$row][$col1];
                    if ($col1 != $col2) {
                        $result += $grid[$row][$col2];
                    }
                    if ($row != $m - 1) {
                        $maxCherries = 0;
                        for ($newCol1 = $col1 - 1; $newCol1 <= $col1 + 1; $newCol1++) {
                            for ($newCol2 = $col2 - 1; $newCol2 <= $col2 + 1; $newCol2++) {
                                if ($newCol1 >= 0 && $newCol1 < $n && $newCol2 >= 0 && $newCol2 < $n) {
                                    $maxCherries = max($maxCherries, $dp[$row + 1][$newCol1][$newCol2]);
                                }
                            }
                        }
                        $result += $maxCherries;
                    }
                    $dp[$row][$col1][$col2] = $result;
                }
            }
        }
        return $dp[0][0][$n - 1];
    }
}

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

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

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

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

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

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

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

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

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:

class Solution {
    function constructArray($n, $k) {
        $answer = [];
        $left = 1;
        $right = $n;
        
        for ($i = 0; $i <= $k; $i++) {
            if ($i % 2 == 0) {
                $answer[] = $left++;
            } else {
                $answer[] = $right--;
            }
        }
        
        if ($k % 2 == 0) {
            for ($i = $right; $i >= $left; $i--) {
                $answer[] = $i;
            }
        } else {
            for ($i = $left; $i <= $right; $i++) {
                $answer[] = $i;
            }
        }
        
        return $answer;
    }
}

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

Задача: 722. Remove Comments
Сложность: medium

Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными.
Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.

Пример:

Input: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

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

1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.

2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.

3⃣После обработки всех строк добавьте непустые строки из buffer в результат.

😎 Решение:

function removeComments($source) {
    $inBlock = false;
    $buffer = "";
    $result = [];
    
    foreach ($source as $line) {
        $i = 0;
        if (!$inBlock) $buffer = "";
        while ($i < strlen($line)) {
            if (!$inBlock && $i + 1 < strlen($line) && $line[$i] == '/' && $line[$i + 1] == '*') {
                $inBlock = true;
                $i++;
            } elseif ($inBlock && $i + 1 < strlen($line) && $line[$i] == '*' && $line[$i + 1] == '/') {
                $inBlock = false;
                $i++;
            } elseif (!$inBlock && $i + 1 < strlen($line) && $line[$i] == '/' && $line[$i + 1] == '/') {
                break;
            } elseif (!$inBlock) {
                $buffer .= $line[$i];
            }
            $i++;
        }
        if (!$inBlock && strlen($buffer) > 0) {
            $result[] = $buffer;
        }
    }
    return $result;
}

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

Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard

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

Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

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

1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).

2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).

3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.

😎 Решение:

class Solution {
    function maxProfit($k, $prices) {
        $n = count($prices);
        if ($n == 0 || $k == 0) return 0;
        if ($k * 2 >= $n) {
            $res = 0;
            for ($i = 1; $i < $n; $i++) {
                $res += max(0, $prices[$i] - $prices[$i - 1]);
            }
            return $res;
        }
        $dp = array_fill(0, $n, array_fill(0, $k + 1, [PHP_INT_MIN / 2, PHP_INT_MIN / 2]));
        $dp[0][0][0] = 0;
        $dp[0][1][1] = -$prices[0];

        for ($i = 1; $i < $n; $i++) {
            for ($j = 0; $j <= $k; $j++) {
                $dp[$i][$j][0] = max($dp[$i - 1][$j][0], $dp[$i - 1][$j][1] + $prices[$i]);
                if ($j > 0) {
                    $dp[$i][$j][1] = max($dp[$i - 1][$j][1], $dp[$i - 1][$j - 1][0] - $prices[$i]);
                }
            }
        }
        $res =

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

Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy

Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.

Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.

Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..

2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.

3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.

😎 Решение:

class Solution {
    function isMajorityElement($nums, $target) {
        $count = 0;
        foreach ($nums as $num) {
            if ($num == $target) {
                $count++;
            }
        }
        return $count > count($nums) / 2;
    }
}

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

#hard
Задача: 827. Making A Large Island

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

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

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

3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.

😎 Решение:

class Solution {
    private $dr = [-1, 0, 1, 0];
    private $dc = [0, -1, 0, 1];
    private $grid;
    private $N;

    function largestIsland($grid) {
        $this->grid = $grid;
        $this->N = count($grid);
        
        $index = 2;
        $area = array_fill(0, $this->N * $this->N + 2, 0);
        for ($r = 0; $r < $this->N; ++$r) {
            for ($c = 0; $c < $this->N; ++$c) {
                if ($grid[$r][$c] == 1) {
                    $area[$index] = $this->dfs($r, $c, $index);
                    ++$index;
                }
            }
        }
        
        $ans = max($area);
        for ($r = 0; $r < $this->N; ++$r) {
            for ($c = 0; $c < $this->N; ++$c) {
                if ($grid[$r][$c] == 0) {
                    $seen = [];
                    foreach ($this->neighbors($r, $c) as $move) {
                        if ($grid[$move[0]][$move[1]] > 1) {
                            $seen[$grid[$move[0]][$move[1]]] = true;
                        }
                    }
                    $bns = 1;
                    foreach (array_keys($seen) as $i) {
                        $bns += $area[$i];
                    }
                    $ans = max($ans, $bns);
                }
            }
        }
        
        return $ans;
    }

    function dfs($r, $c, $index) {
        $ans = 1;
        $this->grid[$r][$c] = $index;
        foreach ($this->neighbors($r, $c) as $move) {
            if ($this->grid[$move[0]][$move[1]] == 1) {
                $this->grid[$move[0]][$move[1]] = $index;
                $ans += $this->dfs($move[0], $move[1], $index);
            }
        }
        return $ans;
    }

    function neighbors($r, $c) {
        $ans = [];
        for ($k = 0; $k < 4; ++$k) {
            $nr = $r + $this->dr[$k];
            $nc = $c + $this->dc[$k];
            if ($nr >= 0 && $nr < $this->N && $nc >= 0 && $nc < $this->N) {
                $ans[] = [$nr, $nc];
            }
        }
        return $ans;
    }

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

Задача №17. Letter Combinations of a Phone Number
Сложность: medium

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

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

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

3⃣Добавлять полученные комбинации в результирующий массив.

😎 Решение:

class Solution { 
 
    public $result = []; 
 
    function letterCombinations($digits) { 
        if(strlen($digits) == 0) { 
            return []; 
        } 
 
        $layouts = [ 
            2 => range('a', 'c'), 
            3 => range('d', 'f'), 
            4 => range('g', 'i'), 
            5 => range('j', 'l'),  
            6 => range('m', 'o'),  
            7 => range('p', 's'), 
            8 => range('t', 'v'), 
            9 => range('w', 'z'), 
        ]; 
 
        return $this->recursive(0, $digits, $layouts); 
    } 
 
    function recursive ($index, $chars, $layouts, $combine = '') { 
        foreach($layouts[$chars[$index]] as $currentLayout) { 
            if($layouts[$chars[$index + 1]]) { 
                $this->recursive($index + 1, $chars, $layouts, $combine . $currentLayout); 
            } else { 
                $this->result[] = $combine . $currentLayout; 
            } 
        } 
 
        return $this->result; 
    } 
}

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

Задача: 226. Invert Binary Tree
Сложность: easy

Дан корень бинарного дерева, инвертируйте дерево и верните его корень.

Пример:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

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

1⃣Рекурсивная инверсия поддеревьев:
Если текущий узел (root) пустой, возвращаем null.
Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right.
Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left.

2⃣Обмен поддеревьев:
Устанавливаем левое поддерево текущего узла равным правому поддереву.
Устанавливаем правое поддерево текущего узла равным левому поддереву.

3⃣Возврат корня:
Возвращаем текущий узел (root) как новый корень инвертированного дерева.

😎 Решение:

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 {
    public function invertTree($root) {
        if ($root === null) {
            return null;
        }
        $right = $this->invertTree($root->right);
        $left = $this->invertTree($root->left);
        $root->left = $right;
        $root->right = $left;
        return $root;
    }
}

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

Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy

В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.

Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

1⃣Инициализируйте пустую 3x3 сетку.

2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B.

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

😎 Решение:

function tictactoe($moves) {
    $grid = array_fill(0, 3, array_fill(0, 3, ''));
    for ($i = 0; $i < count($moves); $i++) {
        $r = $moves[$i][0];
        $c = $moves[$i][1];
        $grid[$r][$c] = $i % 2 == 0 ? 'X' : 'O';
    }

    for ($i = 0; $i < 3; $i++) {
        if ($grid[$i][0] == $grid[$i][1] && $grid[$i][1] == $grid[$i][2] && $grid[$i][0] != '')
            return $grid[$i][0] == 'X' ? 'A' : 'B';
        if ($grid[0][$i] == $grid[1][$i] && $grid[1][$i] == $grid[2][$i] && $grid[0][$i] != '')
            return $grid[0][$i] == 'X' ? 'A' : 'B';
    }

    if ($grid[0][0] == $grid[1][1] && $grid[1][1] == $grid[2][2] && $grid[0][0] != '')
        return $grid[0][0] == 'X' ? 'A' : 'B';
    if ($grid[0][2] == $grid[1][1] && $grid[1][1] == $grid[2][0] && $grid[0][2] != '')
        return $grid[0][2] == 'X' ? 'A' : 'B';

    return count($moves) == 9 ? 'Draw' : 'Pending';
}

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

Задача: 686. Repeated String Match
Сложность: medium

Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1.

Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc".

Пример:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

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

1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)).

2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1.

3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1.

😎 Решение:

class Solution {
    function repeatedStringMatch($A, $B) {
        $q = 1;
        $S = $A;
        while (strlen($S) < strlen($B)) {
            $S .= $A;
            $q++;
        }
        if (strpos($S, $B) !== false) return $q;
        if (strpos($S . $A, $B) !== false) return $q + 1;
        return -1;
    }
}

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

Задача: 146. LRU Cache
Сложность: medium

Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.

Функции get и put должны выполняться за среднее время O(1).

Пример:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

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

1⃣Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив previousEnd.next = node.
Настройте указатели узла: node.prev = previousEnd и node.next = tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.

2⃣Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev.
Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.

3⃣Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val.
put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.

😎 Решение:

class Node {
    public $key;
    public $value;
    public $next;
    public $prev;

    public function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
        $this->next = null;
        $this->prev = null;
    }
}

class LRUCache {
    private $capacity;
    private $dic = [];
    private $head;
    private $tail;
    
    public function __construct($capacity) {
        $this->capacity = $capacity;
        $this->head = new Node(-1, -1);
        $this->tail = new Node(-1, -1);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    public function get($key) {
        if (!array_key_exists($key, $this->dic)) {
            return -1;
        }
        $node = $this->dic[$key];
        $this->remove($node);
        $this->add($node);
        return $node->value;
    }

    public function put($key, $value) {
        if (array_key_exists($key, $this->dic)) {
            $this->remove($this->dic[$key]);
        }
        $node = new Node($key, $value);
        $this->add($node);
        $this->dic[$key] = $node;
        if (count($this->dic) > $this->capacity) {
            $nodeToDelete = $this->head->next;
            $this->remove($nodeToDelete);
            unset($this->dic[$nodeToDelete->key]);
        }
    }

    private function add($node) {
        $pre = $this->tail->prev;
        $pre->next = $node;
        $node->prev = $pre;
        $node->next = $this->tail;
        $this->tail->prev = $node;
    }

    private function remove($node) {
        $pre = $node->prev;
        $nxt = $node->next;
        $pre->next = $nxt;
        $nxt->prev = $pre;
    }
}

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