tgindex

C/C++ | LeetCode

описание

Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv

← к каналу@easy_c_plus_task
3 241
подписчиков
Охват к подписчикам
7,7%
ERR
Реакции к просмотрам
0,02%
1 на 25 постов
Пересылки к просмотрам
0,61%
37
Постов в день
0,9
всего 25

Где отзываются чаще

доля реакций к просмотрам
  • 28 июл.Задача: 681. Next Closest Time Сложность: medium Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено. Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными. Пример: Input: time = "19:34" Output: "19:39" Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later. 👨‍💻 Алгоритм: 1⃣Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время. 2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60. 3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д. 😎 Решение: class Solution { public: string nextClosestTime(string time) { int cur = 60 * stoi(time.substr(0, 2)) + stoi(time.substr(3)); unordered_set<int> allowed; for (char c : time) if (c != ':') { allowed.insert(c - '0'); } while (true) { cur = (cur + 1) % (24 * 60); vector<int> digits = {cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10}; bool valid = true; for (int d : digits) { if (!allowed.count(d)) { valid = false; break; } } if (valid) { return (cur / 60 < 10 ? "0" : "") + to_string(cur / 60) + ":" + (cur % 60 < 10 ? "0" : "") + to_string(cur % 60); } } } }; Ставь 👍 и забирай 📚 Базу знаний0,30%
  • 18:11Задача: 661. Image Smoother Сложность: easy Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке. Пример: Input: img = [[1,1,1],[1,0,1],[1,1,1]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0 👨‍💻 Алгоритм: 1⃣Инициализация: Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания. 2⃣Обработка каждой ячейки: Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку). Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы. 3⃣Возврат результата: Верните результирующую матрицу после применения сглаживания ко всем ячейкам. 😎 Решение: class Solution { public: vector<vector<int>> imageSmoother(vector<vector<int>>& img) { int m = img.size(), n = img[0].size(); vector<vector<int>> result(m, vector<int>(n, 0)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int count = 0, total = 0; for (int ni = max(0, i - 1); ni <= min(m - 1, i + 1); ni++) { for (int nj = max(0, j - 1); nj <= min(n - 1, j + 1); nj++) { total += img[ni][nj]; count++; } } result[i][j] = total / count; } } return result; } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 11:06Задача: 591. Tag Validator Сложность: hard Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности. Фрагмент кода считается корректным, если соблюдаются все следующие правила: Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен. Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны. Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен. Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен. Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены. < неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный). cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>. CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы. Пример: Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>" Output: true 👨‍💻 Алгоритм: 1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA. 2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа. 3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат. 😎 Решение: #include <string> #include <stack> #include <regex> using namespace std; class Solution { stack<string> stack; bool containsTag = false; bool isValidTagName(const string& s, bool ending) { if (ending) { if (!stack.empty() && stack.top() == s) stack.pop(); else return false; } else { containsTag = true; stack.push(s); } return true; } public: bool isValid(string code) { regex pattern("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"); if (!regex_match(code, pattern)) return false; int i = 0; while (i < code.size()) { bool ending = false; if (stack.empty() && containsTag) return false; if (code[i] == '<') { if (code[i + 1] == '!') { i = code.find("]]>", i + 1); if (i == string::npos) return false; continue; } if (code[i + 1] == '/') { i++; ending = true; } int closeIndex = code.find('>', i + 1); if (closeIndex == string::npos || !isValidTagName(code.substr(i + 1, closeIndex - (i + 1)), ending)) return false; i = closeIndex; } i++; } return stack.empty(); } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 16 авг.Задача: 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. 👨‍💻 Алгоритм: 1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции. 2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL. 3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans. 😎 Решение: #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; } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 15 авг.Задача: 283. Move Zeroes Сложность: easy Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов. Обратите внимание, что вы должны сделать это на месте, не создавая копию массива. Пример: Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0] 👨‍💻 Алгоритм: 1⃣Инициализация указателей: Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву. 2⃣Итерация и обмен элементами: Итерируйтесь по массиву с помощью указателя cur. Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt. 3⃣Завершение итерации: Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов. 😎 Решение: void moveZeroes(vector<int>& nums) { for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) { if (nums[cur] != 0) { swap(nums[lastNonZeroFoundAt++], nums[cur]); } } } Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 13 авг.Задача: 870. Advantage Shuffle Сложность: medium Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i]. Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2. Пример: Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11] Output: [2,11,7,15] 👨‍💻 Алгоритм: 1⃣Отсортируйте nums1 и nums2. Для каждой карты a из отсортированного nums1 определите, может ли она побить текущую наименьшую карту b из отсортированного nums2. Если да, добавьте a в assigned[b], если нет, добавьте a в remaining. 2⃣После распределения всех карт из nums1, используйте assigned и remaining для построения итогового результата. Для каждой карты b из nums2, если assigned[b] не пуст, добавьте в результат последнюю карту из assigned[b], иначе добавьте последнюю карту из remaining. 3⃣Верните итоговый результат. 😎 Решение: class Solution { public: vector<int> advantageCount(vector<int>& A, vector<int>& B) { vector<int> sortedA(A); sort(sortedA.begin(), sortedA.end()); vector<pair<int, int>> sortedB; for (int i = 0; i < B.size(); ++i) sortedB.push_back({B[i], i}); sort(sortedB.begin(), sortedB.end()); unordered_map<int, deque<int>> assigned; for (int b: B) assigned[b] = {}; deque<int> remaining; int j = 0; for (int a: sortedA) { if (a > sortedB[j].first) { assigned[sortedB[j++].first].push_back(a); } else { remaining.push_back(a); } } vector<int> ans(B.size()); for (int i = 0; i < B.size(); ++i) { if (assigned[B[i]].size() > 0) { ans[i] = assigned[B[i]].front(); assigned[B[i]].pop_front(); } else { ans[i] = remaining.front(); remaining.pop_front(); } } return ans; } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 12 авг.Задача: 775. Global and Local Inversions Сложность: medium Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1]. Число глобальных инверсий — это количество различных пар (i, j), где: 0 <= i < j < n nums[i] > nums[j] Число локальных инверсий — это количество индексов i, где: 0 <= i < n - 1 nums[i] > nums[i + 1] Верните true, если количество глобальных инверсий равно количеству локальных инверсий. Пример: Input: nums = [1,0,2] Output: true Explanation: There is 1 global inversion and 1 local inversion. 👨‍💻 Алгоритм: 1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1. 2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии. 3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false. 😎 Решение: class Solution { public: bool isIdealPermutation(vector<int>& A) { int N = A.size(); for (int i = 0; i < N; ++i) for (int j = i + 2; j < N; ++j) if (A[i] > A[j]) return false; return true; } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 10 авг.Задача: 733. Flood Fill Сложность: easy Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки. Пример: Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] 👨‍💻 Алгоритм: 1⃣Получите цвет начального пикселя. 2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет. 3⃣Обновите изображение и верните его. 😎 Решение: class Solution { public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { int originalColor = image[sr][sc]; if (originalColor == color) { return image; } dfs(image, sr, sc, originalColor, color); return image; } private: void dfs(vector<vector<int>>& image, int x, int y, int originalColor, int newColor) { if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != originalColor) { return; } image[x][y] = newColor; dfs(image, x + 1, y, originalColor, newColor); dfs(image, x - 1, y, originalColor, newColor); dfs(image, x, y + 1, originalColor, newColor); dfs(image, x, y - 1, originalColor, newColor); } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 10 авг.Задача: 541. Reverse String II Сложность: easy Дана строка 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()); } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 9 авг.Задача: 1100. Find K-Length Substrings With No Repeated Characters Сложность: medium Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов. Пример: Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'. 👨‍💻 Алгоритм: 1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов. 2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s: Для каждого индекса i: Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа. Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот. Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию. Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1. 3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k. 😎 Решение: class Solution { public: int numKLenSubstrNoRepeats(string s, int k) { if (k > 26) return 0; int answer = 0; int n = s.size(); for (int i = 0; i <= n - k; i++) { int freq[26] = {0}; bool isUnique = true; for (int j = i; j < i + k; j++) { freq[s[j] - 'a']++; if (freq[s[j] - 'a'] > 1) { isUnique = false; break; } } if (isUnique) answer++; } return answer; } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 8 авг.Задача: 844. Backspace String Compare Сложность: easy Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace. Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым. Пример: Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac". 👨‍💻 Алгоритм: 1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы. 2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены. 3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false. 😎 Решение: class Solution { public: bool backspaceCompare(string S, string T) { int i = S.length() - 1, j = T.length() - 1; int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { while (i >= 0) { if (S[i] == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else break; } while (j >= 0) { if (T[j] == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else break; } if (i >= 0 && j >= 0 && S[i] != T[j]) { return false; } if ((i >= 0) != (j >= 0)) { return false; } i--; j--; } return true; } }; Ставь 👍 и забирай 📚 Базу знаний0,00%
  • 6 авг.Задача: 1094. Car Pooling Сложность: medium Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад). Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля. Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае. Пример: Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false 👨‍💻 Алгоритм: 1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity. 2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени. 3⃣Мы можем сохранить изменения количества пассажиров в каждый момент времени, отсортировать их по меткам времени и, наконец, пройтись по ним, чтобы проверить фактическую вместимость. 😎 Решение: #include <vector> #include <map> using namespace std; class Solution { public: bool carPooling(vector<vector<int>>& trips, int capacity) { map<int, int> timestamp; for (auto& trip : trips) { timestamp[trip[1]] += trip[0]; timestamp[trip[2]] -= trip[0]; } int usedCapacity = 0; for (auto& change : timestamp) { usedCapacity += change.second; if (usedCapacity > capacity) { return false; } } return true; } }; Ставь 👍 и забирай 📚 Базу знаний0,00%