C/C++ | LeetCode

Задача: 779. K-th Symbol in Grammar Сложность: medium Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10. Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110. Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк. Пример:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

👨‍💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение:

class Solution {
public:
    int depthFirstSearch(int n, int k, int rootVal) {
        if (n == 1) return rootVal;
        int totalNodes = 1 << (n - 1);
        if (k > totalNodes / 2) {
            int nextRootVal = rootVal == 0 ? 1 : 0;
            return depthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal);
        } else {
            int nextRootVal = rootVal == 0 ? 0 : 1;
            return depthFirstSearch(n - 1, k, nextRootVal);
        }
    }

    int kthGrammar(int n, int k) {
        return depthFirstSearch(n, k, 0);
    }
};

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

Задача: 171. Excel Sheet Column Number Сложность: easy Дана строка columnTitle, представляющая название столбца в Excel (например, "A", "AB", "ZY"). Нужно вернуть соответствующий номер столбца. Пример:

Input: "A" → Output: 1

👨‍💻 Алгоритм: 1⃣Представим строку как число в 26-ричной системе счисления, где A = 1, B = 2, ..., Z = 26. 2⃣Проходим по строке слева направо, на каждом шаге умножая результат на 26 и прибавляя значение текущего символа (s[i] - 'A' + 1). 3⃣Таким образом, "AB" = 1×26 + 2 = 28. 😎 Решение:

class Solution {
public:
    int titleToNumber(string s) {
        int result = 0;
        for (char c : s) {
            result = result * 26 + (c - 'A' + 1);
        }
        return result;
    }
};

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

Задача: 906. Super Palindromes Сложность: hard Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию. Пример:

Input: left = "4", right = "1000"
Output: 4

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

class Solution {
public:
    bool isPalindrome(long long x) {
        string s = to_string(x);
        return s == string(s.rbegin(), s.rend());
    }

    int superpalindromesInRange(string left, string right) {
        long long leftNum = stoll(left);
        long long rightNum = stoll(right);
        int count = 0;

        for (int i = 1; i < 100000; i++) {
            string s = to_string(i);
            long long palin1 = stoll(s + string(s.rbegin(), s.rend()));
            long long palin2 = stoll(s + string(s.rbegin() + 1, s.rend()));

            if (palin1 * palin1 > rightNum) {
                break;
            }
            if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
                count++;
            }
            if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
                count++;
            }
        }

        return count;
    }
};

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

Задача: 771. Jewels and Stones Сложность: medium Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями. Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A". Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int ans = 0;
        for (char s : S)
            for (char j : J)
                if (j == s) {
                    ans++;
                    break;
                }
        return ans;
    }
};

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

Задача: 685. Redundant Connection II Сложность: hard В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей. Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi. Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве. Пример:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

👨‍💻 Алгоритм: 1⃣Сначала создаем базовый граф, отслеживая ребра, идущие от узлов с несколькими родителями. В итоге у нас будет либо 2, либо 0 кандидатов на удаление ребра. 2⃣Если кандидатов нет, то каждый узел имеет одного родителя, как в случае 1->2->3->4->1->5. От любого узла идем к его родителю, пока не посетим узел повторно — тогда мы окажемся внутри цикла, и любые последующие посещенные узлы будут частью этого цикла. В этом случае удаляем последнее ребро, входящее в цикл. 3⃣Если есть кандидаты, проверяем, является ли граф, созданный из родителей, корневым деревом. Идем от любого узла к его родителю, пока это возможно, затем выполняем обход в глубину (DFS) от этого корня. Если посещаем каждый узел, удаление последнего из двух кандидатов приемлемо. В противном случае удаляем первое из двух ребер-кандидатов. 😎 Решение:

class Solution {
public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int N = edges.size();
        unordered_map<int, int> parent;
        vector<vector<int>> candidates;
        for (auto& edge : edges) {
            if (parent.count(edge[1])) {
                candidates.push_back({parent[edge[1]], edge[1]});
                candidates.push_back(edge);
            } else {
                parent[edge[1]] = edge[0];
            }
        }

        int root = orbit(1, parent).node;
        if (candidates.empty()) {
            auto cycle = orbit(root, parent).seen;
            vector<int> ans = {0, 0};
            for (auto& edge : edges) {
                if (cycle.count(edge[0]) && cycle.count(edge[1])) {
                    ans = edge;
                }
            }
            return ans;
        }

        unordered_map<int, vector<int>> children;
        for (auto& p : parent) {
            children[p.second].push_back(p.first);
        }

