C/C++ | LeetCode

Задача: 1025. Divisor Game Сложность: easy Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально. Пример:

Input: n = 2
Output: true

👨‍💻 Алгоритм: 1⃣Определение выигрыша: Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом. Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом. 2⃣Проверка четности числа: Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false. 3⃣Возврат результата: Возвращаем результат в зависимости от четности числа n. 😎 Решение:

class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};

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

Задача: 1272. Remove Interval Сложность: medium Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше. Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

👨‍💻 Алгоритм: 1⃣Итерируйтесь по каждому интервалу в списке intervals. 2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов. 3⃣Добавляйте непересекающиеся части текущего интервала в результат. 😎 Решение:

class Solution {
public:
    vector<vector<double>> removeInterval(vector<vector<double>>& intervals, vector<double>& toBeRemoved) {
        vector<vector<double>> result;
        for (auto& interval : intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.push_back({interval[0], min(interval[1], toBeRemoved[0])});
            }
            if (interval[1] > toBeRemoved[1]) {
                result.push_back({max(interval[0], toBeRemoved[1]), interval[1]});
            }
        }
        return result;
    }
};

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

Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Сложность: medium Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit. Пример:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

👨‍💻 Алгоритм: 1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна. 2⃣Итеративно добавлять элементы в дек, поддерживая условие абсолютной разницы между максимальным и минимальным элементом в окне, чтобы она была не больше limit, при необходимости сдвигая left. 3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат. 😎 Решение:

#include <queue>
#include <vector>

class Solution {
public:
    int longestSubarray(std::vector<int>& nums, int limit) {
        std::priority_queue<std::pair<int, int>> maxHeap;
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> minHeap;
        int left = 0, maxLength = 0;

        for (int right = 0; right < nums.size(); ++right) {
            maxHeap.push({nums[right], right});
            minHeap.push({nums[right], right});

            while (maxHeap.top().first - minHeap.top().first > limit) {
                left = std::min(maxHeap.top().second, minHeap.top().second) + 1;
                while (maxHeap.top().second < left) {
                    maxHeap.pop();
                }
                while (minHeap.top().second < left) {
                    minHeap.pop();
                }
            }

            maxLength = std::max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

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

Задача: 647. Palindromic Substrings Сложность: medium Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке. Пример:

Input: s = "abc"
Output: 3

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

int expandAroundCenter(const string& s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        count++;
        left--;
        right++;
    }
    return count;
}

int countSubstrings(string s) {
    int totalCount = 0;
    for (int i = 0; i < s.length(); i++) {
        totalCount += expandAroundCenter(s, i, i);
        totalCount += expandAroundCenter(s, i, i + 1);
    }
    return totalCount;
}

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

Задача: 813. Largest Sum of Averages Сложность: medium Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива. Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом. Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

👨‍💻 Алгоритм: 1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N). 2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i). 3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)). 😎 Решение:

class Solution {
public:
    double largestSumOfAverages(vector<int>& A, int K) {
        int N = A.size();
        vector<double> P(N + 1);
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];
        
        vector<double> dp(N);
        for (int i = 0; i < N; ++i)
            dp[i] = (P[N] - P[i]) / (N - i);
        
        for (int k = 0; k < K - 1; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    dp[i] = max(dp[i], (P[j] - P[i]) / (j - i) + dp[j]);
                }
            }
        }
        
        return dp[0];
    }
};

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

Задача: 1357. Apply Discount Every n Orders Сложность: medium В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i]. Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара). Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100). Реализуйте класс Cashier: Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен. double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты. Пример:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]

👨‍💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами. 2⃣Обработка каждого счета: Создайте метод getBill, который принимает массивы product и amount. Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты. Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу. 3⃣Верните итоговую сумму счета. 😎 Решение:

#include <unordered_map>
#include <vector>

class Cashier {
public:
    Cashier(int n, int discount, std::vector<int>& products, std::vector<int>& prices) 
        : n(n), discount(discount), customerCount(0) {
        for (size_t i = 0; i < products.size(); ++i) {
            productsPrices[products[i]] = prices[i];
        }
    }

