C/C++ | LeetCode

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

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

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

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

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

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

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

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

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

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

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

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

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! Мы подготовили для тебя 5 занятий по теме «Разработка нейро-сотрудников на GPT». Пройди регистрацию для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ищу желающих выполнять задачи с помощью ИИ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе

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

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

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

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