Задача: 309. Best Time to Buy and Sell Stock with Cooldown
Сложность: medium

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

Пример:

Input: prices = [1]
Output: 0

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

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

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

class Solution {
    function maxProfit($prices) {
        if (empty($prices)) return 0;
        
        $hold = -$prices[0];
        $sold = 0;
        $cooldown = 0;
        
        for ($i = 1; $i < count($prices); $i++) {
            $newHold = max($hold, $cooldown - $prices[$i]);
            $newSold = $hold + $prices[$i];
            $newCooldown = max($cooldown, $sold);
            
            $hold = $newHold;
            $sold = $newSold;
            $cooldown = $newCooldown;
        }
        
        return max($sold, $cooldown);
    }
}

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

Задача: 867. Transpose Matrix
Сложность: easy

Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.

Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.

Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

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

1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.

2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].

3⃣Верните матрицу ans.

😎 Решение:

class Solution {
    function transpose($A) {
        $R = count($A);
        $C = count($A[0]);
        $ans = array_fill(0, $C, array_fill(0, $R, 0));
        for ($r = 0; $r < $R; ++$r)
            for ($c = 0; $c < $C; ++$c)
                $ans[$c][$r] = $A[$r][$c];
        return $ans;
    }
}

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

Задача: 251. Flatten 2D Vector
Сложность: medium

Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.

Пример:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

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

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

2⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.

3⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().

😎 Решение:

class Vector2D {
    private $nums;
    private $position;

    public function __construct($v) {
        $this->nums = [];
        foreach ($v as $innerList) {
            $this->nums = array_merge($this->nums, $innerList);
        }
        $this->position = -1;
    }

    public function next() {
        $this->position++;
        return $this->nums[$this->position];
    }

    public function hasNext() {
        return $this->position + 1 < count($this->nums);
    }
}

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

Задача: 63. Unique Paths II
Сложность: medium

Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

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

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

Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.

Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

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

1⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.

2⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.

3⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.

😎 Решение:

function uniquePathsWithObstacles($obstacleGrid) {
    $R = count($obstacleGrid);
    $C = count($obstacleGrid[0]);
    if ($obstacleGrid[0][0] == 1) {
        return 0;
    }
    $obstacleGrid[0][0] = 1;
    for ($i = 1; $i < $R; $i++) {
        $obstacleGrid[$i][0] = ($obstacleGrid[$i][0] == 0 && $obstacleGrid[$i - 1][0] == 1) ? 1 : 0;
    }
    for ($i = 1; $i < $C; $i++) {
        $obstacleGrid[0][$i] = ($obstacleGrid[0][$i] == 0 && $obstacleGrid[0][$i - 1] == 1) ? 1 : 0;
    }
    for ($i = 1; $i < $R; $i++) {
        for ($j = 1; $j < $C; $j++) {
            if ($obstacleGrid[$i][$j] == 0) {
                $obstacleGrid[$i][$j] = $obstacleGrid[$i - 1][$j] + $obstacleGrid[$i][$j - 1];
            } else {
                $obstacleGrid[$i][$j] = 0;
            }
        }
    }
    return $obstacleGrid[$R - 1][$C - 1];
}

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

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

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

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

😎 Решение:

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

    function shortestPathBinaryMatrix($grid) {
        if ($grid[0][0] != 0 || $grid[count($grid) - 1][count($grid[0]) - 1] != 0) {
            return -1;
        }

        $queue = [[0, 0]];
        $grid[0][0] = 1;

        while (!empty($queue)) {
            [$row, $col] = array_shift($queue);
            $distance = $grid[$row][$col];
            if ($row == count($grid) - 1 && $col == count($grid[0]) - 1) {
                return $distance;
            }
            foreach (self::$directions as $direction) {
                $newRow = $row + $direction[0];
                $newCol = $col + $direction[1];
                if ($newRow >= 0 && $newCol >= 0 && $newRow < count($grid) && $newCol < count($grid[0]) && $grid[$newRow][$newCol] == 0) {
                    $queue[] = [$newRow, $newCol];
                    $grid[$newRow][$newCol] = $distance + 1;
                }
            }
        }
        return -1;
    }
}

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

