Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 169. Majority Element
Сложность: easy

Дан массив nums размера n, верните элемент большинства.
Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.

Пример:

Input: nums = [3,2,3]
Output: 3

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

1⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.

2⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.

3⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋

😎 Решение:

function majorityElement($nums) {
    $counts = [];
    foreach ($nums as $num) {
        if (!isset($counts[$num])) {
            $counts[$num] = 1;
        } else {
            $counts[$num]++;
        }
    }
    
    foreach ($counts as $num => $count) {
        if ($count > count($nums) / 2) {
            return $num;
        }
    }
    return 0;
}

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

Задача: 910. Smallest Range II
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Для каждого индекса i, где 0 <= i < nums.length, измените nums[i] на nums[i] + k или nums[i] - k. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после изменения значений в каждом индексе.

Пример:

Input: nums = [1], k = 0
Output: 0

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

1⃣Отсортировать массив nums.

2⃣Рассчитать начальную разницу между максимальным и минимальным элементами.

3⃣Пройтись по всем элементам массива, пытаясь минимизировать разницу, изменяя текущий элемент на +k и -k и вычисляя новые максимальные и минимальные значения массива.

😎 Решение:

function smallestRangeII($nums, $k) {
    sort($nums);
    $n = count($nums);
    $minVal = $nums[0];
    $maxVal = $nums[$n - 1];
    $result = $maxVal - $minVal;

    for ($i = 0; $i < $n - 1; $i++) {
        $high = max($nums[$i] + $k, $maxVal - $k);
        $low = min($nums[$i + 1] - $k, $minVal + $k);
        $result = min($result, $high - $low);
    }

    return $result;
}

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

Задача: 653. Two Sum IV - Input is a BST
Сложность: easy

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

2⃣Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла.

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

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;
    }
}

function findTarget($root, $k) {
    $seen = [];
    return find($root, $k, $seen);
}

function find($node, $k, &$seen) {
    if ($node === null) return false;
    if (in_array($k - $node->val, $seen)) return true;
    $seen[] = $node->val;
    return find($node->left, $k, $seen) || find($node->right, $k, $seen);
}

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

Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.

2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.

😎 Решение:

class Solution {
    function videoStitching($clips, $T) {
        usort($clips, function($a, $b) {
            return $a[0] == $b[0] ? $b[1] - $a[1] : $a[0] - $b[0];
        });
        $end = -1;
        $end2 = 0;
        $res = 0;
        
        foreach ($clips as $clip) {
            if ($end2 >= $T || $clip[0] > $end2) break;
            if ($end < $clip[0] && $clip[0] <= $end2) {
                $res++;
                $end = $end2;
            }
            $end2 = max($end2, $clip[1]);
        }
        return $end2 >= $T ? $res : -1;
    }
}

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

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

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

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

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

😎 Решение:

function numWays($steps, $arrLen) {
    $mod = 1000000007;
    $max_pos = min($arrLen - 1, $steps);
    $dp = array_fill(0, $max_pos + 1, 0);
    $dp[0] = 1;
    for ($step = 0; $step < $steps; $step++) {
        $new_dp = array_fill(0, $max_pos + 1, 0);
        for ($i = 0; $i <= $max_pos; $i++) {
            $new_dp[$i] = $dp[$i] % $mod;
            if ($i > 0) $new_dp[$i] = ($new_dp[$i] + $dp[$i - 1]) % $mod;
            if ($i < $max_pos) $new_dp[$i] = ($new_dp[$i] + $dp[$i + 1]) % $mod;
        }
        $dp = $new_dp;
    }
    return $dp[0];
}

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

Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]
Output: 22

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

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

2⃣Анализ текущего узла:
Если узел является листом (не имеет потомков), добавьте текущее значение числа к общей сумме.
Если узел не является листом, рекурсивно вызовите функцию DFS для левого и правого дочерних узлов, обновляя текущее значение числа.

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 sumRootToLeaf($root) {
        return $this->dfs($root, 0);
    }
    
    private function dfs($node, $currentValue) {
        if ($node === null) return 0;
        $currentValue = ($currentValue << 1) | $node->val;
        if ($node->left === null && $node->right === null) return $currentValue;
        return $this->dfs($node->left, $currentValue) + $this->dfs($node->right, $currentValue);
    }
}

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

Задача: 724. Find Pivot Index
Сложность: easy

Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.

Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

1⃣Вычислите сумму всех элементов массива.

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

3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.

😎 Решение:

function pivotIndex($nums) {
    $totalSum = array_sum($nums);
    $leftSum = 0;
    foreach ($nums as $i => $num) {
        if ($leftSum == $totalSum - $leftSum - $num) {
            return $i;
        }
        $leftSum += $num;
    }
    return -1;
}

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

Задача: 56. Merge Intervals
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