        vector<bool> seen(N + 1, false);
        seen[0] = true;
        stack<int> stk;
        stk.push(root);
        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            if (!seen[node]) {
                seen[node] = true;
                for (int c : children[node]) {
                    stk.push(c);
                }
            }
        }
        for (bool b : seen) {
            if (!b) {
                return candidates[0];
            }
        }
        return candidates[1];
    }

private:
    struct OrbitResult {
        int node;
        unordered_set<int> seen;
        OrbitResult(int n, unordered_set<int> s) : node(n), seen(s) {}
    };

    OrbitResult orbit(int node, unordered_map<int, int>& parent) {
        unordered_set<int> seen;
        while (parent.count(node) && !seen.count(node)) {
            seen.insert(node);
            node = parent[node];
        }
        return OrbitResult(node, seen);
    }
};

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

Задача: 717. 1-bit and 2-bit Characters Сложность: easy У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным. Пример:

Input: bits = [1,0,0]
Output: true

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

bool isOneBitCharacter(vector<int>& bits) {
    int i = 0;
    while (i < bits.size() - 1) {
        i += bits[i] + 1;
    }
    return i == bits.size() - 1;
}

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

Задача: 731. My Calendar II Сложность: medium Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь. Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

class MyCalendarTwo {
public:
    MyCalendarTwo() {}

    bool book(int start, int end) {
        for (const auto& overlap : overlaps) {
            if (start < overlap[1] && end > overlap[0]) {
                return false;
            }
        }
        for (const auto& event : events) {
            if (start < event[1] && end > event[0]) {
                overlaps.push_back({max(start, event[0]), min(end, event[1])});
            }
        }
        events.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> events;
    vector<pair<int, int>> overlaps;
};

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

Задача: 340. Longest Substring with At Most K Distinct Characters Сложность: medium Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов. Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0, right = 0;
        unordered_map<char, int> charCount;
        int maxLength = 0;
        
        while (right < s.length()) {
            charCount[s[right]]++;
            while (charCount.size() > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.erase(s[left]);
                }
                left++;
            }
            maxLength = max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
};

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

Задача: 1208. Get Equal Substrings Within Budget Сложность: medium Вам даны две строки s и t одинаковой длины и целое число maxCost. Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов). Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0. Пример:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost. start для хранения начального индекса текущей подстроки. currCost для хранения текущих затрат на преобразование подстроки s в t. 2⃣Итерация по индексам от 0 до N-1: Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost. Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost. Обновить maxLen длиной текущей подстроки. 3⃣Возврат maxLen как результата. 😎 Решение:

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int N = s.length();
        
        int maxLen = 0;
        int start = 0;
        int currCost = 0;
        
        for (int i = 0; i < N; i++) {
            currCost += abs(s[i] - t[i]);
            
            while (currCost > maxCost) {
                currCost -= abs(s[start] - t[start]);
                start++;
            }
            
            maxLen = max(maxLen, i - start + 1);
        }
        
        return maxLen;
    }
};

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

Задача: 1424. Diagonal Traverse II Сложность: medium Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке. Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь с (0, 0) и список ответов ans. 2⃣Пока очередь не пуста: Извлеките (row, col) из очереди. Добавьте nums[row][col] в ans. Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь. Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь. 3⃣Верните ans. 😎 Решение:

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        queue<pair<int, int>> q;
        q.push({0, 0});
        vector<int> ans;
        
        while (!q.empty()) {
            auto [row, col] = q.front(); q.pop();
            ans.push_back(nums[row][col]);
            
            if (col == 0 && row + 1 < nums.size()) {
                q.push({row + 1, col});
            }
            
            if (col + 1 < nums[row].size()) {
                q.push({row, col + 1});
            }
        }
        
        return ans;
    }
};

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

Задача: 957. Prison Cells After N Days Сложность: medium Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста. Каждый день статус камеры, занята она или пуста, меняется по следующим правилам: Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой. В противном случае, она становится пустой. Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей. Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n. Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше). Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

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

class Solution {
public:
    int cellsToBitmap(vector<int>& cells) {
        int stateBitmap = 0;
        for (int cell : cells) {
            stateBitmap = (stateBitmap << 1) | cell;
        }
        return stateBitmap;
    }

    vector<int> nextDay(vector<int>& cells) {
        vector<int> newCells(cells.size(), 0);
        for (int i = 1; i < cells.size() - 1; ++i) {
            newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
        }
        return newCells;
    }

    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        unordered_map<int, int> seen;
        bool isFastForwarded = false;

