C/C++ | LeetCode

#medium Задача: 537. Complex Number Multiplication Комплексное число можно представить в виде строки в формате "real+imaginaryi", где: real — это действительная часть и является целым числом в диапазоне [-100, 100]. imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100]. i^2 == -1. Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение. Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

👨‍💻 Алгоритм: 1⃣ Извлечение реальной и мнимой частей: Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'. 2⃣ Вычисление произведения: Переведите извлечённые части в целые числа. Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay). 3⃣ Формирование строки результата: Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её. 😎 Решение:

class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        auto x = split(a);
        auto y = split(b);
        int a_real = stoi(x[0]);
        int a_img = stoi(x[1]);
        int b_real = stoi(y[0]);
        int b_img = stoi(y[1]);
        int realPart = a_real * b_real - a_img * b_img;
        int imaginaryPart = a_real * b_img + a_img * b_real;
        return to_string(realPart) + "+" + to_string(imaginaryPart) + "i";
    }

private:
    vector<string> split(const string &s) {
        size_t plus = s.find('+');
        size_t i = s.find('i');
        return {s.substr(0, plus), s.substr(plus + 1, i - plus - 1)};
    }
};

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

Получить игровой ПК за один бой в «Мире кораблей»? ✅Возможно! Ведь мы запускаем грандиозный розыгрыш трёх мощнейших игровых компьютеров стоимостью по 140 000 ₽. Шанс на выигрыш получат все, как новички, так и опытные игроки. Главное — выполнить простые условия! ⚡Переходите на наш портал по ссылке, чтобы узнать, как принять участие! 🏃‍♂️Не упустите возможность выиграть мощный ПК, приглашайте к участию друзей, семью и даже коллег. Кто знает, возможно, тем самым счастливчиком, который заберёт один из трёх игровых ПК, станете именно вы. Желаем всем удачи!❤️ Розыгрыш продлится до 2 декабря 2024 20:59 МСК. 12+ Попробовать #реклама korabli.su О рекламодателе

#easy Задача: 303. Range Sum Query - Immutable Дан целочисленный массив nums. Обработайте несколько запросов следующего типа: Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right. Реализуйте класс NumArray: - NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums. - int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]). Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums. 2⃣Предварительное вычисление сумм: Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат. 😎 Решение:

class NumArray {
private:
    vector<int> sum;
public:
    NumArray(vector<int>& nums) {
        sum.resize(nums.size() + 1);
        for (int i = 0; i < nums.size(); i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
};

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

#medium Задача: 536. Construct Binary Tree from String Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел. Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой. Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует. Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

👨‍💻 Алгоритм: 1⃣ Извлечение числа: Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть. 2⃣ Построение поддерева: Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки. Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют. 3⃣ Основная функция: Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево. 😎 Решение:

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* str2tree(string s) {
        return str2treeInternal(s, 0).first;
    }

private:
    pair<int, int> getNumber(const string& s, int index) {
        bool isNegative = false;
        if (s[index] == '-') {
            isNegative = true;
            index++;
        }
        int number = 0;
        while (index < s.size() && isdigit(s[index])) {
            number = number * 10 + (s[index] - '0');
            index++;
        }
        return {isNegative ? -number : number, index};
    }

    pair<TreeNode*, int> str2treeInternal(const string& s, int index) {
        if (index == s.size()) return {nullptr, index};

        auto numberData = getNumber(s, index);
        int value = numberData.first;
        index = numberData.second;

        TreeNode* node = new TreeNode(value);

        if (index < s.size() && s[index] == '(') {
            auto leftData = str2treeInternal(s, index + 1);
            node->left = leftData.first;
            index = leftData.second;
        }

        if (index < s.size() && s[index] == '(') {
            auto rightData = str2treeInternal(s, index + 1);
            node->right = rightData.first;
            index = rightData.second;
        }

        return {node, index < s.size() && s[index] == ')' ? index + 1 : index};
    }
};

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

Цены на все Серверы онлайн! Удобный конфигуратор! Серверы STSS Flagman✅ Огромный выбор решений 👍 Консультации лучших экспертов 👌 Непревзойденный сервис ❤️ Получить предложение #реклама stss.ru О рекламодателе

#medium Задача: 535. Encode and Decode TinyURL Спроектируйте класс для кодирования 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 "http://tinyurl.com/" + key;
    }

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

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

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

#hard Задача: 302. Smallest Rectangle Enclosing Black Pixels Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель. Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали. Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели. Вы должны написать алгоритм со сложностью менее O(mn). Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

👨‍💻 Алгоритм: 1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно. 2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника: left = min(left, x) right = max(right, x + 1) top = min(top, y) bottom = max(bottom, y + 1) 3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top). 😎 Решение:

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int m = image.size(), n = image[0].size();
        int left = searchColumns(image, 0, y, 0, m, true);
        int right = searchColumns(image, y + 1, n, 0, m, false);
        int top = searchRows(image, 0, x, left, right, true);
        int bottom = searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

