Задача: 112. Path Sum
Сложность: easy

Дан корень бинарного дерева и целое число targetSum. Верните true, если существует путь от корня до листового узла, сумма значений по которому равна targetSum.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true

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

1⃣Инициализация: создаём два стека — один для узлов (node_stack), второй для текущей оставшейся суммы (sum_stack). Начинаем с корня и суммы sum - root->val.

2⃣Обход: в цикле извлекаем узел и соответствующую сумму. Если узел — лист, и сумма равна 0, возвращаем true.

3⃣Добавляем потомков узла в стек, уменьшая текущую сумму на их значения.

😎 Решение:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;

        std::stack<TreeNode*> node_stack;
        std::stack<int> sum_stack;

        node_stack.push(root);
        sum_stack.push(sum - root->val);

        while (!node_stack.empty()) {
            TreeNode* node = node_stack.top(); node_stack.pop();
            int curr_sum = sum_stack.top(); sum_stack.pop();

            if (!node->left && !node->right && curr_sum == 0) {
                return true;
            }

            if (node->right) {
                node_stack.push(node->right);
                sum_stack.push(curr_sum - node->right->val);
            }

            if (node->left) {
                node_stack.push(node->left);
                sum_stack.push(curr_sum - node->left->val);
            }
        }

        return false;
    }
};

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

Задача: 436. Find Right Interval
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.

Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.

Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.

Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

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

1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎 Решение:

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<vector<int>> endIntervals = intervals;
        unordered_map<vector<int>, int> hash;
        for (int i = 0; i < intervals.size(); ++i) {
            hash[intervals[i]] = i;
        }
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });
        sort(endIntervals.begin(), endIntervals.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });
        int j = 0;
        vector<int> res(intervals.size());
        for (int i = 0; i < endIntervals.size(); ++i) {
            while (j < intervals.size() && intervals[j][0] < endIntervals[i][1]) {
                j++;
            }
            res[hash[endIntervals[i]]] = j == intervals.size() ? -1 : hash[intervals[j]];
        }
        return res;
    }
};

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

Задача: 342. Power of Four
Сложность: easy

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 16
Output: true

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

1⃣Проверка неотрицательности:
Убедитесь, что n больше нуля, так как степени числа четыре всегда положительны.

2⃣Проверка логарифмом:
Используйте логарифм для проверки, является ли число степенью четырех. Число n является степенью четырех, если логарифм n по основанию 4 является целым числом.

3⃣Проверка побитовым оператором:
Число является степенью четырех, если оно является степенью двух (только один бит установлен) и количество нулей после этого бита четно.

😎 Решение:

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n <= 0) return false;
        double log_n_base_4 = log(n) / log(4);
        return log_n_base_4 == floor(log_n_base_4);
    }
};

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

Задача: 541. Reverse String II
Сложность: easy

Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.
Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution {
public:
    string reverseStr(string s, int k) {
        vector<char> a(s.begin(), s.end());
        for (int start = 0; start < a.size(); start += 2 * k) {
            int i = start, j = min(start + k - 1, (int)a.size() - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return string(a.begin(), a.end());
    }
};

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

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

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