#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 {
public:
    int findComplement(int num) {
        int 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.

😎 Решение:

int countDigitOne(int n) {
    int countr = 0;
    for (long long i = 1; i <= n; i *= 10) {
        long long divider = i * 10;
        countr += (n / divider) * i + std::min(std::max(n % divider - i + 1, 0LL), 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 {
public:
    bool isValidSerialization(string preorder) {
        int slots = 1;
        stringstream ss(preorder);
        string node;
        
        while (getline(ss, node, ',')) {
            slots -= 1;
            if (slots < 0) {
                return false;
            }
            if (node != "#") {
                slots += 2;
            }
        }
        
        return slots == 0;
    }
};

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

#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 {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;

        ListNode* currentNode = head;
        while (currentNode != nullptr) {
            vals.push_back(currentNode->val);
            currentNode = currentNode->next;
        }

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

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

#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).

😎 Решение:

#include <unordered_map>
#include <list>

class LFUCache {
    std::unordered_map<int, std::list<std::pair<int, int>>> frequencies;
    std::unordered_map<int, std::pair<int, std::list<std::pair<int, int>>::iterator>> cache;
    int capacity;
    int minf;

    void insert(int key, int frequency, int value) {
        frequencies[frequency].emplace_back(key, value);
        cache[key] = {frequency, --frequencies[frequency].end()};
    }

public:
    LFUCache(int capacity) : capacity(capacity), minf(0) {}

    int get(int key) {
        const auto it = cache.find(key);
        if (it == cache.end()) return -1;
        const int f = it->second.first;
        const auto iter = it->second.second;
        const std::pair<int, int> kv = *iter;
        frequencies[f].erase(iter);
        if (frequencies[f].empty()) {
            frequencies.erase(f);
            if (minf == f) ++minf;
        }
        insert(key, f + 1, kv.second);
        return kv.second;
    }

    void put(int key, int value) {
        if (capacity <= 0) return;
        const auto it = cache.find(key);
        if (it != cache.end()) {
            it->second.second->second = value;
            get(key);
            return;
        }
        if (capacity == cache.size()) {
            cache.erase(frequencies[minf].front().first);
            frequencies[minf].pop_front();
            if (frequencies[minf].empty()) frequencies.erase(minf);
        }
        minf = 1;
        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.

😎 Решение:

vector<int> getModifiedArray(int length, vector<vector<int> > updates)
{
    vector<int> result(length, 0);

    for (auto& tuple : updates) {
        int start = tuple[0], end = tuple[1], val = tuple[2];

        for (int i = start; i <= end; i++) {
            result[i] += val;
        }
    }

    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 {
public:
    int getSum(int a, int b) {
        unsigned x = abs(a), y = abs(b);
        if (x < y) return getSum(b, a);
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y) {
                unsigned carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y) {
                unsigned 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 {
public:
    int superPow(int a, vector<int>& b) {
        const int MOD = 1337;

        auto powmod = [](int x, int y, int mod) -> int {
            int result = 1;
            x = x % mod;
            while (y > 0) {
                if (y % 2 == 1) {
                    result = (result * x) % mod;
                }
                y = y / 2;
                x = (x * x) % mod;
            }
            return result;
        };

        function<int(int, vector<int>&, int)> superPowHelper = [&](int a, vector<int>& b, int mod) -> int {
            if (b.empty()) {
                return 1;
            }
            int last_digit = b.back();
            b.pop_back();
            int part1 = powmod(a, last_digit, mod);
            int part2 = powmod(superPowHelper(a, b, mod), 10, mod);
            return (part1 * part2) % mod;
        };

        return superPowHelper(a, b, MOD);
    }
};

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

#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:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

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

#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 {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();

        vector<vector<int>> ans;
        set<pair<int, int>> visited;

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
                       greater<pair<int, pair<int, int>>>> minHeap;
        minHeap.push({nums1[0] + nums2[0], {0, 0}});
        visited.insert({0, 0});

        while (k-- && !minHeap.empty()) {
            auto top = minHeap.top();
            minHeap.pop();
            int i = top.second.first;
            int j = top.second.second;

            ans.push_back({nums1[i], nums2[j]});

            if (i + 1 < m && visited.find({i + 1, j}) == visited.end()) {
                minHeap.push({nums1[i + 1] + nums2[j], {i + 1, j}});
                visited.insert({i + 1, j});
            }

            if (j + 1 < n && visited.find({i, j + 1}) == visited.end()) {
                minHeap.push({nums1[i] + nums2[j + 1], {i, j + 1}});
                visited.insert({i, j + 1});
            }
        }

        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 {
public:
    unordered_map<string, priority_queue<string, vector<string>, greater<string>>> flightMap;
    deque<string> result;

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& ticket : tickets) {
            flightMap[ticket[0]].push(ticket[1]);
        }

        dfs("JFK");
        return vector<string>(result.begin(), result.end());
    }

    void dfs(const string& origin) {
        auto& destList = flightMap[origin];
        while (!destList.empty()) {
            string nextDest = destList.top();
            destList.pop();
            dfs(nextDest);
        }
        result.push_front(origin);
    }
};

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

#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:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class NodeValue {
public:
    int minNode, maxNode, maxSize;
    
    NodeValue(int minNode, int maxNode, int maxSize) : 
        minNode(minNode), maxNode(maxNode), maxSize(maxSize) {}
};

class Solution {
public:
    NodeValue largestBSTSubtreeHelper(TreeNode* root) {
        if (root == nullptr) {
            return NodeValue(INT_MAX, INT_MIN, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root->left);
        NodeValue right = largestBSTSubtreeHelper(root->right);
        
        if (left.maxNode < root->val && root->val < right.minNode) {
            return NodeValue(min(root->val, left.minNode), max(root->val, right.maxNode), 
                             left.maxSize + right.maxSize + 1);
        }
        
        return NodeValue(INT_MIN, INT_MAX, max(left.maxSize, right.maxSize));
    }
    
    int largestBSTSubtree(TreeNode* root) {
        return 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:
    int minMoves2(vector<int>& nums) {
        long ans = LONG_MAX;
        int minval = INT_MAX;
        int maxval = INT_MIN;
        for (int num : nums) {
            minval = min(minval, num);
            maxval = max(maxval, num);
        }
        for (int i = minval; i <= maxval; i++) {
            long sum = 0;
            for (int num : nums) {
                sum += abs(num - i);
            }
            ans = min(ans, sum);
        }
        return (int) ans;
    }
};

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

#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 : public GuessGame {
public:
    int guessNumber(int n) {
        int low = 1, high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
};

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

#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⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

int totalHammingDistance(vector<int>& nums)
{
    int ans = 0;

    if (nums.empty())
        return ans;

    for (int i = 0; i < nums.size() - 1; i++)
        for (int j = i + 1; j < nums.size(); j++)
            ans += __builtin_popcount(nums[i] ^ nums[j]);

    return ans;
}

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

#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 {
public:
    int calculate(int low, int high) {
        if (low >= high)
            return 0;
        int minres = INT_MAX;
        for (int i = low; i <= high; i++) {
            int res = i + max(calculate(i + 1, high), calculate(low, i - 1));
            minres = min(res, minres);
        }
        return minres;
    }

    int getMoneyAmount(int n) {
        return calculate(1, n);
    }
};

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

#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 {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first_num = INT_MAX;
        int second_num = INT_MAX;
        
        for (int n : nums) {
            if (n <= first_num) {
                first_num = n;
            } else if (n <= second_num) {
                second_num = n;
            } else {
                return true;
            }
        }
        return false;
    }
};

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

#medium
Задача: 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:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2)
            return nums.size();
        vector<int> up(nums.size(), 0);
        vector<int> down(nums.size(), 0);
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = max(up[i], down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = max(down[i], up[j] + 1);
                }
            }
        }
        return 1 + max(down[nums.size() - 1], up[nums.size() - 1]);
    }
};

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

#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:
    int islandPerimeter(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        
        int result = 0;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int up = (r == 0) ? 0 : grid[r-1][c];
                    int left = (c == 0) ? 0 : grid[r][c-1];
                    int down = (r == rows-1) ? 0 : grid[r+1][c];
                    int 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.

😎 Решение:

#include <vector>
#include <unordered_map>

class Solution {
private:
    std::unordered_map<int, int> memo;

public:
    int combinationSum4(std::vector<int>& nums, int target) {
        return combs(nums, target);
    }

private:
    int combs(std::vector<int>& nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.find(remain) != memo.end())
            return memo[remain];

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
        }
        memo[remain] = result;
        return result;
    }
};

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