#hard
Задача: 499. The Maze III

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

Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).

Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

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

3⃣Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎 Решение:

class State {
    public $row, $col, $dist, $path;
    public function __construct($r, $c, $d, $p) {
        $this->row = $r; $this->col = $c; $this->dist = $d; $this->path = $p;
    }
}

class MinHeap extends SplMinHeap {
    protected function compare($a, $b) {
        return $a->dist === $b->dist ? strcmp($a->path, $b->path) : $a->dist - $b->dist;
    }
}

class Solution {
    private $dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]];
    private $dirText = ["l", "u", "r", "d"];

    function findShortestWay($maze, $ball, $hole) {
        $m = count($maze); $n = count($maze[0]);
        $heap = new MinHeap();
        $seen = array_fill(0, $m, array_fill(0, $n, false));
        $heap->insert(new State($ball[0], $ball[1], 0, ""));
        
        while (!$heap->isEmpty()) {
            $curr = $heap->extract();
            if ($seen[$curr->row][$curr->col]) continue;
            if ($curr->row == $hole[0] && $curr->col == $hole[1]) return $curr->path;
            $seen[$curr->row][$curr->col] = true;

            foreach ($this->dirs as $i => [$dy, $dx]) {
                $r = $curr->row; $c = $curr->col; $dist = 0;
                while ($r + $dy >= 0 && $r + $dy < $m && $c + $dx >= 0 && $c + $dx < $n && $maze[$r + $dy][$c + $dx] == 0) {
                    $r += $dy; $c += $dx; $dist++;
                    if ($r == $hole[0] && $c == $hole[1]) break;
                }
                $heap->insert(new State($r, $c, $curr->dist + $dist, $curr->path . $this->dirText[$i]));
            }
        }
        return "impossible";
    }
}

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

#hard
Задача: 502. IPO

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

У вас есть n проектов с чистой прибылью profits[i] и минимальным капиталом capital[i] для начала.

Изначально у вас есть капитал w. Завершив проект, вы получаете его прибыль, которая добавляется к вашему капиталу.

Выберите до k проектов, чтобы максимально увеличить капитал, и верните его окончательное значение. Ответ гарантированно поместится в 32-битное целое число.

Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

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

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

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

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

😎 Решение:

class State {
    public $row, $col, $dist, $path;
    public function __construct($r, $c, $d, $p) {
        $this->row = $r; $this->col = $c; $this->dist = $d; $this->path = $p;
    }
}

class MinHeap extends SplMinHeap {
    protected function compare($value1, $value2) {
        if ($value1->dist == $value2->dist) {
            return strcmp($value1->path, $value2->path);
        }
        return $value1->dist - $value2->dist;
    }
}

class Solution {
    private $directions = [[0, -1], [-1, 0], [0, 1], [1, 0]];
    private $textDirections = ["l", "u", "r", "d"];
    private $m, $n;

    function findShortestWay($maze, $ball, $hole) {
        $this->m = count($maze); $this->n = count($maze[0]);
        $heap = new MinHeap();
        $seen = array_fill(0, $this->m, array_fill(0, $this->n, false));
        $heap->insert(new State($ball[0], $ball[1], 0, ""));
        
        while (!$heap->isEmpty()) {
            $curr = $heap->extract();
            if ($seen[$curr->row][$curr->col]) continue;
            if ($curr->row == $hole[0] && $curr->col == $hole[1]) return $curr->path;
            $seen[$curr->row][$curr->col] = true;

            foreach ($this->dirs as $i => [$dy, $dx]) {
                $r = $curr->row; $c = $curr->col; $dist = 0;
                while ($r + $dy >= 0 && $r + $dy < $this->m && $c + $dx >= 0 && $c + $dx < $this->n && $maze[$r + $dy][$c + $dx] == 0) {
                    $r += $dy; $c += $dx; $dist++;
                    if ($r == $hole[0] && $c == $hole[1]) break;
                }
                $heap->insert(new State($r, $c, $curr->dist + $dist, $curr->path . $this->dirText[$i]));
            }
        }
        return "impossible";
    }
}

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

#hard
Задача: 726. Number of Atoms

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

function countOfAtoms($formula) {
    $stack = [array()];
    $n = strlen($formula);
    $i = 0;

    while ($i < $n) {
        if ($formula[$i] == '(') {
            array_push($stack, array());
            $i++;
        } else if ($formula[$i] == ')') {
            $top = array_pop($stack);
            $i++;
            $i_start = $i;
            while ($i < $n && is_numeric($formula[$i])) {
                $i++;
            }
            $multiplicity = $i > $i_start ? intval(substr($formula, $i_start, $i - $i_start)) : 1;
            foreach ($top as $name => $count) {
                $stack[count($stack) - 1][$name] = ($stack[count($stack) - 1][$name] ?? 0) + $count * $multiplicity;
            }
        } else {
            $i_start = $i;
            $i++;
            while ($i < $n && ctype_lower($formula[$i])) {
                $i++;
            }
            $name = substr($formula, $i_start, $i - $i_start);
            $i_start = $i;
            while ($i < $n && is_numeric($formula[$i])) {
                $i++;
            }
            $multiplicity = $i > $i_start ? intval(substr($formula, $i_start, $i - $i_start)) : 1;
            $stack[count($stack) - 1][$name] = ($stack[count($stack) - 1][$name] ?? 0) + $multiplicity;
        }
    }

    $countMap = $stack[0];
    ksort($countMap);
    $result = '';
    foreach ($countMap as $name => $count) {
        $result .= $name;
        if ($count > 1) {
            $result .= $count;
        }
    }
    return $result;
}

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