private:
    int searchColumns(vector<vector<char>>& image, int i, int j, int top, int bottom, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int t = top;
            while (t < bottom && image[t][k] == '0') t++;
            if ((t < bottom) == opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }

    int searchRows(vector<vector<char>>& image, int i, int j, int left, int right, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int l = left;
            while (l < right && image[k][l] == '0') l++;
            if ((l < right) == opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }
};

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

ТОП-4 Курса по Программированию ⚡Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. ✅Хотите стать программистом, но не знаете с какого языка начать? Помогаем разобраться в самых популярных и востребованных языках программирования. Подарок в конце подборки! Выбрать #реклама 16+ tutortop.ru О рекламодателе

#medium Задача: 532. K-diff Pairs in an Array Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве. Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия: 0 <= i, j < nums.length i != j |nums[i] - nums[j]| == k Обратите внимание, что |val| обозначает абсолютное значение val. Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

👨‍💻 Алгоритм: 1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums. 2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям: Если k > 0, проверьте, существует ли ключ, равный x + k. Если k == 0, проверьте, есть ли более одного вхождения x. 3⃣ Увеличьте счётчик результатов, если условие выполняется. 😎 Решение:

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_map<int, int> counter;
        for (int num : nums) {
            counter[num]++;
        }
        
        int result = 0;
        for (const auto& entry : counter) {
            int x = entry.first;
            int val = entry.second;
            if (k > 0 && counter.count(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        
        return result;
    }
};

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

#medium Задача: 531. Lonely Pixel I Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей. Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей. Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

👨‍💻 Алгоритм: 1⃣ Подсчёт количества чёрных пикселей в строках и столбцах: Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1. 2⃣ Поиск одиночных чёрных пикселей: Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1. 3⃣ Возврат результата: Верните answer. 😎 Решение:

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int n = picture.size();
        int m = picture[0].size();
        
        vector<int> rowCount(n, 0);
        vector<int> columnCount(m, 0);
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    columnCount[j]++;
                }
            }
        }
        
        int answer = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && columnCount[j] == 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
};

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

Помощь в трудоустройстве в IT-сфере! В России из-за дефицита айтишников запустили бесплатную программу по обучению IT-специалистов. Теперь любой желающий может попробовать себя в IT с полного нуля и начать обучение бесплатно! Узнайте про дальнейшее трудоустройство в ведущие IT-компании для восполнения кадрового дефицита. Для этого нужно: - Перейти по ссылке - Заполнить анкету и ответить на вопросы (занимает менее 3 минут) - На основании ваших ответов вы сразу узнаете, подходит ли вам сфера IT и сможете ли вы в ней работать Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе

#easy Задача: 541. Reverse String II Дана строка 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());
    }
};

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

#medium Задача: 540. Single Element in a Sorted Array Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз. Верните единственный элемент, который встречается только один раз. Ваше решение должно работать за время O(log n) и использовать O(1) памяти. Пример:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

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

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums.back();
    }
};

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

ТОП коммутаторов доступа ELTEX 2024 Данные оф.дилера завода [17%] MES2324P 24 x 1G с PoE, 4 x 10G [16%] MES2348P 48 x 1G с PoE, 4 x 10G [8%] MES2324 24 x 1G, 4 x 10G [7%] MES2424P 24 x 1G с PoE, 4 x 10G [6%] MES2348B 48 x 1G, 4 x 10G, Battery [6%] MES2448B 48 x 1G, 4 x 10G, Battery [5%] MES2448P 48 x 1G PoE/PoE+, 4 x 10G [5%] MES2428 24 x 1G, 4 x combo Узнать больше #реклама eltexcm.ru О рекламодателе

#easy Задача: 530. Minimum Absolute Difference in BST Дано корень бинарного дерева поиска (BST), верните минимальную абсолютную разницу между значениями любых двух разных узлов в дереве. Пример:

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

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

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> inorderNodes;
        inorderTraversal(root, inorderNodes);
        int minDifference = INT_MAX;
        for (int i = 1; i < inorderNodes.size(); ++i) {
            minDifference = min(minDifference, inorderNodes[i] - inorderNodes[i - 1]);
        }
        return minDifference;
    }

private:
    void inorderTraversal(TreeNode* node, vector<int>& inorderNodes) {
        if (node == nullptr) return;
        inorderTraversal(node->left, inorderNodes);
        inorderNodes.push_back(node->val);
        inorderTraversal(node->right, inorderNodes);
    }
};

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

#medium Задача: 538. Convert BST to Greater Tree Дано корень бинарного дерева поиска (BST), преобразуйте его в дерево, в котором каждый ключ исходного BST изменен на исходный ключ плюс сумму всех ключей, больших исходного ключа в BST. Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям: Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла. Правое поддерево узла содержит только узлы с ключами, большими ключа узла. И левое, и правое поддеревья также должны быть бинарными деревьями поиска. Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

class Solution {
private:
    int sum = 0;

public:
    TreeNode* convertBST(TreeNode* root) {
        if (root != nullptr) {
            convertBST(root->right);
            sum += root->val;
            root->val = sum;
            convertBST(root->left);
        }
        return root;
    }
};

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

Яндекс Директ Только этой осенью Яндекс Директ добавит до 20 000 ₽ на рекламу для вашего бизнеса ⚡ Узнать больше #реклама yandex.ru О рекламодателе

#medium Задача: 528. Random Pick with Weight Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i. Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w). Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%). Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

👨‍💻 Алгоритм: 1⃣ Инициализация и предобработка весов: В конструкторе создайте массив накопительных сумм prefixSums, где каждая позиция будет содержать сумму всех предыдущих весов до текущего индекса включительно. Также в конструкторе сохраните общую сумму весов totalSum. 2⃣ Генерация случайного числа и выбор индекса: В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum. Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу. 3⃣ Возврат результата: Верните найденный индекс. 😎 Решение:

class Solution {
private:
    vector<int> prefixSums;
    int totalSum;

public:
    Solution(vector<int>& w) {
        int prefixSum = 0;
        for (int weight : w) {
            prefixSum += weight;
            prefixSums.push_back(prefixSum);
        }
        totalSum = prefixSum;
    }

    int pickIndex() {
        double target = totalSum * ((double) rand() / RAND_MAX);
        for (int i = 0; i < prefixSums.size(); ++i) {
            if (target < prefixSums[i]) {
                return i;
            }
        }
        return prefixSums.size() - 1;
    }
};

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