Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

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

1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.

2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.

3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.

😎 Решение:

class Solution {
    private function solve($root, $parent, $gParent) {
        if ($root === null) {
            return 0;
        }
        return $this->solve($root->left, $root->val, $parent) + $this->solve($root->right, $root->val, $parent) + ($gParent % 2 == 0 ? $root->val : 0);
    }

    public function sumEvenGrandparent($root) {
        return $this->solve($root, -1, -1);
    }
}

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

Задача: 253. Meeting Rooms II
Сложность: medium

Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

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

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

😎 Решение:

class Solution {
    function minMeetingRooms($intervals) {
        usort($intervals, function($a, $b) {
            return $a[0] - $b[0];
        });
        $heap = new SplMinHeap();
        $heap->insert($intervals[0][1]);
        
        for ($i = 1; $i < count($intervals); $i++) {
            if ($intervals[$i][0] >= $heap->top()) {
                $heap->extract();
            }
            $heap->insert($intervals[$i][1]);
        }
        return $heap->count();
    }
}

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

Задача №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]

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

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

2⃣Если еще можно открыть скобку — добавляем ( и уменьшаем счетчик открытых.

3⃣Если есть закрытые скобки, которые можно закрыть — добавляем ).

😎 Решение:

class Solution { 

    private array $answer = []; 
    private string $current = ''; 

    function generateParenthesis($n) { 
        $this->generateParentheses($n, 0); 
        return $this->answer; 
    } 

    function generateParentheses($toOpen, $toClose) { 
        if ($toOpen == 0 && $toClose == 0) { 
            $this->answer[] = $this->current; 
            return; 
        } 

        if ($toOpen > 0) { 
            $this->current .= '('; 
            $this->generateParentheses($toOpen - 1, $toClose + 1); 
            $this->current = substr($this->current, 0, -1); 
        } 

        if ($toClose > 0) { 
            $this->current .= ')'; 
            $this->generateParentheses($toOpen, $toClose - 1); 
            $this->current = substr($this->current, 0, -1); 
        }         
    } 
}

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

Задача: 58. Length of Last Word
Сложность: easy

Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке.
Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами.

Пример:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

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

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

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

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

😎 Решение:

class Solution {
    public function lengthOfLastWord($s) {
        $p = strlen($s) - 1;
        while ($p >= 0 && $s[$p] == ' ') {
            $p--;
        }
        $length = 0;
        while ($p >= 0 && $s[$p] != ' ') {
            $p--;
            $length++;
        }
        return $length;
    }
}

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

Задача: 1243. Array Transformation
Сложность: easy

Если задан исходный массив arr, то каждый день вы создаете новый массив, используя массив предыдущего дня. В i-й день вы выполняете следующие операции над массивом дня i-1, чтобы получить массив дня i: если элемент меньше своего левого и правого соседа, то этот элемент увеличивается. Если элемент больше своего левого и правого соседа, то этот элемент уменьшается. Первый и последний элементы никогда не меняются. Через несколько дней массив не меняется. Верните этот окончательный массив.

Пример:

Input: arr = [6,2,3,4]
Output: [6,3,3,4]

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

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

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

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

😎 Решение:

function transformArray($arr) {
    do {
        $changed = false;
        $newArr = $arr;
        for ($i = 1; $i < count($arr) - 1; $i++) {
            if ($arr[$i] < $arr[$i - 1] && $arr[$i] < $arr[$i + 1]) {
                $newArr[$i]++;
                $changed = true;
            } else if ($arr[$i] > $arr[$i - 1] && $arr[$i] > $arr[$i + 1]) {
                $newArr[$i]--;
                $changed = true;
            }
        }
        $arr = $newArr;
    } while ($changed);
    return $arr;
}

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

Задача: 1162. As Far from Land as Possible
Сложность: medium

Дана сетка размером n x n, содержащая только значения 0 и 1, где 0 представляет воду, а 1 представляет землю. Найдите ячейку с водой, такое что её расстояние до ближайшей ячейки с землёй максимально, и верните это расстояние. Если в сетке нет ни земли, ни воды, верните -1.

Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|.

Пример:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

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

1⃣Итерируйте по матрице и вставьте координаты ячеек с землёй в очередь. Инициализируйте переменную distance значением -1 для хранения текущего шага обхода в ширину (BFS). Также создайте копию матрицы visited для пометки ячеек с водой как посещённые, чтобы не вставлять их снова в очередь.

2⃣Выполните BFS: Обходите текущие элементы в очереди и для каждого элемента проверяйте координаты в четырёх направлениях, являются ли они ячейками с водой (0). Если да, вставьте их в очередь и измените их на ячейки с землёй (1) в матрице visited. После каждого пройденного уровня (внутренний цикл while завершён), увеличьте переменную distance.

