Задача: 322. Coin Change
Сложность: medium

Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.
Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1.
Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

class Solution {
    public function coinChange($coins, $amount) {
        return $this->coinChangeHelper(0, $coins, $amount);
    }

    private function coinChangeHelper($idxCoin, $coins, $amount) {
        if ($amount == 0) return 0;
        if ($idxCoin < count($coins) && $amount > 0) {
            $maxVal = intdiv($amount, $coins[$idxCoin]);
            $minCost = PHP_INT_MAX;
            for ($x = 0; $x <= $maxVal; $x++) {
                if ($amount >= $x * $coins[$idxCoin]) {
                    $res = $this->coinChangeHelper($idxCoin + 1, $coins, $amount - $x * $coins[$idxCoin]);
                    if ($res != -1) {
                        $minCost = min($minCost, $res + $x);
                    }
                }
            }
            return $minCost == PHP_INT_MAX ? -1 : $minCost;
        }
        return -1;
    }
}

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

Задача: 459. Repeated Substring Pattern
Сложность: easy

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

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

1⃣Создайте целочисленную переменную n, равную длине строки s.

2⃣Итерация по всем префиксным подстрокам длины i от 1 до n/2:
Если i делит n, объявите пустую строку pattern. Используйте внутренний цикл, который выполняется n/i раз для конкатенации подстроки, сформированной из первых i символов строки s.
Если pattern равен s, вернуть true.

3⃣Если нет подстроки, которую можно повторить для формирования s, вернуть false.

😎 Решение:

class Solution {
    public function repeatedSubstringPattern($s) {
        $n = strlen($s);
        for ($i = 1; $i <= $n / 2; $i++) {
            if ($n % $i == 0) {
                $pattern = "";
                $substr = substr($s, 0, $i);
                for ($j = 0; $j < $n / $i; $j++) {
                    $pattern .= $substr;
                }
                if ($s == $pattern) {
                    return true;
                }
            }
        }
        return false;
    }
}

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

Задача: 893. Groups of Special-Equivalent Strings
Сложность: medium

Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].

Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.

Пример:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

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

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

2⃣Использовать множество, чтобы хранить все уникальные канонические формы строк.

3⃣Размер множества будет равен количеству групп специально-эквивалентных строк.

😎 Решение:

function numSpecialEquivGroups($words) {
    $uniqueForms = [];
    
    foreach ($words as $word) {
        $evenChars = [];
        $oddChars = [];
        
        for ($i = 0; $i < strlen($word); $i++) {
            if ($i % 2 == 0) {
                $evenChars[] = $word[$i];
            } else {
                $oddChars[] = $word[$i];
            }
        }
        
        sort($evenChars);
        sort($oddChars);
        $canonicalForm = implode('', $evenChars) . implode('', $oddChars);
        $uniqueForms[$canonicalForm] = true;
    }
    
    return count($uniqueForms);
}

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.

😎 Решение:

function minCostPath($coins, $maxJump) {
    $n = count($coins);
    if ($coins[0] == -1) return [];
    
    $dp = array_fill(0, $n, PHP_INT_MAX);
    $dp[0] = $coins[0];
    $path = array_fill(0, $n, []);
    $path[0] = [1];
    
    $heap = new SplPriorityQueue();
    $heap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    $heap->insert([0, 0], -$coins[0]);
    
    while (!$heap->isEmpty()) {
        $current = $heap->extract();
        $current_cost = -$current['priority'];
        $i = $current['data'][1];
        if ($current_cost > $dp[$i]) continue;
        for ($k = 1; $k <= $maxJump; $k++) {
            if ($i + $k < $n && $coins[$i + $k] != -1) {
                $new_cost = $current_cost + $coins[$i + $k];
                if ($new_cost < $dp[$i + $k] || ($new_cost == $dp[$i + $k] && $path[$i] < array_merge($path[$i], [$i + $k + 1]))) {
                    $dp[$i + $k] = $new_cost;
                    $path[$i + $k] = array_merge($path[$i], [$i + $k + 1]);
                    $heap->insert([$new_cost, $i + $k], -$new_cost);
                }
            }
        }
    }
    
    return $dp[$n - 1] == PHP_INT_MAX ? [] : $path[$n - 1];
}

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

Задача: 984. String Without AAA or BBB
Сложность: medium

Даны два целых числа a и b, верните любую строку s, такую что:

