PHP | LeetCode

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

Вам дан массив целых чисел nums.

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов.

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

2⃣Итерация по первым четырем элементам отсортированного массива: для каждого индекса left от 0 до 3 вычислите соответствующий правый индекс, разницу между элементами на этих индексах и обновите minDiff с минимальным значением.

3⃣Верните minDiff, которое хранит минимальную разницу между наибольшими и наименьшими значениями после удаления до трех элементов.

😎 Решение:

class Solution {
    function minDifference($nums) {
        $numsSize = count($nums);
        
        if ($numsSize <= 4) return 0;
        
        sort($nums);
        
        $minDiff = PHP_INT_MAX;
        
        for ($left = 0, $right = $numsSize - 4; $left < 4; $left++, $right++) {
            $minDiff = min($minDiff, $nums[$right] - $nums[$left]);
        }
        
        return $minDiff;
    }
}

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

Задача: 1422. Maximum Score After Splitting a String
Сложность: easy

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

Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.

Пример:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

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

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

2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц.

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

😎 Решение:

class Solution {
    function maxScore($s) {
        $ones = substr_count($s, '1');
        $zeros = 0;
        $ans = 0;
        $countOnes = $ones;

        for ($i = 0; $i < strlen($s) - 1; $i++) {
            if ($s[$i] === '1') {
                $countOnes--;
            } else {
                $zeros++;
            }
            $ans = max($ans, $zeros + $countOnes);
        }
        return $ans;
    }
}

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

Задача: 1095. Find in Mountain Array
Сложность: hard

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.
Существует некоторое i с 0 < i < arr.length - 1 такое, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).
MountainArray.length() возвращает длину массива.
Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

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

1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем.

3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎 Решение:

class Solution {
    function findInMountainArray($target, $mountainArr) {
        $length = $mountainArr->length()

        $low = 1
        $high = $length - 2
        while ($low != $high) {
            $mid = (int)(($low + $high) / 2)
            if ($mountainArr->get($mid) < $mountainArr->get($mid + 1)) {
                $low = $mid + 1
            } else {
                $high = $mid
            }
        }
        $peak = $low

        $low = 0
        $high = $peak
        while ($low < $high) {
            $mid = (int)(($low + $high) / 2)
            if ($mountainArr->get($mid) < $target) {
                $low = $mid + 1
            } else {
                $high = $mid
            }
        }
        if ($mountainArr->get($low) == $target) {
            return $low
        }

        $low = $peak + 1
        $high = $length - 1
        while ($low < $high) {
            $mid = (int)(($low + $high) / 2)
            if ($mountainArr->get($mid) > $target) {
                $low = $mid + 1
            } else {
                $high = $mid
            }
        }
        if ($mountainArr->get($low) == $target) {
            return $low
        }

        return -1
    }
}

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

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

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски.

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение:

class Solution {
    function getLastMoment($n, $left, $right) {
        $ans = 0;
        foreach ($left as $num) {
            $ans = max($ans, $num);
        }
        foreach ($right as $num) {
            $ans = max($ans, $n - $num);
        }
        return $ans;
    }
}

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

Задача: 29. Divide Two Integers
Сложность: medium

Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора.
Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2.
Возвращает частное после деления делимого на делитель.
Примечание: Если частное строго больше 2^31 - 1, верните 2^31 - 1, а если строго меньше -2^31, верните -2^31.

Пример:

Input: dividend = 10, divisor = 3  
Output: 3  

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

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

2⃣Используем вычитание с накоплением для имитации деления без / и *.

3⃣Проверяем выход за пределы 32-битного диапазона и возвращаем результат.

😎Решение:

class Solution {
    /**
     * @param Integer $dividend
     * @param Integer $divisor
     * @return Integer
     */
    function divide($dividend, $divisor) {
        if ($dividend == -pow(2,31) && $divisor == -1) {
            return pow(2,31)-1;
        }
        
        $sign = (($dividend < 0) ^ ($divisor < 0)) ? -1 : 1;
        $dividend = abs($dividend);
        $divisor = abs($divisor);
        $quotient = 0;
        
        while ($dividend >= $divisor) {
            $temp = $divisor;
            $multiple = 1;
            
            while ($dividend >= ($temp << 1)) {
                $temp <<= 1;
                $multiple <<= 1;
            }
            
            $dividend -= $temp;
            $quotient += $multiple;
        }
        
        return $sign * $quotient;
    }
}

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