    double getBill(std::vector<int>& product, std::vector<int>& amount) {
        customerCount++;
        double bill = 0.0;
        
        for (size_t i = 0; i < product.size(); ++i) {
            bill += productsPrices[product[i]] * amount[i];
        }
        
        if (customerCount % n == 0) {
            bill *= (100.0 - discount) / 100.0;
        }
        
        return bill;
    }

private:
    int n;
    int discount;
    int customerCount;
    std::unordered_map<int, int> productsPrices;
};

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

Задача: 109. Convert Sorted List to Binary Search Tree Сложность: medium Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска. Пример:

Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5]

👨‍💻 Алгоритм: 1⃣Так как список односвязный, для нахождения середины используем два указателя: slow_ptr (двигается на 1 узел) и fast_ptr (на 2 узла). Когда fast_ptr дойдёт до конца, slow_ptr будет в середине. 2⃣Для отделения левой части от средней сохраняем prev_ptr, который указывает на узел перед slow_ptr. Затем делаем prev_ptr->next = nullptr, чтобы отсоединить левую часть списка. 3⃣Рекурсивно строим левое поддерево из головы списка, правое — из mid->next. Базовый случай — если head == mid, это лист, возвращаем его как TreeNode. 😎 Решение:

class Solution {
public:
    ListNode* findMiddleElement(ListNode* head) {
        ListNode* prevPtr = nullptr;
        ListNode* slowPtr = head;
        ListNode* fastPtr = head;

        while (fastPtr != nullptr && fastPtr->next != nullptr) {
            prevPtr = slowPtr;
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }

        if (prevPtr != nullptr) {
            prevPtr->next = nullptr;
        }
        return slowPtr;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        ListNode* mid = this->findMiddleElement(head);
        TreeNode* node = new TreeNode(mid->val);

        if (head == mid) {
            return node;
        }

        node->left = this->sortedListToBST(head);
        node->right = this->sortedListToBST(mid->next);
        return node;
    }
};

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

Задача: 64. Minimum Path Sum Сложность: medium На сетке m x n, заполненной неотрицательными числами, найдите путь от (0, 0) до (m - 1, n - 1) с минимальной суммой. Можно двигаться только вправо или вниз. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализировать матрицу dp такого же размера, где dp[i][j] будет хранить минимальную сумму пути до конца из позиции (i, j) 2⃣Заполнить dp в обратном порядке, начиная с правого нижнего угла. Для каждой ячейки: dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1]) — если оба пути доступны Учитывать границы (последняя строка и столбец) отдельно 3⃣Вернуть dp[0][0] — минимальную сумму пути из начала в конец 😎 Решение:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j != n - 1)
                    dp[i][j] = grid[i][j] + dp[i][j + 1];
                else if (j == n - 1 && i != m - 1)
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (j != n - 1 && i != m - 1)
                    dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);
                else
                    dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
};

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

Задача: 23. Merge k Sorted Lists Сложность: medium Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его. Пример:

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

👨‍💻 Алгоритм: 1⃣Создаем min-кучу, где приоритетом будет минимальное значение узлов. 2⃣Помещаем в кучу первые элементы всех непустых списков. 3⃣Извлекаем минимальный элемент, добавляем в результат, и если у него есть следующий элемент — помещаем его в кучу. 😎 Решение:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class compare {
public:
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;

        priority_queue<ListNode*, vector<ListNode*>, compare> minheap;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL)
                minheap.push(lists[i]);
        }

        ListNode* head = NULL;
        ListNode* temp1;

        while (!minheap.empty()) {
            ListNode* temp = minheap.top();
            minheap.pop();

            if (head == NULL) {
                head = temp;
                temp1 = temp;
            } else {
                temp1->next = temp;
                temp1 = temp;
            }

            if (temp->next != NULL) {
                minheap.push(temp->next);
            }
        }

        if (temp1 != NULL)
            temp1->next = NULL;

        return head;
    }
};

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