s имеет длину a + b и содержит ровно a букв 'a' и ровно b букв 'b'.
Подстрока 'aaa' не встречается в s.
Подстрока 'bbb' не встречается в s.

Пример:

Input: a = 4, b = 1
Output: "aabaa"

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

1⃣Инициализация переменных:
Завести пустую строку s и переменные a_count и b_count для отслеживания оставшихся 'a' и 'b' соответственно.

2⃣Создание строки:
Добавляйте символы в строку s, попеременно добавляя 'a' и 'b', чтобы избегать подстрок 'aaa' и 'bbb'.
Если в строке подряд уже два символа 'a' и осталось ещё 'b', добавьте 'b' и наоборот.
Если оба символа возможны для добавления, выбирайте тот, которого осталось больше.

3⃣Добавление оставшихся символов:
После основной логики добавления символов, добавьте оставшиеся 'a' или 'b' в конец строки, если они остались.

😎 Решение:

class Solution {
    function strWithout3a3b($a, $b) {
        $result = [];
        
        while ($a > 0 || $b > 0) {
            if (count($result) >= 2 && $result[count($result) - 1] == $result[count($result) - 2]) {
                if ($result[count($result) - 1] == 'a') {
                    $result[] = 'b';
                    $b--;
                } else {
                    $result[] = 'a';
                    $a--;
                }
            } else {
                if ($a >= $b) {
                    $result[] = 'a';
                    $a--;
                } else {
                    $result[] = 'b';
                    $b--;
                }
            }
        }
        
        return implode('', $result);
    }
}

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

Задача: 342. Power of Four
Сложность: easy

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 16
Output: true

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

1⃣Проверка неотрицательности:
Убедитесь, что n больше нуля, так как степени числа четыре всегда положительны.

2⃣Проверка логарифмом:
Используйте логарифм для проверки, является ли число степенью четырех. Число n является степенью четырех, если логарифм n по основанию 4 является целым числом.

3⃣Проверка побитовым оператором:
Число является степенью четырех, если оно является степенью двух (только один бит установлен) и количество нулей после этого бита четно.

😎 Решение:

class Solution {
    function isPowerOfFour($n) {
        if ($n <= 0) return false;
        $log_n_base_4 = log($n) / log(4);
        return $log_n_base_4 == floor($log_n_base_4);
    }
}

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

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

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

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

Дан массив nums, отсортированный в порядке неубывания, и число target. Необходимо найти начальную и конечную позицию target в nums.
Если target не найден, вернуть [-1, -1].
Алгоритм должен работать за O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8  
Output: [3,4]  

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

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

2⃣Аналогично находим последнее вхождение target.

3⃣Возвращаем найденные индексы или [-1, -1], если target отсутствует.

😎 Решение:

class Solution {
    function searchRange($nums, $target) {
        return [$this->binarySearch($nums, $target, true), $this->binarySearch($nums, $target, false)];
    }

    function binarySearch($nums, $target, $findFirst) {
        $left = 0;
        $right = count($nums) - 1;
        $index = -1;

        while ($left <= $right) {
            $mid = intdiv($left + $right, 2);

            if ($nums[$mid] == $target) {
                $index = $mid;
                if ($findFirst) {
                    $right = $mid - 1;
                } else {
                    $left = $mid + 1;
                }
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return $index;
    }
}

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

Задача: 361. Bomb Enemy
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

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

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

😎 Решение:

class Solution {
    function maxKilledEnemies($grid) {
        if (count($grid) == 0) return 0;

        $rows = count($grid);
        $cols = count($grid[0]);
        $maxCount = 0;

        for ($row = 0; $row < $rows; ++$row) {
            for ($col = 0; $col < $cols; ++$col) {
                if ($grid[$row][$col] == '0') {
                    $hits = $this->killEnemies($row, $col, $grid);
                    $maxCount = max($maxCount, $hits);
                }
            }
        }

        return $maxCount;
    }

    private function killEnemies($row, $col, $grid) {
        $enemyCount = 0;
        $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

        foreach ($directions as $direction) {
            $r = $row + $direction[0];
            $c = $col + $direction[1];

            while ($r >= 0 && $r < count($grid) && $c >= 0 && $c < count($grid[0])) {
                if ($grid[$r][$c] == 'W') break;
                if ($grid[$r][$c] == 'E') $enemyCount++;
                $r += $direction[0];
                $c += $direction[1];
            }
        }

        return $enemyCount;
    }
}

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