PHP | LeetCode

#medium Задача: 377. Combination Sum IV Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target. Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число. Пример:

Input: nums = [9], target = 3
Output: 0

👨‍💻 Алгоритм: 1⃣В этом подходе мы начнем со стратегии сверху вниз, которая, пожалуй, более интуитивна. Как следует из названия, стратегия сверху вниз начинается с исходных данных, и затем мы рекурсивно уменьшаем входные данные до меньшего масштаба, пока не достигнем уровней, которые больше невозможно разбить. 2⃣Из-за рекурсивной природы формулы мы можем напрямую перевести формулу в рекурсивную функцию. 3⃣Здесь, соответственно, мы определяем рекурсивную функцию под названием combs(remain), которая возвращает количество комбинаций, где каждая комбинация в сумме дает значение remain. 😎 Решение:

class Solution {
    private $memo = [];

    public function combinationSum4($nums, $target) {
        return $this->combs($nums, $target);
    }

    private function combs($nums, $remain) {
        if ($remain == 0) {
            return 1;
        }
        if (isset($this->memo[$remain])) {
            return $this->memo[$remain];
        }

        $result = 0;
        foreach ($nums as $num) {
            if ($remain - $num >= 0) {
                $result += $this->combs($nums, $remain - $num);
            }
        }
        $this->memo[$remain] = $result;
        return $result;
    }
}

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

#easy Задача: 463. Island Perimeter Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду. Клетки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и на ней находится ровно один остров (т.е. одна или более соединённых ячеек суши). У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова. Пример: Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image above. 👨‍💻 Алгоритм: 1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки. 2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши. 3⃣Когда вы находитесь в ячейке с значением 0 (ячейка воды), ничего не делать. Просто перейти к следующей ячейке. 😎 Решение:

class Solution {
    public function islandPerimeter($grid) {
        $rows = count($grid);
        $cols = count($grid[0]);
        
        $result = 0;
        
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] == 1) {
                    $up = ($r == 0) ? 0 : $grid[$r-1][$c];
                    $left = ($c == 0) ? 0 : $grid[$r][$c-1];
                    $down = ($r == $rows-1) ? 0 : $grid[$r+1][$c];
                    $right = ($c == $cols-1) ? 0 : $grid[$r][$c+1];
                    
                    $result += 4 - ($up + $left + $right + $down);
                }
            }
        }
        
        return $result;
    }
}

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

#easy Задача: 376. Wiggle Subsequence Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями. Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными. В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю. Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке. Дан целочисленный массив nums, верните длину самой длинной колеблющейся подпоследовательности из nums. Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

👨‍💻 Алгоритм: 1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием. 2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием. 3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания. 😎 Решение:

class Solution {
    public function islandPerimeter($grid) {
        $rows = count($grid);
        $cols = count($grid[0]);
        
        $result = 0;
        
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] == 1) {
                    $up = ($r == 0) ? 0 : $grid[$r-1][$c];
                    $left = ($c == 0) ? 0 : $grid[$r][$c-1];
                    $down = ($r == $rows-1) ? 0 : $grid[$r+1][$c];
                    $right = ($c == $cols-1) ? 0 : $grid[$r][$c+1];
                    
                    $result += 4 - ($up + $left + $right + $down);
                }
            }
        }
        
        return $result;
    }
}

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

#medium Задача: 334. Increasing Triplet Subsequence Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false. Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки. 2⃣Итерация по массиву: Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки: - если текущий элемент меньше или равен first_num, обновите first_num текущим элементом. - иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом. - иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true. 3⃣Возврат результата: Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false. 😎 Решение:

class Solution {
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function increasingTriplet($nums) {
        $firstNum = PHP_INT_MAX;
        $secondNum = PHP_INT_MAX;
        
        foreach ($nums as $n) {
            if ($n <= $firstNum) {
                $firstNum = $n;
            } elseif ($n <= $secondNum) {
                $secondNum = $n;
            } else {
                return true;
            }
        }
        return false;
    }
}

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

#Medium Задача: 477. Total Hamming Distance Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются. Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums. Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

👨‍💻 Алгоритм: 1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие. 2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой. 3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний. 😎 Решение:

class Solution {
    function totalHammingDistance($nums) {
        $ans = 0;

        if (empty($nums)) {
            return $ans;
        }

        for ($i = 0; $i < count($nums) - 1; $i++) {
            for ($j = $i + 1; $j < count($nums); $j++) {
                $ans += $this->countBits($nums[$i] ^ $nums[$j]);
            }
        }

        return $ans;
    }

    private function countBits($n) {
        $count = 0;
        while ($n > 0) {
            $count += $n & 1;
            $n >>= 1;
        }
        return $count;
    }
}

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