Задача: 1007. Minimum Domino Rotations For Equal Row Сложность: medium В ряду домино, tops[i] и bottoms[i] представляют собой верхнюю и нижнюю половинки i-го домино. (Домино - это плитка с двумя числами от 1 до 6 - по одному на каждой половине плитки.) Мы можем повернуть i-е домино так, чтобы tops[i] и bottoms[i] поменялись значениями. Верните минимальное количество поворотов, чтобы все значения tops были одинаковыми или все значения bottoms были одинаковыми. Если это невозможно сделать, верните -1. Пример:

Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2

👨‍💻 Алгоритм: 1⃣Проверка кандидатов: Для начала рассмотрим два кандидата для достижения цели: tops[0] и bottoms[0]. Это кандидаты для унификации значений в ряду домино, поскольку если есть решение, один из этих двух кандидатов должен быть в верхней или нижней строке всех домино. 2⃣Подсчет поворотов для каждого кандидата: Для каждого из кандидатов (tops[0] и bottoms[0]) подсчитайте количество поворотов, необходимых для унификации значений во всех tops или во всех bottoms. Если какой-либо домино не может быть повернут для достижения требуемого кандидата, этот кандидат исключается из рассмотрения. 3⃣Возврат минимального количества поворотов: Верните минимальное количество поворотов из всех возможных кандидатов. Если ни один кандидат не подходит, верните -1. 😎 Решение:

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        auto check = [&](int x) {
            int rotations_a = 0, rotations_b = 0;
            for (int i = 0; i < tops.size(); ++i) {
                if (tops[i] != x && bottoms[i] != x) {
                    return -1;
                } else if (tops[i] != x) {
                    rotations_a++;
                } else if (bottoms[i] != x) {
                    rotations_b++;
                }
            }
            return min(rotations_a, rotations_b);
        };
        
        int rotations = check(tops[0]);
        if (rotations != -1 || tops[0] == bottoms[0]) {
            return rotations;
        } else {
            return check(bottoms[0]);
        }
    }
};

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

Задача: 728. Self Dividing Numbers Сложность: hard Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right]. Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> result;
        for (int num = left; num <= right; num++) {
            if (isSelfDividing(num)) {
                result.push_back(num);
            }
        }
        return result;
    }

private:
    bool isSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
};

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

Задача: 1238. Circular Permutation in Binary Representation Сложность: medium Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Пример:

Input: arr = ["un","iq","ue"]
Output: 4

👨‍💻 Алгоритм: 1⃣Использование рекурсивного подхода: Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов. Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки. Если не можем, пропускаем текущую строку и переходим к следующей. 2⃣Проверка уникальности символов: Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку. 3⃣Поиск максимальной длины: На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины. 😎 Решение:

class Solution {
public:
    int maxLength(vector<string>& arr) {
        return backtrack(arr, 0, "");
    }

private:
    bool isUnique(const string& s) {
        unordered_set<char> char_set(s.begin(), s.end());
        return char_set.size() == s.size();
    }

    int backtrack(const vector<string>& arr, int index, const string& current) {
        if (!isUnique(current)) return 0;
        int max_length = current.size();
        for (int i = index; i < arr.size(); ++i) {
            max_length = max(max_length, backtrack(arr, i + 1, current + arr[i]));
        }
        return max_length;
    }
};

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

Задача: 89. Gray Code Сложность: medium Последовательность Грея длины n — это последовательность 2^n чисел от 0 до 2^n - 1, в которой каждое следующее число отличается от предыдущего ровно на один бит, и ни одно число не повторяется. Пример:

Input: n = 2
Output: [0,1,3,2]
Пояснение: бинарный вид: [00, 01, 11, 10]

👨‍💻 Алгоритм: 1⃣Начинаем с добавления 0 в результат — все коды Грея начинаются с нуля. 2⃣Используем DFS с backtracking: перебираем числа, которые отличаются от текущего на один бит (используя current ^ (1 << i)). 3⃣Храним уже использованные числа в unordered_set, чтобы не добавлять повторения. Если длина результата достигла 2^n, возвращаем true. Иначе пробуем добавить подходящее следующее число. Если неудачно — откатываемся назад. 😎 Решение:

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        result.push_back(0);
        unordered_set<int> isPresent;
        isPresent.insert(0);
        grayCodeHelper(result, n, isPresent);
        return result;
    }