3⃣Повторяйте, пока очередь не станет пустой. Верните значение distance. Если оно равно 0, это означает, что не было ячеек с водой и обход завершился после первого шага, поэтому верните -1. Если в матрице не было ячеек с землёй, цикл while вообще не начнётся, и переменная distance останется с начальным значением (-1).

😎 Решение:

class Solution {
    function maxDistance($grid) {
        $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        $visited = $grid;
        $q = [];
        
        for ($i = 0; $i < count($grid); $i++) {
            for ($j = 0; $j < count($grid[0]); $j++) {
                if ($grid[$i][$j] == 1) {
                    $q[] = [$i, $j];
                }
            }
        }
        
        $distance = -1;
        while (count($q) > 0) {
            $qSize = count($q);
            while ($qSize-- > 0) {
                list($landX, $landY) = array_shift($q);
                foreach ($directions as $dir) {
                    $x = $landX + $dir[0];
                    $y = $landY + $dir[1];
                    if ($x >= 0 && $y >= 0 && $x < count($grid) && $y < count($grid[0]) && $visited[$x][$y] == 0) {
                        $visited[$x][$y] = 1;
                        $q[] = [$x, $y];
                    }
                }
            }
            $distance++;
        }
        
        return $distance == 0 ? -1 : $distance;
    }
}

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

Задача: 821. Shortest Distance to a Character
Сложность: easy

Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.

Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.

Пример:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

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

1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.

2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.

3⃣Мы берем минимальное значение из этих двух ответов для создания нашего окончательного ответа.

😎 Решение:

class Solution {
    function shortestToChar($S, $C) {
        $N = strlen($S);
        $ans = array_fill(0, $N, PHP_INT_MAX);
        $prev = -$N;

        for ($i = 0; $i < $N; ++$i) {
            if ($S[$i] == $C) {
                $prev = $i;
            }
            $ans[$i] = $i - $prev;
        }

        $prev = 2 * $N;
        for ($i = $N - 1; $i >= 0; --$i) {
            if ($S[$i] == $C) {
                $prev = $i;
            }
            $ans[$i] = min($ans[$i], $prev - $i);
        }

        return $ans;
    }
}

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

Задача: 924. Minimize Malware Spread
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial.

2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО.

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом.

😎 Решение:

function minMalwareSpread($graph, $initial) {
    function dfs($graph, $node, &$infected) {
        for ($neighbor = 0; $neighbor < count($graph); $neighbor++) {
            if ($graph[$node][$neighbor] == 1 && !in_array($neighbor, $infected)) {
                $infected[] = $neighbor;
                dfs($graph, $neighbor, $infected);
            }
        }
    }

    $n = count($graph);
    $initialSet = $initial;
    sort($initial);
    $minInfected = PHP_INT_MAX;
    $bestNode = $initial[0];
    
    foreach ($initial as $node) {
        $infected = $initialSet;
        $infected = array_diff($infected, [$node]);
        foreach ($initialSet as $i) {
            if ($i != $node) {
                dfs($graph, $i, $infected);
            }
        }
        if (count($infected) < $minInfected) {
            $minInfected = count($infected);
            $bestNode = $node;
        }
    }
    
    return $bestNode;
}

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

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

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

Задача: 166. Fraction to Recurring Decimal
Сложность: medium

Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.
Если дробная часть повторяется, заключите повторяющуюся часть в скобки.
Если возможны несколько ответов, верните любой из них.
Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

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

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

3⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎 Решение:

class Solution {
    function fractionToDecimal($numerator, $denominator) {
        if ($numerator == 0) {
            return "0";
        }

        $fraction = "";
        if (($numerator < 0) xor ($denominator < 0)) {
            $fraction .= "-";
        }

        $dividend = abs($numerator);
        $divisor = abs($denominator);

        $fraction .= intval($dividend / $divisor);
        $remainder = $dividend % $divisor;
        if ($remainder == 0) {
            return $fraction;
        }

        $fraction .= ".";
        $lookup = [];
        while ($remainder != 0) {
            if (isset($lookup[$remainder])) {
                $pos = $lookup[$remainder];
                $fraction = substr($fraction, 0, $pos) . "(" . substr($fraction, $pos) . ")";
                break;
            }
            $lookup[$remainder] = strlen($fraction);
            $remainder *= 10;
            $fraction .= intval($remainder / $divisor);
            $remainder %= $divisor;
        }

        return $fraction;
    }
}

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

🔥 Скрытые вакансии с удаленной работой для PHP разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.

🔹 PHP Jobs | Вакансии

🔸 Все каналы с вакансиями

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

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