Задача: 35. Search Insert Position
Сложность: easy

Дан отсортированный массив различных целых чисел nums и число target. Необходимо вернуть индекс target, если он найден. Если target отсутствует, вернуть индекс, куда он должен быть вставлен, чтобы сохранить порядок.
Алгоритм должен работать за O(log n).

Пример:

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

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

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

2⃣сли nums[mid] == target, возвращаем mid.

3⃣Если nums[mid] < target, продолжаем поиск справа, иначе — слева.

😎 Решение:

class Solution {
    function searchInsert($nums, $target) {
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = intdiv($left + $right, 2);
            if ($nums[$mid] == $target) {
                return $mid;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return $left;
    }
}

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

Задача: 174. Dungeon Game
Сложность: hard

Демоны захватили принцессу и заточили её в правом нижнем углу подземелья. Подземелье состоит из m x n комнат, расположенных в виде двумерной сетки. Наш отважный рыцарь изначально находится в левом верхнем углу и должен пробиться через подземелье, чтобы спасти принцессу.
У рыцаря есть начальное количество очков здоровья, представленное положительным целым числом. Если в какой-то момент его очки здоровья упадут до 0 или ниже, он немедленно умрёт.
Некоторые комнаты охраняются демонами (представлены отрицательными числами), поэтому рыцарь теряет здоровье, заходя в эти комнаты; другие комнаты либо пусты (представлены как 0), либо содержат магические шары, увеличивающие здоровье рыцаря (представлены положительными числами).
Чтобы как можно быстрее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге.
Верните минимальное начальное количество здоровья рыцаря, чтобы он мог спасти принцессу.
Учтите, что любая комната может содержать угрозы или усиления, включая первую комнату, в которую входит рыцарь, и последнюю комнату, где заточена принцесса.

Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

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

1⃣Определяем матрицу dp[row][col], где элемент dp[row][col] указывает минимальное количество очков здоровья, которое потребуется рыцарю, начиная с соответствующей ячейки подземелья dungeon[row][col], чтобы добраться до цели.

2⃣Для расчета значений матрицы dp начинаем с правого нижнего угла подземелья и идем в порядке справа-налево и снизу-вверх. Для каждой ячейки подземелья рассчитываем соответствующее значение dp[row][col].

3⃣Значение dp[row][col] определяется следующими условиями:
Если возможно, сделав шаг вправо из текущей ячейки подземелья, рыцарь может нуждаться в right_health очках здоровья.
Если возможно, сделав шаг вниз из текущей ячейки подземелья, рыцарь может нуждаться в down_health очках здоровья.
Если существует хотя бы одна из вышеуказанных альтернатив, берём минимальное значение из них для dp[row][col].
Если ни одна из вышеуказанных альтернатив не существует, то есть мы находимся в целевой ячейке, возможны два случая:
Если текущая ячейка содержит магический шар, то достаточно одного очка здоровья.
Если текущая ячейка содержит демона, то рыцарь должен иметь одно очко здоровья плюс очки урона, которые нанесет демон.

😎 Решение:

function calculateMinimumHP($dungeon) {
    $rows = count($dungeon);
    $cols = count($dungeon[0]);
    $dp = array_fill(0, $rows, array_fill(0, $cols, PHP_INT_MAX));

    function get_min_health($dp, $currCell, $nextRow, $nextCol, $rows, $cols) {
        if ($nextRow >= $rows || $nextCol >= $cols) {
            return PHP_INT_MAX;
        }
        $nextCell = $dp[$nextRow][$nextCol];
        return max(1, $nextCell - $currCell);
    }

    for ($row = $rows - 1; $row >= 0; --$row) {
        for ($col = $cols - 1; $col >= 0; --$col) {
            $currCell = $dungeon[$row][$col];

            $right_health = get_min_health($dp, $currCell, $row, $col + 1, $rows, $cols);
            $down_health = get_min_health($dp, $currCell, $row + 1, $col, $rows, $cols);
            $next_health = min($right_health, $down_health);

            if ($next_health != PHP_INT_MAX) {
                $min_health = $next_health;
            } else {
                $min_health = $currCell >= 0 ? 1 : 1 - $currCell;
            }

            $dp[$row][$col] = $min_health;
        }
    }

    return $dp[0][0];
}

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

Задача: 1004. Max Consecutive Ones III
Сложность: medium

Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    function longestOnes($nums, $k) {
        $left = 0;
        $maxOnes = 0;
        $zeroCount = 0;

        for ($right = 0; $right < count($nums); $right++) {
            if ($nums[$right] == 0) {
                $zeroCount++;
            }

            while ($zeroCount > $k) {
                if ($nums[$left] == 0) {
                    $zeroCount--;
                }
                $left++;
            }

            $maxOnes = max($maxOnes, $right - $left + 1);
        }

        return $maxOnes;
    }
}

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

