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

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

Задача: 598. Range Addition II
Сложность: Easy

Вам дана матрица M размером m x n, инициализированная нулями, и массив операций ops, где ops[i] = [ai, bi] означает, что значение M[x][y] должно быть увеличено на единицу для всех 0 <= x < ai и 0 <= y < bi.
Подсчитайте и верните количество максимальных чисел в матрице после выполнения всех операций.

Пример:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

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

1⃣Все операции выполняются на прямоугольной подматрице изначальной матрицы M, заполненной нулями, с верхним левым углом в точке (0,0) и нижним правым углом для операции [i,j] в точке (i,j).

2⃣Максимальный элемент будет тем, на который выполнены все операции. Максимальные элементы будут находиться в области пересечения прямоугольников, представляющих операции. Для определения этой области нужно найти нижний правый угол пересекающейся области (x,y), который равен (min(op[0]), min(op[1])).

3⃣Количество элементов, находящихся в области пересечения, определяется как произведение координат x и y.

😎 Решение:

class Solution {
    function maxCount($m, $n, $ops) {
        $minA = $m;
        $minB = $n;
        foreach ($ops as $op) {
            $minA = min($minA, $op[0]);
            $minB = min($minB, $op[1]);
        }
        return $minA * $minB;
    }
}

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

Задача: 995. Minimum Number of K Consecutive Bit Flips
Сложность: hard

Дан бинарный массив nums и целое число k.

Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0.

Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1.

Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].

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

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

2⃣Перебор элементов массива:
Для каждого элемента определите, необходимо ли его переворачивать, учитывая текущее количество переворотов и значение в массиве.
Если нужно перевернуть, увеличьте счетчик переворотов и обновите массив flip.

3⃣Проверка возможности выполнения задачи:
Если количество переворотов больше длины массива, верните -1.

😎 Решение:

class Solution {
    function minKBitFlips($nums, $k) {
        $n = count($nums);
        $flip = 0;
        $flips = 0;
        $flipQueue = array_fill(0, $n, 0);
        
        for ($i = 0; $i < $n; $i++) {
            if ($i >= $k) {
                $flip ^= $flipQueue[$i - $k];
            }
            if ($nums[$i] == $flip) {
                if ($i + $k > $n) return -1;
                $flips++;
                $flip ^= 1;
                $flipQueue[$i] = 1;
            }
        }
        return $flips;
    }
}

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