C/C++ | LeetCode

Задача: 67. Add Binary Сложность: easy Даны две строки a и b, представляющие двоичные числа. Верните их сумму также в виде двоичной строки. Пример:

Input: a = "11", b = "1" Output: "100"

👨‍💻 Алгоритм: 1⃣Инициализируем переменные: carry = 0, указатели на последние символы строк a и b, и пустую строку result 2⃣Идем с конца строк, складываем соответствующие биты и carry, добавляем результат по модулю 2 в result, переносим carry на следующий разряд 3⃣После завершения всех итераций, если carry == 1, добавляем '1' в result, затем переворачиваем строку и возвращаем результат 😎 Решение:

class Solution {
public:
    string addBinary(string a, string b) {
        int n = a.size(), m = b.size();
        if (n < m)
            return addBinary(b, a);

        string result;
        int carry = 0, j = m - 1;

        for (int i = n - 1; i >= 0; --i) {
            if (a[i] == '1') ++carry;
            if (j >= 0 && b[j--] == '1') ++carry;

            result.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry == 1) result.push_back('1');

        reverse(result.begin(), result.end());
        return result;
    }
};

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

Задача: 231. Power of Two Сложность: easy Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false. Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x. Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

👨‍💻 Алгоритм: 1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки. 2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций. 3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x. 😎 Решение:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n == 0) return false;
        long x = n;
        return (x & (-x)) == x;
    }
};

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

Задача: 425. Word Squares Сложность: hard Дан массив уникальных строк words, верните все квадраты слов, которые можно построить из этих слов. Одно и то же слово из words можно использовать несколько раз. Вы можете вернуть ответ в любом порядке. Последовательность строк образует допустимый квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(количество строк, количество столбцов). Например, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали. Пример:

Input: words = ["area","lead","wall","lady","ball"]
Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

👨‍💻 Алгоритм: 1⃣Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов. 2⃣При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов. 3⃣Используйте алгоритм с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, вернитесь к предыдущему состоянию и попробуйте другое слово. 😎 Решение:

#include <vector>
#include <unordered_map>
#include <string>
#include <list>
#include <algorithm>

using namespace std;

class Solution {
private:
    int N = 0;
    vector<string> words;
    unordered_map<string, vector<string>> prefixHashTable;

    void buildPrefixHashTable(vector<string>& words) {
        for (auto& word : words) {
            for (int i = 1; i < N; ++i) {
                string prefix = word.substr(0, i);
                prefixHashTable[prefix].push_back(word);
            }
        }
    }

    vector<string> getWordsWithPrefix(string prefix) {
        if (prefixHashTable.find(prefix) != prefixHashTable.end()) {
            return prefixHashTable[prefix];
        }
        return {};
    }

    void backtracking(int step, list<string>& wordSquares, vector<vector<string>>& results) {
        if (step == N) {
            results.push_back(vector<string>(wordSquares.begin(), wordSquares.end()));
            return;
        }

        string prefix;
        for (auto& word : wordSquares) {
            prefix += word[step];
        }

        for (auto& candidate : getWordsWithPrefix(prefix)) {
            wordSquares.push_back(candidate);
            backtracking(step + 1, wordSquares, results);
            wordSquares.pop_back();
        }
    }

public:
    vector<vector<string>> wordSquares(vector<string>& words) {
        this->words = words;
        this->N = words[0].length();

        vector<vector<string>> results;
        buildPrefixHashTable(words);

        for (auto& word : words) {
            list<string> wordSquares;
            wordSquares.push_back(word);
            backtracking(1, wordSquares, results);
        }
        return results;
    }
};

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

Новая фича на easyoffer – Автоотлики Вы автоматически откликаетесь на подходящие вам вакансии. Попробуйте её бесплатно и начните получать больше предложений о работе. 🚀 Запуск занимаем всего 3 минуты, а экономит очень много времени 🛡 Это безопасно: easyoffer официально одобрен HeadHunter и прошел его модерацию. 🥷🏻 Автоотклик незаметен для рекртера. Автоотклик ничем не отличается от обычного отклика, который вы делаете вручную Рекрутеры давно используют автоматизацию для поиска кандидатов. Так почему вы должны откликаться вручную? 💡Совет – Добавьте шаблон сопроводительного письма, чтобы откликаться на большее количество вакансий (на некоторые вакансии нельзя откликнуться без сопроводительного) Попробовать бесплатно → https://easyoffer.ru/autoapply

