PHP | LeetCode

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

    return $result;
}

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

Задача: 599. Minimum Index Sum of Two Lists
Сложность: Easy

Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов.
Общая строка - это строка, которая появляется и в list1, и в list2.
Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк.
Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке.

Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

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

1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме.

2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j.

3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой.

😎 Решение:

class Solution {
    function findRestaurant($list1, $list2) {
        $map = [];
        for ($i = 0; $i < count($list1); $i++) {
            for ($j = 0; $j < count($list2); $j++) {
                if ($list1[$i] == $list2[$j]) {
                    if (!isset($map[$i + $j])) {
                        $map[$i + $j] = [];
                    }
                    $map[$i + $j][] = $list1[$i];
                }
            }
        }
        $minIndexSum = min(array_keys($map));
        return $map[$minIndexSum];
    }
}

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

Задача: 65. Valid Number
Сложность: hard

Учитывая строку s, определите, является ли s валидным числом.
Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".
Формально, валидное число определяется с использованием одного из следующих определений:
Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.
Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:
Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.
Цифры определяются как одна или более цифр.

Пример:

Input: s = "0"

Output: true

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

1⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true.

2⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число.

3⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры.

😎 Решение:

function isNumber($s) {
    $seenDigit = false;
    $seenExponent = false;
    $seenDot = false;
    for ($i = 0; $i < strlen($s); $i++) {
        $curr = $s[$i];
        if (is_numeric($curr)) {
            $seenDigit = true;
        } elseif ($curr === "+" || $curr === "-") {
            if ($i > 0 && $s[$i - 1] !== "e" && $s[$i - 1] !== "E") {
                return false;
            }
        } elseif ($curr === "e" || $curr === "E") {
            if ($seenExponent || !$seenDigit) {
                return false;
            }
            $seenExponent = true;
            $seenDigit = false; // Reset seenDigit after an exponent
        } elseif ($curr === ".") {
            if ($seenDot || $seenExponent) {
                return false;
            }
            $seenDot = true;
        } else {
            return false;
        }
    }
    return $seenDigit;
}

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

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

😎 Решение:

class Solution {
    function minCostToMoveChips($position) {
        $evenCount = 0;
        $oddCount = 0;
        
        foreach ($position as $pos) {
            if ($pos % 2 == 0) {
                $evenCount++;
            } else {
                $oddCount++;
            }
        }
        
        return min($evenCount, $oddCount);
    }
}

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

Задача: 1143. Longest Common Subsequence
Сложность: medium

Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.

Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.
Например, "ace" является подпоследовательностью "abcde".
Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк.

Пример:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

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

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

2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями.

3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.

😎 Решение:

class Solution {
    private $memo = [];
    private $text1;
    private $text2;
    
    function longestCommonSubsequence($text1, $text2) {
        $this->text1 = $text1;
        $this->text2 = $text2;
        $len1 = strlen($text1);
        $len2 = strlen($text2);
        $this->memo = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, -1));
        return $this->memoSolve(0, 0);
    }
    
    private function memoSolve($p1, $p2) {
        if ($p1 == strlen($this->text1) || $p2 == strlen($this->text2)) return 0;
        if ($this->memo[$p1][$p2] != -1) return $this->memo[$p1][$p2];
        if ($this->text1[$p1] == $this->text2[$p2]) {
            $this->memo[$p1][$p2] = 1 + $this->memoSolve($p1 + 1, $p2 + 1);
        } else {
            $this->memo[$p1][$p2] = max($this->memoSolve($p1, $p2 + 1), $this->memoSolve($p1 + 1, $p2));
        }
        return $this->memo[$p1][$p2];
    }
}

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

Задача: 661. Image Smoother
Сложность: easy

Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.

Пример:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

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

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

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

3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.

😎 Решение:

class Solution {
    function imageSmoother($img) {
        $m = count($img);
        $n = count($img[0]);
        $result = array_fill(0, $m, array_fill(0, $n, 0));
        
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $count = 0;
                $total = 0;
                for ($ni = max(0, $i - 1); $ni <= min($m - 1, $i + 1); $ni++) {
                    for ($nj = max(0, $j - 1); $nj <= min($n - 1, $j + 1); $nj++) {
                        $total += $img[$ni][$nj];
                        $count++;
                    }
                }
                $result[$i][$j] = floor($total / $count);
            }
        }
        
        return $result;
    }
}

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

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

