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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard

Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

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

2⃣Создание узлов:
Создайте новые узлы на основе уровня и значения из строки. Для каждого нового узла найдите его родительский узел из стека и добавьте узел как левого или правого ребенка.

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

😎 Решение:

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

class Solution {
    function recoverFromPreorder($S) {
        $stack = [];
        $i = 0;
        
        while ($i < strlen($S)) {
            $level = 0;
            while ($i < strlen($S) && $S[$i] == '-') {
                $level++;
                $i++;
            }
            
            $value = 0;
            while ($i < strlen($S) && is_numeric($S[$i])) {
                $value = $value * 10 + intval($S[$i]);
                $i++;
            }
            
            $node = new TreeNode($value);
            if ($level == count($stack)) {
                if (!empty($stack)) {
                    $stack[count($stack) - 1]->left = $node;
                }
            } else {
                while ($level != count($stack)) {
                    array_pop($stack);
                }
                $stack[count($stack) - 1]->right = $node;
            }
            array_push($stack, $node);
        }
        
        while (count($stack) > 1) {
            array_pop($stack);
        }
        
        return $stack[0];
    }
}

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

Задача: 756. Pyramid Transition Matrix
Сложность: medium

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

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

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

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

😎 Решение:

function pyramidTransition($bottom, $allowed) {
    $allowedDict = [];

    foreach ($allowed as $pattern) {
        $key = substr($pattern, 0, 2);
        $value = $pattern[2];
        if (!isset($allowedDict[$key])) {
            $allowedDict[$key] = [];
        }
        $allowedDict[$key][] = $value;
    }

    return canBuild($bottom, $allowedDict);
}

function canBuild($currentLevel, $allowedDict) {
    if (strlen($currentLevel) == 1) return true;

    $nextLevelOptions = [];
    for ($i = 0; $i < strlen($currentLevel) - 1; $i++) {
        $key = substr($currentLevel, $i, 2);
        if (!isset($allowedDict[$key])) return false;
        $nextLevelOptions[] = $allowedDict[$key];
    }

    return canBuildNextLevel($nextLevelOptions, 0, "", $allowedDict);
}

function canBuildNextLevel($options, $index, $nextLevel, $allowedDict) {
    if ($index == count($options)) return canBuild($nextLevel, $allowedDict);
    foreach ($options[$index] as $option) {
        if (canBuildNextLevel($options, $index + 1, $nextLevel . $option, $allowedDict)) return true;
    }
    return false;
}

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

Задача: 517. Super Washing Machines
Сложность: hard

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.
За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.
Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1.

Пример:

Input: machines = [1,0,5]
Output: 3
Explanation:
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

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

1⃣Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

2⃣Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

3⃣Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎 Решение:

class Solution {
    function findMinMoves($machines) {
        $n = count($machines);
        $dressTotal = array_sum($machines);
        if ($dressTotal % $n != 0) return -1;

        $dressPerMachine = intval($dressTotal / $n);
        for ($i = 0; $i < $n; $i++) $machines[$i] -= $dressPerMachine;

        $currSum = 0;
        $maxSum = 0;
        $res = 0;
        foreach ($machines as $m) {
            $currSum += $m;
            $maxSum = max($maxSum, abs($currSum));
            $res = max($res, max($maxSum, $m));
        }
        return $res;
    }
}

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

Задача: 992. Subarrays with K Different Integers
Сложность: hard

Дан целочисленный массив nums и целое число k, верните количество "хороших" подмассивов в nums.

"Хороший" массив - это массив, в котором количество различных целых чисел равно k.

Например, в массиве [1,2,3,1,2] есть 3 различных целых числа: 1, 2 и 3.
Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

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

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

2⃣Проверка условий:
Как только количество различных элементов достигнет k, перемещайте левый указатель, чтобы уменьшить размер подмассива и попытаться найти все возможные "хорошие" подмассивы.
Подсчитывайте количество подмассивов, удовлетворяющих условию.

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

😎 Решение:

class Solution {
    function countGoodSubarrays($nums, $k) {
        $count = 0;
        $left = 0;
        $right = 0;
        $distinctCount = 0;
        $freq = [];
        
        while ($right < count($nums)) {
            if (!isset($freq[$nums[$right]])) {
                $freq[$nums[$right]] = 0;
            }
            $freq[$nums[$right]]++;
            if ($freq[$nums[$right]] == 1) {
                $distinctCount++;
            }
            $right++;
            
            while ($distinctCount > $k) {
                $freq[$nums[$left]]--;
                if ($freq[$nums[$left]] == 0) {
                    $distinctCount--;
                }
                $left++;
            }
            
            if ($distinctCount == $k) {
                $count++;
            }
        }
        
        return $count;
    }
}

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