Задача: 1530. Number of Good Leaf Nodes Pairs
Сложность: medium

Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance.

Верните количество хороших пар листовых узлов в дереве.

Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

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

1⃣Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла.

2⃣Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS.

3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.

😎 Решение:

class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        unordered_map<TreeNode*, vector<TreeNode*>> graph;
        unordered_set<TreeNode*> leafNodes;
        traverseTree(root, nullptr, graph, leafNodes);
        int ans = 0;
        for (auto leaf : leafNodes) {
            queue<TreeNode*> bfsQueue;
            unordered_set<TreeNode*> seen;
            bfsQueue.push(leaf);
            seen.insert(leaf);
            for (int i = 0; i <= distance; ++i) {
                int size = bfsQueue.size();
                for (int j = 0; j < size; ++j) {
                    TreeNode* currNode = bfsQueue.front();
                    bfsQueue.pop();
                    if (leafNodes.count(currNode) && currNode != leaf) {
                        ++ans;
                    }
                    for (auto neighbor : graph[currNode]) {
                        if (!seen.count(neighbor)) {
                            bfsQueue.push(neighbor);
                            seen.insert(neighbor);
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

private:
    void traverseTree(TreeNode* currNode, TreeNode* prevNode,
                      unordered_map<TreeNode*, vector<TreeNode*>>& graph, unordered_set<TreeNode*>& leafNodes) {
        if (!currNode) {
            return;
        }
        if (!currNode->left && !currNode->right) {
            leafNodes.insert(currNode);
        }
        if (prevNode) {
            graph[prevNode].push_back(currNode);
            graph[currNode].push_back(prevNode);
        }
        traverseTree(currNode->left, currNode, graph, leafNodes);
        traverseTree(currNode->right, currNode, graph, leafNodes);
    }
};

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

Задача: 258. Add Digits
Сложность: easy

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

Пример:

Input: num = 38
Output: 2
Объяснение: 3 + 8 = 11 → 1 + 1 = 2

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

1⃣Используем переменную digital_root, в которую будем поэтапно добавлять цифры num.

2⃣В цикле:
Добавляем num % 10 к digital_root
Делим num на 10 (удаляем последнюю цифру)
Если num == 0 и digital_root > 9, значит, число всё ещё не однозначное — присваиваем digital_root в num и обнуляем digital_root, продолжая цикл.

3⃣Как только число становится однозначным, возвращаем его.

😎 Решение:

class Solution {
public:
    int addDigits(int num) {
        int digital_root = 0;
        while (num > 0) {
            digital_root += num % 10;
            num /= 10;
            if (num == 0 && digital_root > 9) {
                num = digital_root;
                digital_root = 0;
            }
        }
        return digital_root;
    }
};

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

Задача: 40. Combination Sum II
Сложность: medium

Дан массив candidates и число target. Найдите все уникальные комбинации, где сумма элементов равна target. Каждое число можно использовать только один раз.

Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

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

1⃣Отсортировать и подсчитать количество каждого уникального элемента, чтобы избежать дубликатов.

2⃣Запустить рекурсивный backtrack, на каждом шаге выбирая доступный элемент, уменьшая его частоту и остаток target.

3⃣Если remain == 0 — сохранить комбинацию; иначе — откатить шаг (уменьшение глубины, восстановление частоты и удаление элемента из комбинации).

😎 Решение:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> comb;
        map<int, int> counter;
        for (int candidate : candidates) {
            counter[candidate]++;
        }
        vector<pair<int, int>> counterList(counter.begin(), counter.end());
        backtrack(comb, target, 0, counterList, results);
        return results;
    }

private:
    void backtrack(vector<int>& comb, int remain, int curr,
                   vector<pair<int, int>>& counter,
                   vector<vector<int>>& results) {
        if (remain == 0) {
            results.push_back(comb);
            return;
        } else if (remain < 0) {
            return;
        }

        for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
            auto& [candidate, freq] = counter[nextCurr];
            if (freq == 0) continue;

            comb.push_back(candidate);
            --freq;

            backtrack(comb, remain - candidate, nextCurr, counter, results);

            ++freq;
            comb.pop_back();
        }
    }
};

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

Задача: 739. Daily Temperatures
Сложность: medium

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

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

2⃣Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек.

3⃣Возвращайте массив ответов.

😎 Решение:

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> answer(n, 0);
        stack<int> stack;
        
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && T[i] > T[stack.top()]) {
                int j = stack.top();
                stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        return answer;
    }
};

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

Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium

Даны два целых числа n и k, верните массив всех целых чисел длины n, где разница между каждыми двумя последовательными цифрами равна k. Вы можете вернуть ответ в любом порядке.

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

1⃣ Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

2⃣ Инициализируйте список очередей начальными цифрами от 1 до 9.

3⃣ Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k.

😎 Решение:

class Solution {
public:
    vector<int> numsSameConsecDiff(int N, int K) {
        if (N == 1) return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        vector<int> queue = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        for (int level = 1; level < N; ++level) {
            vector<int> nextQueue;
            for (int num : queue) {
                int tailDigit = num % 10;
                vector<int> nextDigits = {tailDigit + K, tailDigit - K};
                
                for (int nextDigit : nextDigits) {
                    if (nextDigit >= 0 && nextDigit < 10) {
                        nextQueue.push_back(num * 10 + nextDigit);
                    }
                }
            }
            queue = nextQueue;
        }
        
        return queue;
    }
};

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

Задача: 1235. Maximum Profit in Job Scheduling
Сложность: hard

У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X.

Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

1⃣Сортировка заданий:
Сначала мы сортируем задания по времени их окончания. Это позволит нам легко проверять, какие задания могут быть выбраны без пересечения с предыдущими выбранными заданиями.

2⃣Использование динамического программирования с двоичным поиском:
Используем массив dp, где dp[i] будет хранить максимальную прибыль, которую можно получить, рассматривая первые i заданий.

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

😎 Решение:

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<tuple<int, int, int>> jobs;
        for (int i = 0; i < startTime.size(); ++i) {
            jobs.emplace_back(endTime[i], startTime[i], profit[i]);
        }
        sort(jobs.begin(), jobs.end());

        vector<pair<int, int>> dp = {{0, 0}};

        for (auto& [e, s, p] : jobs) {
            auto it = upper_bound(dp.begin(), dp.end(), make_pair(s, INT_MAX));
            int new_profit = prev(it)->second + p;
            if (new_profit > dp.back().second) {
                dp.emplace_back(e, new_profit);
            }
        }

        return dp.back().second;
    }
};

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

Задача: 535. Encode and Decode TinyURL
Сложность: medium

Спроектируйте класс для кодирования URL и декодирования короткого URL.
Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL.
Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.

Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

1⃣ Инициализация:
Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода.
Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов.
Создайте объект для генерации случайных чисел.

2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.

3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.

😎 Решение:

class Codec {
public:
    string alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    unordered_map<string, string> map;
    random_device rd;
    mt19937 gen;
    
    Codec() : gen(rd()) {}
    
    string getRand() {
        string res;
        for (int i = 0; i < 6; ++i) {
            res += alphabet[gen() % 62];
        }
        return res;
    }
    
    string encode(string longUrl) {
        string key = getRand();
        while (map.find(key) != map.end()) {
            key = getRand();
        }
        map[key] = longUrl;
        return "https://tinyurl.com/" + key;
    }

    string decode(string shortUrl) {
        string key = shortUrl.substr(19);
        return map[key];
    }
};

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

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

Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s.

Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти.

Пример:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

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

1⃣Инициализация указателей:
Установите два указателя: один на начало массива (left), другой на конец массива (right).

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

3⃣Завершение работы:
Повторяйте шаг 2 до тех пор, пока левый указатель не станет больше или равен правому.

😎 Решение:

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

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

Задача: 113. Path Sum II
Сложность: medium

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

Пример:

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

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

1⃣Функция recurseTree принимает текущий узел, оставшуюся сумму и текущий путь pathNodes. Она исследует дерево рекурсивно.

2⃣Если текущий узел — лист и его значение равно оставшейся сумме, сохраняем копию пути в pathsList.

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

😎 Решение:

class Solution {
public:
    void recurseTree(TreeNode* node, int remainingSum, vector<int>& pathNodes,
                     vector<vector<int>>& pathsList) {
        if (node == NULL) {
            return;
        }

        pathNodes.push_back(node->val);

        if (remainingSum == node->val && node->left == NULL && node->right == NULL) {
            pathsList.push_back(vector<int>(pathNodes));
        } else {
            this->recurseTree(node->left, remainingSum - node->val, pathNodes, pathsList);
            this->recurseTree(node->right, remainingSum - node->val, pathNodes, pathsList);
        }

        pathNodes.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> pathsList;
        vector<int> pathNodes;
        this->recurseTree(root, sum, pathNodes, pathsList);
        return pathsList;
    }
};

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