😎 Решение:

class Solution {
    function shiftAndCount($xShift, $yShift, $M, $R) {
        $leftShiftCount = 0;
        $rightShiftCount = 0;
        $rRow = 0;
        for ($mRow = $yShift; $mRow < count($M); ++$mRow) {
            $rCol = 0;
            for ($mCol = $xShift; $mCol < count($M); ++$mCol) {
                if ($M[$mRow][$mCol] == 1 && $M[$mRow][$mCol] == $R[$rRow][$rCol]) {
                    $leftShiftCount++;
                }
                if ($M[$mRow][$rCol] == 1 && $M[$mRow][$rCol] == $R[$rRow][$mCol]) {
                    $rightShiftCount++;
                }
                $rCol++;
            }
            $rRow++;
        }
        return max($leftShiftCount, $rightShiftCount);
    }

    function largestOverlap($A, $B) {
        $maxOverlaps = 0;
        for ($yShift = 0; $yShift < count($A); ++$yShift) {
            for ($xShift = 0; $xShift < count($A); ++$xShift) {
                $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $A, $B));
                $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $B, $A));
            }
        }
        return $maxOverlaps;
    }
}

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

Задача №26. Remove Duplicates from Sorted Array
Сложность: easy

Учитывая целочисленный массив nums, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов.

Пример:

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

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

1⃣Использовать два указателя: index для записи уникальных элементов и i для перебора массива.

2⃣Если текущий элемент отличается от предыдущего, записать его на index-позицию.

3⃣Вернуть index как количество уникальных элементов.

😎 Решение:

class Solution {
    function removeDuplicates(&$nums) { 
        $index = 1;
        for ($i = 1; $i < count($nums); $i++) {
            if ($nums[$i] !== $nums[$i - 1]) { 
                $nums[$index++] = $nums[$i];
            }  
        }  
        return $index;
    }
}

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

Задача: 284. Peeking Iterator
Сложность: medium

Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).
Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.

Пример:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

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

1⃣Инициализация итератора:
В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null.

2⃣Операция peek:
Метод peek возвращает значение next, не перемещая указатель итератора.

3⃣Операции next и hasNext:
Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException.
Метод hasNext возвращает true, если next не равно null, и false в противном случае.

😎 Решение:

class PeekingIterator {
    private $iterator;
    private $nextElement;

    public function __construct(Iterator $iterator) {
        $this->iterator = $iterator;
        $this->nextElement = $iterator->valid() ? $iterator->current() : null;
    }

    public function next() {
        $currentElement = $this->nextElement;
        $this->iterator->next();
        $this->nextElement = $this->iterator->valid() ? $this->iterator->current() : null;
        return $currentElement;
    }

    public function hasNext() {
        return $this->nextElement !== null;
    }

    public function peek() {
        return $this->nextElement;
    }
}

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

Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:

Input: s = "bccb"
Output: 6

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

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

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:

function countPalindromicSubsequences($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n, array_fill(0, $n, 0));

    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = 1;
    }

    for ($length = 2; $length <= $n; $length++) {
        for ($i = 0; $i <= $n - $length; $i++) {
            $j = $i + $length - 1;
            if ($s[$i] == $s[$j]) {
                $l = $i + 1;
                $r = $j - 1;
                while ($l <= $r && $s[$l] != $s[$i]) $l++;
                while ($l <= $r && $s[$r] != $s[$j]) $r--;
                if ($l > $r) {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 + 2;
                } else if ($l == $r) {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 + 1;
                } else {
                    $dp[$i][$j] = $dp[$i + 1][$j - 1] * 2 - $dp[$l + 1][$r - 1];
                }
            } else {
                $dp[$i][$j] = $dp[$i + 1][$j] + $dp[$i][$j - 1] - $dp[$i + 1][$j - 1];
            }
            $dp[$i][$j] = ($dp[$i][$j] + $MOD) % $MOD;
        }
    }

    return $dp[0][$n - 1];
}

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

Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium

Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.