        while (N > 0) {
            if (!isFastForwarded) {
                int stateBitmap = cellsToBitmap(cells);
                if (seen.find(stateBitmap) != seen.end()) {
                    N %= seen[stateBitmap] - N;
                    isFastForwarded = true;
                } else {
                    seen[stateBitmap] = N;
                }
            }

            if (N > 0) {
                N--;
                cells = nextDay(cells);
            }
        }
        return cells;
    }
};

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

Задача: 1246. Palindrome Removal Сложность: hard Вам дан целочисленный массив arr. За один ход вы можете выбрать палиндромный подмассив arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подмассив из данного массива. Обратите внимание, что после удаления подмассива элементы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. Верните минимальное количество ходов, необходимое для удаления всех чисел из массива. Пример:

Input: arr = [1,2]
Output: 2

👨‍💻 Алгоритм: 1⃣Базовый случай: Если подмассив состоит из одного элемента, то его удаление займет 1 ход, поэтому dp[i][i] = 1. 2⃣Рекурсивный случай: Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подмассив arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подмассив arr[i+1...j-1] и затем удалим arr[i] и arr[j]). 3⃣В противном случае, минимальное количество ходов для удаления подмассива arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подмассивов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1. 😎 Решение:

int minMovesToDelete(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }

    for (int length = 2; length <= n; ++length) {
        for (int i = 0; i <= n - length; ++i) {
            int j = i + length - 1;
            if (arr[i] == arr[j]) {
                dp[i][j] = (length > 2) ? dp[i + 1][j - 1] : 1;
            } else {
                dp[i][j] = INT_MAX;
                for (int k = i; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
    }

    return dp[0][n - 1];
}

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

Задача: 56. Merge Intervals Сложность: medium Дан массив интервалов intervals, где intervals[i] = [start_i, end_i]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, покрывающий те же отрезки. Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]

👨‍💻 Алгоритм: 1⃣Построение графа: Каждый интервал — вершина. Если два интервала пересекаются, между ними проводится ребро. 2⃣Поиск компонент связности: Обход графа (DFS), чтобы найти все интервалы, входящие в одну компоненту — они образуют один объединённый интервал. 3⃣Слияние компонент: Для каждой компоненты берём минимальное начало и максимальный конец интервалов и создаём один новый интервал. Решение:

#include <vector>
#include <map>
#include <set>
#include <stack>
using namespace std;

class Solution {
public:
    map<vector<int>, vector<vector<int>>> graph;
    map<int, vector<vector<int>>> nodes_in_comp;
    set<vector<int>> visited;

    bool overlap(vector<int>& a, vector<int>& b) {
        return a[0] <= b[1] && b[0] <= a[1];
    }

    void buildGraph(vector<vector<int>>& intervals) {
        for (auto interval1 : intervals) {
            for (auto interval2 : intervals) {
                if (overlap(interval1, interval2)) {
                    graph[interval1].push_back(interval2);
                    graph[interval2].push_back(interval1);
                }
            }
        }
    }

    vector<int> mergeNodes(vector<vector<int>>& nodes) {
        int min_start = nodes[0][0];
        int max_end = nodes[0][1];

        for (auto node : nodes) {
            min_start = min(min_start, node[0]);
            max_end = max(max_end, node[1]);
        }

        return {min_start, max_end};
    }

    void markComponentDFS(vector<int>& start, int comp_number) {
        stack<vector<int>> stk;
        stk.push(start);

        while (!stk.empty()) {
            vector<int> node = stk.top();
            stk.pop();

            if (visited.find(node) == visited.end()) {
                visited.insert(node);
                nodes_in_comp[comp_number].push_back(node);

                for (auto child : graph[node]) {
                    stk.push(child);
                }
            }
        }
    }

    void buildComponents(vector<vector<int>>& intervals) {
        int comp_number = 0;

        for (auto interval : intervals) {
            if (visited.find(interval) == visited.end()) {
                markComponentDFS(interval, comp_number);
                comp_number++;
            }
        }
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        buildGraph(intervals);
        buildComponents(intervals);

        vector<vector<int>> merged;
        for (size_t comp = 0; comp < nodes_in_comp.size(); comp++) {
            merged.push_back(mergeNodes(nodes_in_comp[comp]));
        }

        return merged;
    }
};

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

Задача: 1425. Constrained Subsequence Sum Сложность: hard Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k. Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке. Пример:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums. 2⃣Итерируйте i по индексам nums: Если i минус первый элемент queue больше k, удалите элемент из начала queue. Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()]. Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue. Если dp[i] > 0, добавьте i в конец queue. 3⃣Верните максимальное значение в массиве dp. 😎 Решение:

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        deque<int> queue;
        vector<int> dp(nums.size());
        int maxSum = INT_MIN;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (!queue.empty() && i - queue.front() > k) {
                queue.pop_front();
            }
            
            dp[i] = (queue.empty() ? 0 : dp[queue.front()]) + nums[i];
            
            while (!queue.empty() && dp[queue.back()] < dp[i]) {
                queue.pop_back();
            }
            
            if (dp[i] > 0) {
                queue.push_back(i);
            }
            
            maxSum = max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
};

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

