C/C++ | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر
3 207
مشترکین
اطلاعاتی وجود ندارد24 ساعت
-107 روز
-1930 روز
آرشیو پست ها
3 207
Онлайн-магистратура с IT специальностями от Яндекса
Совместно с ИТМО, МИФИ, МФТИ.
Онлайн-магистратура с актуальными программами и гибким графиком обучения.
Получите высокооплачиваемую IT профессию, официальный диплом и практические знания.
Господдержка оплаты. Совмещение с работой!
Подать заявку
#реклама 16+
practicum.yandex.ru
О рекламодателе
3 207
Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One
Сложность: medium
Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.
Пример:
Input: s = "1101" Output: 6 Explanation: "1101" corressponds to number 13 in their decimal representation. Step 1) 13 is odd, add 1 and obtain 14. Step 2) 14 is even, divide by 2 and obtain 7. Step 3) 7 is odd, add 1 and obtain 8. Step 4) 8 is even, divide by 2 and obtain 4. Step 5) 4 is even, divide by 2 and obtain 2. Step 6) 2 is even, divide by 2 and obtain 1.👨💻 Алгоритм: 1⃣Инициализируйте переменную operations значением 0. 2⃣Повторяйте операции, пока длина строки s больше 1: Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит. В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию. 3⃣Верните количество операций. 😎 Решение:
class Solution {
public:
int numSteps(string s) {
int operations = 0;
while (s.size() > 1) {
if (s.back() == '0') {
s.pop_back();
} else {
int i = s.size() - 1;
while (i >= 0 && s[i] == '1') {
s[i] = '0';
i--;
}
if (i < 0) {
s.insert(s.begin(), '1');
} else {
s[i] = '1';
}
}
operations++;
}
return operations;
}
};3 207
Баранкины и камни силы
Смотрите на Кинопоиске с 7 августа.
Семья таксистов обретает сверхсилы — и родственницу из XIX века. Фантастическая комедия с Андреем Федорцовым
Узнать больше
#реклама 16+
kinopoisk.ru
О рекламодателе
3 207
Задача: 366. Find Leaves of Binary Tree
Сложность: medium
Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.
Пример:
Input: root = [1,2,3,4,5] Output: [[4,5,3],[2],[1]] Explanation: [[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.👨💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1. 2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте. 3⃣Организовать узлы по высоте и вернуть результат. 😎 Решение:
#include <vector>
#include <algorithm>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
vector<pair<int, int>> pairs;
int getHeight(TreeNode* node) {
if (!node) return -1;
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
int currHeight = max(leftHeight, rightHeight) + 1;
pairs.push_back({currHeight, node->val});
return currHeight;
}
public:
vector<vector<int>> findLeaves(TreeNode* root) {
getHeight(root);
sort(pairs.begin(), pairs.end());
vector<vector<int>> solution;
int currentHeight = -1;
for (const auto& p : pairs) {
if (p.first != currentHeight) {
solution.push_back(vector<int>());
currentHeight = p.first;
}
solution.back().push_back(p.second);
}
return solution;
}
};3 207
Регистрируйтесь на Yandex Ecom Open Air 8 августа
Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг.
Участие бесплатно!
Зарегистрироваться
#реклама 18+
ecomfest.ru
О рекламодателе
3 207
Repost from easyoffer
⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней.
Напоминаю, что в честь релиза запускаем акцию.
Первые 500 покупателей получат:
🚀 Скидку 50% на PRO тариф на 1 год
🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал
🔔 Подпишитесь на этот канал: https://t.me/+b2fZN17A9OQ3ZmJi
В нем мы опубликуем сообщение о релизе в первую очередь
3 207
Задача: 846. Hand of Straights
Сложность: medium
У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.
Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.
Пример:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]👨💻 Алгоритм: 1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false. 2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand. 3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп: Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount. Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false. Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount. 😎 Решение:
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int groupSize) {
if (hand.size() % groupSize != 0) {
return false;
}
unordered_map<int, int> cardCount;
for (int card : hand) {
cardCount[card]++;
}
sort(hand.begin(), hand.end());
for (int card : hand) {
if (cardCount[card] == 0) {
continue;
}
for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
if (cardCount[nextCard] == 0) {
return false;
}
cardCount[nextCard]--;
}
}
return true;
}
};3 207
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
3 207
Задача: 204. Count Primes
Сложность: medium
Дано целое число n.
Нужно вернуть количество простых чисел, которые строго меньше n.
Пример:
Input: n = 10 Output: 4 Объяснение: простые числа: 2, 3, 5, 7👨💻 Алгоритм: 1⃣Инициализируем булев массив numbers длиной n, где numbers[i] == true означает, что число i — потенциально простое. 2⃣Начинаем с p = 2 и до sqrt(n): – Если numbers[p] == true, обнуляем все кратные p, начиная с p * p. 3⃣После завершения прохода, все индексы, где numbers[i] == true (и i >= 2), являются простыми. 😎 Решение:
class Solution {
public:
int countPrimes(int n) {
if (n <= 2) {
return 0;
}
vector<bool> numbers(n, true);
for (int p = 2; p <= sqrt(n); ++p) {
if (numbers[p]) {
for (int j = p * p; j < n; j += p) {
numbers[j] = false;
}
}
}
int numberOfPrimes = 0;
for (int i = 2; i < n; i++) {
if (numbers[i]) {
++numberOfPrimes;
}
}
return numberOfPrimes;
}
};3 207
Регистрируйтесь на Yandex Neuro Scale
В этом году у конференции новое имя и фокус: главной темой становятся нейротехнологии. Мы покажем, как бизнес уже применяет сервисы и как создавать собственных AI-агентов с помощью инструментов нашей платформы.
✨Ждём вас на главной конференции Yandex Cloud!✨
Зарегистрироваться
#реклама 16+
scale.yandex.cloud
О рекламодателе
Реклама на Яндексе
3 207
Задача: 281. Zigzag Iterator
Сложность: medium
Даны два вектора v1 и v2. Необходимо реализовать итератор, который будет поочередно возвращать элементы из этих двух векторов: сначала из первого, затем из второго и так далее.
Пример:
Input: v1 = [1,2], v2 = [3,4,5,6] Output: [1,3,2,4,5,6]👨💻 Алгоритм 1⃣Инициализация Создаем структуру, которая будет хранить оба вектора и очередь индексов (номер вектора, индекс элемента). В очередь добавляются только непустые вектора. 2⃣Метод next() Извлекаем пару (номер вектора, индекс элемента), возвращаем соответствующее значение. Если в этом векторе есть еще элементы — добавляем следующую пару в очередь. 3⃣Метод hasNext() Просто проверяет, пуста ли очередь. Если нет — значит остались элементы. 😎 Решение
#include <vector>
#include <queue>
#include <utility>
class ZigzagIterator {
private:
std::vector<std::vector<int>> vectors;
std::queue<std::pair<int, int>> queue;
public:
ZigzagIterator(std::vector<int>& v1, std::vector<int>& v2) {
vectors.push_back(v1);
vectors.push_back(v2);
for (int i = 0; i < vectors.size(); ++i) {
if (!vectors[i].empty()) {
queue.push({i, 0});
}
}
}
int next() {
auto [vecIndex, elemIndex] = queue.front();
queue.pop();
int nextElemIndex = elemIndex + 1;
if (nextElemIndex < vectors[vecIndex].size()) {
queue.push({vecIndex, nextElemIndex});
}
return vectors[vecIndex][elemIndex];
}
bool hasNext() {
return !queue.empty();
}
};3 207
Задача: 92. Reverse Linked List II
Сложность: medium
Дан односвязный список и два числа left и right.
Нужно перевернуть часть списка от позиции left до right (включительно)
и вернуть изменённый список, сохранив остальные узлы нетронутыми.
Пример:
Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]👨💻 Алгоритм: 1⃣Запускаем рекурсивную функцию recurseAndReverse, передавая указатель right (начинается с head), а также значения m и n — относительные позиции для переворота. 2⃣Перед каждым рекурсивным вызовом сдвигаем right = right->next, и если m > 1, то сдвигаем left = left->next. Таким образом, когда n == 1, left указывает на начало, а right — на конец подсписка. 3⃣Во время отката рекурсии — обмениваем значения в left и right, затем двигаем left = left->next. Останавливаем обмены, если указатели пересеклись (left == right) или пересекаются (right->next == left). 😎 Решение:
class Solution {
public:
ListNode* left = nullptr;
bool stop = false;
void recurseAndReverse(ListNode* right, int m, int n) {
if (n == 1) return;
right = right->next;
if (m > 1) this->left = this->left->next;
recurseAndReverse(right, m - 1, n - 1);
if (this->left == right || right->next == this->left) stop = true;
if (!stop) {
int t = this->left->val;
this->left->val = right->val;
right->val = t;
this->left = this->left->next;
}
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
this->left = head;
recurseAndReverse(head, m, n);
return head;
}
};3 207
Битрикс24 ускоряет работу команды. Вот как это работает
Бесплатный онлайн-сервис для совместной работы заменяет десятки приложений.
📱Например, обсуждаете проект в чате. Тут же ставьте задачи, кидайте файлы и собирайте встречи — без переключения окон. Задачи сразу попадают в трекер, обсуждения превращаются в дела, а календарь сам напоминает о встречах. После созвонов AI подводит итоги и добавляет в тот же чат.
Работайте бесшовно в Битрикс24, чтобы не терять время на переключения.
👌Коллеги, пользуемся
Зарегистрироваться
#реклама 16+
bitrix24.ru
О рекламодателе
3 207
Задача: 989. Add to Array-Form of Integer
Сложность: easy
Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.
Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.
Пример:
Input: num = [1,2,0,0], k = 34 Output: [1,2,3,4] Explanation: 1200 + 34 = 1234👨💻 Алгоритм: 1⃣Инициализация переменных: Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k). Завести переменную carry для хранения переноса и инициализировать ее нулем. Создать пустой массив result для хранения результата. 2⃣Сложение массивов: Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry). Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1. Если сумма меньше 10, установите carry в 0. Добавьте результат текущего сложения в массив result 3⃣Обработка оставшихся цифр и переноса: Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом. Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result. Переверните массив result обратно и верните его. 😎 Решение:
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<int> addToArrayForm(std::vector<int>& num, int k) {
std::vector<int> result;
int n = num.size();
for (int i = n - 1; i >= 0; i--) {
k += num[i];
result.push_back(k % 10);
k /= 10;
}
while (k > 0) {
result.push_back(k % 10);
k /= 10;
}
std::reverse(result.begin(), result.end());
return result;
}
};3 207
Бесплатный 4-х дневный марафон по веб-дизайну
"Just do design"
✅День 1 - Как зарабатывать на дизайне?
✅День 2 - Отрисовка концепта "Nike"
✅День 3 - Отрисовка дополнительных экранов концепта "Nike"
✅День 4 - Анимация концепта "Nike"
Практический марафон по дизайну - легкий старт в профессию мечты.
Вас ждут 4 урока, 4 домашних задания, персональный куратор-эксперт и обратная связь.
Дойдите до конца марафона и пополните портфолио концептом «NIKE».
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
3 207
Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
Сложность: hard
Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу.
Верните минимальное количество шагов, необходимых для преобразования матрицы mat в нулевую матрицу или -1, если это невозможно.
Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1.
Нулевая матрица - это матрица, в которой все ячейки равны 0.
Пример:
Input: mat = [[0,0],[0,1]] Output: 3 Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.👨💻 Алгоритм: 1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой. 2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed: Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1. Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке. 3⃣После обработки всех строк проверьте, содержит ли lastState все нули, чтобы определить, является ли это допустимым решением. Верните минимальное количество переворотов для всех допустимых решений. 😎 Решение:
class Solution {
int better(int x, int y) {
return x < 0 || (y >= 0 && y < x) ? y : x;
}
int dfs(const vector<vector<int>>& mat, vector<int>& operations) {
if (operations.size() == mat[0].size()) {
vector<int> changed(mat[0].size());
vector<int> last_state = operations;
int maybe = 0;
for (const vector<int>& row : mat) {
vector<int> state = changed;
for (int j = 0; j < row.size(); ++j) {
state[j] ^= row[j];
if (last_state[j]) {
state[j] ^= 1;
if (j) {
state[j - 1] ^= 1;
}
if (j + 1 < row.size()) {
state[j + 1] ^= 1;
}
++maybe;
}
}
changed = last_state;
last_state = state;
}
for (int x : last_state) {
if (x) {
return -1;
}
}
return maybe;
}
operations.push_back(0);
const int maybe1 = dfs(mat, operations);
operations.back() = 1;
const int maybe2 = dfs(mat, operations);
operations.pop_back();
return better(maybe1, maybe2);
}
public:
int minFlips(vector<vector<int>>& mat) {
vector<int> operations;
return dfs(mat, operations);
}
};3 207
Мы ищем людей, которые хотят работать турагентом из дома
💰Оплата от 150.000 рублей в месяц
Образование, место жительства, трудовой стаж — не важны!
Подходит, как для подработки / декретного отпуска, так и для полной занятости.
Если заинтересовались, то для старта нужно:
— зарегистрироваться на сайте
— пройти трехдневный курс
На что можно рассчитывать:
✅ удаленная работа
✅ зп от 150.000 рублей (потолка нет)
✅ стабильная подработка, если не хотите уходить с основной работы
Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку.
⚡ Набор заканчивается в понедельник!
Зарегистрироваться
#реклама
интревел.рф
О рекламодателе
3 207
Задача: 745. Prefix and Suffix Search
Сложность: hard
Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.
Пример:
Input: letters = ["c","f","j"], target = "a" Output: "c"👨💻 Алгоритм: 1⃣Сохраните слова и их индексы в словаре. 2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций. 3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу. 😎 Решение:
class WordFilter {
public:
WordFilter(vector<string>& words) {
for (int index = 0; index < words.size(); ++index) {
string word = words[index];
int length = word.length();
for (int prefixLength = 1; prefixLength <= length; ++prefixLength) {
for (int suffixLength = 1; suffixLength <= length; ++suffixLength) {
string prefix = word.substr(0, prefixLength);
string suffix = word.substr(length - suffixLength);
string key = prefix + "#" + suffix;
prefixSuffixMap[key] = index;
}
}
}
}
int f(string pref, string suff) {
string key = pref + "#" + suff;
return prefixSuffixMap.count(key) ? prefixSuffixMap[key] : -1;
}
private:
unordered_map<string, int> prefixSuffixMap;
};3 207
Дима Билан на Yandex Ecom Open Air 8 августа
Регистрируйтесь на B2B-фестиваль от Яндекса для тех, кто развивает онлайн-коммерцию.
Участие бесплатно!
Зарегистрироваться
#реклама 18+
ecomfest.ru
О рекламодателе
3 207
Задача: 765. Couples Holding Hands
Сложность: hard
Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.
Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).
Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами.
Пример:
Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.class Solution {
public:
int N;
vector<vector<int>> pairs;
int minSwapsCouples(vector<int>& row) {
N = row.size() / 2;
pairs.resize(N, vector<int>(2));
for (int i = 0; i < N; ++i) {
pairs[i][0] = row[2 * i] / 2;
pairs[i][1] = row[2 * i + 1] / 2;
}
return solve(0);
}
void swap(int a, int b, int c, int d) {
int t = pairs[a][b];
pairs[a][b] = pairs[c][d];
pairs[c][d] = t;
}
int solve(int i) {
if (i == N) return 0;
int x = pairs[i][0], y = pairs[i][1];
if (x == y) return solve(i + 1);
int jx = 0, kx = 0, jy = 0, ky = 0;
for (int j = i + 1; j < N; ++j) {
for (int k = 0; k <= 1; ++k) {
if (pairs[j][k] == x) { jx = j; kx = k; }
if (pairs[j][k] == y) { jy = j; ky = k; }
}
}
swap(i, 1, jx, kx);
int ans1 = 1 + solve(i + 1);
swap(i, 1, jx, kx);
swap(i, 0, jy, ky);
int ans2 = 1 + solve(i + 1);
swap(i, 0, jy, ky);
return min(ans1, ans2);
}
};