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

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

Задача: 1049. Last Stone Weight II
Сложность: medium

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

Пример:

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

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

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

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

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

😎 Решение:

function lastStoneWeightII($stones) {
    $totalSum = array_sum($stones);
    $halfSum = intdiv($totalSum, 2);
    $dp = array_fill(0, $halfSum + 1, 0);

    foreach ($stones as $stone) {
        for ($j = $halfSum; $j >= $stone; $j--) {
            $dp[$j] = max($dp[$j], $dp[$j - $stone] + $stone);
        }
    }

    return $totalSum - 2 * $dp[$halfSum];
}

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

Задача: 383. Ransom Note
Сложность: easy

Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае.
Каждая буква из magazine может быть использована в ransomNote только один раз.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления".

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

3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы.

😎 Решение:

function canConstruct($ransomNote, $magazine) {
    for ($i = 0; $i < strlen($ransomNote); $i++) {
        $char = $ransomNote[$i];
        $index = strpos($magazine, $char);
        if ($index === false) {
            return false;
        }
        $magazine = substr($magazine, 0, $index) . substr($magazine, $index + 1);
    }
    return true;
}

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

Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

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

1⃣Представить каждую строку и столбец как узлы в графе.

2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.

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

😎 Решение:

function removeStones($stones) {
    $parent = [];
    
    function find($x) {
        global $parent;
        if (!isset($parent[$x])) $parent[$x] = $x;
        if ($parent[$x] != $x) $parent[$x] = find($parent[$x]);
        return $parent[$x];
    }
    
    function union($x, $y) {
        global $parent;
        $parent[find($x)] = find($y);
    }
    
    foreach ($stones as $stone) {
        union($stone[0], ~$stone[1]);
    }
    
    $uniqueRoots = [];
    foreach ($parent as $key => $value) {
        $uniqueRoots[find($key)] = true;
    }
    
    return count($stones) - count($uniqueRoots);
}

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

Задача: 736. Parse Lisp Expression
Сложность: hard

Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример:

Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
Output: 14

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

1⃣Определите функцию для оценки выражений.

2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных).

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

😎 Решение:

class Solution {
    public function evaluate($expression) {
        return $this->evaluateExpression($expression, []);
    }

    private function evaluateExpression($expression, $env) {
        if ($expression[0] !== '(') {
            if (is_numeric($expression) || $expression[0] === '-') {
                return intval($expression);
            }
            return $env[$expression] ?? 0;
        }

        $tokens = $this->tokenize($expression);
        if ($tokens[0] === "let") {
            for ($i = 1; $i < count($tokens) - 2; $i += 2) {
                $env[$tokens[$i]] = $this->evaluateExpression($tokens[$i + 1], $env);
            }
            return $this->evaluateExpression($tokens[count($tokens) - 1], $env);
        } elseif ($tokens[0] === "add") {
            return $this->evaluateExpression($tokens[1], $env) + $this->evaluateExpression($tokens[2], $env);
        } elseif ($tokens[0] === "mult") {
            return $this->evaluateExpression($tokens[1], $env) * $this->evaluateExpression($tokens[2], $env);
        }
        return 0;
    }

    private function tokenize($expression) {
        $tokens = [];
        $token = '';
        $parens = 0;

        for ($i = 0; $i < strlen($expression); $i++) {
            $c = $expression[$i];
            if ($c === '(') {
                $parens++;
                if ($parens === 1) continue;
            } elseif ($c === ')') {
                $parens--;
                if ($parens === 0) {
                    $tokens = array_merge($tokens, $this->tokenize($token));
                    $token = '';
                    continue;
                }
            } elseif ($c === ' ' && $parens === 1) {
                if ($token !== '') {
                    $tokens[] = $token;
                    $token = '';
                }
                continue;
            }
            $token .= $c;
        }
        if ($token !== '') {
            $tokens[] = $token;
        }
        return $tokens;
    }
}

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

Задача: 94. Binary Tree Inorder Traversal
Сложность: easy

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

Пример:

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

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

1⃣Если узел пустой — ничего не делаем.

2⃣Рекурсивно вызываем обход для левого поддерева.

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

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;

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

class Solution {
    public function inorderTraversal($root) {
        $res = [];
        $this->helper($root, $res);
        return $res;
    }

    private function helper($root, &$res) {
        if ($root !== null) {
            $this->helper($root->left, $res);
            $res[] = $root->val;
            $this->helper($root->right, $res);
        }
    }
}

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

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

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

Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

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

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:

class Solution {
    function powerfulIntegers($x, $y, $bound) {
        $a = $x == 1 ? $bound : intval(log($bound) / log($x));
        $b = $y == 1 ? $bound : intval(log($bound) / log($y));
        $powerfulIntegers = [];

        for ($i = 0; $i <= $a; $i++) {
            for ($j = 0; $j <= $b; $j++) {
                $value = pow($x, $i) + pow($y, $j);
                if ($value <= $bound) {
                    $powerfulIntegers[$value] = true;
                }
                if ($y == 1) break;
            }
            if ($x == 1) break;
        }

        return array_keys($powerfulIntegers);
    }
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

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

3⃣Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $arr
     * @return Integer
     */
    function longestMountain($arr) {
        $n = count($arr);
        $ans = 0;
        $base = 0;

        while ($base < $n) {
            $end = $base;
            if ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
                while ($end + 1 < $n && $arr[$end] < $arr[$end + 1]) {
                    $end++;
                }
                if ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
                    while ($end + 1 < $n && $arr[$end] > $arr[$end + 1]) {
                        $end++;
                    }
                    $ans = max($ans, $end - $base + 1);
                }
            }
            $base = max($end, $base + 1);
        }

        return $ans;
    }
}

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

