PHP | LeetCode

Задача: 155. Min Stack
Сложность: medium

Разработайте стек, который поддерживает операции добавления элемента, удаления элемента, получения верхнего элемента и извлечения минимального элемента за постоянное время.
Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.
Вы должны реализовать решение с временной сложностью O(1) для каждой функции.

Пример:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

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

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

2⃣Работа со стеком:
Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.

3⃣Доступ к элементам:
Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.

😎 Решение:

class MinStack {
    private $stack = [];

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

    private function last() {
        return end($this->stack);
    }

    public function push($x) {
        if (empty($this->stack)) {
            array_push($this->stack, [$x, $x]);
            return;
        }

        $currentMin = $this->last()[1];
        array_push($this->stack, [$x, min($currentMin, $x)]);
    }

    public function pop() {
        array_pop($this->stack);
    }

    public function top() {
        $last = $this->last();
        return $last[0];
    }

    public function getMin() {
        $last = $this->last();
        return $last[1];
    }
}

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

Задача: 205. Isomorphic Strings
Сложность: easy

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

Пример:

Input: s = "egg", t = "add"
Output: true

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

1⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

class Solution {
    function isIsomorphic($s, $t) {
        $mappingStoT = [];
        $mappingTtoS = [];

        for ($i = 0; $i < strlen($s); ++$i) {
            $c1 = $s[$i];
            $c2 = $t[$i];

            if (!isset($mappingStoT[$c1]) && !isset($mappingTtoS[$c2])) {
                $mappingStoT[$c1] = $c2;
                $mappingTtoS[$c2] = $c1;
            } else if (($mappingStoT[$c1] ?? null) !== $c2 || ($mappingTtoS[$c2] ?? null) !== $c1) {
                return false;
            }
        }

        return true;
    }
}

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

Задача: 1248. Count Number of Nice Subarrays
Сложность: medium

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

Пример:

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

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

1⃣Преобразуйте массив чисел nums, заменив все чётные числа на 0, а все нечётные числа на 1.

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

3⃣Подсчитайте количество таких подмассивов и верните этот результат.

😎 Решение:

class Solution {
    function numberOfSubarrays($nums, $k) {
        return $this->atMost($nums, $k) - $this->atMost($nums, $k - 1);
    }

    private function atMost($nums, $k) {
        $res = 0;
        $left = 0;
        $count = 0;
        for ($right = 0; $right < count($nums); $right++) {
            if ($nums[$right] % 2 === 1) $count++;
            while ($count > $k) {
                if ($nums[$left++] % 2 === 1) $count--;
            }
            $res += $right - $left + 1;
        }
        return $res;
    }
}

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

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

class Solution {
    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isCompleteTree($root) {
        if ($root === null) {
            return true;
        }

        $queue = [$root];
        $nullNodeFound = false;

        while (!empty($queue)) {
            $node = array_shift($queue);
            
            if ($node === null) {
                $nullNodeFound = true;
            } else {
                if ($nullNodeFound) {
                    return false;
                }
                $queue[] = $node->left;
                $queue[] = $node->right;
            }
        }
        return true;
    }
}

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

Задача: 979. Distribute Coins in Binary Tree
Сложность: medium

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

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

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

Пример:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

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

1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.

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

3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.

😎 Решение:

class Solution {
    private $moves;

    function distributeCoins($root) {
        $this->moves = 0;
        $this->dfs($root);
        return $this->moves;
    }

    private function dfs($current) {
        if ($current == null) return 0;
        $leftCoins = $this->dfs($current->left);
        $rightCoins = $this->dfs($current->right);
        $this->moves += abs($leftCoins) + abs($rightCoins);
        return $current->val - 1 + $leftCoins + $rightCoins;
    }
}

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

Задача: 441. Arranging Coins
Сложность: medium

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.
Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

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

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

class Solution {
    function arrangeCoins($n) {
        return (int)(sqrt(2 * $n + 0.25) - 0.5);
    }
}

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

Задача: 57. Insert Interval
Сложность: medium

Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.
Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).
Верните массив intervals после вставки.
Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

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

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

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

3⃣Обработка интервалов после вставки:
Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.
Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом.

😎 Решение:

class Solution {
    public function insert($intervals, $newInterval) {
        $res = [];
        $i = 0;

        // Process intervals with no overlap before the new interval
        while ($i < count($intervals) && $intervals[$i][1] < $newInterval[0]) {
            array_push($res, $intervals[$i]);
            $i++;
        }

        // Merge overlapping intervals with newInterval
        while ($i < count($intervals) && $newInterval[1] >= $intervals[$i][0]) {
            $newInterval[0] = min($newInterval[0], $intervals[$i][0]);
            $newInterval[1] = max($newInterval[1], $intervals[$i][1]);
            $i++;
        }
        array_push($res, $newInterval);

        // Append remaining intervals after merging
        while ($i < count($intervals)) {
            array_push($res, $intervals[$i]);
            $i++;
        }

        return $res;
    }
}

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

Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