Input: n = 4
Output: [2,1,4,3]

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

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

😎 Решение:

function beautifulArray($n) {
    return construct($n);
}

function construct($n) {
    if ($n == 1) return [1];
    $odd = array_map(fn($x) => 2 * $x - 1, construct(($n + 1) / 2));
    $even = array_map(fn($x) => 2 * $x, construct($n / 2));
    return array_merge($odd, $even);
}

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

Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium

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

Пример:

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

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

1⃣Найдите сумму всех элементов массива.

2⃣Если сумма делится на 3, то она и есть ответ.

3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2).
Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2).

😎 Решение:

function maxSumDivThree($nums) {
    $totalSum = array_sum($nums);
    if ($totalSum % 3 == 0) {
        return $totalSum;
    }
    
    $mod1 = [];
    $mod2 = [];
    foreach ($nums as $num) {
        if ($num % 3 == 1) {
            $mod1[] = $num;
        } elseif ($num % 3 == 2) {
            $mod2[] = $num;
        }
    }
    
    sort($mod1);
    sort($mod2);
    
    if ($totalSum % 3 == 1) {
        $remove1 = empty($mod1) ? PHP_INT_MAX : $mod1[0];
        $remove2 = count($mod2) < 2 ? PHP_INT_MAX : $mod2[0] + $mod2[1];
        return $totalSum - min($remove1, $remove2);
    } else {
        $remove2 = empty($mod2) ? PHP_INT_MAX : $mod2[0];
        $remove1 = count($mod1) < 2 ? PHP_INT_MAX : $mod1[0] + $mod1[1];
        return $totalSum - min($remove2, $remove1);
    }
}

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

class Solution {
    function fixedPoint($arr) {
        $left = 0;
        $right = count($arr) - 1;
        $answer = -1;
        
        while ($left <= $right) {
            $mid = intdiv($left + $right, 2);
            
            if ($arr[$mid] == $mid) {
                $answer = $mid;
                $right = $mid - 1;
            } else if ($arr[$mid] < $mid) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        
        return $answer;
    }
}

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

Задача: 1266. Minimum Time Visiting All Points
Сложность: easy

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7

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

1⃣Инициализируйте переменную для хранения минимального времени.

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

3⃣Суммируйте время переходов для получения общего минимального времени.

😎 Решение:

class Solution {
    function minTimeToVisitAllPoints($points) {
        $time = 0;
        for ($i = 0; $i < count($points) - 1; $i++) {
            $time += $this->distance($points[$i], $points[$i + 1]);
        }
        return $time;
    }

