Задача: 72. Edit Distance
Сложность: medium

Даны две строки word1 и word2. Нужно найти минимальное количество операций (вставка, удаление, замена), чтобы преобразовать word1 в word2.

Пример:

Input: word1 = "horse", word2 = "ros"
Output: 3
Пояснение:
horse → rorse (замена h на r)
rorse → rose (удаление r)
rose → ros (удаление e)

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

1⃣Используем рекурсивный подход с кэшированием: minDistance(i, j) — минимальная стоимость преобразования word1[0..i-1] в word2[0..j-1]

2⃣Базовые случаи:
если i == 0, нужно вставить j символов
если j == 0, нужно удалить i символов

3⃣Рекурсия:
если символы совпадают → переходим к предыдущим
иначе:
вставка (i, j-1)
удаление (i-1, j)
замена (i-1, j-1)
→ берём минимум из трёх и добавляем 1

😎 Решение:

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

    int minDistance(string word1, string word2) {
        memo.resize(word1.length() + 1, vector<int>(word2.length() + 1, -1));
        return minDistanceRecur(word1, word2, word1.size(), word2.size());
    }

    int minDistanceRecur(string &word1, string &word2, int word1Index, int word2Index) {
        if (word1Index == 0) return word2Index;
        if (word2Index == 0) return word1Index;

        if (memo[word1Index][word2Index] != -1)
            return memo[word1Index][word2Index];

        int minEditDistance = 0;

        if (word1[word1Index - 1] == word2[word2Index - 1]) {
            minEditDistance = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
        } else {
            int insertOp = minDistanceRecur(word1, word2, word1Index, word2Index - 1);
            int deleteOp = minDistanceRecur(word1, word2, word1Index - 1, word2Index);
            int replaceOp = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
            minEditDistance = 1 + min(insertOp, min(deleteOp, replaceOp));
        }

        memo[word1Index][word2Index] = minEditDistance;
        return minEditDistance;
    }
};

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

Задача: 1037. Valid Boomerang
Сложность: easy

Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией.

Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

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

1⃣Проверка уникальности точек:
Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг.

2⃣Проверка на коллинеарность:
Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны.

3⃣Результат:
Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false.

😎 Решение:

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        return (x1 != x2 || y1 != y2) && (x1 != x3 || y1 != y3) && (x2 != x3 || y2 != y3) && (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0;
    }
};

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

Задача: 1207. Unique Number of Occurrences
Сложность: easy

Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

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

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }
        unordered_set<int> freqSet;
        for (auto& pair : freq) {
            freqSet.insert(pair.second);
        }
        return freq.size() == freqSet.size();
    }
};

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

Задача: 104. Maximum Depth of Binary Tree
Сложность: easy

Дан корень бинарного дерева, верните его максимальную глубину.

Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7] Output: 3

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

1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2⃣Для данной задачи подойдёт несколько способов.

3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

class Solution {
  public:
    int maxDepth(TreeNode *root) {
      if (root == NULL) {
        return 0;
      }
      return max(1 + maxDepth(root -> left), 1 + maxDepth(root -> right));
    }
};

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

Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium

Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.

Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

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

1⃣Создайте двумерный массив для хранения длин общих подмассивов.

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

3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива.

😎 Решение:

int findLength(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
    int maxLength = 0;
    for (int i = nums1.size() - 1; i >= 0; i--) {
        for (int j = nums2.size() - 1; j >= 0; j--) {
            if (nums1[i] == nums2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }
    return maxLength;
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

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

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval {
public:
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
        vector<Interval> intervals;
        for (const auto& employee : schedule) {
            intervals.insert(intervals.end(), employee.begin(), employee.end());
        }
        
        sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });
        
        vector<Interval> merged;
        for (const auto& interval : intervals) {
            if (merged.empty() || merged.back().end < interval.start) {
                merged.push_back(interval);
            } else {
                merged.back().end = max(merged.back().end, interval.end);
            }
        }
        
        vector<Interval> freeTime;
        for (int i = 1; i < merged.size(); ++i) {
            if (merged[i].start > merged[i-1].end) {
                freeTime.push_back(Interval(merged[i-1].end, merged[i].start));
            }
        }
        
        return freeTime;
    }
};

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

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

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