C/C++ | LeetCode
Открыть в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Больше
Сеть:3 208
Подписчики
-124 часа
-107 дней
-2030 дней
Архив постов
3 208
Задача: 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;
}
};3 208
Задача: 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. 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);
}
};3 208
Задача: 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;
}
};3 208
Задача: 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());
}
};3 208
Задача: 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];
}
}3 208
Задача: 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)#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;
}
};3 208
Ищу желающих выполнять задачи с помощью ИИ!
Работа полностью на удаленке с зп до 150 000 рублей в месяц.
Без опыта, нужен только телефон, занятость 3-6 часов в день.
Всему обучат на бесплатном курсе и после возьму на работу:
✅ 3 дня уроков по 30 минут
✅ Домашки с проверкой и оплатой бонусами
✅ Плачу 10 тыс за каждую выполненную домашку
Все кто пройдет курс, получат сертификат от школы с образовательной лицензией.
⚡ Набор заканчивается завтра.
👍 Для регистрации жмите кнопку "Зарегистрироваться":
Зарегистрироваться
#реклама 16+
ganstaagency.com
О рекламодателе
3 208
Задача: 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;
}
};3 208
Задача: 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;
}
};3 208
Бесплатный курс Digital-дизайна
На бесплатном курсе ты сможешь:
✨попробовать себя в digital-дизайне: афиши, сайты, UX/UI
✨сделать 3 проекта для портфолио с фидбэком от наставника
✨понять, как устроена работа дизайнера
✨получить доступ к «секретной базе» и гайдам по профессии
Попробовать
#реклама 16+
study.logomachine.ru
О рекламодателе
3 208
Задача: 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;
}
};3 208
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
3 208
Задача: 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;
}
};3 208
+5
Бесплатный курс по дизайну: веб, графический и UX/UI
Получи востребованные навыки:
- создание дизайна сайтов и приложений
- создание инфографики и карточек для маркетплейсов
- работа в графическом редакторе Figma и др.
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Зарегистрироваться
#реклама 16+
yudaevschool24.online
О рекламодателе
3 208
Задача: 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];
}
};3 208
+5
Бесплатный курс по дизайну: веб, графический и UX/UI
Получи востребованные навыки:
- создание дизайна сайтов и приложений
- создание инфографики и карточек для маркетплейсов
- работа в графическом редакторе Figma и др.
Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰
Зарегистрироваться
#реклама 16+
ydaev.ru
О рекламодателе
3 208
Задача: 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]);
}
}
};3 208
Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля
Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰
Научись ей бесплатно!
- Бесплатный доступ
- Разбор ДЗ от наставника
- Мощные кейсы в портфолио
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
3 208
Задача: 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;
}
};3 208
Задача: 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--;
}
}
};