class Solution {
    function minSwaps($data) {
        $ones = array_sum($data);
        $cnt_one = 0;
        $max_one = 0;
        $left = 0;
        $right = 0;

        while ($right < count($data)) {
            $cnt_one += $data[$right++];
            if ($right - $left > $ones) {
                $cnt_one -= $data[$left++];
            }
            $max_one = max($max_one, $cnt_one);
        }
        return $ones - $max_one;
    }
}

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

Задача: 1396. Design Underground System
Сложность: medium

Подземная железнодорожная система отслеживает время поездок между станциями для вычисления среднего времени поездки от одной станции до другой.

Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке.

Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5

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

1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.

2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.

3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.

😎 Решение:

class UndergroundSystem {
    private $journeyData;
    private $checkInData;

    function __construct() {
        $this->journeyData = [];
        $this->checkInData = [];
    }

    function checkIn($id, $stationName, $t) {
        $this->checkInData[$id] = [$stationName, $t];
    }

    function checkOut($id, $stationName, $t) {
        list($startStation, $startTime) = $this->checkInData[$id];
        unset($this->checkInData[$id]);
        $routeKey = "{$startStation}->{$stationName}";
        $tripTime = $t - $startTime;
        if (!isset($this->journeyData[$routeKey])) {
            $this->journeyData[$routeKey] = [0, 0];
        }
        list($totalTime, $trips) = $this->journeyData[$routeKey];
        $this->journeyData[$routeKey] = [$totalTime + $tripTime, $trips + 1];
    }

    function getAverageTime($startStation, $endStation) {
        list($totalTime, $trips) = $this->journeyData["{$startStation}->{$endStation}"];
        return $totalTime / $trips;
    }
}

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    function getSum($a, $b) {
        $x = abs($a);
        $y = abs($b);
        if ($x < $y) return $this->getSum($b, $a);
        $sign = $a > 0 ? 1 : -1;

        if ($a * $b >= 0) {
            while ($y != 0) {
                $carry = ($x & $y) << 1;
                $x ^= $y;
                $y = $carry;
            }
        } else {
            while ($y != 0) {
                $borrow = ((~$x) & $y) << 1;
                $x ^= $y;
                $y = $borrow;
            }
        }
        return $x * $sign;
    }
}

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

Задача: 152. Maximum Product Subarray
Сложность: Medium

Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

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

1⃣Инициализация:
Если массив nums пуст, возвращаем 0, так как нет элементов для обработки.
Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.

2⃣Перебор элементов:
Используем вложенные циклы для обработки всех возможных подмассивов:
Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива.
Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив.

3⃣Вычисление произведения и обновление результата:
Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого.
Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.

😎 Решение:

class Solution {
    function maxProduct($nums) {
        if (count($nums) == 0) return 0;

        $result = $nums[0];

        for ($i = 0; $i < count($nums); $i++) {
            $accu = 1;
            for ($j = $i; $j < count($nums); $j++) {
                $accu *= $nums[$j];
                $result = max($result, $accu);
            }
        }

        return $result;
    }
}

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

Задача: 594. Longest Harmonious Subsequence
Сложность: easy

Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1.
Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.
Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

3⃣Верните максимальную длину гармоничной подпоследовательности.

😎 Решение:

class Solution {
    function findLHS($nums) {
        $count = [];
        $res = 0;
        
        foreach ($nums as $num) {
            if (isset($count[$num])) {
                $count[$num]++;
            } else {
                $count[$num] = 1;
            }
            if (isset($count[$num + 1])) {
                $res = max($res, $count[$num] + $count[$num + 1]);
            }
            if (isset($count[$num - 1])) {
                $res = max($res, $count[$num] + $count[$num - 1]);
            }
        }
        
        return $res;
    }
}

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

Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

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

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

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

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

😎 Решение:

class Solution {
    function minRemoveToMakeValid($s) {
        $stack = [];
        $s = str_split($s);
        for ($i = 0; $i < count($s); $i++) {
            if ($s[$i] == '(') {
                array_push($stack, $i);
            } elseif ($s[$i] == ')') {
                if (!empty($stack)) {
                    array_pop($stack);
                } else {
                    $s[$i] = '';
                }
            }
        }
        while (!empty($stack)) {
            $s[array_pop($stack)] = '';
        }
        return implode('', $s);
    }
}

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

Задача: 784. Letter Case Permutation
Сложность: medium

Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве.

Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

2⃣Если c является цифрой, мы добавим его к каждому слову.

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

😎 Решение:

class Solution {
    function letterCasePermutation($S) {
        $ans = [[]];

        foreach (str_split($S) as $char) {
            $n = count($ans);
            if (ctype_alpha($char)) {
                for ($i = 0; $i < $n; $i++) {
                    $ans[] = $ans[$i];
                    $ans[$i][] = strtolower($char);
                    $ans[$n + $i][] = strtoupper($char);
                }
            } else {
                for ($i = 0; $i < $n; $i++) {
                    $ans[$i][] = $char;
                }
            }
        }

        return array_map(function($arr) {
            return implode('', $arr);
        }, $ans);
    }
}

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

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

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