Задача: 498. Diagonal Traverse Сложность: medium Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке. Пример:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

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

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        if (mat.empty() || mat[0].empty()) return {};
        int N = mat.size(), M = mat[0].size();
        vector<int> result;
        
        for (int d = 0; d < N + M - 1; ++d) {
            vector<int> intermediate;
            int r = d < M ? 0 : d - M + 1;
            int c = d < M ? d : M - 1;
            
            while (r < N && c >= 0) {
                intermediate.push_back(mat[r][c]);
                ++r;
                --c;
            }
            
            if (d % 2 == 0) {
                reverse(intermediate.begin(), intermediate.end());
            }
            result.insert(result.end(), intermediate.begin(), intermediate.end());
        }
        
        return result;
    }
};

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

REKONFA Live 6 ноября приглашаем рекламодателей, агентства и рекламные площадки обсудить технологии, маркетинговые инструменты и актуальные новинки. Ключевые участники рынка поделятся опытом и расскажут: — О ситуации на рынке рекламы — Как продвигать и продавать в интернете в 2025 году — Как бизнесу адаптироваться к меняющимся условиям Вас ждут доклады на актуальные темы, классный нетворкинг, вдохновляющая атмосфера для творчества и креатива. Встречаемся 6 ноября в Москве. Для тех, кто не сможет приехать, организуем интерактивное digital-шоу. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 80. Remove Duplicates from Sorted Array II Сложность: medium Дан массив nums, отсортированный в неубывающем порядке. Удалите дубликаты на месте, чтобы каждый элемент встречался не более двух раз. Порядок должен сохраниться. Использовать можно только O(1) дополнительной памяти. Пример:

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

👨‍💻 Алгоритм: 1⃣Если nums.size() < 3, сразу возвращаем длину — все элементы допустимы. 2⃣Инициализируем указатель j = 2, который будет указывать, куда вставлять следующий допустимый элемент. 3⃣Проходим по массиву с i = 2. Если nums[i] != nums[j - 2], это означает, что текущий элемент встречается не более двух раз — копируем его на позицию j и увеличиваем j. Возвращаем j — это количество допустимых элементов в массиве. 😎 Решение:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3) return nums.size();
        int j = 2;
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] != nums[j - 2]) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
};

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

Задача: 254. Factor Combinations Сложность: medium Дано число n, нужно вернуть все возможные комбинации множителей, таких что их произведение даёт n. Каждая комбинация состоит из множителей в диапазоне [2, n-1]. Порядок вхождения комбинаций не имеет значения. Пример:

Input: n = 8 → Output: [[2,4],[2,2,2]]
Input: n = 1 → Output: []

👨‍💻 Алгоритм: 1⃣Рекурсивный бэктрекинг Создаём вспомогательную функцию backtracking, которая принимает текущие множители factors и сохраняет результаты в ans. 2⃣Разложение числа Берём последний элемент из factors, пробуем все возможные делители i, начиная с 2 или последнего использованного множителя (для сортировки). Если lastFactor % i == 0, то i и lastFactor/i добавляются как следующая пара, и вызывается рекурсия. 3⃣Откат (backtrack) После возврата из рекурсии удаляем последние два элемента из factors, чтобы попробовать другие комбинации. 😎 Решение:

#include <vector>
#include <list>
#include <algorithm>

using namespace std;

class Solution {
public:
    void backtracking(list<int>& factors, vector<vector<int>>& ans) {
        if (factors.size() > 1) {
            ans.push_back(vector<int>(factors.begin(), factors.end()));
        }
        int lastFactor = factors.back();
        factors.pop_back();
        for (int i = factors.empty() ? 2 : factors.back(); i <= lastFactor / i; ++i) {
            if (lastFactor % i == 0) {
                factors.push_back(i);
                factors.push_back(lastFactor / i);
                backtracking(factors, ans);
                factors.pop_back();
                factors.pop_back();
            }
        }
        factors.push_back(lastFactor);
    }

    vector<vector<int>> getFactors(int n) {
        vector<vector<int>> ans;
        list<int> factors = {n};
        backtracking(factors, ans);
        return ans;
    }
};

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

Задача: 1216. Valid Palindrome III Сложность: hard Дана строка s и целое число k. Верните true, если s является k-палиндромом. Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов. Пример:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

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

class Solution {
public:
    vector<vector<int>> memo;

    int isValidPalindromeHelper(const string& s, int i, int j) {
        if (i == j) return 0;
        if (i == j - 1) return s[i] != s[j] ? 1 : 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (s[i] == s[j]) {
            memo[i][j] = isValidPalindromeHelper(s, i + 1, j - 1);
        } else {
            memo[i][j] = 1 + min(isValidPalindromeHelper(s, i + 1, j), isValidPalindromeHelper(s, i, j - 1));
        }
        return memo[i][j];
    }

