#easy
Задача: 476. Number Complement

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.

Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

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

1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1.

3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask.

😎 Решение:

class Solution {
    function findComplement($num) {
        $bitmask = $num;
        $bitmask |= ($bitmask >> 1);
        $bitmask |= ($bitmask >> 2);
        $bitmask |= ($bitmask >> 4);
        $bitmask |= ($bitmask >> 8);
        $bitmask |= ($bitmask >> 16);
        return $bitmask ^ $num;
    }
}

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

#hard
Задача: 233. Number of Digit One

Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

function countDigitOne($n) {
    $countr = 0;
    for ($i = 1; $i <= $n; $i *= 10) {
        $divider = $i * 10;
        $countr += intval($n / $divider) * $i + min(max($n % $divider - $i + 1, 0), $i);
    }
    return $countr;
}

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

#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;
    }
}

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

#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);
    }
}

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

#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;
}

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

#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;
    }
}

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

#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;
    }
}

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

#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');
    }
}

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

#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);
    }
}

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

#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;
    }
}

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

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

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

#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;
    }
}

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

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

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

#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;
    }
}

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

#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;
    }
}

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

#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;
    }
}

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

#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;
    }
}

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

#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;
    }
}

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