Задача: 1531. String Compression II Сложность: hard Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной. Найдите минимальную длину сжатой версии строки s после удаления не более k символов. Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

👨‍💻 Алгоритм: 1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования. 2⃣Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить. 3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия. 😎 Решение:

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

class Solution {
    std::unordered_map<int, int> memo;
    std::unordered_set<int> add = {1, 9, 99};

public:
    int getLengthOfOptimalCompression(std::string s, int k) {
        return dp(s, 0, 'a' + 26, 0, k);
    }

private:
    int dp(const std::string& s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return INT_MAX / 2;
        }

        if (idx == s.size()) {
            return 0;
        }

        int key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k;

        if (memo.count(key)) {
            return memo[key];
        }

        int deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        int keepChar;
        if (s[idx] == lastChar) {
            keepChar = dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.count(lastCharCount) ? 1 : 0);
        } else {
            keepChar = dp(s, idx + 1, s[idx], 1, k) + 1;
        }

        int res = std::min(keepChar, deleteChar);
        memo[key] = res;

        return res;
    }
};

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

Задача: 744. Find Smallest Letter Greater Than Target Сложность: easy Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах. Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left = 0, right = letters.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return letters[left % letters.size()];
    }
};

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

Задача: 70. Climbing Stairs Сложность: easy Чтобы добраться до вершины лестницы с n ступенями, можно каждый раз делать шаг на 1 или 2 ступеньки. Нужно посчитать, сколькими способами можно подняться на вершину. Пример:

Input: n = 2 Output: 2
Варианты:
1 + 1
2

👨‍💻 Алгоритм: 1⃣На каждом шаге есть 2 варианта: подняться на 1 или на 2 ступеньки — задача сводится к подсчёту всех таких комбинаций 2⃣Используем рекурсивную функцию: climb(i, n) = climb(i + 1, n) + climb(i + 2, n) — сумма способов дойти с текущей позиции i до цели n 3⃣Базовые случаи: если i == n — достигли цели, вернуть 1 если i > n — вышли за пределы, вернуть 0 😎 Решение:

class Solution {
public:
    int climbStairs(int n) { return climb_Stairs(0, n); }

    int climb_Stairs(int i, int n) {
        if (i > n) return 0;
        if (i == n) return 1;
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
    }
};

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

Задача: 1493. Longest Subarray of 1's After Deleting One Element Сложность: medium Дан бинарный массив nums, из которого следует удалить один элемент. Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует. Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

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

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int zeroCount = 0;
        int longestWindow = 0;
        int start = 0;

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 0) {
                zeroCount++;
            }

            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }

            longestWindow = max(longestWindow, i - start);
        }

        return longestWindow;
    }
};

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

Задача: 1167. Minimum Cost to Connect Sticks Сложность: medium У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки. Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка. Верните минимальную стоимость соединения всех данных палочек в одну палочку таким образом. Пример:

Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

👨‍💻 Алгоритм: 1⃣Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4). 2⃣Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость. 3⃣Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций. 😎 Решение:

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        int totalCost = 0;
        priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end());
        
        while (pq.size() > 1) {
            int stick1 = pq.top(); 
            pq.pop();
            int stick2 = pq.top(); 
            pq.pop();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.push(cost);
        }
        
        return totalCost;
    }
};

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

Задача: 841. Keys and Rooms Сложность: medium Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее. Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты. Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае. Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> seen(rooms.size(), false);
        seen[0] = true;
        stack<int> stk;
        stk.push(0);

        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            for (int nei : rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true;
                    stk.push(nei);
                }
            }
        }

        for (bool v : seen) {
            if (!v) return false;
        }
        return true;
    }
};

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