    bool isValidPalindrome(string s, int k) {
        int n = s.size();
        memo = vector<vector<int>>(n, vector<int>(n, -1));
        return isValidPalindromeHelper(s, 0, n - 1) <= k;
    }
};

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

Задача: 715. Range Module Сложность: hard Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right). Пример:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

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

class RangeModule {
public:
    RangeModule() {}

    void addRange(int left, int right) {
        vector<pair<int, int>> newRanges;
        int i = 0;
        while (i < ranges.size() && ranges[i].second < left) {
            newRanges.push_back(ranges[i]);
            i++;
        }
        while (i < ranges.size() && ranges[i].first <= right) {
            left = min(left, ranges[i].first);
            right = max(right, ranges[i].second);
            i++;
        }
        newRanges.push_back({left, right});
        while (i < ranges.size()) {
            newRanges.push_back(ranges[i]);
            i++;
        }
        ranges = newRanges;
    }

    bool queryRange(int left, int right) {
        for (auto& range : ranges) {
            if (range.first <= left && right <= range.second) {
                return true;
            }
        }
        return false;
    }

    void removeRange(int left, int right) {
        vector<pair<int, int>> newRanges;
        for (auto& range : ranges) {
            if (range.first < left) {
                newRanges.push_back({range.first, min(range.second, left)});
            }
            if (right < range.second) {
                newRanges.push_back({max(range.first, right), range.second});
            }
        }
        ranges = newRanges;
    }

private:
    vector<pair<int, int>> ranges;
};

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

Изиоффер переходит в публичное бета-тестирование! 🎉 Что нового: 🟢Анализ IT собеседований на основе 4500+ реальных интервью 🟢Вопросы из собеседований с вероятностью встречи 🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов 🟢Пример лучшего ответа 🟢Задачи из собеседований 🟢Тестовые задания 🟢Примеры собеседований 🟢Фильтрация всего контента по грейдам, компаниям 🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек 🟢Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро) 🟢Автоотклики на HeadHunter 🟢Закрытое сообщество easyoffer 💎 Акция в честь открытия для первых 500 покупателей: 🚀 Скидка 50% на PRO тариф на 1 год 🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 253. Meeting Rooms II Сложность: medium Дан массив intervals, где каждая пара [start, end] представляет встречу. Нужно вернуть минимальное количество конференц-залов, чтобы все встречи могли пройти без перекрытия. Пример:

Input: intervals = [[0,30],[5,10],[15,20]] Output: 2

👨‍💻 Алгоритм: 1⃣Сортировка по времени начала Сначала отсортируйте все встречи по началу — это позволит обрабатывать их по времени начала. 2⃣Мин-куча для отслеживания комнат Инициализируйте min-heap (приоритетную очередь), где будем хранить время окончания встреч. Если новая встреча может использовать уже освобождённую комнату (её start >= min(endTimes)), удаляем эту запись из кучи. 3⃣Добавление комнат Если текущая встреча не помещается в существующую комнату, добавляем новую. После обработки всех встреч размер кучи будет равен количеству необходимых комнат. 😎 Решение:

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

        priority_queue<int, vector<int>, greater<int>> heap;
        heap.push(intervals[0][1]);

        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= heap.top()) {
                heap.pop();
            }
            heap.push(intervals[i][1]);
        }

        return heap.size();
    }
};

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

Задача: 200. Number of Islands Сложность: medium Дана двумерная бинарная сетка m x n, где '1' — земля, а '0' — вода. Необходимо вернуть количество островов — соединённых участков земли, соседствующих по горизонтали или вертикали. Предполагается, что все четыре края сетки окружены водой. Пример:

Input: grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]] Output: 1

👨‍💻 Алгоритм: 1⃣Пройти по каждому элементу сетки. Если найдена '1', это старт нового острова. Запустить DFS от этой ячейки. 2⃣Внутри DFS заменять каждую посещённую '1' на '0', чтобы избежать повторного подсчёта. 3⃣Каждый запуск DFS соответствует одному острову — увеличиваем счётчик. Решение:

class Solution {
private:
  void dfs(vector<vector<char>>& grid, int r, int c) {
    int nr = grid.size();
    int nc = grid[0].size();

    grid[r][c] = '0';
    if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
    if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
  }

public:
  int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();

    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
};

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 836. Rectangle Overlap Сложность: easy Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y. Два прямоугольника перекрываются, если площадь их пересечения положительна. Для ясности, два прямоугольника, которые касаются только в углу или по краям, не перекрываются. Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false. Пример:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

👨‍💻 Алгоритм: 1⃣ Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]). 2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]). 3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются. 😎 Решение:

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        return min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]) &&
               min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]);
    }
};

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

