C/C++ LeetCode - задачи

Задача: 1256. Encode Number Сложность: medium Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно. Пример: Input: num = 23 Output: "1000" 👨💻 Алгоритм: 1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n) 2⃣Из таблицы видно, что последовательность строк соответствует последовательности чисел в двоичной системе счисления за исключением начального значения n = 0. 3⃣Таким образом, можно вывести, что: Для каждого значения n > 0, функция f(n) представляет собой двоичное представление числа (n - 1). 😎 Решение: class Solution { public: string encode(int num) { if (num == 0) return ""; string binary = ""; num -= 1; while (num > 0) { binary = (num % 2 == 0 ? "0" : "1") + binary; num /= 2; } return binary; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1370. Increasing Decreasing String Сложность: easy Дана строка s. Переставьте символы строки, используя следующий алгоритм: Выберите наименьший символ из s и добавьте его к результату. Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его. Повторяйте шаг 2, пока не сможете выбрать больше символов. Выберите наибольший символ из s и добавьте его к результату. Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его. Повторяйте шаг 5, пока не сможете выбрать больше символов. Повторяйте шаги с 1 по 6, пока не выберете все символы из s. На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату. Верните результирующую строку после сортировки s с помощью этого алгоритма. Пример: Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm. 👨💻 Алгоритм: 1⃣Инициализация и сортировка: Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result. 2⃣Перебор и добавление символов: Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре. 3⃣Проверка завершения: Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result. 😎 Решение: #include #include class Solution { public: std::string sortString(std::string s) { std::vector charCount(26, 0); for (char c : s) { charCount[c - 'a']++; } std::string result; while (result.size() < s.size()) { for (char c = 'a'; c 0) { result += c; charCount[c - 'a']--; } } for (char c = 'z'; c >= 'a'; c--) { if (charCount[c - 'a'] > 0) { result += c; charCount[c - 'a']--; } } } return result; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1271. Hexspeak Сложность: easy Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR". Пример: Input: num = "257" Output: "IOI" 👨💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение: class Solution { public: string toHexString(string num) { stringstream ss; ss

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps Сложность: hard У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример: Input: steps = 3, arrLen = 2 Output: 4 👨💻 Алгоритм: 1⃣Инициализируйте массив для хранения количества способов достижения каждого индекса на каждом шаге. 2⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 3⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 😎 Решение: class Solution { public: int numWays(int steps, int arrLen) { const int mod = 1e9 + 7; int max_pos = min(arrLen - 1, steps); vector dp(max_pos + 1, 0); dp[0] = 1; for (int step = 0; step < steps; ++step) { vector new_dp(max_pos + 1, 0); for (int i = 0; i 0) new_dp[i] = (new_dp[i] + dp[i - 1]) % mod; if (i < max_pos) new_dp[i] = (new_dp[i] + dp[i + 1]) % mod; } dp = new_dp; } return dp[0]; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 201. Bitwise AND of Numbers Range Сложность: medium Даны два целых числа left и right, обозначающие диапазон [left, right]. Нужно вернуть результат побитового AND всех чисел в этом диапазоне (включительно). Пример: Input: left = 5, right = 7 Output: 4 👨💻 Алгоритм: 1⃣Пока left < right, сдвигаем оба числа вправо (>>= 1), пока они не станут равны. Это находит общий префикс битов. 2⃣Подсчитываем количество сдвигов — это количество младших битов, которые могут изменяться в диапазоне, и обнуляются при AND. 3⃣После этого сдвигаем результат left обратно влево (>= 1; n >>= 1; ++shift; } return m

Задача: 1043. Partition Array for Maximum Sum Сложность: medium Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число. Пример: Input: arr = [1,15,7,9,2,5,10], k = 3 Output: 84 👨💻 Алгоритм: 1⃣Инициализация: Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i. 2⃣Заполнение массива dp: Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой. 3⃣Поддержание максимального значения в подмассиве: Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i]. 😎 Решение: class Solution { public: int maxSumAfterPartitioning(vector& arr, int k) { int n = arr.size(); vector dp(n, 0); for (int i = 0; i < n; ++i) { int max_val = 0; for (int j = 1; j = 0) { max_val = max(max_val, arr[i - j + 1]); if (i - j >= 0) { dp[i] = max(dp[i], dp[i - j] + max_val * j); } else { dp[i] = max(dp[i], max_val * j); } } } } return dp[n - 1]; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1133. Largest Unique Number Сложность: easy Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1. Пример: Input: nums = [5,7,3,9,4,9,8,3,1] Output: 8 Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer. 👨💻 Алгоритм: 1⃣Создайте хеш-таблицу для хранения количества каждого числа в массиве. 2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа. 3⃣Инициализируйте результат значением -1. Пройдите по хеш-таблице и если значение ключа равно 1, установите результат равным максимальному значению между ключом и текущим результатом. Верните результат. 😎 Решение: class Solution { public: int largestUniqueNumber(vector& nums) { unordered_map count; for (int num : nums) { count[num]++; } int result = -1; for (auto& entry : count) { if (entry.second == 1) { result = max(result, entry.first); } } return result; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing Сложность: hard Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим. В одной операции вы можете выбрать два индекса 0

Задача: 715. Range Module Сложность: hard Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left