Задача: 478. Generate Random Point in a Circle
Сложность: Medium

Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.
Реализуйте класс Solution:
- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].

Пример:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

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

1⃣Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R.

2⃣Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния.

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

😎 Решение:

class Solution {
    private $rad, $xc, $yc;

    function __construct($radius, $x_center, $y_center) {
        $this->rad = $radius;
        $this->xc = $x_center;
        $this->yc = $y_center;
    }

    function randPoint() {
        $x0 = $this->xc - $this->rad;
        $y0 = $this->yc - $this->rad;

        while (true) {
            $xg = $x0 + lcg_value() * $this->rad * 2;
            $yg = $y0 + lcg_value() * $this->rad * 2;
            if (sqrt(pow($xg - $this->xc, 2) + pow($yg - $this->yc, 2)) <= $this->rad) {
                return array($xg, $yg);
            }
        }
    }
}

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

Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

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

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

function atMostNGivenDigitSet($digits, $n) {
    $s = strval($n);
    $K = strlen($s);
    $dp = array_fill(0, $K + 1, 0);
    $dp[$K] = 1;

    for ($i = $K - 1; $i >= 0; --$i) {
        foreach ($digits as $d) {
            if ($d < $s[$i]) {
                $dp[$i] += pow(count($digits), $K - $i - 1);
            } elseif ($d == $s[$i]) {
                $dp[$i] += $dp[$i + 1];
            }
        }
    }

    for ($i = 1; $i < $K; ++$i) {
        $dp[0] += pow(count($digits), $i);
    }

    return $dp[0];
}

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

Задача: 474. Ones and Zeroes
Сложность: medium

Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.

Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

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

1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.

2⃣Считаем количество нулей и единиц в каждом подмножестве.

3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.

😎 Решение:

class Solution {
    function findMaxForm($strs, $m, $n) {
        $maxlen = 0;
        for ($i = 0; $i < (1 << count($strs)); $i++) {
            $zeroes = 0;
            $ones = 0;
            $len = 0;
            for ($j = 0; $j < 32; $j++) {
                if (($i & (1 << $j)) != 0) {
                    $count = $this->countZeroesOnes($strs[$j]);
                    $zeroes += $count[0];
                    $ones += $count[1];
                    if ($zeroes > $m || $ones > $n)
                        break;
                    $len++;
                }
            }
            if ($zeroes <= $m && $ones <= $n)
                $maxlen = max($maxlen, $len);
        }
        return $maxlen;
    }

    function countZeroesOnes($s) {
        $c = array(0, 0);
        for ($i = 0; $i < strlen($s); $i++) {
            $c[$s[$i] - '0']++;
        }
        return $c;
    }
}

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

Задача: 1496. Path Crossing
Сложность: easy

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных:
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями.
Инициализировать множество visited с начальной точкой (0, 0).
Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path:
Для каждого символа c в path получить значения (dx, dy) из moves[c].
Обновить координаты: добавить dx к x и dy к y.
Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true.
Добавить текущую точку (x, y) в visited.

3⃣Возврат результата:
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

class Solution {
    function isPathCrossing($path) {
        $moves = [
            'N' => [0, 1], 'S' => [0, -1],
            'E' => [1, 0], 'W' => [-1, 0]
        ];
        $visited = [[0, 0]];
        $x = 0;
        $y = 0;

        foreach (str_split($path) as $c) {
            list($dx, $dy) = $moves[$c];
            $x += $dx;
            $y += $dy;
            $point = [$x, $y];
            if (in_array($point, $visited)) {
                return true;
            }
            $visited[] = $point;
        }

        return false;
    }
}

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

Задача: 1394. Find Lucky Integer in an Array
Сложность: easy

Дан массив целых чисел arr. Счастливое число — это число, частота которого в массиве равна его значению.

Верните наибольшее счастливое число в массиве. Если счастливого числа нет, верните -1.

Пример:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

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

1⃣Создайте хэш-карту для подсчёта частоты каждого числа в массиве.