2⃣Определение компонент связности:
Для определения, в какой компоненте связности находится каждый узел, мы выполняем обходы графа от произвольных непосещенных узлов до тех пор, пока все узлы не будут посещены. Для эффективности мы храним посещенные узлы в множестве (Set), что позволяет проводить проверки на принадлежность и вставку за константное время.

3⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

Решение:

class Solution {
    private $graph = [];
    private $nodesInComp = [];
    private $visited = [];

    private function overlap($a, $b) {
        return $a[0] <= $b[1] && $b[0] <= $a[1];
    }

    private function buildGraph($intervals) {
        foreach ($intervals as $interval1) {
            foreach ($intervals as $interval2) {
                if ($this->overlap($interval1, $interval2)) {
                    $this->graph[serialize($interval1)][] = $interval2;
                    $this->graph[serialize($interval2)][] = $interval1;
                }
            }
        }
    }

    private function mergeNodes($nodes) {
        $minStart = $nodes[0][0];
        $maxEnd = $nodes[0][1];
        foreach ($nodes as $node) {
            $minStart = min($minStart, $node[0]);
            $maxEnd = max($maxEnd, $node[1]);
        }
        return [$minStart, $maxEnd];
    }

    private function markComponentDFS($start, $compNumber) {
        $stack = [];
        array_push($stack, $start);
        while (!empty($stack)) {
            $node = array_pop($stack);
            if (!in_array($node, $this->visited, true)) {
                $this->visited[] = $node;
                $this->nodesInComp[$compNumber][] = $node;
                foreach ($this->graph[serialize($node)] as $child) {
                    array_push($stack, $child);
                }
            }
        }
    }

    private function buildComponents($intervals) {
        $compNumber = 0;
        foreach ($intervals as $interval) {
            if (!in_array($interval, $this->visited, true)) {
                $this->markComponentDFS($interval, $compNumber);
                $compNumber++;
            }
        }
    }

    public function merge($intervals) {
        $this->buildGraph($intervals);
        $this->buildComponents($intervals);
        $merged = [];
        foreach ($this->nodesInComp as $components) {
            $merged[] = $this->mergeNodes($components);
        }
        return $merged;
    }
}

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

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

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

1⃣Использовать словарь для хранения количества встреченных сумм префиксов. Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.

2⃣Пройти по массиву и обновить текущую сумму. Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов. Обновить словарь префиксных сумм.

3⃣Вернуть счетчик подмассивов.

😎 Решение:

function numSubarraysWithSum($nums, $goal) {
    $prefixSumCount = [0 => 1];
    $currentSum = 0;
    $count = 0;

    foreach ($nums as $num) {
        $currentSum += $num;

        if (isset($prefixSumCount[$currentSum - $goal])) {
            $count += $prefixSumCount[$currentSum - $goal];
        }

        if (isset($prefixSumCount[$currentSum])) {
            $prefixSumCount[$currentSum]++;
        } else {
            $prefixSumCount[$currentSum] = 1;
        }
    }

    return $count;
}

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

Задача: 784. Letter Case Permutation
Сложность: medium

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

Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

1⃣Если следующий символ c является буквой, то мы удвоим все слова в нашем текущем ответе, и добавим lowercase(c) к каждому слову в первой половине, и uppercase(c) к каждому слову во второй половине.

2⃣Если c является цифрой, мы добавим его к каждому слову.

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

😎 Решение:

class Solution {
    function letterCasePermutation($S) {
        $ans = [[]];

        foreach (str_split($S) as $char) {
            $n = count($ans);
            if (ctype_alpha($char)) {
                for ($i = 0; $i < $n; $i++) {
                    $ans[] = $ans[$i];
                    $ans[$i][] = strtolower($char);
                    $ans[$n + $i][] = strtoupper($char);
                }
            } else {
                for ($i = 0; $i < $n; $i++) {
                    $ans[$i][] = $char;
                }
            }
        }

        return array_map(function($arr) {
            return implode('', $arr);
        }, $ans);
    }
}

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

Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

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

1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.

3⃣Создайте новую строку, удалив все помеченные скобки.

😎 Решение:

class Solution {
    function minRemoveToMakeValid($s) {
        $stack = [];
        $s = str_split($s);
        for ($i = 0; $i < count($s); $i++) {
            if ($s[$i] == '(') {
                array_push($stack, $i);
            } elseif ($s[$i] == ')') {
                if (!empty($stack)) {
                    array_pop($stack);
                } else {
                    $s[$i] = '';
                }
            }
        }
        while (!empty($stack)) {
            $s[array_pop($stack)] = '';
        }
        return implode('', $s);
    }
}

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

Задача: 594. Longest Harmonious Subsequence
Сложность: easy

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

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

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

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

😎 Решение:

class Solution {
    function findLHS($nums) {
        $count = [];
        $res = 0;
        
        foreach ($nums as $num) {
            if (isset($count[$num])) {
                $count[$num]++;
            } else {
                $count[$num] = 1;
            }
            if (isset($count[$num + 1])) {
                $res = max($res, $count[$num] + $count[$num + 1]);
            }
            if (isset($count[$num - 1])) {
                $res = max($res, $count[$num] + $count[$num - 1]);
            }
        }
        
        return $res;
    }
}

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

