C/C++ | LeetCode
Открыть в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Больше
3 205
Подписчики
Нет данных24 часа
-67 дней
-2430 дней
Архив постов
3 205
Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium
Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.
Пример:
Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2 Output: 20👨💻 Алгоритм: 1⃣Предварительные вычисления: Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках. 2⃣Поиск максимальной суммы: Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen. 3⃣Сравнение двух случаев: Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая. 😎 Решение:
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums, secondLen, firstLen));
}
private:
int maxSumNonOverlap(vector<int>& nums, int firstLen, int secondLen) {
int n = nums.size();
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
vector<int> max_first(n, 0);
for (int i = firstLen - 1; i < n; ++i) {
max_first[i] = max((i > 0 ? max_first[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
}
vector<int> max_second(n, 0);
for (int i = secondLen - 1; i < n; ++i) {
max_second[i] = max((i > 0 ? max_second[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
}
int max_sum = 0;
for (int i = firstLen + secondLen - 1; i < n; ++i) {
max_sum = max(max_sum, max_first[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
}
return max_sum;
}
};3 205
Задача: 928. Minimize Malware Spread II
Сложность: hard
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] Output: 0👨💻 Алгоритм: 1⃣Определить компоненты связности в графе. Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов. 2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов. 3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом. 😎 Решение:
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
vector<unordered_set<int>> components;
unordered_set<int> visited;
auto dfs = [&](int node) {
stack<int> stk;
stk.push(node);
unordered_set<int> component;
while (!stk.empty()) {
int u = stk.top();
stk.pop();
if (!visited.count(u)) {
visited.insert(u);
component.insert(u);
for (int v = 0; v < n; ++v) {
if (graph[u][v] == 1 && !visited.count(v)) {
stk.push(v);
}
}
}
}
components.push_back(component);
};
for (int i = 0; i < n; ++i) {
if (!visited.count(i)) {
dfs(i);
}
}
vector<int> infectedInComponent(components.size(), 0);
vector<int> nodeToComponent(n, -1);
for (int i = 0; i < components.size(); ++i) {
for (int node : components[i]) {
nodeToComponent[node] = i;
if (find(initial.begin(), initial.end(), node) != initial.end()) {
infectedInComponent[i]++;
}
}
}
int minInfected = INT_MAX;
int resultNode = *min_element(initial.begin(), initial.end());
for (int node : initial) {
int componentIdx = nodeToComponent[node];
if (infectedInComponent[componentIdx] == 1) {
int componentSize = components[componentIdx].size();
if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
minInfected = componentSize;
resultNode = node;
}
}
}
return resultNode;
}
};3 205
Офисные башни JOIS от MR Office в 5 мин от Москва-Сити
JOIS - это современные башни класса А от нового бренда, объединяющего все офисные объекты MR Group.
Проект премиального бизнес-центра включает две башни:
1) 43-этажный небоскреб MAST с офисами от 96 м² и возможностью приобретения офисных помещений по отдельности, а также целыми этажами или блоками
2) Башня CREDO представляет из себя единый офис площадью 22 000 м²
Главные преимущества будущего проекта:
✨Ландшафтный парк площадью 1,3 Га и пешеходный маршрут более 2,3 км
✨Расположение в 5 минутах до ТТК и Москва-сити
✨3-уровневый подземный паркинг, рассчитанный на 400 машиномест
✨Отделка Shell&Core - оптимальное решение для создания эксклюзивного интерьера
✨Рассрочка 0% на приобретение коммерческой недвижимости
Узнать больше
Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ Л2-ДЕВЕЛОПМЕНТ
#реклама
mr-group.ru
О рекламодателе
3 205
Задача: 776. Split BST
Сложность: medium
Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.
Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.
Верните массив из двух корней двух поддеревьев в порядке.
Пример:
Input: root = [4,2,6,1,3,5,7], target = 2
Output: [[2,1],[4,3,6,null,null,5,7]]class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<TreeNode*> splitBST(TreeNode* root, int target) {
if (!root) {
return {nullptr, nullptr};
}
if (root->val > target) {
auto left = splitBST(root->left, target);
root->left = left[1];
return {left[0], root};
} else {
auto right = splitBST(root->right, target);
root->right = right[0];
return {root, right[1]};
}
}
};3 205
Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard
Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.
Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.
Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга.
Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.
Пример:
Input: hats = [[3,4],[4,5],[5]] Output: 1 Explanation: There is only one way to choose hats given the conditions. First person choose hat 3, Second person choose hat 4 and last one hat 5.👨💻 Алгоритм: 1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей. 2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп. 3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп. 😎 Решение:
class Solution {
vector<vector<int>> memo;
int done;
int n;
const int MOD = 1000000007;
unordered_map<int, vector<int>> hatsToPeople;
public:
int numberWays(vector<vector<int>>& hats) {
n = hats.size();
for (int i = 0; i < n; i++) {
for (int hat: hats[i]) {
hatsToPeople[hat].push_back(i);
}
}
done = (1 << n) - 1;
memo = vector<vector<int>>(41, vector<int>(done, -1));
return dp(1, 0);
}
private:
int dp(int hat, int mask) {
if (mask == done) {
return 1;
}
if (hat > 40) {
return 0;
}
if (memo[hat][mask] != -1) {
return memo[hat][mask];
}
int ans = dp(hat + 1, mask);
if (hatsToPeople.count(hat)) {
for (int person: hatsToPeople[hat]) {
if ((mask & (1 << person)) == 0) {
ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD;
}
}
}
memo[hat][mask] = ans;
return ans;
}
};3 205
Крупнейший университет искусственного интеллекта
Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудников и зарабатывать на искусственном интеллекте.
✨ 8 000+ студентов со всего мира
✨ 600+ AI-проектов, созданных студентами
✨ Сборная Университета — победители крупнейших AI-хакатонов России
✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие)
✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие)
Будем рады видеть тебя в наших рядах!
Узнать больше
#реклама 16+
neural-university.ru
О рекламодателе
3 205
Задача: 1469. Find All The Lonely Nodes
Сложность: easy
В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.
Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.
Пример:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
void DFS(TreeNode* root, bool isLonely, vector<int>& ans) {
if (root == NULL) {
return;
}
if (isLonely) {
ans.push_back(root->val);
}
DFS(root->left, root->right == NULL, ans);
DFS(root->right, root->left == NULL, ans);
}
vector<int> getLonelyNodes(TreeNode* root) {
vector<int> ans;
DFS(root, false, ans);
return ans;
}
};3 205
Как навести порядок в IT-заявках?
⚡Бесплатный вебинар.
Как создать прозрачную систему управления IT-заявками и сократить время обработки обращений с 8 часов до 15 минут.
✅ Бонус при регистрации: интерактивный чек-лист для аудита вашей IT-поддержки
Экспресс-диагностика по 20 ключевым параметрам
Сравнение ваших показателей со средними по рынку
Персональные рекомендации по оптимизации
Записаться онлайн
#реклама 16+
promo.itilium.ru
О рекламодателе
3 205
Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium
Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).
Пример:
Input: matrix = [[-5]], k = 1 Output: -5👨💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:
using namespace std;
class MyHeapNode {
public:
int row;
int column;
int value;
MyHeapNode(int v, int r, int c) : value(v), row(r), column(c) {}
};
class MyHeapComparator {
public:
bool operator()(const MyHeapNode& x, const MyHeapNode& y) const {
return x.value > y.value;
}
};
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int N = matrix.size();
priority_queue<MyHeapNode, vector<MyHeapNode>, MyHeapComparator> minHeap;
for (int r = 0; r < min(N, k); r++) {
minHeap.push(MyHeapNode(matrix[r][0], r, 0));
}
MyHeapNode element = minHeap.top();
while (k-- > 0) {
element = minHeap.top();
minHeap.pop();
int r = element.row, c = element.column;
if (c < N - 1) {
minHeap.push(MyHeapNode(matrix[r][c + 1], r, c + 1));
}
}
return element.value;
}
};3 205
Курсы JAVA-разработки Гарантия ЗП от 120 000р в договоре
Jаvа — это язык, на котором строятся банковские системы, мобильные приложения, крупные веб-сервисы и многое другое, а спрос на Jаvа-разработчиков стабильно высок. Благодаря кроссплатформенности и надежности, ты сможешь работать в любой сфере IТ — от финансов до Коммерческой отрасли.📊💰
Почему это работает?✨
- Минимальные вложения.
- Тысячи человек уже в IТ. Наши выпускники работают в крутых компаниях: от стартапов до международных корпораций.
- Наши менторы — это опытные разработчики, которые ежедневно работают в IТ и готовы делиться актуальными знаниями.
P.S. Если всё ещё сомневаешься и думаешь что будет сложно — просто попробуй.😊
Мы берем на себя все риски: ты оплачиваешь основную стоимость обучения только после успешного трудоустройства — это закреплено в договоре.
Подать заявку
#реклама 16+
kata.academy
О рекламодателе
3 205
Задача: 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 {
fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
val toDeleteSet = to_delete.toSet()
val forest = mutableListOf<TreeNode?>()
fun processNode(node: TreeNode?): TreeNode? {
if (node == null) return null
node.left = processNode(node.left)
node.right = processNode(node.right)
if (toDeleteSet.contains(node.`val`)) {
node.left?.let { forest.add(it) }
node.right?.let { forest.add(it) }
return null
}
return node
}
val root = processNode(root)
if (root != null) forest.add(root)
return forest
}
}3 205
Крупнейший университет искусственного интеллекта
Приглашаем на бесплатный курс по искусственному интеллекту!
5 занятий по теме «Промпт-инжиниринг». Регистрируйся для получения полного бесплатного доступа к курсу.
✨ 8 000+ студентов со всего мира
✨ 600+ AI-проектов, созданных студентами
✨ Сборная Университета — победители крупнейших AI-хакатонов России
✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие)
✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие)
Будем рады видеть тебя в наших рядах!
Узнать больше
#реклама 16+
neural-university.ru
О рекламодателе
3 205
Задача: 640. Solve the Equation
Сложность: medium
Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом.
Пример:
Input: s = "*" Output: 9👨💻 Алгоритм: 1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='. 2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений. 3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'. 😎 Решение:
class Solution {
public:
string solveEquation(string equation) {
auto parse = [](const string& s) {
int coeff = 0, constPart = 0, sign = 1, num = 0;
int i = 0;
while (i < s.size()) {
if (s[i] == '+') {
sign = 1;
i++;
} else if (s[i] == '-') {
sign = -1;
i++;
} else if (isdigit(s[i])) {
num = 0;
while (i < s.size() && isdigit(s[i])) {
num = num * 10 + (s[i] - '0');
i++;
}
if (i < s.size() && s[i] == 'x') {
coeff += sign * num;
i++;
} else {
constPart += sign * num;
}
} else if (s[i] == 'x') {
coeff += sign;
i++;
}
}
return make_pair(coeff, constPart);
};
auto [leftCoeff, leftConst] = parse(equation.substr(0, equation.find('=')));
auto [rightCoeff, rightConst] = parse(equation.substr(equation.find('=') + 1));
int coeff = leftCoeff - rightCoeff;
int constPart = rightConst - leftConst;
if (coeff == 0) {
return constPart == 0 ? "Infinite solutions" : "No solution";
}
return "x=" + to_string(constPart / coeff);
}
};3 205
Современная магистратура от Центрального университета
Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой?
Поступай в магистратуру Центрального университета!
- 4 офлайн программы по востребованным направлениям ИТ
- Онлайн-программа по машинному обучению
- 300 мест с грантами до 1,2 млн руб.
- Вечерние занятия и учеба по выходным — удобно совмещать с работой
- Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса
- Возможность стажировок и трудоустройства в ведущих компаниях
- Государственный диплом за 2 года
Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии.
Оставляй заявку на грант уже сейчас!
Подать заявку
#реклама 16+
apply.centraluniversity.ru
О рекламодателе
3 205
Задача: 917. Reverse Only Letters
Сложность: easy
Задав строку s, переверните ее в соответствии со следующими правилами: все символы, не являющиеся английскими буквами, остаются в той же позиции. Все английские буквы (строчные или прописные) должны быть перевернуты. Верните s после перевертывания.
Пример:
Input: s = "ab-cd" Output: "dc-ba"👨💻 Алгоритм: 1⃣Создать массив для хранения только английских букв из строки s. 2⃣Перевернуть массив с английскими буквами. Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива. 3⃣Вернуть результат. 😎 Решение:
class Solution {
public:
string reverseOnlyLetters(string s) {
vector<char> letters;
for (char c : s) {
if (isalpha(c)) {
letters.push_back(c);
}
}
reverse(letters.begin(), letters.end());
string result;
int idx = 0;
for (char c : s) {
if (isalpha(c)) {
result += letters[idx++];
} else {
result += c;
}
}
return result;
}
};3 205
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
3 205
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
3 205
Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium
Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.
Если общего элемента нет, верните -1.
Пример:
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]] Output: 5👨💻 Алгоритм: 1⃣Инициализация переменных: Инициализируйте массив позиций pos, переменную для текущего максимального значения cur_max и счетчик cnt нулями. 2⃣Итерация по строкам матрицы: Для каждой строки: - увеличивайте позицию в строке, пока значение не станет равным или больше текущего максимума. - если достигли конца строки, возвращайте -1. - если значение равно текущему максимуму, увеличивайте счетчик. - в противном случае, сбросьте счетчик до 1 и обновите текущий максимум. 3⃣Проверка счетчика: Если счетчик равен количеству строк, возвращайте текущий максимум. Повторите шаг 2. 😎 Решение:
class Solution {
public:
int smallestCommonElement(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
vector<int> pos(n, 0);
int cur_max = 0, cnt = 0;
while (true) {
for (int i = 0; i < n; ++i) {
while (pos[i] < m && mat[i][pos[i]] < cur_max) {
++pos[i];
}
if (pos[i] >= m) {
return -1;
}
if (mat[i][pos[i]] != cur_max) {
cnt = 1;
cur_max = mat[i][pos[i]];
} else if (++cnt == n) {
return cur_max;
}
}
}
}
};3 205
Получи грант на обучение в Центральном университете
Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе.
Для школьников 10-х и 11-х классов, СПО.
Подать заявку
#реклама
apply.centraluniversity.ru
О рекламодателе
3 205
Задача: 190. Reverse Bits
Сложность: easy
Переверните биты заданного 32-битного беззнакового целого числа.
Пример:
Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000)👨💻 Алгоритм: 1⃣Итерируем по числу, по 8 бит за раз. Извлекаем байт с помощью n & 0xff. 2⃣Каждый байт переворачиваем с помощью вспомогательной функции reverseByte, которая использует битовые маски и мемоизацию для ускорения. 3⃣Полученные байты сдвигаем на соответствующие позиции в результирующем числе и суммируем. 😎 Решение:
class Solution {
public:
uint32_t reverseByte(uint32_t byte, map<uint32_t, uint32_t> cache) {
if (cache.find(byte) != cache.end()) {
return cache[byte];
}
uint32_t value = (byte * 0x0202020202 & 0x010884422010) % 1023;
cache.emplace(byte, value);
return value;
}
uint32_t reverseBits(uint32_t n) {
uint32_t ret = 0, power = 24;
map<uint32_t, uint32_t> cache;
while (n != 0) {
ret += reverseByte(n & 0xff, cache) << power;
n = n >> 8;
power -= 8;
}
return ret;
}
};