Задача: 1344. Angle Between Hands of a Clock
Сложность: medium

Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками.

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

Пример:

Input: hour = 12, minutes = 30
Output: 165

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

1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30.

2⃣Найти разницу: diff = abs(hour_angle - minutes_angle).

3⃣Вернуть меньший угол: min(diff, 360 - diff).

😎 Решение:

class Solution {
  public function angleClock($hour, $minutes) {
    $oneMinAngle = 6;
    $oneHourAngle = 30;

    $minutesAngle = $oneMinAngle * $minutes;
    $hourAngle = ($hour % 12 + $minutes / 60) * $oneHourAngle;

    $diff = abs($hourAngle - $minutesAngle);
    return min($diff, 360 - $diff);
  }
}

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

Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

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

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

function wordSubsets($words1, $words2) {
    $maxCount = array_fill(0, 26, 0);

    foreach ($words2 as $word) {
        $count = getCount($word);
        for ($i = 0; $i < 26; $i++) {
            $maxCount[$i] = max($maxCount[$i], $count[$i]);
        }
    }

    $result = [];
    foreach ($words1 as $word) {
        $count = getCount($word);
        if (isUniversal($count, $maxCount)) {
            $result[] = $word;
        }
    }

    return $result;
}

function getCount($word) {
    $count = array_fill(0, 26, 0);
    foreach (str_split($word) as $char) {
        $count[ord($char) - ord('a')]++;
    }
    return $count;
}

function isUniversal($count, $maxCount) {
    for ($i = 0; $i < 26; $i++) {
        if ($count[$i] < $maxCount[$i]) {
            return false;
        }
    }
    return true;
}

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

Задача: 480. Sliding Window Median
Сложность: Hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.

Пример:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

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

1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.

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

3⃣Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.

😎 Решение:

function medianSlidingWindow($nums, $k) {
    $medians = [];

    for ($i = 0; $i + $k <= count($nums); $i++) {
        $window = array_slice($nums, $i, $k);
        sort($window);

        if ($k % 2 == 1) {
            $medians[] = $window[$k / 2];
        } else {
            $medians[] = ($window[$k / 2 - 1] + $window[$k / 2]) / 2.0;
        }
    }

    return $medians;
}

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

Задача: 170. Two Sum III - Data structure design
Сложность: easy

Разработайте структуру данных, которая принимает поток целых чисел и проверяет, есть ли в ней пара чисел, сумма которых равна определенному значению.
Реализуйте класс TwoSum:
- TwoSum() инициализирует объект TwoSum с изначально пустым массивом.
- void add(int number) добавляет число в структуру данных.
- boolean find(int value) возвращает true, если существует хотя бы одна пара чисел, сумма которых равна значению value, в противном случае возвращает false.

Пример:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

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

1⃣Инициализация указателей:
Инициализируйте два указателя low и high, которые указывают на первый и последний элементы списка соответственно.

2⃣Итерация с использованием двух указателей:
Запустите цикл для итерации по списку. Цикл завершится, когда будет найдено решение с двумя суммами или когда два указателя встретятся.
На каждом шаге цикла перемещайте один из указателей в зависимости от различных условий:
Если сумма элементов, на которые указывают текущие указатели, меньше желаемого значения, то необходимо попытаться увеличить сумму для достижения желаемого значения, то есть переместить указатель low вперёд для получения большего значения.
Если сумма элементов больше желаемого значения, то следует попытаться уменьшить сумму, перемещая указатель high в сторону указателя low.
Если сумма равна желаемому значению, можно сразу выполнить возврат из функции.

3⃣Завершение цикла:
Если цикл завершается тем, что два указателя встречаются, то можно быть уверенным, что решения для желаемого значения не существует.

😎 Решение:

class TwoSum {
    private $nums = [];

    public function __construct() {}

    public function add($number) {
        if (!isset($this->nums[$number])) {
            $this->nums[$number] = 0;
        }
        $this->nums[$number]++;
    }