private:
    bool grayCodeHelper(vector<int> &result, int n,
                        unordered_set<int> &isPresent) {
        if (result.size() == (1 << n)) return true;

        int current = result.back();
        for (int i = 0; i < n; i++) {
            int next = current ^ (1 << i);
            if (isPresent.find(next) == isPresent.end()) {
                result.push_back(next);
                isPresent.insert(next);
                if (grayCodeHelper(result, n, isPresent)) return true;
                isPresent.erase(next);
                result.pop_back();
            }
        }
        return false;
    }
};

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

Задача: 775. Global and Local Inversions Сложность: medium Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1]. Число глобальных инверсий — это количество различных пар (i, j), где: 0 <= i < j < n nums[i] > nums[j] Число локальных инверсий — это количество индексов i, где: 0 <= i < n - 1 nums[i] > nums[i + 1] Верните true, если количество глобальных инверсий равно количеству локальных инверсий. Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

👨‍💻 Алгоритм: 1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1. 2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии. 3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false. 😎 Решение:

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        int N = A.size();
        for (int i = 0; i < N; ++i)
            for (int j = i + 2; j < N; ++j)
                if (A[i] > A[j]) return false;
        return true;
    }
};

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

Задача: 1283. Find the Smallest Divisor Given a Threshold Сложность: medium Дан массив целых чисел nums и целое число threshold. Мы выберем положительный целый делитель, разделим все элементы массива на него и суммируем результат деления. Найдите наименьший делитель, такой что результат, упомянутый выше, меньше или равен threshold. Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5). Гарантируется, что решение существует. Пример:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2). 

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

class Solution {
public:
    int smallestDivisor(vector<int>& nums, int threshold) {
        int maxElement = *max_element(nums.begin(), nums.end());
        
        for (int divisor = 1; divisor <= maxElement; ++divisor) {
            int sumOfDivisionResults = 0;
            bool thresholdExceeded = true;
            
            for (int num : nums) {
                sumOfDivisionResults += (num + divisor - 1) / divisor;
                if (sumOfDivisionResults > threshold) {
                    thresholdExceeded = false;
                    break;
                }
            }
            
            if (thresholdExceeded) {
                return divisor;
            }
        }
        
        return -1;
    }
};

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

Задача: 1353. Maximum Number of Events That Can Be Attended Сложность: medium Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi. Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d. Верните максимальное количество событий, которые вы можете посетить. Пример:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

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

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        set<int> visitedDays;
        int count = 0;
        
        for (const auto& event : events) {
            for (int day = event[0]; day <= event[1]; day++) {
                if (visitedDays.find(day) == visitedDays.end()) {
                    visitedDays.insert(day);
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};

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

Задача: 721. Accounts Merge Сложность: medium Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке. Пример:

nput: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

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

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <algorithm>

using namespace std;

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, string> emailToName;
    unordered_map<string, unordered_set<string>> graph;

    
    for (auto& account : accounts) {
        string name = account[0];
        string firstEmail = account[1];
        for (int i = 1; i < account.size(); ++i) {
            string email = account[i];
            graph[firstEmail].insert(email);
            graph[email].insert(firstEmail);
            emailToName[email] = name;
        }
    }

    unordered_set<string> seen;
    vector<vector<string>> mergedAccounts;

   
    for (auto& [email, _] : emailToName) {
        if (seen.count(email) == 0) {
            vector<string> emails;
            stack<string> stk;
            stk.push(email);

            while (!stk.empty()) {
                string node = stk.top();
                stk.pop();
                if (seen.count(node) == 0) {
                    seen.insert(node);
                    emails.push_back(node);
                    for (auto& neighbor : graph[node]) {
                        if (!seen.count(neighbor)) {
                            stk.push(neighbor);
                        }
                    }
                }
            }

            sort(emails.begin(), emails.end());
            vector<string> account;
            account.push_back(emailToName[email]);
            account.insert(account.end(), emails.begin(), emails.end());
            mergedAccounts.push_back(account);
        }
    }

    return mergedAccounts;
}

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

Задача: 958. Check Completeness of a Binary Tree Сложность: medium Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом. В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно. Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

👨‍💻 Алгоритм: 1⃣Если корень дерева равен null, верните true. 2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева. 3⃣Пока очередь не пуста: Извлеките первый элемент из очереди. Если элемент равен null, установите nullNodeFound в true. Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла. 😎 Решение:

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if (!root) return true;

        queue<TreeNode*> q;
        q.push(root);
        bool nullNodeFound = false;

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (!node) {
                nullNodeFound = true;
            } else {
                if (nullNodeFound) {
                    return false;
                }
                q.push(node->left);
                q.push(node->right);
            }
        }
        return true;
    }
};

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

