Задача №21. Merge Two Sorted Lists
Сложность: easy

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Верните заголовок объединенного связанного списка.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]

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

1⃣Создать новый список для объединенного результата.

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

3⃣Добавить оставшиеся элементы после окончания одного из списков.

😎 Решение:

class Solution { 

    function mergeTwoLists($list1, $list2) { 
        $newList = new ListNode(); 
        $current = $newList; 

        while($list1 || $list2) { 
            if ($list1 && !$list2) { 
                $current->next = new ListNode($list1->val); 
                $list1 = $list1->next; 
            } elseif (!$list1 && $list2) { 
                $current->next = new ListNode($list2->val); 
                $list2 = $list2->next; 
            } else { 
                if ($list1->val <= $list2->val) { 
                    $current->next = new ListNode($list1->val); 
                    $list1 = $list1->next; 
                } else { 
                    $current->next = new ListNode($list2->val); 
                    $list2 = $list2->next; 
                } 
            } 
            $current = $current->next; 
        } 

        return $newList->next; 
    } 
}

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

Задача: 1003. Check If Word Is Valid After Substitutions
Сложность: medium

Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false.

Пример:

Input: s = "aabcbc"
Output: true

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

1⃣Проверка допустимости длины строки:
Проверьте, что длина строки s кратна 3. Если нет, верните false.

2⃣Использование стека для проверки:
Инициализируйте пустой стек. Проходите по каждому символу строки s.
Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false.
Если текущий символ не 'c', добавьте его в стек.

3⃣Проверка остатка стека:
В конце, если стек пуст, верните true. Иначе верните false.

😎 Решение:

class Solution {
    function isValid($s) {
        if (strlen($s) % 3 != 0) return false;

        $stack = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if ($char == 'c') {
                if (count($stack) < 2 || array_pop($stack) != 'b' || array_pop($stack) != 'a') {
                    return false;
                }
            } else {
                $stack[] = $char;
            }
        }

        return empty($stack);
    }
}

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

Задача: 1429. First Unique Number
Сложность: medium

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

Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.

Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

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

2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет.

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

😎 Решение:

class FirstUnique {
    private $queue;
    private $isUnique;

    function __construct($nums) {
        $this->queue = new SplDoublyLinkedList();
        $this->isUnique = [];
        foreach ($nums as $num) {
            $this->add($num);
        }
    }

    function showFirstUnique() {
        while (!$this->queue->isEmpty() && !$this->isUnique[$this->queue->bottom()]) {
            $this->queue->shift();
        }
        if ($this->queue->isEmpty()) {
            return -1;
        }
        return $this->queue->bottom();
    }

    function add($value) {
        if (!isset($this->isUnique[$value])) {
            $this->isUnique[$value] = true;
            $this->queue->push($value);
        } elseif ($this->isUnique[$value]) {
            $this->isUnique[$value] = false;
        }
    }
}

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

Задача: 553. Optimal Division
Сложность: medium

Дано целочисленный массив nums. Соседние целые числа в nums будут выполнять деление с плавающей запятой.
Например, для nums = [2,3,4] мы будем вычислять выражение "2/3/4".
Однако, вы можете добавить любое количество скобок в любое место, чтобы изменить приоритет операций. Вы хотите добавить эти скобки так, чтобы значение выражения после вычисления было максимальным.
Верните соответствующее выражение, которое имеет максимальное значение в строковом формате.

Пример:

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

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

1⃣Разверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры во втором числе: держите переменную переноса, изначально равную 0. Инициализируйте массив (currentResult), начинающийся с некоторых нулей в зависимости от места цифры во втором числе.

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

3⃣После итерации по каждой цифре в первом числе, если перенос не равен нулю, добавьте перенос к массиву currentResult. Добавьте currentResult к массиву ans. Если последняя цифра в ans равна нулю, перед разворотом ans удалите этот ноль, чтобы избежать ведущего нуля в окончательном ответе. Разверните ans и верните его.

😎 Решение:

class Solution {
    private function addStrings($num1, $num2) {
        $ans = [];
        $carry = 0;
        $n1 = count($num1);
        $n2 = count($num2);

        for ($i = 0; $i < max($n1, $n2) || $carry; $i++) {
            $digit1 = $i < $n1 ? $num1[$i] : 0;
            $digit2 = $i < $n2 ? $num2[$i] : 0;
            $sum = $digit1 + $digit2 + $carry;
            $carry = intdiv($sum, 10);
            $ans[] = $sum % 10;
        }
        return $ans;
    }