2⃣Пройдитесь по ключам и значениям хэш-карты, чтобы найти счастливые числа.

3⃣Верните наибольшее счастливое число или -1, если таких чисел нет.

😎 Решение:

class Solution {
    function findLucky($arr) {
        $counts = array_count_values($arr);
        $largestLuckyNumber = -1;
        
        foreach ($counts as $num => $count) {
            if ($num == $count) {
                $largestLuckyNumber = max($largestLuckyNumber, $num);
            }
        }
        
        return $largestLuckyNumber;
    }
}

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

Задача: 920. Number of Music Playlists4
Сложность: hard

В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен.

2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

3⃣Ответ находится в dp[goal][n].

😎 Решение:

function numMusicPlaylists($n, $goal, $k) {
    $MOD = 1_000_000_007;
    $dp = array_fill(0, $goal + 1, array_fill(0, $n + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $goal; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            $dp[$i][$j] = $dp[$i-1][$j-1] * ($n - $j + 1) % $MOD;
            if ($j > $k) {
                $dp[$i][$j] = ($dp[$i][$j] + $dp[$i-1][$j] * ($j - $k) % $MOD) % $MOD;
            }
        }
    }

    return $dp[$goal][$n];
}

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

Задача: 936. Stamping The Sequence
Сложность: hard

Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив

Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

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

1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.

2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.

3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.

😎 Решение:

function movesToStamp($stamp, $target) {
    $s = str_split($stamp);
    $t = str_split($target);
    $m = count($s);
    $n = count($t);
    $res = [];
    $done = array_fill(0, $n, false);
    
    $canStamp = function($i) use ($s, $t, $m) {
        for ($j = 0; $j < $m; $j++) {
            if ($t[$i + $j] !== '?' && $t[$i + $j] !== $s[$j]) {
                return false;
            }
        }
        return true;
    };
    
    $doStamp = function($i) use (&$t, &$res, &$done, $m) {
        for ($j = 0; $j < $m; $j++) {
            $t[$i + $j] = '?';
        }
        $res[] = $i;
        $done[$i] = true;
    };
    
    $changed = true;
    while ($changed) {
        $changed = false;
        for ($i = 0; $i <= $n - $m; $i++) {
            if (!$done[$i] && $canStamp($i)) {
                $doStamp($i);
                $changed = true;
            }
        }
    }
    
    foreach ($t as $c) {
        if ($c !== '?') {
            return [];
        }
    }
    
    return array_reverse($res);
}

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

Задача: 70. Climbing Stairs
Сложность: easy

Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек.
Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины?

Пример:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

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

1⃣В этом методе грубой силы мы рассматриваем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге.

2⃣На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций.

3⃣Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг.

😎 Решение:

function climbStairs($n) {
    return climb_Stairs(0, $n);
}

function climb_Stairs($i, $n) {
    if ($i > $n) {
        return 0;
    }
    if ($i == $n) {
        return 1;
    }
    return climb_Stairs($i + 1, $n) + climb_Stairs($i + 2, $n);
}

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

Задача: 179. Largest Number
Сложность: medium

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

Пример:

Input: nums = [10,2]
Output: "210"

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

1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    function largestNumber($nums) {
        $strNums = array_map('strval', $nums);
        usort($strNums, function($a, $b) {
            return strcmp($b . $a, $a . $b);
        });
        if ($strNums[0] === "0") {
            return "0";
        }
        return implode('', $strNums);
    }
}

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

Задача: 326. Power of Three
Сложность: easy

Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.
Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

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

2⃣Цикл деления на 3
Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3.

3⃣Проверка конечного значения
Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false.

😎 Решение:

class Solution {
    function isPowerOfThree($n) {
        if ($n <= 0) return false;
        while ($n % 3 == 0) {
            $n /= 3;
        }
        return $n == 1;
    }
}

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

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

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