#hard
Задача: 727. Minimum Window Subsequence

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

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

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

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

😎 Решение:

function minWindow($s1, $s2) {
    if (!$s1 || !$s2) {
        return "";
    }

    $dictT = array_count_values(str_split($s2));
    $required = count($dictT);
    $l = 0;
    $r = 0;
    $formed = 0;
    $windowCounts = [];
    $ans = [PHP_INT_MAX, 0, 0];

    while ($r < strlen($s1)) {
        $char = $s1[$r];
        $windowCounts[$char] = ($windowCounts[$char] ?? 0) + 1;

        if (isset($dictT[$char]) && $windowCounts[$char] == $dictT[$char]) {
            $formed++;
        }

        while ($l <= $r && $formed == $required) {
            $char = $s1[$l];

            if ($r - $l + 1 < $ans[0]) {
                $ans = [$r - $l + 1, $l, $r];
            }

            $windowCounts[$char]--;
            if (isset($dictT[$char]) && $windowCounts[$char] < $dictT[$char]) {
                $formed--;
            }

            $l++;
        }

        $r++;
    }

    return $ans[0] == PHP_INT_MAX ? "" : substr($s1, $ans[1], $ans[0]);
}

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

#hard
Задача: 728. Self Dividing Numbers

Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].

Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

1⃣Переберите все числа в диапазоне от left до right.

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

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

😎 Решение:

function selfDividingNumbers($left, $right) {
    $result = [];
    for ($num = $left; $num <= $right; $num++) {
        if (isSelfDividing($num)) {
            $result[] = $num;
        }
    }
    return $result;
}

function isSelfDividing($num) {
    $n = $num;
    while ($n > 0) {
        $digit = $n % 10;
        if ($digit == 0 || $num % $digit != 0) {
            return false;
        }
        $n = (int)($n / 10);
    }
    return true;
}

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

#hard
Задача: 730. Count Different Palindromic Subsequences

Поскольку ответ может быть очень большим, верните его по модулю 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];
}

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

#hard
Задача: 732. My Calendar III

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

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

2⃣Для каждого нового события обновите словари начала и конца событий.

3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎 Решение:

class MyCalendarThree {
    private $events;
    
    function __construct() {
        $this->events = [];
    }
    
    function book($startTime, $endTime) {
        if (!isset($this->events[$startTime])) {
            $this->events[$startTime] = 0;
        }
        if (!isset($this->events[$endTime])) {
            $this->events[$endTime] = 0;
        }
        $this->events[$startTime]++;
        $this->events[$endTime]--;
        
        ksort($this->events);
        
        $active = 0;
        $maxActive = 0;
        foreach ($this->events as $time => $count) {
            $active += $count;
            $maxActive = max($maxActive, $active);
        }
        
        return $maxActive;
    }
}

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

#hard
Задача: 736. Parse Lisp Expression

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

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

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

😎 Решение:

class Solution {
    public function evaluate($expression) {
        return $this->evaluateExpression($expression, []);
    }

    private function evaluateExpression($expression, $env) {
        if ($expression[0] !== '(') {
            if (is_numeric($expression) || $expression[0] === '-') {
                return intval($expression);
            }
            return $env[$expression] ?? 0;
        }

        $tokens = $this->tokenize($expression);
        if ($tokens[0] === "let") {
            for ($i = 1; $i < count($tokens) - 2; $i += 2) {
                $env[$tokens[$i]] = $this->evaluateExpression($tokens[$i + 1], $env);
            }
            return $this->evaluateExpression($tokens[count($tokens) - 1], $env);
        } elseif ($tokens[0] === "add") {
            return $this->evaluateExpression($tokens[1], $env) + $this->evaluateExpression($tokens[2], $env);
        } elseif ($tokens[0] === "mult") {
            return $this->evaluateExpression($tokens[1], $env) * $this->evaluateExpression($tokens[2], $env);
        }
        return 0;
    }

    private function tokenize($expression) {
        $tokens = [];
        $token = '';
        $parens = 0;

        for ($i = 0; $i < strlen($expression); $i++) {
            $c = $expression[$i];
            if ($c === '(') {
                $parens++;
                if ($parens === 1) continue;
            } elseif ($c === ')') {
                $parens--;
                if ($parens === 0) {
                    $tokens = array_merge($tokens, $this->tokenize($token));
                    $token = '';
                    continue;
                }
            } elseif ($c === ' ' && $parens === 1) {
                if ($token !== '') {
                    $tokens[] = $token;
                    $token = '';
                }
                continue;
            }
            $token .= $c;
        }
        if ($token !== '') {
            $tokens[] = $token;
        }
        return $tokens;
    }
}

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