#easy Задача: 375. Guess Number Higher or Lower II Мы играем в угадайку. Правила игры следующие: Я загадываю число между 1 и n. Вы угадываете число. Если вы угадаете правильное число, вы выигрываете игру. Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать. Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру. Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю. Пример:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

👨‍💻 Алгоритм: 1️⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента. 2️⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость. 3️⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы. 😎 Решение:

class Solution {
    function calculate($low, $high) {
        if ($low >= $high)
            return 0;
        $minres = PHP_INT_MAX;
        for ($i = $low; $i <= $high; $i++) {
            $res = $i + max($this->calculate($i + 1, $high), $this->calculate($low, $i - 1));
            $minres = min($res, $minres);
        }
        return $minres;
    }

    function getMoneyAmount($n) {
        return $this->calculate(1, $n);
    }
}

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

#easy Задача: 374. Guess Number Higher or Lower Мы играем в игру "Угадай число". Правила игры следующие: Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал. Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения. Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов: -1: Ваше предположение больше загаданного числа (т.е. num > pick). 1: Ваше предположение меньше загаданного числа (т.е. num < pick). 0: Ваше предположение равно загаданному числу (т.е. num == pick). Верните загаданное число. Пример:

Input: n = 10, pick = 6
Output: 6

👨‍💻 Алгоритм: 1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess. 2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного. 3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного. 😎 Решение:

class Solution extends GuessGame {
    function guessNumber($n) {
        $low = 1;
        $high = $n;
        while ($low <= $high) {
            $mid = $low + intdiv($high - $low, 2);
            $res = guess($mid);
            if ($res == 0)
                return $mid;
            else if ($res < 0)
                $high = $mid - 1;
            else
                $low = $mid + 1;
        }
        return -1;
    }
}

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

#easy Задача: 234. Palindrome Linked List Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае. Пример:

Input: head = [1,2,2,1]
Output: true

👨‍💻 Алгоритм: 1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null. 2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся. 3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата. 😎 Решение:

class Solution {
    function isPalindrome($head) {
        $vals = [];
        $currentNode = $head;

        while ($currentNode !== null) {
            $vals[] = $currentNode->val;
            $currentNode = $currentNode->next;
        }

        $front = 0;
        $back = count($vals) - 1;
        while ($front < $back) {
            if ($vals[$front] != $vals[$back]) {
                return false;
            }
            $front++;
            $back--;
        }
        return true;
    }
}

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

#medium Задача: 462. Minimum Moves to Equal Array Elements II Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными. В одном ходе вы можете увеличить или уменьшить элемент массива на 1. Тестовые случаи составлены так, что ответ поместится в 32-битное целое число. Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

👨‍💻 Алгоритм: 1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива. 2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k. 3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом. 😎 Решение:

class Solution {
    public function minMoves2($nums) {
        $ans = PHP_INT_MAX;
        $minval = min($nums);
        $maxval = max($nums);
        for ($i = $minval; $i <= $maxval; $i++) {
            $sum = 0;
            foreach ($nums as $num) {
                $sum += abs($num - $i);
            }
            $ans = min($ans, $sum);
        }
        return (int) $ans;
    }
}

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

#medium Задача: 333. Largest BST Subtree Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов. Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства: Значения в левом поддереве меньше значения их родительского (корневого) узла. Значения в правом поддереве больше значения их родительского (корневого) узла. Примечание: Поддерево должно включать всех своих потомков. Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

👨‍💻 Алгоритм: 1⃣Пост-упорядоченный обход дерева: Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды. 2⃣Проверка условий BST для каждой ноды: Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST: - значение текущей ноды должно быть больше максимального значения в левом поддереве. - значение текущей ноды должно быть меньше минимального значения в правом поддереве. Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды). 3⃣Возврат максимального размера BST: Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева. В конце рекурсивного обхода верните максимальный размер BST в дереве. 😎 Решение:

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 NodeValue {
    public $minNode;
    public $maxNode;
    public $maxSize;
    
    function __construct($minNode, $maxNode, $maxSize) {
        $this->minNode = $minNode;
        $this->maxNode = $maxNode;
        $this->maxSize = $maxSize;
    }
}

class Solution {
    private function largestBSTSubtreeHelper($root) {
        if ($root === null) {
            return new NodeValue(PHP_INT_MAX, PHP_INT_MIN, 0);
        }
        
        $left = $this->largestBSTSubtreeHelper($root->left);
        $right = $this->largestBSTSubtreeHelper($root->right);
        
        if ($left->maxNode < $root->val && $root->val < $right->minNode) {
            return new NodeValue(min($root->val, $left->minNode), max($root->val, $right->maxNode), 
                                 $left->maxSize + $right->maxSize + 1);
        }
        
        return new NodeValue(PHP_INT_MIN, PHP_INT_MAX, max($left->maxSize, $right->maxSize));
    }
    