Задача: 152. Maximum Product Subarray
Сложность: Medium

Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

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

1⃣Инициализация:
Если массив nums пуст, возвращаем 0, так как нет элементов для обработки.
Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.

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

3⃣Вычисление произведения и обновление результата:
Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого.
Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.

😎 Решение:

class Solution {
    function maxProduct($nums) {
        if (count($nums) == 0) return 0;

        $result = $nums[0];

        for ($i = 0; $i < count($nums); $i++) {
            $accu = 1;
            for ($j = $i; $j < count($nums); $j++) {
                $accu *= $nums[$j];
                $result = max($result, $accu);
            }
        }

        return $result;
    }
}

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
    function getSum($a, $b) {
        $x = abs($a);
        $y = abs($b);
        if ($x < $y) return $this->getSum($b, $a);
        $sign = $a > 0 ? 1 : -1;

        if ($a * $b >= 0) {
            while ($y != 0) {
                $carry = ($x & $y) << 1;
                $x ^= $y;
                $y = $carry;
            }
        } else {
            while ($y != 0) {
                $borrow = ((~$x) & $y) << 1;
                $x ^= $y;
                $y = $borrow;
            }
        }
        return $x * $sign;
    }
}

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

Задача: 1396. Design Underground System
Сложность: medium

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

Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке.

Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5

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

1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.

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

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

😎 Решение:

class UndergroundSystem {
    private $journeyData;
    private $checkInData;

    function __construct() {
        $this->journeyData = [];
        $this->checkInData = [];
    }

    function checkIn($id, $stationName, $t) {
        $this->checkInData[$id] = [$stationName, $t];
    }

    function checkOut($id, $stationName, $t) {
        list($startStation, $startTime) = $this->checkInData[$id];
        unset($this->checkInData[$id]);
        $routeKey = "{$startStation}->{$stationName}";
        $tripTime = $t - $startTime;
        if (!isset($this->journeyData[$routeKey])) {
            $this->journeyData[$routeKey] = [0, 0];
        }
        list($totalTime, $trips) = $this->journeyData[$routeKey];
        $this->journeyData[$routeKey] = [$totalTime + $tripTime, $trips + 1];
    }

    function getAverageTime($startStation, $endStation) {
        list($totalTime, $trips) = $this->journeyData["{$startStation}->{$endStation}"];
        return $totalTime / $trips;
    }
}

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

Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

class Solution {
    function minSwaps($data) {
        $ones = array_sum($data);
        $cnt_one = 0;
        $max_one = 0;
        $left = 0;
        $right = 0;

        while ($right < count($data)) {
            $cnt_one += $data[$right++];
            if ($right - $left > $ones) {
                $cnt_one -= $data[$left++];
            }
            $max_one = max($max_one, $cnt_one);
        }
        return $ones - $max_one;
    }
}

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

Задача: 57. Insert Interval
Сложность: medium

Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.
Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).
Верните массив intervals после вставки.
Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

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

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

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

3⃣Обработка интервалов после вставки:
Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.
Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом.

😎 Решение:

class Solution {
    public function insert($intervals, $newInterval) {
        $res = [];
        $i = 0;

        // Process intervals with no overlap before the new interval
        while ($i < count($intervals) && $intervals[$i][1] < $newInterval[0]) {
            array_push($res, $intervals[$i]);
            $i++;
        }

        // Merge overlapping intervals with newInterval
        while ($i < count($intervals) && $newInterval[1] >= $intervals[$i][0]) {
            $newInterval[0] = min($newInterval[0], $intervals[$i][0]);
            $newInterval[1] = max($newInterval[1], $intervals[$i][1]);
            $i++;
        }
        array_push($res, $newInterval);

        // Append remaining intervals after merging
        while ($i < count($intervals)) {
            array_push($res, $intervals[$i]);
            $i++;
        }

        return $res;
    }
}

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

Задача: 441. Arranging Coins
Сложность: medium

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

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

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

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

class Solution {
    function arrangeCoins($n) {
        return (int)(sqrt(2 * $n + 0.25) - 0.5);
    }
}

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

Задача: 979. Distribute Coins in Binary Tree
Сложность: medium

Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.

За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.

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

Пример:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

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

1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.

2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves.

3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.

😎 Решение:

class Solution {
    private $moves;

    function distributeCoins($root) {
        $this->moves = 0;
        $this->dfs($root);
        return $this->moves;
    }

    private function dfs($current) {
        if ($current == null) return 0;
        $leftCoins = $this->dfs($current->left);
        $rightCoins = $this->dfs($current->right);
        $this->moves += abs($leftCoins) + abs($rightCoins);
        return $current->val - 1 + $leftCoins + $rightCoins;
    }
}

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