#hard
Задача: 741. Cherry Pickup

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

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

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

😎 Решение:

function cherryPickup($grid) {
    $n = count($grid);
    $dp = array_fill(0, $n, array_fill(0, $n, array_fill(0, 2 * $n - 1, -INF)));
    $dp[0][0][0] = $grid[0][0];

    for ($k = 1; $k < 2 * $n - 1; $k++) {
        for ($i1 = max(0, $k - $n + 1); $i1 <= min($n - 1, $k); $i1++) {
            for ($i2 = max(0, $k - $n + 1); $i2 <= min($n - 1, $k); $i2++) {
                $j1 = $k - $i1;
                $j2 = $k - $i2;
                if ($j1 < $n && $j2 < $n && $grid[$i1][$j1] != -1 && $grid[$i2][$j2] != -1) {
                    $maxCherries = -INF;
                    if ($i1 > 0 && $i2 > 0) $maxCherries = max($maxCherries, $dp[$i1 - 1][$i2 - 1][$k - 1]);
                    if ($i1 > 0) $maxCherries = max($maxCherries, $dp[$i1 - 1][$i2][$k - 1]);
                    if ($i2 > 0) $maxCherries = max($maxCherries, $dp[$i1][$i2 - 1][$k - 1]);
                    $maxCherries = max($maxCherries, $dp[$i1][$i2][$k - 1]);
                    if ($maxCherries != -INF) {
                        $dp[$i1][$i2][$k] = $maxCherries + $grid[$i1][$j1];
                        if ($i1 != $i2) $dp[$i1][$i2][$k] += $grid[$i2][$j2];
                    }
                }
            }
        }
    }

    return max(0, $dp[$n - 1][$n - 1][2 * $n - 1]);
}

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

#hard
Задача: 745. Prefix and Suffix Search

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter {
    private $prefixSuffixMap = [];
    
    function __construct($words) {
        foreach ($words as $index => $word) {
            $length = strlen($word);
            for ($prefixLength = 1; $prefixLength <= $length; $prefixLength++) {
                for ($suffixLength = 1; $suffixLength <= $length; $suffixLength++) {
                    $prefix = substr($word, 0, $prefixLength);
                    $suffix = substr($word, $length - $suffixLength);
                    $key = $prefix . '#' . $suffix;
                    $this->prefixSuffixMap[$key] = $index;
                }
            }
        }
    }
    
    function f($pref, $suff) {
        $key = $pref . '#' . $suff;
        return array_key_exists($key, $this->prefixSuffixMap) ? $this->prefixSuffixMap[$key] : -1;
    }
}

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

#hard
Задача: 928. Minimize Malware Spread II

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

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

😎 Решение:

function minMalwareSpread($graph, $initial) {
    $n = count($graph);

    function dfs($node, &$visited, &$component, $graph, $n) {
        $stack = [$node];
        while (!empty($stack)) {
            $u = array_pop($stack);
            $component[] = $u;
            for ($v = 0; $v < $n; $v++) {
                if ($graph[$u][$v] === 1 && !isset($visited[$v])) {
                    $visited[$v] = true;
                    $stack[] = $v;
                }
            }
        }
    }

    $components = [];
    $visited = [];

    for ($i = 0; $i < $n; $i++) {
        if (!isset($visited[$i])) {
            $component = [];
            $visited[$i] = true;
            dfs($i, $visited, $component, $graph, $n);
            $components[] = $component;
        }
    }

    $infectedInComponent = array_fill(0, count($components), 0);
    $nodeToComponent = [];

    foreach ($components as $idx => $component) {
        foreach ($component as $node) {
            $nodeToComponent[$node] = $idx;
        }
    }

    foreach ($initial as $node) {
        $componentIdx = $nodeToComponent[$node];
        $infectedInComponent[$componentIdx]++;
    }

    sort($initial);
    $minInfected = PHP_INT_MAX;
    $resultNode = $initial[0];

    foreach ($initial as $node) {
        $componentIdx = $nodeToComponent[$node];
        if ($infectedInComponent[$componentIdx] === 1) {
            $componentSize = count($components[$componentIdx]);
            if ($componentSize < $minInfected || ($componentSize === $minInfected && $node < $resultNode)) {
                $minInfected = $componentSize;
                $resultNode = $node;
            }
        }
    }

    return $resultNode;
}

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

#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

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

1⃣Отсортируйте интервалы по их конечным точкам.

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

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

😎 Решение:

function minSetSize($intervals) {
    usort($intervals, function($a, $b) {
        return $a[1] - $b[1];
    });
    $nums = [];
    foreach ($intervals as $interval) {
        $start = $interval[0];
        $end = $interval[1];
        if (empty($nums) || end($nums) < $start) {
            $nums[] = $end - 1;
            $nums[] = $end;
        } elseif (end($nums) == $end - 1) {
            $nums[] = $end;
        }
    }
    return count($nums);
}

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

#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;
    }

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