Задача: 526. Beautiful Arrangement
Сложность: medium

Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий:
perm[i] делится на i.
i делится на perm[i].
Дано целое число n, верните количество красивых перестановок, которые вы можете создать.

Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

1⃣ Инициализация и подготовка массива:
Создайте массив чисел от 1 до N и инициализируйте счетчик красивых перестановок.
Создайте функцию для перестановки элементов массива.

2⃣ Рекурсивное создание перестановок и проверка условий:
Напишите рекурсивную функцию для создания всех возможных перестановок массива, начиная с текущей позиции l.
На каждом шаге перестановки проверяйте, удовлетворяет ли текущий элемент условиям делимости. Если условие выполняется, продолжайте создание перестановок рекурсивно для следующей позиции.

3⃣ Возврат результата:
В основной функции вызовите рекурсивную функцию с начальной позицией 0 и верните значение счетчика красивых перестановок.

😎 Решение:

class Solution {
public:
    int count = 0;
    
    int countArrangement(int N) {
        vector<int> nums(N);
        iota(nums.begin(), nums.end(), 1);
        permute(nums, 0);
        return count;
    }
    
    void permute(vector<int>& nums, int l) {
        if (l == nums.size()) {
            count++;
        }
        for (int i = l; i < nums.size(); ++i) {
            swap(nums[i], nums[l]);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                permute(nums, l + 1);
            }
            swap(nums[i], nums[l]);
        }
    }
};

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

Задача: 397. Integer Replacement
Сложность: medium

К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.

Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

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

1⃣Начните с данного числа n и выполните одну из следующих операций:
Если n четное, замените n на n / 2.
Если n нечетное, замените n на n + 1 или n - 1.

2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов.

3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат.

😎 Решение:

class Solution {
public:
    int integerReplacement(int n) {
        unordered_map<long, int> memo;
        return helper(n, memo);
    }
    
    int helper(long n, unordered_map<long, int>& memo) {
        if (n == 1) return 0;
        if (memo.count(n)) return memo[n];
        
        if (n % 2 == 0) {
            memo[n] = 1 + helper(n / 2, memo);
        } else {
            memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo));
        }
        
        return memo[n];
    }
};

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

Задача: 205. Isomorphic Strings
Сложность: easy

Даны две строки s и t, определить, являются ли они изоморфными.
Строки считаются изоморфными, если символы одной строки можно взаимно однозначно сопоставить символам другой строки, сохраняя порядок.

Пример:

Input: s = "egg", t = "add" Output: true

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

1⃣Создаём два словаря (или массивы) mapping_s_t и mapping_t_s для хранения отображений символов s → t и t → s.

2⃣Проходим по строкам:
Если сопоставление ещё не задано — сохраняем его.
Если уже задано — проверяем корректность: mapping_s_t[s[i]] должно быть t[i], и наоборот.

3⃣Если обнаружена ошибка в отображении — возвращаем false. В противном случае — true.

😎 Решение:

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int mappingDictStoT[256] = {0};
        int mappingDictTtoS[256] = {0};

        for (int i = 0; i < s.length(); ++i) {
            char c1 = s[i];
            char c2 = t[i];
            if (mappingDictStoT[c1] == 0 && mappingDictTtoS[c2] == 0) {
                mappingDictStoT[c1] = c2;
                mappingDictTtoS[c2] = c1;
            }
            else if (!(mappingDictStoT[c1] == c2 &&
                       mappingDictTtoS[c2] == c1)) {
                return false;
            }
        }

        return true;
    }
};

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

Задача: 71. Simplify Path
Сложность: medium

Дан абсолютный путь в стиле Unix. Требуется упростить его до канонического вида, убрав . (текущий каталог), .. (на уровень выше), пустые сегменты и повторяющиеся слэши.

Пример:

Input: path = "/home/" Output: "/home"

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

1⃣Разделить строку path по символу '/' — получим массив строк, где каждая строка — компонент пути

2⃣Пройтись по компонентам:
если компонент "." или "" — пропускаем
если ".." — удалить верхний элемент из стека, если он есть
иначе — добавить компонент в стек (как имя директории)

3⃣Собрать итоговый путь из стека, добавив '/' перед каждым элементом.
Если стек пуст — путь это просто "/"