    function largestBSTSubtree($root) {
        return $this->largestBSTSubtreeHelper($root)->maxSize;
    }
}

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

#medium Задача: 373. Find K Pairs with Smallest Sums Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k. Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива. Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами. Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

👨‍💻 Алгоритм: 1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар. 2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited. 3⃣Повторяйте до получения k пар и пока minHeap не пуст: Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2]. Добавьте пару (nums1[i], nums2[j]) в ans. Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap. Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap. Верните ans. 😎 Решение:

class Solution {
    function kSmallestPairs($nums1, $nums2, $k) {
        $m = count($nums1);
        $n = count($nums2);
        $ans = [];
        $visited = [];
        $minHeap = new SplPriorityQueue();
        $minHeap->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
        $minHeap->insert([0, 0], -($nums1[0] + $nums2[0]));
        $visited["0,0"] = true;

        while ($k > 0 && !$minHeap->isEmpty()) {
            $top = $minHeap->extract();
            list($i, $j) = $top['data'];
            $ans[] = [$nums1[$i], $nums2[$j]];

            if ($i + 1 < $m && !isset($visited[($i + 1) . ",$j"])) {
                $minHeap->insert([$i + 1, $j], -($nums1[$i + 1] + $nums2[$j]));
                $visited[($i + 1) . ",$j"] = true;
            }

            if ($j + 1 < $n && !isset($visited["$i," . ($j + 1)])) {
                $minHeap->insert([$i, $j + 1], -($nums1[$i] + $nums2[$j + 1]));
                $visited["$i," . ($j + 1)] = true;
            }
            $k--;
        }

        return $ans;
    }
}

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

#hard Задача: 332. Reconstruct Itinerary Вам дан список авиабилетов, где tickets[i] = [fromi, toi] представляют собой аэропорты отправления и прибытия одного рейса. Восстановите маршрут в порядке следования и верните его. Все билеты принадлежат человеку, который вылетает из "JFK", поэтому маршрут должен начинаться с "JFK". Если существует несколько возможных маршрутов, вы должны вернуть маршрут, который имеет наименьший лексикографический порядок при чтении как одна строка. Например, маршрут ["JFK", "LGA"] имеет меньший лексикографический порядок, чем ["JFK", "LGB"]. Вы можете предположить, что все билеты формируют хотя бы один действительный маршрут. Вы должны использовать все билеты один раз и только один раз. Пример:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

👨‍💻 Алгоритм: 1⃣Построение графа и сортировка: Создайте граф flightMap, где ключи - это аэропорты отправления, а значения - это списки аэропортов прибытия. Пройдите по всем билетам и заполните flightMap соответствующими значениями. Отсортируйте списки аэропортов прибытия в лексикографическом порядке. 2⃣Пост-упорядоченный обход (DFS): Создайте функцию DFS, которая будет рекурсивно проходить по всем ребрам (рейсам), начиная с аэропорта "JFK". Во время обхода удаляйте использованные рейсы из графа, чтобы не проходить по ним повторно. 3⃣Формирование маршрута: По мере завершения обхода добавляйте текущий аэропорт в начало списка результата. После завершения DFS верните сформированный маршрут. 😎 Решение:

class Solution {
    private $flightMap = [];
    private $result = [];

    function findItinerary($tickets) {
        foreach ($tickets as $ticket) {
            $this->flightMap[$ticket[0]][] = $ticket[1];
        }

        foreach ($this->flightMap as &$destList) {
            sort($destList);
        }

        $this->dfs("JFK");
        return $this->result;
    }

    function dfs($origin) {
        while (isset($this->flightMap[$origin]) && count($this->flightMap[$origin]) > 0) {
            $nextDest = array_shift($this->flightMap[$origin]);
            $this->dfs($nextDest);
        }
        array_unshift($this->result, $origin);
    }
}

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

#easy Задача: 461. Hamming Distance Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны. Даны два целых числа x и y, верните расстояние Хэмминга между ними. Пример:

Input: x = 3, y = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед. 2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов. 3⃣Пошаговый подсчет битов: Выполните побитовое XOR между x и y. Инициализируйте счетчик bitCount = 0. Пока число не равно нулю: Если текущий бит равен 1, увеличьте bitCount. Сдвиньте число вправо на один бит. Возвращайте bitCount. 😎 Решение:

class Solution {
    public function hammingDistance($x, $y) {
        return substr_count(decbin($x ^ $y), '1');
    }
}

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

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

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

👨‍💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:

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

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

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

#medium Задача: 371. Sum of Two Integers Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -. Пример:

Input: a = 1, b = 2
Output: 3