    public function find($value) {
        foreach ($this->nums as $num => $count) {
            $complement = $value - $num;
            if (($complement != $num && isset($this->nums[$complement])) ||
                ($complement == $num && $count > 1)) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy

Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.

Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.

Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

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

1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.

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

3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.

😎 Решение:

class Solution {
    function arrayStringsAreEqual($word1, $word2) {
        $list2 = implode('', $word2);
        $index = 0;
        $n = strlen($list2);

        foreach ($word1 as $word) {
            for ($i = 0; $i < strlen($word); $i++) {
                if ($index >= $n || $word[$i] != $list2[$index]) {
                    return false;
                }
                $index++;
            }
        }

        return $index == $n;
    }
}

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

Задача: 206. Reverse Linked List
Сложность: easy

Дан односвязный список, разверните этот список и верните развернутый список.

Пример:

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

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

1⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.

2⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.

3⃣После завершения цикла верните prev как новую голову развернутого списка.

😎 Решение:

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

class Solution {
    function reverseList($head) {
        $prev = null;
        $curr = $head;
        while ($curr !== null) {
            $nextTemp = $curr->next;
            $curr->next = $prev;
            $prev = $curr;
            $curr = $nextTemp;
        }
        return $prev;
    }
}

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

Задача: 1168. Optimize Water Distribution in a Village
Сложность: hard

В деревне есть n домов. Мы хотим обеспечить все дома водой, строя колодцы и прокладывая трубы.

Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами.

Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой.

Пример:

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

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

1⃣Представление графа: Постройте список смежности для представления графа, где вершины и ребра соответствуют домам и трубам. Список смежности можно представить в виде списка списков или словаря списков.

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

3⃣Очередь с приоритетом (куча): Используйте кучу для реализации жадной стратегии. На каждом шаге определяйте лучшее ребро для добавления на основе стоимости его добавления в дерево. Куча позволяет извлекать минимальный элемент за константное время и удалять минимальный элемент за логарифмическое время. Это идеально подходит для нашей задачи повторного нахождения ребра с наименьшей стоимостью.

😎 Решение:

class Solution {
    function minCostToSupplyWater($n, $wells, $pipes) {
        $graph = array_fill(0, $n + 1, []);
        $minHeap = new SplPriorityQueue();
        $minHeap->setExtractFlags(SplPriorityQueue::EXTR_DATA);
        
        foreach ($wells as $i => $cost) {
            $graph[0][] = [$cost, $i + 1];
            $minHeap->insert([$cost, $i + 1], -$cost);
        }
        
        foreach ($pipes as $pipe) {
            [$house1, $house2, $cost] = $pipe;
            $graph[$house1][] = [$cost, $house2];
            $graph[$house2][] = [$cost, $house1];
        }
        
        $mstSet = [0 => true];
        $totalCost = 0;
        
        while (count($mstSet) < $n + 1) {
            $edge = $minHeap->extract();
            [$cost, $nextHouse] = $edge;
            if (isset($mstSet[$nextHouse])) continue;
            $mstSet[$nextHouse] = true;
            $totalCost += $cost;
            foreach ($graph[$nextHouse] as $neighborEdge) {
                if (!isset($mstSet[$neighborEdge[1]])) {
                    $minHeap->insert($neighborEdge, -$neighborEdge[0]);
                }
            }
        }
        
        return $totalCost;
    }
}

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

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

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

class Solution {
    function rectangleArea($rectangles) {
        $N = count($rectangles);
        $Xvals = [];
        $Yvals = [];

        foreach ($rectangles as $rec) {
            $Xvals[$rec[0]] = true;
            $Xvals[$rec[2]] = true;
            $Yvals[$rec[1]] = true;
            $Yvals[$rec[3]] = true;
        }

        $imapx = array_keys($Xvals);
        sort($imapx);
        $imapy = array_keys($Yvals);
        sort($imapy);

        $mapx = [];
        $mapy = [];
        foreach ($imapx as $i => $v) {
            $mapx[$v] = $i;
        }
        foreach ($imapy as $i => $v) {
            $mapy[$v] = $i;
        }

        $grid = array_fill(0, count($imapx), array_fill(0, count($imapy), false));
        foreach ($rectangles as $rec) {
            for ($x = $mapx[$rec[0]]; $x < $mapx[$rec[2]]; $x++) {
                for ($y = $mapy[$rec[1]]; $y < $mapy[$rec[3]]; $y++) {
                    $grid[$x][$y] = true;
                }
            }
        }

        $ans = 0;
        for ($x = 0; $x < count($grid); $x++) {
            for ($y = 0; $y < count($grid[0]); $y++) {
                if ($grid[$x][$y]) {
                    $ans += ($imapx[$x + 1] - $imapx[$x]) * ($imapy[$y + 1] - $imapy[$y]);
                }
            }
        }

        $ans %= 1_000_000_007;
        return (int)$ans;
    }
}

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

Задача: 690. Employee Importance
Сложность: medium

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

Вам дан массив сотрудников employees, где:

employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.

Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

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

1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.

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

3⃣Используйте DFS для вычисления общей важности, начиная с заданного идентификатора сотрудника.

😎 Решение:

class Employee {
    public $id;
    public $importance;
    public $subordinates;
    
    function __construct($id, $importance, $subordinates) {
        $this->id = $id;
        $this->importance = $importance;
        $this->subordinates = $subordinates;
    }
}

class Solution {
    private $emap;
    
    function getImportance($employees, $queryid) {
        $this->emap = [];
        foreach ($employees as $e) {
            $this->emap[$e->id] = $e;
        }
        return $this->dfs($queryid);
    }
    
    private function dfs($eid) {
        $employee = $this->emap[$eid];
        $ans = $employee->importance;
        foreach ($employee->subordinates as $subid) {
            $ans += $this->dfs($subid);
        }
        return $ans;
    }
}

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

Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium

Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.

Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false

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

1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.

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

3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.

😎 Решение:

function leadsToDestination($n, $edges, $source, $destination) {
    $graph = [];
    foreach ($edges as $edge) {
        $graph[$edge[0]][] = $edge[1];
    }
    
    $visited = array_fill(0, $n, 0);
    
    function dfs($node, $graph, &$visited, $destination) {
        if ($visited[$node] != 0) return $visited[$node] == 2;
        if (!isset($graph[$node])) return $node == $destination;
        $visited[$node] = 1;
        foreach ($graph[$node] as $neighbor) {
            if (!dfs($neighbor, $graph, $visited, $destination)) return false;
        }
        $visited[$node] = 2;
        return true;
    }
    
    return dfs($source, $graph, $visited, $destination);
}

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

Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium

Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.

Пример:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

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

1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.

2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.

3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.

😎 Решение:

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 Solution {
    private $index = 0;

    function bstFromPreorder($preorder) {
        return $this->constructBST($preorder, PHP_INT_MIN, PHP_INT_MAX);
    }

    private function constructBST($preorder, $lower, $upper) {
        if ($this->index == count($preorder)) {
            return null;
        }

        $val = $preorder[$this->index];
        if ($val < $lower || $val > $upper) {
            return null;
        }

        $this->index++;
        $root = new TreeNode($val);
        $root->left = $this->constructBST($preorder, $lower, $val);
        $root->right = $this->constructBST($preorder, $val, $upper);
        return $root;
    }
}

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

Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

function countPalindromicSubsequences($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n, array_fill(0, $n, 0));

    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = 1;
    }

    for ($length = 2; $length <= $n; $length++) {
        for ($i = 0; $i <= $n - $length; $i++) {
            $j = $i + $length - 1;
            if ($s[$i] == $s[$j]) {
                $l = $i + 1;
                $r = $j - 1;
                while ($l <= $r && $s[$l] != $s[$i]) $l++;
                while ($l <= $r && $s[$r] != $s[$j]) $r--;
                if ($l > $r) {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 + 2;
                } else if ($l == $r) {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 + 1;
                } else {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 - $dp[$l + 1][$r - 1];
                }
            } else {
                $dp[$i][$j] = $dp[$i + 1][$j] + $dp[$i][$j - 1] - $dp[$i + 1][$j - 1];
            }
            $dp[$i][$j] = ($dp[$i][$j] + $MOD) % $MOD;
        }
    }

    return $dp[0][$n - 1];
}

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

Задача: 284. Peeking Iterator
Сложность: medium

Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).
Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.