😎 Решение:

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stack;
        stringstream ss(path);
        string temp;

        while (getline(ss, temp, '/')) {
            if (temp == "..") {
                if (!stack.empty()) stack.pop_back();
            } else if (temp != "." && !temp.empty()) {
                stack.push_back(temp);
            }
        }

        string res = "";
        for (const auto& str : stack) {
            res += "/" + str;
        }

        return res.empty() ? "/" : res;
    }
};

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

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

Верните корни деревьев в оставшемся лесу. Вы можете вернуть результат в любом порядке.

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

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

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

😎 Решение:

class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        unordered_set<int> toDeleteSet(to_delete.begin(), to_delete.end());
        vector<TreeNode*> forest;

        root = processNode(root, toDeleteSet, forest);
        if (root) {
            forest.push_back(root);
        }

        return forest;
    }

private:
    TreeNode* processNode(TreeNode* node, unordered_set<int>& toDeleteSet, vector<TreeNode*>& forest) {
        if (!node) return nullptr;

        node->left = processNode(node->left, toDeleteSet, forest);
        node->right = processNode(node->right, toDeleteSet, forest);

        if (toDeleteSet.count(node->val)) {
            if (node->left) forest.push_back(node->left);
            if (node->right) forest.push_back(node->right);
            return nullptr;
        }

        return node;
    }
};

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

Задача: 1017. Convert to Base -2
Сложность: medium

Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".

Пример:

Input: n = 2
Output: "110"

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

1⃣Инициализация переменных:
Создайте пустую строку для хранения двоичного представления числа.
Используйте цикл для вычисления каждой цифры числа в базе -2.

2⃣Вычисление цифр:
В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2.
Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1.
Добавляйте остаток в начало строки.

3⃣Возврат результата:
Верните строку, представляющую число в базе -2. Если строка пустая, верните "0".

😎 Решение:

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0) return "0";
        string res = "";
        while (n != 0) {
            int remainder = n % -2;
            n /= -2;
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            res = to_string(remainder) + res;
        }
        return res;
    }
};

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

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

2⃣Если ключ начинается с префикса, добавить его значение к ответу.

3⃣Вернуть полученную сумму как результат.

😎 Решение:

#include <unordered_map>
#include <string>

class MapSum {
    std::unordered_map<std::string, int> map;
public:
    MapSum() {}
    void insert(std::string key, int val) {
        map[key] = val;
    }
    int sum(std::string prefix) {
        int ans = 0;
        for (const auto& pair : map) {
            if (pair.first.find(prefix) == 0) {
                ans += pair.second;
            }
        }
        return ans;
    }
};

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

Задача: 651. 4 Keys Keyboard
Сложность: medium

Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.

Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

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

1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.

2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста.

3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.

😎 Решение:

public class Solution {
    public int MaxA(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 2; j < i; j++) {
                dp[i] = Math.Max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }
        return dp[n];
    }
}

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

Задача: 970. Powerful Integers
Сложность: medium

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

Вы можете вернуть ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза.

Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

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

1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎 Решение:

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        int a = x == 1 ? bound : log(bound) / log(x);
        int b = y == 1 ? bound : log(bound) / log(y);
        unordered_set<int> powerfulIntegers;

        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                int value = pow(x, i) + pow(y, j);
                if (value <= bound) {
                    powerfulIntegers.insert(value);
                }
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }

        return vector<int>(powerfulIntegers.begin(), powerfulIntegers.end());
    }
};

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

Задача: 1232. Check If It Is a Straight Line
Сложность: easy

Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.

Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

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

1⃣Определение наклона:
Вычисляем наклон между первыми двумя точками и используем его как эталон.

2⃣Проверка других точек:
Для всех остальных точек проверяем, совпадает ли наклон, образуемый этими точками с первой точкой, с эталонным наклоном.

3⃣Если все наклоны совпадают, то все точки лежат на одной прямой.

😎 Решение:

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        
        for (const auto& point : coordinates) {
            int x = point[0], y = point[1];
            if ((x1 - x0) * (y - y0) != (y1 - y0) * (x - x0)) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, 
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

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

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int biggest = 0;
        int secondBiggest = 0;
        for (int num : nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else if (num > secondBiggest) {
                secondBiggest = num;
            }
        }
        return (biggest - 1) * (secondBiggest - 1);
    }
};

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

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

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