    private function multiplyOneDigit($firstNumber, $secondNumberDigit, $numZeros) {
        $currentResult = array_fill(0, $numZeros, 0);
        $carry = 0;

        for ($i = 0; $i < strlen($firstNumber); $i++) {
            $multiplication = (intval($secondNumberDigit) * intval($firstNumber[$i])) + $carry;
            $carry = intdiv($multiplication, 10);
            $currentResult[] = $multiplication % 10;
        }
        if ($carry != 0) {
            $currentResult[] = $carry;
        }
        return $currentResult;
    }

    public function multiply($firstNumber, $secondNumber) {
        if ($firstNumber === "0" || $secondNumber === "0") {
            return "0";
        }

        $firstNumber = strrev($firstNumber);
        $secondNumber = strrev($secondNumber);

        $ans = array_fill(0, strlen($firstNumber) + strlen($secondNumber), 0);

        for ($i = 0; $i < strlen($secondNumber); $i++) {
            $ans = $this->addStrings($this->multiplyOneDigit($firstNumber, $secondNumber[$i], $i), $ans);
        }

        while (end($ans) === 0) {
            array_pop($ans);
        }

        return implode('', array_reverse($ans));
    }
}

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

Задача: 433. Minimum Genetic Mutation
Сложность: medium

Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.
Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.
Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.
Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.
Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк.

Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

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

1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene.

2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen.

3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1.

😎 Решение:

function minMutation($start, $end, $bank) {
    $queue = [$start];
    $seen = [$start => true];
    $steps = 0;

    while (count($queue) > 0) {
        $nodesInQueue = count($queue);

        for ($j = 0; $j < $nodesInQueue; $j++) {
            $node = array_shift($queue);

            if ($node === $end) {
                return $steps;
            }

            foreach (str_split("ACGT") as $c) {
                for ($i = 0; $i < strlen($node); $i++) {
                    $neighbor = substr($node, 0, $i) . $c . substr($node, $i + 1);
                    if (!isset($seen[$neighbor]) && in_array($neighbor, $bank)) {
                        $queue[] = $neighbor;
                        $seen[$neighbor] = true;
                    }
                }
            }
        }

        $steps++;
    }

    return -1;
}

echo minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"]) . "\n"; // Output: 1
echo minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]) . "\n"; // Output: 2
echo minMutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"]) . "\n"; // Output: 3

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

Задача: 860. Lemonade Change
Сложность: easy

На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5.

Обратите внимание, что изначально у вас нет никакой сдачи.

Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае.

Пример:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

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

1⃣Инициализируем переменные для хранения количества пятерок и десяток. Если покупатель платит $5, добавляем эту купюру в наш запас.

2⃣Если покупатель платит $10, проверяем наличие пятерки для сдачи. Если пятерки нет, возвращаем false. В противном случае, уменьшаем количество пятерок и увеличиваем количество десяток.

3⃣Если покупатель платит $20, сначала пытаемся дать сдачу десяткой и пятеркой. Если это невозможно, проверяем наличие трех пятерок. Если не можем дать сдачу, возвращаем false. После обработки всех покупателей, возвращаем true.

😎 Решение:

class Solution {
    function lemonadeChange($bills) {
        $five = 0;
        $ten = 0;
        foreach ($bills as $bill) {
            if ($bill == 5) {
                $five++;
            } elseif ($bill == 10) {
                if ($five == 0) return false;
                $five--;
                $ten++;
            } else {
                if ($five > 0 && $ten > 0) {
                    $five--;
                    $ten--;
                } elseif ($five >= 3) {
                    $five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

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

Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy

Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.

На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).

Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.

Пример:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

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

1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.

2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.

3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.

😎 Решение:

class Solution {
    function minStartValue($nums) {
        $startValue = 1;
        while (true) {
            $total = $startValue;
            $isValid = true;
            foreach ($nums as $num) {
                $total += $num;
                if ($total < 1) {
                    $isValid = false;
                    break;
                }
            }
            if ($isValid) {
                return $startValue;
            }
            $startValue++;
        }
    }
}

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

Задача: 1046. Last Stone Weight
Сложность: easy

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

1⃣Создай максимальную кучу из массива камней.

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

3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось.

😎 Решение:

function lastStoneWeight($stones) {
    rsort($stones);
    
    while (count($stones) > 1) {
        $first = array_shift($stones);
        $second = array_shift($stones);
        if ($first != $second) {
            array_push($stones, $first - $second);
            rsort($stones);
        }
    }
    
    return count($stones) ? $stones[0] : 0;
}

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

Задача: 136. Single Number
Сложность: easy

Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

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

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

1⃣Переберите все элементы в массиве nums.

2⃣Если какое-то число в nums новое для массива, добавьте его.

3⃣Если какое-то число уже есть в массиве, удалите его.

😎 Решение:

function singleNumber($nums) {
    $noDuplicateList = [];
    foreach ($nums as $i) {
        if (!in_array($i, $noDuplicateList)) {
            array_push($noDuplicateList, $i);
        } else {
            $index = array_search($i, $noDuplicateList);
            array_splice($noDuplicateList, $index, 1);
        }
    }
    return $noDuplicateList[0];
}

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

Задача: 1053. Previous Permutation With One Swap
Сложность: medium

Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].

Пример:

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

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

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

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

😎 Решение:

function prevPermOpt1($arr) {
    $n = count($arr);
    for ($i = $n - 2; $i >= 0; $i--) {
        if ($arr[$i] > $arr[$i + 1]) {
            break;
        }
    }
    if ($i == -1) {
        return $arr;
    }
    
    for ($j = $n - 1; $j > $i; $j--) {
        if ($arr[$j] < $arr[$i] && ($j == $n - 1 || $arr[$j] != $arr[$j + 1])) {
            break;
        }
    }
    
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
    
    return $arr;
}

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

Задача: 161. One Edit Distance
Сложность: medium

Даны две строки s и t. Верните true, если они отличаются ровно на одну операцию редактирования, иначе верните false.
Строка s считается отличающейся на одну операцию редактирования от строки t, если можно:
- Вставить ровно один символ в строку s, чтобы получить t.
- Удалить ровно один символ из строки s, чтобы получить t.
- Заменить ровно один символ в строке s на другой символ, чтобы получить t.

Пример:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

1⃣Проверка длины строк:
Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.
Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2⃣Сравнение строк посимвольно:
Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.
Если находите различающийся символ:
Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.
Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

3⃣Проверка на возможное добавление символа в конец s:
Если после посимвольного сравнения не было найдено различий на всей длине s и t длиннее s на один символ, это означает, что t можно получить добавлением одного символа в конец s. В этом случае верните true.
В противном случае верните false, так как это означает, что t либо имеет больше отличий, либо такой же размер как s без возможности привести их к равенству одной операцией редактирования.

😎 Решение:

class Solution {
    function isOneEditDistance($s, $t) {
        $ns = strlen($s);
        $nt = strlen($t);
        if ($ns > $nt) return $this->isOneEditDistance($t, $s);
        if ($nt - $ns > 1) return false;

        for ($i = 0; $i < $ns; $i++) {
            if ($s[$i] != $t[$i]) {
                if ($ns == $nt) return substr($s, $i + 1) == substr($t, $i + 1);
                else return substr($s, $i) == substr($t, $i + 1);
            }
        }
        return $ns + 1 == $nt;
    }
}

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

Задача: 238. Product of Array Except Self
Сложность: medium

Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i].
Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число.
Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления.

Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

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

1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].

2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.

3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.

😎 Решение:

class Solution {
    function productExceptSelf($nums) {
        $length = count($nums);
        $L = array_fill(0, $length, 1);
        $R = array_fill(0, $length, 1);
        $answer = array_fill(0, $length, 1);

        for ($i = 1; $i < $length; $i++) {
            $L[$i] = $nums[$i - 1] * $L[$i - 1];
        }

        for ($i = $length - 2; $i >= 0; $i--) {
            $R[$i] = $nums[$i + 1] * $R[$i + 1];
        }

        for ($i = 0; $i < $length; $i++) {
            $answer[$i] = $L[$i] * $R[$i];
        }

        return $answer;
    }
}

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

Задача: 715. Range Module
Сложность: hard

Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).

Пример:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

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

1⃣Инициализируйте класс RangeModule с пустым списком диапазонов.

2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.

3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.

😎 Решение:

class RangeModule {

    private $ranges;

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

    function addRange($left, $right) {
        $newRanges = [];
        $i = 0;
        while ($i < count($this->ranges) && $this->ranges[$i][1] < $left) {
            $newRanges[] = $this->ranges[$i];
            $i++;
        }
        while ($i < count($this->ranges) && $this->ranges[$i][0] <= $right) {
            $left = min($left, $this->ranges[$i][0]);
            $right = max($right, $this->ranges[$i][1]);
            $i++;
        }
        $newRanges[] = [$left, $right];
        while ($i < count($this->ranges)) {
            $newRanges[] = $this->ranges[$i];
            $i++;
        }
        $this->ranges = $newRanges;
    }