Пример:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

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

1⃣Инициализация итератора:
В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null.

2⃣Операция peek:
Метод peek возвращает значение next, не перемещая указатель итератора.

3⃣Операции next и hasNext:
Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException.
Метод hasNext возвращает true, если next не равно null, и false в противном случае.

😎 Решение:

class PeekingIterator {
    private $iterator;
    private $nextElement;

    public function __construct(Iterator $iterator) {
        $this->iterator = $iterator;
        $this->nextElement = $iterator->valid() ? $iterator->current() : null;
    }

    public function next() {
        $currentElement = $this->nextElement;
        $this->iterator->next();
        $this->nextElement = $this->iterator->valid() ? $this->iterator->current() : null;
        return $currentElement;
    }

    public function hasNext() {
        return $this->nextElement !== null;
    }

    public function peek() {
        return $this->nextElement;
    }
}

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

Задача №26. Remove Duplicates from Sorted Array
Сложность: easy

Учитывая целочисленный массив nums, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов.

Пример:

Input: nums = [1,1,2]  
Output: 2, nums = [1,2,_]

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

1⃣Использовать два указателя: index для записи уникальных элементов и i для перебора массива.

2⃣Если текущий элемент отличается от предыдущего, записать его на index-позицию.

3⃣Вернуть index как количество уникальных элементов.

