Задача: 764. Largest Plus Sign
Сложность: medium

Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0.
Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0.
Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1.

Пример:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

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

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

2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки.

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

😎 Решение:

class Solution {
    function orderOfLargestPlusSign($N, $mines) {
        $banned = [];
        foreach ($mines as $mine) {
            $banned[$mine[0] * $N + $mine[1]] = true;
        }
        
        $ans = 0;
        for ($r = 0; $r < $N; ++$r) {
            for ($c = 0; $c < $N; ++$c) {
                $k = 0;
                while ($k <= $r && $r < $N - $k && $k <= $c && $c < $N - $k &&
                      !isset($banned[($r - $k) * $N + $c]) &&
                      !isset($banned[($r + $k) * $N + $c]) &&
                      !isset($banned[$r * $N + $c - $k]) &&
                      !isset($banned[$r * $N + $c + $k])) {
                    $k++;
                }
                $ans = max($ans, $k);
            }
        }
        return $ans;
    }
}

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

Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).

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

Пример:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

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

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

3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎 Решение:

class Solution {
    function countOrders($n) {
        $MOD = 1_000_000_007;
        $dp = array_fill(0, $n + 1, 0);
        $dp[0] = 1;
        
        for ($i = 1; $i <= $n; $i++) {
            $dp[$i] = $dp[$i - 1] * (2 * $i - 1) * $i % $MOD;
        }
        
        return $dp[$n];
    }
}

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

Задача: 133. Clone Graph
Сложность: medium

Дана ссылка на узел в связанном неориентированном графе.
Верните глубокую копию (клон) графа.
Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей.

Пример:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

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

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

2⃣Добавьте первый узел в очередь, клонируйте его и добавьте в хеш-таблицу посещенных.

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

😎 Решение:

function cloneGraph($node) {
    if ($node === null) return $node;
    $visited = new SplObjectStorage();
    $queue = [$node];
    $visited[$node] = (object) ['val' => $node->val, 'neighbors' => []];

    while (!empty($queue)) {
        $n = array_shift($queue);
        foreach ($n->neighbors as $neighbor) {
            if (!$visited->contains($neighbor)) {
                $visited[$neighbor] = (object) ['val' => $neighbor->val, 'neighbors' => []];
                array_push($queue, $neighbor);
            }
            array_push($visited[$n]->neighbors, $visited[$neighbor]);
        }
    }
    return $visited[$node];
}

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

Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

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

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа.

2⃣Отсортировать список подсчета в порядке убывания.

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

😎 Решение:

class Solution {
    function minSetSize($arr) {
        sort($arr);
        
        $counts = [];
        $currentRun = 1;
        for ($i = 1; $i < count($arr); $i++) {
            if ($arr[$i] == $arr[$i - 1]) {
                $currentRun += 1;
                continue;
            }
            $counts[] = $currentRun;
            $currentRun = 1;
        }
        $counts[] = $currentRun;
        
        rsort($counts);
        
        $numbersRemovedFromArr = 0;
        $setSize = 0;
        foreach ($counts as $count) {
            $numbersRemovedFromArr += $count;
            $setSize += 1;   
            if ($numbersRemovedFromArr >= count($arr) / 2) {
                break;
            }
        }
        
        return $setSize;
    }
}

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