    function queryRange($left, $right) {
        foreach ($this->ranges as $range) {
            if ($range[0] <= $left && $right <= $range[1]) {
                return true;
            }
        }
        return false;
    }

    function removeRange($left, $right) {
        $newRanges = [];
        foreach ($this->ranges as $range) {
            if ($range[0] < $left) {
                $newRanges[] = [$range[0], min($range[1], $left)];
            }
            if ($right < $range[1]) {
                $newRanges[] = [max($range[0], $right), $range[1]];
            }
        }
        $this->ranges = $newRanges;
    }
}

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

Задача: 642. Design Search Autocomplete System
Сложность: hard

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

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

2⃣Операции вставки
Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

3⃣Операции удаления
Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class TrieNode {
    public $children;
    public $count;

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

class AutocompleteSystem {
    private $root;
    private $prefix;

    function __construct($sentences, $times) {
        $this->root = new TrieNode();
        $this->prefix = "";
        for ($i = 0; $i < count($sentences); $i++) {
            $this->add($sentences[$i], $times[$i]);
        }
    }

    private function add($sentence, $count) {
        $node = $this->root;
        for ($i = 0; $i < strlen($sentence); $i++) {
            $char = $sentence[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
            if (!isset($node->count[$sentence])) {
                $node->count[$sentence] = 0;
            }
            $node->count[$sentence] += $count;
        }
    }

    function input($c) {
        if ($c == '#') {
            $this->add($this->prefix, 1);
            $this->prefix = "";
            return [];
        }

        $this->prefix .= $c;
        $node = $this->root;
        for ($i = 0; $i < strlen($this->prefix); $i++) {
            $char = $this->prefix[$i];
            if (!isset($node->children[$char])) {
                return [];
            }
            $node = $node->children[$char];
        }

        $pq = [];
        foreach ($node->count as $sentence => $count) {
            $pq[] = [$sentence, $count];
        }

        usort($pq, function($a, $b) {
            if ($a[1] == $b[1]) {
                return strcmp($a[0], $b[0]);
            }
            return $b[1] - $a[1];
        });

        $result = [];
        for ($i = 0; $i < min(3, count($pq)); $i++) {
            $result[] = $pq[$i][0];
        }

        return $result;
    }
}

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

Задача: 376. Wiggle Subsequence
Сложность: easy

Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями.
Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными.
В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю.
Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке.

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

Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

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

1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием.

2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием.

3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания.

😎 Решение:

class Solution {
    public function islandPerimeter($grid) {
        $rows = count($grid);
        $cols = count($grid[0]);
        
        $result = 0;
        
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] == 1) {
                    $up = ($r == 0) ? 0 : $grid[$r-1][$c];
                    $left = ($c == 0) ? 0 : $grid[$r][$c-1];
                    $down = ($r == $rows-1) ? 0 : $grid[$r+1][$c];
                    $right = ($c == $cols-1) ? 0 : $grid[$r][$c+1];
                    
                    $result += 4 - ($up + $left + $right + $down);
                }
            }
        }
        
        return $result;
    }
}

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

Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.

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

😎 Решение:

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

class Solution {
    function insertIntoMaxTree($root, $val) {
        if ($root == null || $val > $root->val) {
            return new TreeNode($val, $root, null);
        }
        $root->right = $this->insertIntoMaxTree($root->right, $val);
        return $root;
    }
}

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

Задача: 364. Nested List Weight Sum II
Сложность: medium

Вам дан вложенный список целых чисел nestedList. Каждый элемент является либо целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.
Верните сумму каждого целого числа в nestedList, умноженную на его вес.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

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

1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.

3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎 Решение:

class Solution {
    function depthSumInverse($nestedList) {
        $queue = $nestedList;
        $depth = 1;
        $maxDepth = 0;
        $sumOfElements = 0;
        $sumOfProducts = 0;

        while (!empty($queue)) {
            $size = count($queue);
            $maxDepth = max($maxDepth, $depth);

            for ($i = 0; $i < $size; $i++) {
                $nested = array_shift($queue);

                if ($nested->isInteger()) {
                    $value = $nested->getInteger();
                    $sumOfElements += $value;
                    $sumOfProducts += $value * $depth;
                } else {
                    $queue = array_merge($queue, $nested->getList());
                }
            }
            $depth++;
        }
        return ($maxDepth + 1) * $sumOfElements - $sumOfProducts;
    }
}

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