😎 Решение:

class Solution {
    function removeDuplicates(&$nums) { 
        $index = 1;
        for ($i = 1; $i < count($nums); $i++) {
            if ($nums[$i] !== $nums[$i - 1]) { 
                $nums[$index++] = $nums[$i];
            }  
        }  
        return $index;
    }
}

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

class Solution {
    function shiftAndCount($xShift, $yShift, $M, $R) {
        $leftShiftCount = 0;
        $rightShiftCount = 0;
        $rRow = 0;
        for ($mRow = $yShift; $mRow < count($M); ++$mRow) {
            $rCol = 0;
            for ($mCol = $xShift; $mCol < count($M); ++$mCol) {
                if ($M[$mRow][$mCol] == 1 && $M[$mRow][$mCol] == $R[$rRow][$rCol]) {
                    $leftShiftCount++;
                }
                if ($M[$mRow][$rCol] == 1 && $M[$mRow][$rCol] == $R[$rRow][$mCol]) {
                    $rightShiftCount++;
                }
                $rCol++;
            }
            $rRow++;
        }
        return max($leftShiftCount, $rightShiftCount);
    }

    function largestOverlap($A, $B) {
        $maxOverlaps = 0;
        for ($yShift = 0; $yShift < count($A); ++$yShift) {
            for ($xShift = 0; $xShift < count($A); ++$xShift) {
                $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $A, $B));
                $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $B, $A));
            }
        }
        return $maxOverlaps;
    }
}

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

Задача: 661. Image Smoother
Сложность: easy

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

Пример:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

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

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

2⃣Обработка каждой ячейки:
Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку).
Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы.

3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.

😎 Решение:

class Solution {
    function imageSmoother($img) {
        $m = count($img);
        $n = count($img[0]);
        $result = array_fill(0, $m, array_fill(0, $n, 0));
        
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $count = 0;
                $total = 0;
                for ($ni = max(0, $i - 1); $ni <= min($m - 1, $i + 1); $ni++) {
                    for ($nj = max(0, $j - 1); $nj <= min($n - 1, $j + 1); $nj++) {
                        $total += $img[$ni][$nj];
                        $count++;
                    }
                }
                $result[$i][$j] = floor($total / $count);
            }
        }
        
        return $result;
    }
}

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