Пример:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

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

1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.

2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.

3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.

😎 Решение:

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 {
    private $index = 0;

    function bstFromPreorder($preorder) {
        return $this->constructBST($preorder, PHP_INT_MIN, PHP_INT_MAX);
    }

    private function constructBST($preorder, $lower, $upper) {
        if ($this->index == count($preorder)) {
            return null;
        }

        $val = $preorder[$this->index];
        if ($val < $lower || $val > $upper) {
            return null;
        }

        $this->index++;
        $root = new TreeNode($val);
        $root->left = $this->constructBST($preorder, $lower, $val);
        $root->right = $this->constructBST($preorder, $val, $upper);
        return $root;
    }
}

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

Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium

Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.

Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false

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

1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.

2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.

3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.

😎 Решение:

function leadsToDestination($n, $edges, $source, $destination) {
    $graph = [];
    foreach ($edges as $edge) {
        $graph[$edge[0]][] = $edge[1];
    }
    
    $visited = array_fill(0, $n, 0);
    
    function dfs($node, $graph, &$visited, $destination) {
        if ($visited[$node] != 0) return $visited[$node] == 2;
        if (!isset($graph[$node])) return $node == $destination;
        $visited[$node] = 1;
        foreach ($graph[$node] as $neighbor) {
            if (!dfs($neighbor, $graph, $visited, $destination)) return false;
        }
        $visited[$node] = 2;
        return true;
    }
    
    return dfs($source, $graph, $visited, $destination);
}

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

Задача: 690. Employee Importance
Сложность: medium

У вас есть структура данных с информацией о сотрудниках, включая уникальный идентификатор сотрудника, значение его важности и идентификаторы его прямых подчиненных.

Вам дан массив сотрудников employees, где:

employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.

Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

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

1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.

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

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

😎 Решение:

class Employee {
    public $id;
    public $importance;
    public $subordinates;
    
    function __construct($id, $importance, $subordinates) {
        $this->id = $id;
        $this->importance = $importance;
        $this->subordinates = $subordinates;
    }
}

class Solution {
    private $emap;
    
    function getImportance($employees, $queryid) {
        $this->emap = [];
        foreach ($employees as $e) {
            $this->emap[$e->id] = $e;
        }
        return $this->dfs($queryid);
    }
    
    private function dfs($eid) {
        $employee = $this->emap[$eid];
        $ans = $employee->importance;
        foreach ($employee->subordinates as $subid) {
            $ans += $this->dfs($subid);
        }
        return $ans;
    }
}

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

Задача: 850. Rectangle Area II
Сложность: hard

Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.

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

Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.

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

1⃣Переназначьте каждую x координату на 0, 1, 2, .... Аналогично, переназначьте все y координаты.

2⃣Теперь мы имеем задачу, которую можно решить методом грубой силы: для каждого прямоугольника с переназначенными координатами (rx1, ry1, rx2, ry2) заполним сетку grid[x][y] = True для rx1 <= x < rx2 и ry1 <= y < ry2.

3⃣Затем каждая ячейка grid[rx][ry] будет представлять площадь (imapx(rx+1) - imapx(rx)) * (imapy(ry+1) - imapy(ry)), где если x был переназначен на rx, то imapx(rx) = x ("обратная карта x для переназначенного x равна x"), аналогично для imapy.

😎 Решение:

class Solution {
    function rectangleArea($rectangles) {
        $N = count($rectangles);
        $Xvals = [];
        $Yvals = [];

        foreach ($rectangles as $rec) {
            $Xvals[$rec[0]] = true;
            $Xvals[$rec[2]] = true;
            $Yvals[$rec[1]] = true;
            $Yvals[$rec[3]] = true;
        }

        $imapx = array_keys($Xvals);
        sort($imapx);
        $imapy = array_keys($Yvals);
        sort($imapy);

        $mapx = [];
        $mapy = [];
        foreach ($imapx as $i => $v) {
            $mapx[$v] = $i;
        }
        foreach ($imapy as $i => $v) {
            $mapy[$v] = $i;
        }

        $grid = array_fill(0, count($imapx), array_fill(0, count($imapy), false));
        foreach ($rectangles as $rec) {
            for ($x = $mapx[$rec[0]]; $x < $mapx[$rec[2]]; $x++) {
                for ($y = $mapy[$rec[1]]; $y < $mapy[$rec[3]]; $y++) {
                    $grid[$x][$y] = true;
                }
            }
        }

        $ans = 0;
        for ($x = 0; $x < count($grid); $x++) {
            for ($y = 0; $y < count($grid[0]); $y++) {
                if ($grid[$x][$y]) {
                    $ans += ($imapx[$x + 1] - $imapx[$x]) * ($imapy[$y + 1] - $imapy[$y]);
                }
            }
        }

        $ans %= 1_000_000_007;
        return (int)$ans;
    }
}

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

Задача: 1168. Optimize Water Distribution in a Village
Сложность: hard

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

Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами.

Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой.

Пример:

Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

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

1⃣Представление графа: Постройте список смежности для представления графа, где вершины и ребра соответствуют домам и трубам. Список смежности можно представить в виде списка списков или словаря списков.

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

3⃣Очередь с приоритетом (куча): Используйте кучу для реализации жадной стратегии. На каждом шаге определяйте лучшее ребро для добавления на основе стоимости его добавления в дерево. Куча позволяет извлекать минимальный элемент за константное время и удалять минимальный элемент за логарифмическое время. Это идеально подходит для нашей задачи повторного нахождения ребра с наименьшей стоимостью.

😎 Решение:

class Solution {
    function minCostToSupplyWater($n, $wells, $pipes) {
        $graph = array_fill(0, $n + 1, []);
        $minHeap = new SplPriorityQueue();
        $minHeap->setExtractFlags(SplPriorityQueue::EXTR_DATA);
        
        foreach ($wells as $i => $cost) {
            $graph[0][] = [$cost, $i + 1];
            $minHeap->insert([$cost, $i + 1], -$cost);
        }
        
        foreach ($pipes as $pipe) {
            [$house1, $house2, $cost] = $pipe;
            $graph[$house1][] = [$cost, $house2];
            $graph[$house2][] = [$cost, $house1];
        }
        
        $mstSet = [0 => true];
        $totalCost = 0;
        
        while (count($mstSet) < $n + 1) {
            $edge = $minHeap->extract();
            [$cost, $nextHouse] = $edge;
            if (isset($mstSet[$nextHouse])) continue;
            $mstSet[$nextHouse] = true;
            $totalCost += $cost;
            foreach ($graph[$nextHouse] as $neighborEdge) {
                if (!isset($mstSet[$neighborEdge[1]])) {
                    $minHeap->insert($neighborEdge, -$neighborEdge[0]);
                }
            }
        }
        
        return $totalCost;
    }
}

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

Задача: 206. Reverse Linked List
Сложность: easy

Дан односвязный список, разверните этот список и верните развернутый список.

Пример:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

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

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

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

3⃣После завершения цикла верните prev как новую голову развернутого списка.

😎 Решение:

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

class Solution {
    function reverseList($head) {
        $prev = null;
        $curr = $head;
        while ($curr !== null) {
            $nextTemp = $curr->next;
            $curr->next = $prev;
            $prev = $curr;
            $curr = $nextTemp;
        }
        return $prev;
    }
}

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

Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy

Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.

Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.

Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

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

1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.

2⃣Итерация по word1 и проверка соответствующих символов:
Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2.

3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.

😎 Решение:

class Solution {
    function arrayStringsAreEqual($word1, $word2) {
        $list2 = implode('', $word2);
        $index = 0;
        $n = strlen($list2);

        foreach ($word1 as $word) {
            for ($i = 0; $i < strlen($word); $i++) {
                if ($index >= $n || $word[$i] != $list2[$index]) {
                    return false;
                }
                $index++;
            }
        }

        return $index == $n;
    }
}

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