function colorBorder($grid, $row, $col, $color) {
    $m = count($grid);
    $n = count($grid[0]);
    $originalColor = $grid[$row][$col];
    $visited = array_fill(0, $m, array_fill(0, $n, false));
    $borders = [];

    function dfs($r, $c, $m, $n, $originalColor, &$grid, &$visited, &$borders) {
        $visited[$r][$c] = true;
        $isBorder = false;
        foreach ([[-1, 0], [1, 0], [0, -1], [0, 1]] as [$dr, $dc]) {
            $nr = $r + $dr;
            $nc = $c + $dc;
            if ($nr >= 0 && $nr < $m && $nc >= 0 && $nc < $n) {
                if (!$visited[$nr][$nc]) {
                    if ($grid[$nr][$nc] == $originalColor) {
                        dfs($nr, $nc, $m, $n, $originalColor, $grid, $visited, $borders);
                    } else {
                        $isBorder = true;
                    }
                }
            } else {
                $isBorder = true;
            }
        }
        if ($isBorder || $r == 0 || $r == $m - 1 || $c == 0 || $c == $n - 1) {
            $borders[] = [$r, $c];
        }
    }

    dfs($row, $col, $m, $n, $originalColor, $grid, $visited, $borders);
    foreach ($borders as [$r, $c]) {
        $grid[$r][$c] = $color;
    }

    return $grid;
}

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

Задача: 750. Number Of Corner Rectangles
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]
Output: 1

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

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

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

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

😎 Решение:

function countCornerRectangles($grid) {
    $count = 0;
    for ($i = 0; $i < count($grid); $i++) {
        for ($j = $i + 1; $j < count($grid); $j++) {
            $numPairs = 0;
            for ($k = 0; $k < count($grid[0]); $k++) {
                if ($grid[$i][$k] == 1 && $grid[$j][$k] == 1) {
                    $numPairs++;
                }
            }
            if ($numPairs > 1) {
                $count += $numPairs * ($numPairs - 1) / 2;
            }
        }
    }
    return $count;
}

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

Задача: 953. Verifying an Alien Dictionary
Сложность: hard

В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке.

Пример:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true

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

1⃣Создать словарь для хранения порядка каждой буквы в инопланетном языке.
Пройти по каждому слову и сравнить его с последующим словом.

2⃣Для каждого слова, сравнить буквы, используя созданный словарь порядка.
Если обнаружена пара слов, нарушающая порядок, вернуть false.

3⃣Если все слова отсортированы правильно, вернуть true.

😎 Решение:

function isAlienSorted($words, $order) {
    $orderMap = array_flip(str_split($order));
    
    for ($i = 0; $i < count($words) - 1; $i++) {
        if (!compare($words[$i], $words[$i + 1], $orderMap)) {
            return false;
        }
    }
    return true;
}

function compare($word1, $word2, $orderMap) {
    $minLength = min(strlen($word1), strlen($word2));
    for ($i = 0; $i < $minLength; $i++) {
        if ($orderMap[$word1[$i]] < $orderMap[$word2[$i]]) {
            return true;
        } elseif ($orderMap[$word1[$i]] > $orderMap[$word2[$i]]) {
            return false;
        }
    }
    return strlen($word1) <= strlen($word2);
}

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

Задача: 410. Split Array Largest Sum
Сложность: easy

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

Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

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

1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

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

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

😎 Решение:

function splitArray($nums, $k) {
    $left = max($nums);
    $right = array_sum($nums);
    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        if (canSplit($nums, $k, $mid)) {
            $right = $mid;
        } else {
            $left = $mid + 1;
        }
    }
    return $left;
}

function canSplit($nums, $k, $maxSum) {
    $currentSum = 0;
    $subarrays = 1;
    foreach ($nums as $num) {
        if ($currentSum + $num > $maxSum) {
            $currentSum = $num;
            $subarrays++;
            if ($subarrays > $k) {
                return false;
            }
        } else {
            $currentSum += $num;
        }
    }
    return true;
}

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

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

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

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

3⃣Первый и последний элементы массива остаются неизменными.

😎 Решение:

function transformArray($arr) {
    do {
        $changed = false;
        $newArr = $arr;
        for ($i = 1; $i < count($arr) - 1; $i++) {
            if ($arr[$i] < $arr[$i - 1] && $arr[$i] < $arr[$i + 1]) {
                $newArr[$i]++;
                $changed = true;
            } else if ($arr[$i] > $arr[$i - 1] && $arr[$i] > $arr[$i + 1]) {
                $newArr[$i]--;
                $changed = true;
            }
        }
        $arr = $newArr;
    } while ($changed);
    return $arr;
}

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