function numSubarraysWithSum($nums, $goal) {
    $prefixSumCount = [0 => 1];
    $currentSum = 0;
    $count = 0;

    foreach ($nums as $num) {
        $currentSum += $num;

        if (isset($prefixSumCount[$currentSum - $goal])) {
            $count += $prefixSumCount[$currentSum - $goal];
        }

        if (isset($prefixSumCount[$currentSum])) {
            $prefixSumCount[$currentSum]++;
        } else {
            $prefixSumCount[$currentSum] = 1;
        }
    }

    return $count;
}

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

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

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

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

Решение:

class Solution {
    private $graph = [];
    private $nodesInComp = [];
    private $visited = [];

    private function overlap($a, $b) {
        return $a[0] <= $b[1] && $b[0] <= $a[1];
    }

    private function buildGraph($intervals) {
        foreach ($intervals as $interval1) {
            foreach ($intervals as $interval2) {
                if ($this->overlap($interval1, $interval2)) {
                    $this->graph[serialize($interval1)][] = $interval2;
                    $this->graph[serialize($interval2)][] = $interval1;
                }
            }
        }
    }

    private function mergeNodes($nodes) {
        $minStart = $nodes[0][0];
        $maxEnd = $nodes[0][1];
        foreach ($nodes as $node) {
            $minStart = min($minStart, $node[0]);
            $maxEnd = max($maxEnd, $node[1]);
        }
        return [$minStart, $maxEnd];
    }

    private function markComponentDFS($start, $compNumber) {
        $stack = [];
        array_push($stack, $start);
        while (!empty($stack)) {
            $node = array_pop($stack);
            if (!in_array($node, $this->visited, true)) {
                $this->visited[] = $node;
                $this->nodesInComp[$compNumber][] = $node;
                foreach ($this->graph[serialize($node)] as $child) {
                    array_push($stack, $child);
                }
            }
        }
    }

    private function buildComponents($intervals) {
        $compNumber = 0;
        foreach ($intervals as $interval) {
            if (!in_array($interval, $this->visited, true)) {
                $this->markComponentDFS($interval, $compNumber);
                $compNumber++;
            }
        }
    }

    public function merge($intervals) {
        $this->buildGraph($intervals);
        $this->buildComponents($intervals);
        $merged = [];
        foreach ($this->nodesInComp as $components) {
            $merged[] = $this->mergeNodes($components);
        }
        return $merged;
    }
}

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

Задача: 724. Find Pivot Index
Сложность: easy

Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.

Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

1⃣Вычислите сумму всех элементов массива.

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

3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.

😎 Решение:

function pivotIndex($nums) {
    $totalSum = array_sum($nums);
    $leftSum = 0;
    foreach ($nums as $i => $num) {
        if ($leftSum == $totalSum - $leftSum - $num) {
            return $i;
        }
        $leftSum += $num;
    }
    return -1;
}

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

Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]
Output: 22

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

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

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

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

😎 Решение:

class TreeNode {
    public $val = 0;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function sumRootToLeaf($root) {
        return $this->dfs($root, 0);
    }
    
    private function dfs($node, $currentValue) {
        if ($node === null) return 0;
        $currentValue = ($currentValue << 1) | $node->val;
        if ($node->left === null && $node->right === null) return $currentValue;
        return $this->dfs($node->left, $currentValue) + $this->dfs($node->right, $currentValue);
    }
}

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

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

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

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

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

😎 Решение:

function numWays($steps, $arrLen) {
    $mod = 1000000007;
    $max_pos = min($arrLen - 1, $steps);
    $dp = array_fill(0, $max_pos + 1, 0);
    $dp[0] = 1;
    for ($step = 0; $step < $steps; $step++) {
        $new_dp = array_fill(0, $max_pos + 1, 0);
        for ($i = 0; $i <= $max_pos; $i++) {
            $new_dp[$i] = $dp[$i] % $mod;
            if ($i > 0) $new_dp[$i] = ($new_dp[$i] + $dp[$i - 1]) % $mod;
            if ($i < $max_pos) $new_dp[$i] = ($new_dp[$i] + $dp[$i + 1]) % $mod;
        }
        $dp = $new_dp;
    }
    return $dp[0];
}

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

Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.

2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.

😎 Решение:

class Solution {
    function videoStitching($clips, $T) {
        usort($clips, function($a, $b) {
            return $a[0] == $b[0] ? $b[1] - $a[1] : $a[0] - $b[0];
        });
        $end = -1;
        $end2 = 0;
        $res = 0;
        
        foreach ($clips as $clip) {
            if ($end2 >= $T || $clip[0] > $end2) break;
            if ($end < $clip[0] && $clip[0] <= $end2) {
                $res++;
                $end = $end2;
            }
            $end2 = max($end2, $clip[1]);
        }
        return $end2 >= $T ? $res : -1;
    }
}

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