    private function distance($p1, $p2) {
        return max(abs($p1[0] - $p2[0]), abs($p1[1] - $p2[1]));
    }
}

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

Задача: 66. Plus One
Сложность: easy

Вам дано большое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это i-я цифра числа. Цифры расположены в порядке от старшей к младшей слева направо. Большое число не содержит ведущих нулей.
Увеличьте большое число на один и верните результирующий массив цифр.

Пример:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

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

1⃣Проходим по входному массиву, начиная с конца массива.

2⃣Устанавливаем все девятки на конце массива в ноль. Если мы встречаем цифру, не равную девяти, увеличиваем её на один. Работа выполнена — возвращаем массив цифр.

3⃣Мы здесь, потому что все цифры были равны девяти. Теперь они все установлены в ноль. Затем мы добавляем цифру 1 в начало остальных цифр и возвращаем результат

😎 Решение:

function plusOne($digits) {
    $n = count($digits);
    for ($i = $n - 1; $i >= 0; --$i) {
        if ($digits[$i] == 9) {
            $digits[$i] = 0;
        } else {
            $digits[$i]++;
            return $digits;
        }
    }
    array_unshift($digits, 1);
    return $digits;
}

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

Задача: 1165. Single-Row Keyboard
Сложность: easy

Есть специальная клавиатура, на которой все клавиши расположены в один ряд.

Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.

Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.

Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

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

1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.

2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.

3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.

😎 Решение:

class Solution {
    function calculateTime($keyboard, $word) {
        $keyIndices = array_fill(0, 26, -1);
        for ($i = 0; $i < strlen($keyboard); $i++) {
            $keyIndices[ord($keyboard[$i]) - ord('a')] = $i;
        }
        
        $prev = 0;
        $result = 0;
        
        for ($i = 0; $i < strlen($word); $i++) {
            $index = $keyIndices[ord($word[$i]) - ord('a')];
            $result += abs($prev - $index);
            $prev = $index;
        }
        
        return $result;
    }
}

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

Задача: 1522. Diameter of N-Ary Tree
Сложность: medium

Дано корневое дерево N-арности, нужно вычислить длину диаметра дерева.

Диаметр N-арного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.

(Входная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.)

Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

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

1⃣Определите функцию height(node), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один.

2⃣Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева.

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

😎 Решение:

class Solution {
    private $diameter = 0;

    private function height($node) {
        if (count($node->children) === 0) return 0;

        $maxHeight1 = 0;
        $maxHeight2 = 0;
        foreach ($node->children as $child) {
            $parentHeight = $this->height($child) + 1;
            if ($parentHeight > $maxHeight1) {
                $maxHeight2 = $maxHeight1;
                $maxHeight1 = $parentHeight;
            } else if ($parentHeight > $maxHeight2) {
                $maxHeight2 = $parentHeight;
            }
            $distance = $maxHeight1 + $maxHeight2;
            $this->diameter = max($this->diameter, $distance);
        }

        return $maxHeight1;
    }