Задача: 1200. Minimum Absolute Difference
Сложность: easy

Дан массив различных целых чисел arr, найдите все пары элементов с минимальной абсолютной разницей между любыми двумя элементами.

Верните список пар в порядке возрастания (по отношению к парам), каждая пара [a, b] следует условиям:
a, b из arr
a < b
b - a равна минимальной абсолютной разнице между любыми двумя элементами в arr

Пример:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

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

1⃣Инициализация вспомогательного массива:
Найдите минимальный элемент minElement и максимальный элемент maxElement в массиве arr.
Инициализируйте вспомогательный массив line размером maxElement - minElement + 1 и установите смещение shift равным -minElement.
Пройдите по массиву arr и для каждого элемента value увеличьте значение в индексе value + shift на 1.

2⃣Поиск минимальной абсолютной разницы:
Пройдите по вспомогательному массиву line, начиная с индекса, соответствующего минимальному элементу.
Проверьте значения на каждом индексе curr:
- если line[curr] равно 0, пропустите этот индекс.
- если line[curr] равно 1, сравните абсолютную разницу текущей пары currPairDiff с минимальной найденной разницей minPairDiff.
- если currPairDiff больше minPairDiff, продолжайте.
- если currPairDiff равно minPairDiff, добавьте эту пару в список ответов.
- если currPairDiff меньше minPairDiff, очистите список ответов, добавьте эту пару и обновите minPairDiff.

3⃣Возврат результата:
После прохождения всех элементов массива line, список ответов будет содержать все пары с минимальной абсолютной разницей. Верните список ответов.

😎 Решение:

class Solution {
    function minimumAbsDifference($arr) {
        sort($arr);
        $minDiff = PHP_INT_MAX;
        $result = [];
        
        for ($i = 1; $i < count($arr); $i++) {
            $diff = $arr[$i] - $arr[$i - 1];
            if ($diff < $minDiff) {
                $minDiff = $diff;
                $result = [[$arr[$i - 1], $arr[$i]]];
            } else if ($diff == $minDiff) {
                $result[] = [$arr[$i - 1], $arr[$i]];
            }
        }
        
        return $result;
    }
}

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

Задача: 662. Maximum Width of Binary Tree
Сложность: medium

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

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

1⃣Инициализация:
Создайте очередь для хранения узлов и их позиций на уровне.
Начните с корневого узла и его позиции 0.

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

3⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

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

class Solution {
    function widthOfBinaryTree($root) {
        if ($root === null) return 0;
        
        $maxWidth = 0;
        $queue = [[$root, 0]];

        while (!empty($queue)) {
            $levelSize = count($queue);
            $firstPos = $queue[0][1];
            for ($i = 0; $i < $levelSize; $i++) {
                list($node, $pos) = array_shift($queue);
                if ($node->left !== null) $queue[] = [$node->left, 2 * $pos];
                if ($node->right !== null) $queue[] = [$node->right, 2 * $pos + 1];
            }
            $lastPos = !empty($queue) ? end($queue)[1] : $firstPos;
            $maxWidth = max($maxWidth, $lastPos - $firstPos + 1);
        }

        return $maxWidth;
    }
}

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

Задача: 588. Design In-Memory File System
Сложность: hard

Спроектируйте структуру данных, которая симулирует файловую систему в памяти.
Реализуйте класс FileSystem:
FileSystem() Инициализирует объект системы.
List<String> ls(String path)
Если path является путем к файлу, возвращает список, содержащий только имя этого файла.
Если path является путем к директории, возвращает список имен файлов и директорий в этой директории.
Ответ должен быть в лексикографическом порядке.
void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их.
void addContentToFile(String filePath, String content)
Если filePath не существует, создает файл, содержащий заданный контент.
Если filePath уже существует, добавляет заданный контент к исходному содержимому.
String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath.

Пример:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

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

1⃣Инициализация файловой системы:
Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content.

2⃣Обработка команд:
Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом.
Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их.
Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его.
Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути.

3⃣Обработка путей и работа с файлами/директориями:
Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов.
Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий.

😎 Решение:

class File {
    public $isFile = false;
    public $files = [];
    public $content = "";
}

class FileSystem {
    private $root;

    public function __construct() {
        $this->root = new File();
    }

    private function navigate($path) {
        $t = $this->root;
        if ($path !== "/") {
            $dirs = explode("/", $path);
            foreach ($dirs as $dir) {
                if (!empty($dir)) {
                    if (!isset($t->files[$dir])) {
                        $t->files[$dir] = new File();
                    }
                    $t = $t->files[$dir];
                }
            }
        }
        return $t;
    }

    public function ls($path) {
        $t = $this->navigate($path);
        if ($t->isFile) return [basename($path)];
        $res = array_keys($t->files);
        sort($res);
        return $res;
    }

    public function mkdir($path) {
        $this->navigate($path);
    }

    public function addContentToFile($filePath, $content) {
        $t = $this->navigate($filePath);
        $t->isFile = true;
        $t->content .= $content;
    }

    public function readContentFromFile($filePath) {
        return $this->navigate($filePath)->content;
    }
}

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