👨‍💻 Алгоритм: 1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата. 2⃣Если нужно вычислить сумму: Пока перенос не равен нулю (y != 0): Текущий ответ без переноса равен XOR x и y: answer = x ^ y. Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = carry. Верните x * sign. 3⃣Если нужно вычислить разность: Пока заимствование не равно нулю (y != 0): Текущий ответ без заимствования равен XOR x и y: answer = x ^ y. Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = borrow. Верните x * sign. 😎 Решение:

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

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

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

GitHub теперь в Telegram! Более 7000+ репозиториев с исходным кодом нейросетей, ботов, сайтов и других интересных проектов для разработчиков: Всё разбито по #хештегам. Подписывайтесь: @GitHub

#medium Задача: 370. Range Addition Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci]. У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci. Верните arr после применения всех обновлений. Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

👨‍💻 Алгоритм: 1⃣Для каждого обновления (start, end, val) выполните две операции: Увеличьте значение в позиции start на val: arr[start] = arr[start] + val. Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val. 2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0). 3⃣Верните обновленный массив arr. 😎 Решение:

function getModifiedArray($length, $updates) {
    $result = array_fill(0, $length, 0);

    foreach ($updates as $update) {
        list($start, $end, $val) = $update;
        $result[$start] += $val;
        if ($end + 1 < $length) {
            $result[$end + 1] -= $val;
        }
    }

    for ($i = 1; $i < $length; $i++) {
        $result[$i] += $result[$i - 1];
    }

    return $result;
}

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

#hard Задача: 460. LFU Cache Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU). Реализуйте класс LFUCache: LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных. int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1. void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ. Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом. Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа. Функции get и put должны иметь среднюю временную сложность O(1). Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

👨‍💻 Алгоритм: 1⃣insert(int key, int frequency, int value): Вставить пару частота-значение в cache с заданным ключом. Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ. 2⃣int get(int key): Если ключа нет в кеше, вернуть -1. Получить частоту и значение из кеша. Удалить ключ из LinkedHashSet, связанного с частотой. Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies. Вызвать insert(key, frequency + 1, value). Вернуть значение. 3⃣void put(int key, int value): Если capacity <= 0, выйти. Если ключ существует, обновить значение и вызвать get(key). Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша. Установить minf в 1. Вызвать insert(key, 1, value). 😎 Решение:

class LFUCache {
    private $frequencies;
    private $cache;
    private $capacity;
    private $minf;

    function __construct($capacity) {
        $this->capacity = $capacity;
        $this->minf = 0;
        $this->frequencies = [];
        $this->cache = [];
    }

    private function insert($key, $frequency, $value) {
        if (!isset($this->frequencies[$frequency])) {
            $this->frequencies[$frequency] = [];
        }
        $this->frequencies[$frequency][$key] = $value;
        $this->cache[$key] = [$frequency, $value];
    }

    function get($key) {
        if (!isset($this->cache[$key])) return -1;
        [$frequency, $value] = $this->cache[$key];
        unset($this->frequencies[$frequency][$key]);
        if (empty($this->frequencies[$frequency])) {
            unset($this->frequencies[$frequency]);
            if ($this->minf == $frequency) $this->minf++;
        }
        $this->insert($key, $frequency + 1, $value);
        return $value;
    }

    function put($key, $value) {
        if ($this->capacity <= 0) return;
        if (isset($this->cache[$key])) {
            $this->cache[$key][1] = $value;
            $this->get($key);
            return;
        }
        if (count($this->cache) == $this->capacity) {
            $oldest = array_key_first($this->frequencies[$this->minf]);
            unset($this->cache[$oldest]);
            unset($this->frequencies[$this->minf][$oldest]);
            if (empty($this->frequencies[$this->minf])) unset($this->frequencies[$this->minf]);
        }
        $this->minf = 1;
        $this->insert($key, 1, $value);
    }
}

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

Все надоело и пропал интерес, чувствуешь себя амебой и хочется только залипать в телефоне. Бывает? Психолог взрослого человека - канал для айтишников, у которых периодически опускаются руки и отключается мозг, ибо переработки и постоянная тревожность не приводят к другим исходам. ✔️ Как научиться отвлекаться от работы и отдыхать? ✔️ Как совместить кучу рабочих задач и время с семьей? ✔️ Как справиться с прокрастинацией? ✔️ Как не растерять запал, даже если начальник и коллеги 💩 и кажется, что ничего не выходит? Подписывайтесь на канал @vadimpetrov_psy и научитесь работать без упахивания, выгорания и ущерба для личной жизни! 👨🏻‍💻 Псс. Заходите в закреп канала - там много полезного. https://t.me/+Bz2LiDjD8_s3ZTNi

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

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

👨‍💻 Алгоритм: 1⃣Инициализация и разбор строки: Инициализируйте переменную slots значением 1, представляющую количество доступных слотов. Разделите строку по запятым, чтобы получить массив элементов. 2⃣Итерация по элементам и проверка: Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1. Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию. Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота. 3⃣Проверка завершения: После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false. 😎 Решение:

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

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