    public function diameter($root) {
        $this->diameter = 0;
        $this->height($root);
        return $this->diameter;
    }
}

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

Задача: 71. Simplify Path
Сложность: medium

Дан абсолютный путь для файловой системы в стиле Unix, который начинается с символа '/'. Преобразуйте этот путь в его упрощенный канонический путь.
В контексте файловой системы Unix-style одинарная точка '.' обозначает текущий каталог, двойная точка '..' означает переход на один уровень каталога вверх, а несколько слэшей, таких как '//', интерпретируются как один слэш. В этой задаче последовательности точек, не охваченные предыдущими правилами (например, '...'), следует рассматривать как допустимые имена для файлов или каталогов.
Упрощенный канонический путь должен соответствовать следующим правилам:
Он должен начинаться с одного слэша '/'.
Каталоги в пути должны быть разделены только одним слэшем '/'.
Он не должен заканчиваться слэшем '/', если только это не корневой каталог.
Он должен исключать любые одинарные или двойные точки, используемые для обозначения текущих или родительских каталогов.
Верните новый путь.

Пример:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

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

1⃣Инициализируем стек S, который будет использоваться в нашей реализации. Разделяем входную строку, используя символ '/' в качестве разделителя. Этот шаг очень важен, поскольку входные данные всегда являются допустимым путем, и наша задача — лишь его сократить. Таким образом, все, что находится между двумя символами '/', является либо именем каталога, либо специальным символом, и мы должны соответственно обработать их.

2⃣Как только входной путь разделен, мы обрабатываем каждый компонент по отдельности. Если текущий компонент — это точка '.' или пустая строка, мы ничего не делаем и просто продолжаем. Если вспомнить, массив строк, полученный при разделении строки '/a//b', будет [a, , b], где между a и b находится пустая строка, что в контексте общего пути не имеет значения. Если мы сталкиваемся с двойной точкой '..', это означает, что нужно подняться на один уровень выше в текущем пути каталога. Поэтому мы удаляем запись из нашего стека, если он не пуст.

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

😎 Решение:

function simplifyPath($path) {
    $stack = [];
    $portions = explode("/", $path);
    foreach ($portions as $portion) {
        if ($portion === "..") {
            if (!empty($stack)) {
                array_pop($stack);
            }
        } elseif ($portion !== "." && $portion !== "") {
            array_push($stack, $portion);
        }
    }
    return "/" . implode("/", $stack);
}

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

Задача: 96. Unique Binary Search Trees
Сложность: medium

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

Пример:

Input: n = 3
Output: 5

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

1⃣Вводим G(n) — количество уникальных BST, которые можно построить из n узлов.

2⃣Для каждого i от 1 до n, количество деревьев с i в качестве корня равно G(i−1) * G(n−i), где i−1 — количество узлов в левом поддереве, а n−i — в правом.

3⃣Для подсчета G(n) используем динамическое программирование с базовыми случаями:
G(0) = 1 (пустое дерево)
G(1) = 1 (один узел)

😎 Решение:

class Solution {
    function numTrees($n) {
        $G = array_fill(0, $n + 1, 0);
        $G[0] = $G[1] = 1;

        for ($i = 2; $i <= $n; $i++) {
            for ($j = 1; $j <= $i; $j++) {
                $G[$i] += $G[$j - 1] * $G[$i - $j];
            }
        }

        return $G[$n];
    }
}

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

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 getAllElements($root1, $root2) {
        $stack1 = new SplStack();
        $stack2 = new SplStack();
        $output = [];

        while ($root1 !== null || $root2 !== null || !$stack1->isEmpty() || !$stack2->isEmpty()) {
            while ($root1 !== null) {
                $stack1->push($root1);
                $root1 = $root1->left;
            }
            while ($root2 !== null) {
                $stack2->push($root2);
                $root2 = $root2->left;
            }
            if ($stack2->isEmpty() || (!$stack1->isEmpty() && $stack1->top()->val <= $stack2->top()->val)) {
                $root1 = $stack1->pop();
                $output[] = $root1->val;
                $root1 = $root1->right;
            } else {
                $root2 = $stack2->pop();
                $output[] = $root2->val;
                $root2 = $root2->right;
            }
        }
        return $output;
    }
}

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

Задача: 160. Intersection of Two Linked Lists
Сложность: easy

Даны головы двух односвязных списков headA и headB. Верните узел, в котором эти два списка пересекаются. Если два связанных списка не имеют пересечений, верните null.
Например, следующие два связанных списка начинают пересекаться в узле c1.

Пример:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

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

1⃣Сохранение ссылок из списка B:
Проходим по всем узлам списка B и сохраняем ссылки (адреса) каждого узла в хеш-таблицу. Это позволит нам быстро проверять, содержится ли узел из списка A в списке B.

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

3⃣Обработка отсутствия пересечения:
Если до конца списка A не найдено ни одного узла, который бы совпал с узлами из хеш-таблицы, возвращаем null, указывая на отсутствие пересечения между списками.

😎 Решение:

class ListNode {
    public $val;
    public $next = null;
    
    function __construct($val) {
        $this->val = $val;
    }
}

