Задача: 32. Longest Valid Parentheses
Сложность: hard

Дана строка, содержащая только символы ( и ). Нужно найти длину самой длинной допустимой (правильно сформированной) подстроки круглых скобок.

Пример:

Input: s = "(()"  
Output: 2  

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

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

2⃣Если s[i] == ')' и перед ней есть (, обновляем dp[i] на основе dp[i-1] и dp[i-dp[i-1]-2].

3⃣Возвращаем максимальное значение из dp.

😎 Решение:

class Solution {
    function longestValidParentheses($s) {
        $s2 = ')'.$s;
        $n = strlen($s2);
        $dp = array_fill(0, $n, 0);

        for ($i = 1; $i < $n; $i++) {
            if ($s2[$i] === ')' && $s2[$i - $dp[$i - 1] - 1] === '(') {
                $dp[$i] = $dp[$i - 1] + $dp[$i - $dp[$i - 1] - 2] + 2;
            }
        }

        return max($dp);
    }
}

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

Задача: 754. Reach a Number
Сложность: medium

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

function reachTarget($target) {
    $target = abs($target);
    $position = 0;
    $steps = 0;
    while ($position < $target || ($position - $target) % 2 != 0) {
        $steps += 1;
        $position += $steps;
    }
    return $steps;
}

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

Задача: 412. Fizz Buzz
Сложность: easy

Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.

Пример:

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

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

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

2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку.

3⃣Верните полученный список.

😎 Решение:

function fizzBuzz($n) {
    $answer = [];
    for ($i = 1; $i <= $n; $i++) {
        if ($i % 3 == 0 && $i % 5 == 0) {
            $answer[] = "FizzBuzz";
        } elseif ($i % 3 == 0) {
            $answer[] = "Fizz";
        } elseif ($i % 5 == 0) {
            $answer[] = "Buzz";
        } else {
            $answer[] = (string)$i;
        }
    }
    return $answer;
}

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

Задача: 859. Buddy Strings
Сложность: easy

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

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

class Solution {
    function buddyStrings($s, $goal) {
        if (strlen($s) != strlen($goal)) return false;
        if ($s == $goal) {
            $freq = array_fill(0, 26, 0);
            foreach (str_split($s) as $ch) {
                if (++$freq[ord($ch) - ord('a')] > 1) return true;
            }
            return false;
        }

        $firstIndex = -1;
        $secondIndex = -1;
        for ($i = 0; $i < strlen($s); ++$i) {
            if ($s[$i] != $goal[$i]) {
                if ($firstIndex == -1) $firstIndex = $i;
                else if ($secondIndex == -1) $secondIndex = $i;
                else return false;
            }
        }

        return $secondIndex != -1 &&
               $s[$firstIndex] == $goal[$secondIndex] &&
               $s[$secondIndex] == $goal[$firstIndex];
    }
}

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

Задача: 482. License Key Formatting
Сложность: Easy

Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.
Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные.
Верните переформатированный лицензионный ключ.

Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

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

1⃣Инициализация
Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата.

2⃣Итерация по входной строке в обратном порядке
Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count.

3⃣Завершение
Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её.

😎 Решение:

class Solution {
    function licenseKeyFormatting($s, $k) {
        $count = 0;
        $ans = [];

        for ($i = strlen($s) - 1; $i >= 0; $i--) {
            if ($s[$i] != '-') {
                $ans[] = strtoupper($s[$i]);
                $count++;
                if ($count == $k) {
                    $ans[] = '-';
                    $count = 0;
                }
            }
        }

        if (end($ans) == '-') {
            array_pop($ans);
        }

        return implode('', array_reverse($ans));
    }
}

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

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах.

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
    function arraysIntersection($arr1, $arr2, $arr3) {
        $counter = array();
        
        foreach ($arr1 as $e) {
            if (isset($counter[$e])) $counter[$e]++;
            else $counter[$e] = 1;
        }
        
        foreach ($arr2 as $e) {
            if (isset($counter[$e])) $counter[$e]++;
            else $counter[$e] = 1;
        }
        
        foreach ($arr3 as $e) {
            if (isset($counter[$e])) $counter[$e]++;
            else $counter[$e] = 1;
        }

        $ans = array();
        foreach ($counter as $key => $value) {
            if ($value == 3) array_push($ans, $key);
        }

        return $ans;
    }
}

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

Задача: 865. Smallest Subtree with all the Deepest Nodes
Сложность: medium

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

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

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

Поддерево узла — это дерево, состоящее из этого узла и всех его потомков.

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

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

1⃣В первой фазе используем поиск в глубину (DFS), чтобы аннотировать узлы. Каждый узел будет хранить информацию о своей глубине и о самой большой глубине среди его потомков.

2⃣Во второй фазе также используем DFS для функции answer(node), которая возвращает наименьшее поддерево, содержащее все самые глубокие узлы. Функция сравнивает глубины левых и правых поддеревьев узла для определения наименьшего поддерева.

3⃣Функция answer(node) возвращает поддерево, которое содержит все самые глубокие узлы всего дерева, а не только рассматриваемого поддерева.

😎 Решение:

class Solution {
    private $depth = [];
    private $maxDepth = -1;

    function subtreeWithAllDeepest($root) {
        $this->depth[null] = -1;
        $this->dfs($root, null);
        $this->maxDepth = max($this->depth);
        return $this->answer($root);
    }

    private function dfs($node, $parent) {
        if ($node !== null) {
            $this->depth[$node->val] = $this->depth[$parent->val] + 1;
            $this->dfs($node->left, $node);
            $this->dfs($node->right, $node);
        }
    }

    private function answer($node) {
        if ($node === null || $this->depth[$node->val] == $this->maxDepth) return $node;
        $L = $this->answer($node->left);
        $R = $this->answer($node->right);
        if ($L !== null && $R !== null) return $node;
        return $L !== null ? $L : $R;
    }
}

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

Задача: 742. Closest Leaf in a Binary Tree
Сложность: medium

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

Пример:

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

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

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

2⃣Найдите все листья и минимальное расстояние до них, используя BFS, начиная с найденного узла k.

3⃣Верните значение ближайшего листа.

😎 Решение:

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

function findClosestLeaf($root, $k) {
    $path = [];
    $leaves = [];
    
    function findPath($node, $k, &$path) {
        if (!$node) return false;
        $path[] = $node;
        if ($node->val == $k) return true;
        if (findPath($node->left, $k, $path) || findPath($node->right, $k, $path)) return true;
        array_pop($path);
        return false;
    }
    
    function findLeaves($node, &$leaves) {
        if (!$node) return;
        if (!$node->left && !$node->right) $leaves[spl_object_hash($node)] = 0;
        findLeaves($node->left, $leaves);
        findLeaves($node->right, $leaves);
    }
    
    findPath($root, $k, $path);
    findLeaves($root, $leaves);
    
    $queue = [[end($path), 0]];
    $visited = [];
    
    while ($queue) {
        list($node, $dist) = array_shift($queue);
        if (isset($leaves[spl_object_hash($node)])) return $node->val;
        $visited[spl_object_hash($node)] = true;
        if ($node->left && !isset($visited[spl_object_hash($node->left)])) $queue[] = [$node->left, $dist + 1];
        if ($node->right && !isset($visited[spl_object_hash($node->right)])) $queue[] = [$node->right, $dist + 1];
        if (count($path) > 1) $queue[] = [array_pop($path), $dist + 1];
    }
    return -1;
}

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

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

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