Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

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

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

2⃣Поиск максимальной суммы:
Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
    function maxSumTwoNoOverlap($nums, $firstLen, $secondLen) {
        return max($this->maxSumNonOverlap($nums, $firstLen, $secondLen), $this->maxSumNonOverlap(array_reverse($nums), $secondLen, $firstLen));
    }
    
    private function maxSumNonOverlap($nums, $firstLen, $secondLen) {
        $n = count($nums);
        $prefix = array_fill(0, $n + 1, 0);
        for ($i = 0; $i < $n; $i++) {
            $prefix[$i + 1] = $prefix[$i] + $nums[$i];
        }
        
        $maxFirst = array_fill(0, $n, 0);
        for ($i = $firstLen - 1; $i < $n; $i++) {
            $maxFirst[$i] = max(($i > 0 ? $maxFirst[$i - 1] : 0), $prefix[$i + 1] - $prefix[$i + 1 - $firstLen]);
        }
        
        $maxSecond = array_fill(0, $n, 0);
        for ($i = $secondLen - 1; $i < $n; $i++) {
            $maxSecond[$i] = max(($i > 0 ? $maxSecond[$i - 1] : 0), $prefix[$i + 1] - $prefix[$i + 1 - $secondLen]);
        }
        
        $maxSum = 0;
        for ($i = $firstLen + $secondLen - 1; $i < $n; $i++) {
            $maxSum = max($maxSum, $maxFirst[$i - $secondLen] + ($prefix[$i + 1] - $prefix[$i + 1 - $secondLen]));
        }
        
        return $maxSum;
    }
}

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

Задача: 1017. Convert to Base -2
Сложность: medium

Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".

Пример:

Input: n = 2
Output: "110"

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

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

2⃣Вычисление цифр:
В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2.
Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1.
Добавляйте остаток в начало строки.

3⃣Возврат результата:
Верните строку, представляющую число в базе -2. Если строка пустая, верните "0".

😎 Решение:

class Solution {
    function baseNeg2($n) {
        if ($n == 0) return "0";
        $res = "";
        while ($n != 0) {
            $remainder = $n % -2;
            $n = intdiv($n, -2);
            if ($remainder < 0) {
                $remainder += 2;
                $n += 1;
            }
            $res = $remainder . $res;
        }
        return $res;
    }
}

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60
Сложность: medium

Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.

Пример:

Input: time = [30,20,150,100,40]
Output: 3

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

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

2⃣Подсчет пар:
Пройдитесь по каждой песне в списке и для каждого элемента:
Вычислите остаток от деления времени песни на 60.
Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0).
Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0).
Обновите массив остатков, увеличивая количество песен с текущим остатком на 1.

3⃣Возврат результата:
Верните общее количество пар.

😎 Решение:

class Solution {
    function numPairsDivisibleBy60($time) {
        $remainders = array_fill(0, 60, 0);
        $count = 0;
        
        foreach ($time as $t) {
            if ($t % 60 == 0) {
                $count += $remainders[0];
            } else {
                $count += $remainders[60 - $t % 60];
            }
            $remainders[$t % 60]++;
        }
        
        return $count;
    }
}

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

Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

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

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

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

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

class Solution {
    function findSmallestRegion($regions, $region1, $region2) {
        $parent = [];

        foreach ($regions as $regionList) {
            for ($i = 1; $i < count($regionList); $i++) {
                $parent[$regionList[$i]] = $regionList[0];
            }
        }

        $ancestors1 = [];
        while ($region1 !== null) {
            $ancestors1[$region1] = true;
            $region1 = isset($parent[$region1]) ? $parent[$region1] : null;
        }

        while (!isset($ancestors1[$region2])) {
            $region2 = isset($parent[$region2]) ? $parent[$region2] : null;
        }

        return $region2;
    }
}

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

Задача: 942. DI String Match
Сложность: easy

Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.

Пример:

Input: s = "IDID"
Output: [0,4,1,3,2]

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

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

2⃣Создать массив perm длиной n + 1.
Пройти по строке s:
Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low.
Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high.
Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm.

3⃣Вернуть массив perm.

😎 Решение:

function diStringMatch($s) {
    $n = strlen($s);
    $low = 0;
    $high = $n;
    $perm = array_fill(0, $n + 1, 0);
    
    for ($i = 0; $i < $n; $i++) {
        if ($s[$i] == 'I') {
            $perm[$i] = $low++;
        } else {
            $perm[$i] = $high--;
        }
    }
    
    $perm[$n] = $low;
    return $perm;
}

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

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

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: num = "69"
Output: true

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

1⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    function isStrobogrammatic($num) {
        $rotated = '';
        for ($i = strlen($num) - 1; $i >= 0; $i--) {
            $c = $num[$i];
            if ($c == '0' || $c == '1' || $c == '8') {
                $rotated .= $c;
            } else if ($c == '6') {
                $rotated .= '9';
            } else if ($c == '9') {
                $rotated .= '6';
            } else {
                return false;
            }
        }
        return $num == $rotated;
    }
}

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

Задача: 1345. Jump Game IV
Сложность: hard

Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.

За один шаг вы можете прыгнуть с индекса i на индекс:

- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.

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

Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.

Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

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

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

2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.

3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.

😎 Решение:

class Solution {
    public function minJumps($arr) {
        $n = count($arr);
        if ($n <= 1) {
            return 0;
        }

        $graph = [];
        for ($i = 0; $i < $n; $i++) {
            if (!isset($graph[$arr[$i]])) {
                $graph[$arr[$i]] = [];
            }
            $graph[$arr[$i]][] = $i;
        }

        $curs = [0];
        $visited = [0 => true];
        $step = 0;

        while (!empty($curs)) {
            $nex = [];

            foreach ($curs as $node) {
                if ($node == $n - 1) {
                    return $step;
                }

                foreach ($graph[$arr[$node]] as $child) {
                    if (!isset($visited[$child])) {
                        $visited[$child] = true;
                        $nex[] = $child;
                    }
                }

                $graph[$arr[$node]] = [];

                if ($node + 1 < $n && !isset($visited[$node + 1])) {
                    $visited[$node + 1] = true;
                    $nex[] = $node + 1;
                }
                if ($node - 1 >= 0 && !isset($visited[$node - 1])) {
                    $visited[$node - 1] = true;
                    $nex[] = $node - 1;
                }
            }

            $curs = $nex;
            $step++;
        }

        return -1;
    }
}

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

Задача: 1282. Group the People Given the Group Size They Belong To
Сложность: medium

Есть n человек, которые разделены на неизвестное количество групп. Каждый человек имеет уникальный ID от 0 до n - 1.

Вам дан целочисленный массив groupSizes, где groupSizes[i] - это размер группы, в которой находится человек i. Например, если groupSizes[1] = 3, то человек 1 должен быть в группе размером 3.

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

Каждый человек должен быть ровно в одной группе, и каждый человек должен быть в группе. Если существует несколько ответов, верните любой из них. Гарантируется, что для данного ввода существует хотя бы одно правильное решение.

Пример:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

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

1⃣Инициализируйте пустой список списков ans для хранения индексов групп. Создайте хэш-таблицу szToGroup, где ключи — целые числа, представляющие размеры групп, а значения — массивы соответствующих индексов в группе.

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

3⃣Верните ans.


😎 Решение:

class Solution {
    function groupThePeople($groupSizes) {
        $ans = [];
        $szToGroup = [];
        
        for ($i = 0; $i < count($groupSizes); $i++) {
            $size = $groupSizes[$i];
            if (!isset($szToGroup[$size])) {
                $szToGroup[$size] = [];
            }
            $szToGroup[$size][] = $i;
            
            if (count($szToGroup[$size]) == $size) {
                $ans[] = $szToGroup[$size];
                $szToGroup[$size] = [];
            }
        }
        
        return $ans;
    }
}

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

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.
Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

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

1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

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

😎 Решение:

class Solution {
    function findLengthOfLCIS($nums) {
        $ans = 0;
        $anchor = 0;
        for ($i = 0; $i < count($nums); ++$i) {
            if ($i > 0 && $nums[$i - 1] >= $nums[$i]) {
                $anchor = $i;
            }
            $ans = max($ans, $i - $anchor + 1);
        }
        return $ans;
    }
}

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

Задача: 224. Basic Calculator
Сложность: hard

Дана строка s, представляющая собой допустимое выражение, реализуйте базовый калькулятор для его вычисления и верните результат вычисления.
Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

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

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

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

😎 Решение:

class Solution {
    private function evaluateExpr(&$stack) {
        if (empty($stack) || !is_int(end($stack))) {
            array_push($stack, 0);
        }

        $res = array_pop($stack);

        while (!empty($stack) && end($stack) !== ')') {
            $sign = array_pop($stack);

            if ($sign === '+') {
                $res += array_pop($stack);
            } else {
                $res -= array_pop($stack);
            }
        }
        return $res;
    }

    public function calculate($s) {
        $operand = 0;
        $n = 0;
        $stack = array();

        for ($i = strlen($s) - 1; $i >= 0; $i--) {
            $ch = $s[$i];

            if (ctype_digit($ch)) {
                $operand = pow(10, $n) * ((int) $ch) + $operand;
                $n += 1;
            } else if ($ch !== ' ') {
                if ($n !== 0) {
                    array_push($stack, $operand);
                    $n = 0;
                    $operand = 0;
                }
                if ($ch === '(') {
                    $res = $this->evaluateExpr($stack);
                    array_pop($stack);
                    array_push($stack, $res);
                } else {
                    array_push($stack, $ch);
                }
            }
        }

        if ($n !== 0) {
            array_push($stack, $operand);
        }

        return $this->evaluateExpr($stack);
    }
}

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

Задача: 948. Bag of Tokens
Сложность: medium

Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.

Пример:

Input: tokens = [100], power = 50

Output: 0

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

1⃣Отсортировать массив tokens.
Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.
Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore

2⃣Повторять следующие шаги, пока left не превысит right:
Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.
Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.
Обновить максимальный счет, если текущий счет больше максимального.

3⃣Вернуть максимальный счет.

😎 Решение:

function bagOfTokensScore($tokens, $power) {
    sort($tokens);
    $left = 0;
    $right = count($tokens) - 1;
    $score = 0;
    $maxScore = 0;
    
    while ($left <= $right) {
        if ($power >= $tokens[$left]) {
            $power -= $tokens[$left];
            $score++;
            $left++;
            $maxScore = max($maxScore, $score);
        } elseif ($score > 0) {
            $power += $tokens[$right];
            $score--;
            $right--;
        } else {
            break;
        }
    }
    
    return $maxScore;
}

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