class Solution {
    function getIntersectionNode($headA, $headB) {
        $nodesInB = [];
        
        while ($headB !== null) {
            $nodesInB[spl_object_hash($headB)] = $headB;
            $headB = $headB->next;
        }
        
        while ($headA !== null) {
            if (isset($nodesInB[spl_object_hash($headA)])) {
                return $headA;
            }
            $headA = $headA->next;
        }
        
        return null;
    }
}

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

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

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution {
    private $maxTime = -PHP_INT_MAX;
    
    function DFS($adjList, $informTime, $curr, $time) {
        $this->maxTime = max($this->maxTime, $time);
        foreach ($adjList[$curr] as $adjacent) {
            $this->DFS($adjList, $informTime, $adjacent, $time + $informTime[$curr]);
        }
    }
    
    function numOfMinutes($n, $headID, $manager, $informTime) {
        $adjList = array_fill(0, $n, []);
        for ($i = 0; $i < $n; $i++) {
            if ($manager[$i] != -1) {
                $adjList[$manager[$i]][] = $i;
            }
        }
        $this->DFS($adjList, $informTime, $headID, 0);
        return $this->maxTime;
    }
}

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

Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

Input: nums = [1,17,8]
Output: 2

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

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

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

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

😎 Решение:

class Solution {
    function numSquarefulPerms($nums) {
        sort($nums);
        $used = array_fill(0, count($nums), false);
        $result = [];
        $path = [];
        $this->backtrack($nums, $used, $path, $result);
        return count($result);
    }
    
    private function backtrack($nums, &$used, &$path, &$result) {
        if (count($path) == count($nums)) {
            if ($this->isSquareful($path)) {
                $result[implode(',', $path)] = true;
            }
            return;
        }
        
        for ($i = 0; $i < count($nums); $i++) {
            if ($used[$i] || ($i > 0 && $nums[$i] == $nums[$i - 1] && !$used[$i - 1])) continue;
            $path[] = $nums[$i];
            $used[$i] = true;
            $this->backtrack($nums, $used, $path, $result);
            array_pop($path);
            $used[$i] = false;
        }
    }
    
    private function isSquareful($perm) {
        for ($i = 0; $i < count($perm) - 1; $i++) {
            $sum = $perm[$i] + $perm[$i + 1];
            $root = (int)sqrt($sum);
            if ($root * $root != $sum) return false;
        }
        return true;
    }
}

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

Задача: 509. Fibonacci Number
Сложность: easy

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

class Solution {
    function fib($N) {
        if ($N <= 1) return $N;
        $current = 0;
        $prev1 = 1;
        $prev2 = 0;

        for ($i = 2; $i <= $N; $i++) {
            $current = $prev1 + $prev2;
            $prev2 = $prev1;
            $prev1 = $current;
        }
        return $current;
    }
}

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

Задача: 331. Verify Preorder Serialization of a Binary Tree
Сложность: medium

Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.
Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.
Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.

Пример:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

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

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

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

3⃣Проверка завершения:
После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false.

😎 Решение:

class Solution {
    function isValidSerialization($preorder) {
        $slots = 1;
        $nodes = explode(',', $preorder);
        
        foreach ($nodes as $node) {
            $slots--;
            if ($slots < 0) {
                return false;
            }
            if ($node !== "#") {
                $slots += 2;
            }
        }
        
        return $slots == 0;
    }
}

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

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

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

3⃣Вернуть count.

😎 Решение:

function minDeletionSize($strs) {
    $count = 0;
    $rows = count($strs);
    $cols = strlen($strs[0]);
    for ($col = 0; $col < $cols; $col++) {
        for ($row = 1; $row < $rows; $row++) {
            if ($strs[$row][$col] < $strs[$row - 1][$col]) {
                $count++;
                break;
            }
        }
    }
    return $count;
}

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

Задача: 789. Escape The Ghosts
Сложность: medium

Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами.

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

Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом.

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

Пример:

Input: ghosts = [[1,0],[0,3]], target = [0,1]
Output: true
Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you.

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

1⃣Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели.

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

3⃣Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен.

😎 Решение:

class Solution {
    function escapeGhosts($ghosts, $target) {
        $taxi = function($P, $Q) {
            return abs($P[0] - $Q[0]) + abs($P[1] - $Q[1]);
        };

        $playerDistance = $taxi([0, 0], $target);
        foreach ($ghosts as $ghost) {
            if ($taxi($ghost, $target) <= $playerDistance) {
                return false;
            }
        }
        return true;
    }
}

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