PHP | LeetCode

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

2⃣Если ключ начинается с префикса, добавить его значение к ответу.

3⃣Вернуть полученную сумму как результат.

😎 Решение:

class MapSum {
    private $mapData;

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

    public function insert($key, $val) {
        $this->mapData[$key] = $val;
    }

    public function sum($prefix) {
        $ans = 0;
        foreach ($this->mapData as $key => $val) {
            if (strpos($key, $prefix) === 0) {
                $ans += $val;
            }
        }
        return $ans;
    }
}

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

Задача: 734. Sentence Similarity
Сложность: easy

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].
Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false.

2⃣Создайте словарь для хранения всех пар похожих слов.

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

😎 Решение:

function areSentencesSimilar($sentence1, $sentence2, $similarPairs) {
    if (count($sentence1) != count($sentence2)) {
        return false;
    }

    $similar = [];
    foreach ($similarPairs as $pair) {
        list($x, $y) = $pair;
        if (!isset($similar[$x])) {
            $similar[$x] = [];
        }
        if (!isset($similar[$y])) {
            $similar[$y] = [];
        }
        $similar[$x][] = $y;
        $similar[$y][] = $x;
    }

    for ($i = 0; $i < count($sentence1); $i++) {
        $w1 = $sentence1[$i];
        $w2 = $sentence2[$i];
        if ($w1 != $w2 && (!isset($similar[$w1]) || !in_array($w2, $similar[$w1]))) {
            return false;
        }
    }

    return true;
}

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

Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

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

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

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

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

function countPrimeSetBits($left, $right) {
    function countBits($x) {
        return substr_count(decbin($x), '1');
    }
    
    function isPrime($x) {
        if ($x < 2) return false;
        for ($i = 2; $i * $i <= $x; $i++) {
            if ($x % $i == 0) return false;
        }
        return true;
    }
    
    $count = 0;
    for ($num = $left; $num <= $right; $num++) {
        if (isPrime(countBits($num))) {
            $count++;
        }
    }
    return $count;
}

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

Задача: 134. Gas Station
Сложность: medium

Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].
У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.
Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.

Пример:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

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

1⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0.

2⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i].
Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2.

3⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer.

😎 Решение:

function canCompleteCircuit($gas, $cost) {
    $currGain = 0;
    $totalGain = 0;
    $answer = 0;
    for ($i = 0; $i < count($gas); ++$i) {
        $totalGain += $gas[$i] - $cost[$i];
        $currGain += $gas[$i] - $cost[$i];
        if ($currGain < 0) {
            $answer = $i + 1;
            $currGain = 0;
        }
    }
    return $totalGain >= 0 ? $answer : -1;
}

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

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

Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).

Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.

Пример:

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

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

1⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

function subsets($nums) {
    $output = [];
    $n = count($nums);
    
    function backtrack($first, $curr, $k, &$output, $nums, $n) {
        if (count($curr) == $k) {
            $output[] = $curr;
            return;
        }
        for ($i = $first; $i < $n; $i++) {
            $curr[] = $nums[$i];
            backtrack($i + 1, $curr, $k, $output, $nums, $n);
            array_pop($curr);
        }
    }
    
    for ($k = 0; $k <= $n; $k++) {
        backtrack(0, [], $k, $output, $nums, $n);
    }
    return $output;
}

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

Задача: 1247. Minimum Swaps to Make Strings Equal
Сложность: hard

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

Input: arr = [1,2]
Output: 2

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

1⃣Подсчет несоответствующих пар:
Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'.

2⃣Проверка четности:
Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1.

3⃣Вычисление минимального количества замен:
Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2.
Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2.

😎 Решение:

function minimumSwap($s1, $s2) {
    $xy = 0;
    $yx = 0;
    for ($i = 0; $i < strlen($s1); $i++) {
        if ($s1[$i] === 'x' && $s2[$i] === 'y') {
            $xy++;
        } else if ($s1[$i] === 'y' && $s2[$i] === 'x') {
            $yx++;
        }
    }
    if (($xy + $yx) % 2 != 0) {
        return -1;
    }
    return intdiv($xy, 2) + intdiv($yx, 2) + ($xy % 2) * 2;
}

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

Задача: 382. Linked List Random Node
Сложность: medium

Дан односвязный список, вернуть значение случайного узла из списка. Каждый узел должен иметь одинаковую вероятность быть выбранным.
Реализуйте класс Solution:
Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

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

😎 Решение:

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

class Solution {
    private $range = array();

    public function __construct($head) {
        while ($head !== null) {
            $this->range[] = $head->val;
            $head = $head->next;
        }
    }

    public function getRandom() {
        $pick = rand(0, count($this->range) - 1);
        return $this->range[$pick];
    }
}
?>

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

Задача: 130. Surrounded Regions
Сложность: Medium

Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:

Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.

Пример:

Input: board = [["X"]]

Output: [["X"]]

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

1⃣Выбор начальных ячеек и инициация DFS:
Начинаем с выбора всех ячеек, расположенных на границах доски.
Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS).

2⃣Логика и выполнение DFS:
Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'.
Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'.

3⃣Классификация и финальная обработка ячеек:
После обхода всех граничных ячеек мы получаем три типа ячеек:
Ячейки с буквой 'X': эти ячейки можно считать стеной.
Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'.
Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'.

😎 Решение:

function solve(&$board) {
    if ($board == null || count($board) == 0) {
        return;
    }
    $ROWS = count($board);
    $COLS = count($board[0]);
    $borders = [];
    for ($r = 0; $r < $ROWS; ++$r) {
        array_push($borders, [$r, 0], [$r, $COLS - 1]);
    }
    for ($c = 0; $c < $COLS; ++$c) {
        array_push($borders, [0, $c], [$ROWS - 1, $c]);
    }
    foreach ($borders as $pair) {
        dfs($board, $pair[0], $pair[1]);
    }
    for ($r = 0; $r < $ROWS; ++$r) {
        for ($c = 0; $c < $COLS; ++$c) {
            if ($board[$r][$c] == "O") $board[$r][$c] = "X";
            if ($board[$r][$c] == "E") $board[$r][$c] = "O";
        }
    }
}

function dfs(&$board, $row, $col) {
    if ($board[$row][$col] != "O") return;
    $board[$row][$col] = "E";
    $ROWS = count($board);
    $COLS = count($board[0]);
    if ($col < $COLS - 1) dfs($board, $row, $col + 1);
    if ($row < $ROWS - 1) dfs($board, $row + 1, $col);
    if ($col > 0) dfs($board, $row, $col - 1);
    if ($row > 0) dfs($board, $row - 1, $col);
}

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