Задача: 587. Erect the Fence Сложность: hard Вам дан массив trees, где trees[i] = [xi, yi] представляет местоположение дерева в саду. Оградите весь сад с использованием минимальной длины веревки, так как это дорого. Сад хорошо огорожен только в том случае, если все деревья окружены. Верните координаты деревьев, которые находятся точно на периметре ограды. Вы можете вернуть ответ в любом порядке. Пример:

Input: trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[4,2],[3,3],[2,4]]
Explanation: All the trees will be on the perimeter of the fence except the tree at [2, 2], which will be inside the fence.

👨‍💻 Алгоритм: 1⃣ Сортировка точек и построение нижней оболочки: Отсортируйте точки по их x-координатам, а в случае совпадения x-координат, по y-координатам. Постройте нижнюю оболочку, добавляя точки к оболочке и удаляя последние точки, если они не образуют против часовой стрелки поворот. 2⃣ Построение верхней оболочки: Пройдитесь по точкам в обратном порядке, чтобы построить верхнюю оболочку. Добавляйте точки к оболочке и удаляйте последние точки, если они не образуют против часовой стрелки поворот. 3⃣ Удаление дублирующих элементов и возврат результата: Используйте HashSet, чтобы удалить дублирующиеся точки из стека. Преобразуйте результат в массив и верните его. 😎 Решение:

class Solution {
public:
    int orientation(vector<int>& p, vector<int>& q, vector<int>& r) {
        return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](vector<int>& p, vector<int>& q) {
            return p[0] == q[0] ? p[1] < q[1] : p[0] < q[0];
        });

        vector<vector<int>> hull;

        for (auto& point : points) {
            while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), point) > 0)
                hull.pop_back();
            hull.push_back(point);
        }

        hull.pop_back();

        for (int i = points.size() - 1; i >= 0; --i) {
            while (hull.size() >= 2 && orientation(hull[hull.size() - 2], hull.back(), points[i]) > 0)
                hull.pop_back();
            hull.push_back(points[i]);
        }

        set<vector<int>> s(hull.begin(), hull.end());
        return vector<vector<int>>(s.begin(), s.end());
    }
};

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

Задача: 364. Nested List Weight Sum II Сложность: medium Вам дан вложенный список целых чисел nestedList. Каждый элемент является либо целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа. Вес целого числа определяется как maxDepth - (глубина целого числа) + 1. Верните сумму каждого целого числа в nestedList, умноженную на его вес. Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

👨‍💻 Алгоритм: 1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь. 2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts. 3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts. 😎 Решение:

#include <vector>
#include <queue>
using namespace std;

class NestedInteger {
public:
    bool isInteger() const;
    int getInteger() const;
    const vector<NestedInteger> &getList() const;
};

class Solution {
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        queue<NestedInteger> q;
        for (auto& ni : nestedList) q.push(ni);

        int depth = 1, maxDepth = 0, sumOfElements = 0, sumOfProducts = 0;

        while (!q.empty()) {
            int size = q.size();
            maxDepth = max(maxDepth, depth);

            for (int i = 0; i < size; ++i) {
                NestedInteger nested = q.front();
                q.pop();

                if (nested.isInteger()) {
                    int value = nested.getInteger();
                    sumOfElements += value;
                    sumOfProducts += value * depth;
                } else {
                    for (auto& ni : nested.getList()) q.push(ni);
                }
            }
            depth++;
        }
        return (maxDepth + 1) * sumOfElements - sumOfProducts;
    }
};

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