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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача: 750. Number Of Corner Rectangles
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

1⃣Пройдите по строкам матрицы. Для каждой пары строк, найдите все столбцы, где оба значения равны 1.

2⃣Подсчитайте количество таких столбцов. Если их больше одного, то они образуют прямоугольники.

3⃣Для каждой пары строк добавьте количество возможных прямоугольников в общий счетчик.

😎 Решение:

class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = i + 1; j < grid.size(); j++) {
                int numPairs = 0;
                for (int k = 0; k < grid[0].size(); k++) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        numPairs++;
                    }
                }
                if (numPairs > 1) {
                    count += numPairs * (numPairs - 1) / 2;
                }
            }
        }
        return count;
    }
};

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

Задача: 1325. Delete Leaves With a Given Value
Сложность: medium

Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.

Обратите внимание, что после удаления листового узла со значением target, если его родительский узел становится листовым узлом и имеет значение target, он также должен быть удален (необходимо продолжать делать это, пока это возможно).

Пример:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

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

1⃣Базовый случай: Если root равен null, верните null, чтобы обработать условия пустого дерева или прохождения за пределы листовых узлов.

2⃣Рекурсивный обход: Выполните обход в постфиксном порядке, чтобы гарантировать обработку всех потомков перед текущим узлом (root):
— Рекурсивно вызовите removeLeafNodes для левого дочернего узла root и обновите левый дочерний узел возвращаемым значением.
— Аналогично, рекурсивно вызовите removeLeafNodes для правого дочернего узла root и обновите правый дочерний узел возвращаемым значением.

3⃣Оценка узла:
— Проверьте, является ли текущий узел root листовым узлом и совпадает ли его значение с target. Если оба условия выполнены, верните null, чтобы эффективно удалить узел, не присоединяя его к родителю.
— Если узел не является листом или не совпадает с target, верните сам root.

😎 Решение:

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (root == nullptr) {
            return nullptr;
        }

        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);

        if (root->left == nullptr && root->right == nullptr && root->val == target) {
            return nullptr;
        }
        return root;
    }
};

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

Задача: 79. Word Search
Сложность: medium

Дана сетка символов board размером m на n и строка word.
Верните true, если word существует в сетке.
Слово можно составить из букв смежных ячеек по вертикали или горизонтали.
Одна ячейка не может быть использована более одного раза.

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

1⃣Проходим по всем ячейкам сетки и вызываем backtrack() на каждой, начиная поиск слова с этой позиции.

2⃣В backtrack() проверяем:
Достигнут ли конец слова (index == word.length()) — вернуть true
Не вышли ли за границы или текущий символ не совпадает — вернуть false

3⃣Если текущий символ совпадает — временно помечаем его (например, '#'),
запускаем DFS в 4 направлениях, а после — восстанавливаем значение ячейки.
Если из одного из направлений вернётся true, значит слово найдено.

😎 Решение:

class Solution {
private:
    vector<vector<char>> board;
    int ROWS;
    int COLS;

public:
    bool exist(vector<vector<char>>& board, string word) {
        this->board = board;
        ROWS = board.size();
        COLS = board[0].size();
        for (int row = 0; row < ROWS; ++row)
            for (int col = 0; col < COLS; ++col)
                if (backtrack(row, col, word, 0)) return true;
        return false;
    }

protected:
    bool backtrack(int row, int col, const string& word, int index) {
        if (index >= word.length()) return true;
        if (row < 0 || row == ROWS || col < 0 || col == COLS ||
            board[row][col] != word[index])
            return false;
        
        bool ret = false;
        board[row][col] = '#';
        int rowOffsets[4] = {0, 1, 0, -1};
        int colOffsets[4] = {1, 0, -1, 0};
        for (int d = 0; d < 4; ++d) {
            ret = backtrack(row + rowOffsets[d], col + colOffsets[d], word, index + 1);
            if (ret) break;
        }
        board[row][col] = word[index];
        return ret;
    }
};

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

Задача: 723. Candy Crush
Сложность: medium

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления.

2⃣Удалите отмеченные конфеты, установив их значение в 0.

3⃣Переместите конфеты вниз, чтобы заполнить пустые ячейки, и повторите процесс, пока не останется групп конфет для удаления.

😎 Решение:

vector<vector<int>> candyCrush(vector<vector<int>>& board) {
    int m = board.size();
    int n = board[0].size();
    bool stable = false;

    while (!stable) {
        stable = true;
        vector<vector<bool>> crush(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                int v = abs(board[i][j]);
                if (v != 0 && v == abs(board[i][j + 1]) && v == abs(board[i][j + 2])) {
                    stable = false;
                    crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = true;
                }
            }
        }

        for (int i = 0; i < m - 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int v = abs(board[i][j]);
                if (v != 0 && v == abs(board[i + 1][j]) && v == abs(board[i + 2][j])) {
                    stable = false;
                    crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = true;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (crush[i][j]) {
                    board[i][j] = 0;
                }
            }
        }

        for (int j = 0; j < n; ++j) {
            int idx = m - 1;
            for (int i = m - 1; i >= 0; --i) {
                if (board[i][j] != 0) {
                    board[idx][j] = board[i][j];
                    idx--;
                }
            }
            for (int i = idx; i >= 0; --i) {
                board[i][j] = 0;
            }
        }
    }

    return board;
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка по k за раз и верните измененный список. Если количество узлов не кратно k, то оставшиеся узлы должны остаться в исходном порядке. Значения в узлах менять нельзя — разрешено только изменять указатели.

Пример:

Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]

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

1⃣Подсчитываем количество узлов — если их меньше k, возвращаем head без изменений.

2⃣Разворачиваем первые k узлов обычным способом с помощью трех указателей.

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 Solution {
public:
    int count(ListNode* head){
        int n = 0;
        while (head) {
            head = head->next;
            n++;
        }
        return n;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        int num = count(head);
        if (num < k) return head;

        ListNode *next, *prev = NULL;
        ListNode *curr = head;
        int x = k;

        while (x--) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        head->next = reverseKGroup(next, k);
        return prev;
    }
};

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

Задача: 331. Verify Preorder Serialization of a Binary Tree
Сложность: medium

Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (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;
    }
};

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