Готовы с нуля создавать телекоммуникационные решения для беспроводных мобильных сетей и сопутствующих услуг? 🧑‍💻 Отправляйте резюме до 19 октября и присоединяйтесь к команде YADRO Телеком! Как получить оффер за 3 дня? Листайте карточки выше — все подробности там! 💙 Оставляйте заявку — мы ждём именно вас!

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 352. Data Stream as Disjoint Intervals Сложность: hard Дано поступление данных из последовательности неотрицательных целых чисел a1, a2, ..., an, необходимо обобщить увиденные числа в виде списка непересекающихся интервалов. Реализуйте класс SummaryRanges: SummaryRanges() Инициализирует объект с пустым потоком. void addNum(int value) Добавляет целое число в поток. int[][] getIntervals() Возвращает обобщение текущих чисел в потоке в виде списка непересекающихся интервалов [starti, endi]. Ответ должен быть отсортирован по starti. Пример:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

👨‍💻 Алгоритм: 1⃣Инициализировать структуру данных TreeSet для хранения значений. 2⃣addNum(int value) Просто добавить value в values. Если эквивалент TreeSet вашего языка программирования позволяет дублировать значения, как например SortedList в Python, нужно также проверить, что value не существует в values, так как дубликаты нарушат алгоритм. 3⃣getIntervals Если values пуст, вернуть пустой массив. Создать пустой список интервалов. Установить left = right = -1. left представляет левую границу текущего интервала, а right представляет правую границу. Итерировать по values. На каждой итерации: Если left < 0, установить left = right = value. Иначе, если value = right + 1, установить right = value, так как мы можем продолжить текущий интервал. Иначе, мы не можем продолжить текущий интервал. Вставить [left, right] в intervals и установить left = right = value для начала нового интервала. Вставить [left, right] в intervals и вернуть intervals. 😎 Решение:

class SummaryRanges {
    set<int> values;

public:
    SummaryRanges() {}

    void addNum(int value) { values.insert(value); }

    vector<vector<int>> getIntervals() {
        if (values.empty()) {
            return {};
        }
        vector<vector<int>> intervals;
        int left = -1, right = -1;
        for (int value : values) {
            if (left < 0) {
                left = right = value;
            } else if (value == right + 1) {
                right = value;
            } else {
                intervals.push_back({left, right});
                left = right = value;
            }
        }
        intervals.push_back({left, right});
        return intervals;
    }
};

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

Задача: 363. Max Sum of Rectangle No Larger Than K Сложность: hard Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k. Гарантируется, что будет прямоугольник с суммой, не превышающей k. Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

#include <vector>
#include <set>
#include <algorithm>
#include <climits>

class Solution {
public:
    int result = INT_MIN;

    void updateResult(std::vector<int>& nums, int k) {
        int sum = 0;
        std::set<int> sortedSum;
        sortedSum.insert(0);

        for (int num : nums) {
            sum += num;
            auto it = sortedSum.lower_bound(sum - k);
            if (it != sortedSum.end()) {
                result = std::max(result, sum - *it);
            }
            sortedSum.insert(sum);
        }
    }

    int maxSumSubmatrix(std::vector<std::vector<int>>& matrix, int k) {
        int rows = matrix.size();
        int cols = matrix[0].size();

        for (int i = 0; i < rows; ++i) {
            std::vector<int> rowSum(cols, 0);
            for (int row = i; row < rows; ++row) {
                for (int col = 0; col < cols; ++col) {
                    rowSum[col] += matrix[row][col];
                }
                updateResult(rowSum, k);
                if (result == k) {
                    return result;
                }
            }
        }
        return result;
    }
};

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

Задача: 46. Permutations Сложность: medium Дан массив nums, состоящий из различных целых чисел. Верните все возможные перестановки. Ответ может быть в любом порядке. Пример:

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

👨‍💻 Алгоритм: 1⃣Если размер текущей последовательности curr равен размеру nums, добавить копию curr в ans и выйти 2⃣Перебрать все числа из nums. Если число ещё не в curr, добавить его, вызвать рекурсию, затем удалить (backtrack) 3⃣Запустить backtrack с пустым curr. В конце вернуть ans 😎 Решение:

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr = {};
        backtrack(curr, ans, nums);
        return ans;
    }

    void backtrack(vector<int>& curr, vector<vector<int>>& ans,
                   vector<int>& nums) {
        if (curr.size() == nums.size()) {
            ans.push_back(curr);
            return;
        }

        for (int num : nums) {
            if (find(curr.begin(), curr.end(), num) == curr.end()) {
                curr.push_back(num);
                backtrack(curr, ans, nums);
                curr.pop_back();
            }
        }
    }
};

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