C/C++ | LeetCode

Задача: 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; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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]); } } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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); } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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()); } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1260. Shift 2D Grid Сложность: easy Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз. Пример: Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[9,1,2],[3,4,5],[6,7,8]] 👨‍💻 Алгоритм: 1⃣Преобразовать двумерную сетку в одномерный массив. 2⃣Выполнить сдвиг элементов в одномерном массиве. 3⃣Преобразовать одномерный массив обратно в двумерную сетку. 😎 Решение: class Solution { public: vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) { int m = grid.size(), n = grid[0].size(); int total = m * n; k = k % total; if (k == 0) { return grid; } vector<int> flatArray(total); for (int i = 0; i < total; ++i) { flatArray[i] = grid[i / n][i % n]; } vector<int> newArray(total); for (int i = 0; i < total; ++i) { newArray[(i + k) % total] = flatArray[i]; } vector<vector<int>> newGrid(m, vector<int>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { newGrid[i][j] = newArray[i * n + j]; } } return newGrid; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: №30. Substring with Concatenation of All Words Сложность: hard Вам дана строка s и массив строк words, где все слова одинаковой длины. Найдите все стартовые индексы подстрок в s, которые являются конкатенацией всех слов из массива (в любом порядке, без дополнительных символов между ними). Пример: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] 👨‍💻 Алгоритм: 1⃣Вычисляем длину каждого слова и общее количество слов. 2⃣Используем скользящее окно с шагом = длине слова, и на каждом шаге проверяем, входят ли текущие слова в заданный набор. 3⃣Отслеживаем, сколько раз каждое слово встречается, используя unordered_map. 😎 Решение: vector<int> findSubstring(string str, vector<string>& words) { int len = words[0].length(); unordered_map<string, int> contain; for (string s : words) contain[s]++; vector<int> res; for (int j = 0; j < len; j++) { unordered_map<string, int> found; int st = j; for (int i = j; i <= str.size() - len; i += len) { string curr = str.substr(i, len); if (contain.find(curr) != contain.end()) { found[curr]++; while (found[curr] > contain[curr]) { found[str.substr(st, len)]--; st += len; } int size = (i - st + len) / len; if (size == words.size()) { res.push_back(st); } } else { found.clear(); st = i + len; } } } return res; } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1372. Longest ZigZag Path in a Binary Tree Сложность: medium Вам дан корень бинарного дерева. Зигзагообразный путь для бинарного дерева определяется следующим образом: Выберите любой узел в бинарном дереве и направление (вправо или влево). Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу. Измените направление с вправо на влево или с влево на вправо. Повторяйте второй и третий шаги, пока не сможете двигаться по дереву. Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0). Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве. Пример: Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm. 👨‍💻 Алгоритм: 1⃣Рекурсивная функция DFS: Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо). 2⃣Обновление максимальной длины пути: При каждом вызове рекурсивной функции обновляйте максимальную длину зигзагообразного пути, если текущая длина больше текущего максимума. 3⃣Рекурсивный вызов для левого и правого дочерних узлов: Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления. 😎 Решение: #include <algorithm> struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: int maxLength = 0; int longestZigZag(TreeNode* root) { dfs(root, true, 0); dfs(root, false, 0); return maxLength; } void dfs(TreeNode* node, bool isLeft, int length) { if (!node) return; maxLength = std::max(maxLength, length); if (isLeft) { dfs(node->left, false, length + 1); dfs(node->right, true, 1); } else { dfs(node->right, true, length + 1); dfs(node->left, false, 1); } } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 347. Top K Frequent Elements Сложность: medium Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке. Пример: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] 👨‍💻 Алгоритм: 1⃣Подсчет частоты: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums. 2⃣Создание кучи: Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов. 3⃣Возврат результата: Верните k самых частых элементов. 😎 Решение: #include <vector> #include <unordered_map> #include <queue> #include <algorithm> using namespace std; class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> count; for (int num : nums) { count[num]++; } priority_queue<pair<int, int>> heap; for (const auto& [num, freq] : count) { heap.emplace(freq, num); } vector<int> result; for (int i = 0; i < k; ++i) { result.push_back(heap.top().second); heap.pop(); } return result; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 763. Partition Labels Сложность: medium Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей. Пример: Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] 👨‍💻 Алгоритм: 1⃣Создайте словарь для хранения последней позиции каждой буквы в строке. 2⃣Пройдите по строке, отслеживая максимальную позицию текущей части. 3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую. 😎 Решение: class Solution { public: vector<int> partitionLabels(string s) { vector<int> lastPos(26, 0); for (int i = 0; i < s.size(); i++) { lastPos[s[i] - 'a'] = i; } vector<int> partitions; int j = 0, anchor = 0; for (int i = 0; i < s.size(); i++) { j = max(j, lastPos[s[i] - 'a']); if (i == j) { partitions.push_back(i - anchor + 1); anchor = i + 1; } } return partitions; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 267. Palindrome Permutation II Сложность: medium Пример: Input: s = "aabb" Output: ["abba","baab"] 👨‍💻 Алгоритм: 1⃣Подсчёт частоты символов Создаем хеш-таблицу частот. Если количество символов с нечетной частотой больше 1 — палиндром невозможен. 2⃣Формирование первой половины Из каждого символа берём его частоту пополам и формируем строку half. Символ с нечетной частотой (если есть) сохраняем как центральный. 3⃣Генерация палиндромов С помощью backtracking создаём все уникальные перестановки строки half, дополняем их зеркально. Если есть центральный символ — добавляем его в середину. 😎 Решение: class Solution { private: void backtrack(string& half, vector<bool>& used, string& path, string& mid, vector<string>& res) { if (path.size() == half.size()) { string rev = path; reverse(rev.begin(), rev.end()); res.push_back(path + mid + rev); return; } for (int i = 0; i < half.size(); ++i) { if (used[i]) continue; if (i > 0 && half[i] == half[i - 1] && !used[i - 1]) continue; used[i] = true; path.push_back(half[i]); backtrack(half, used, path, mid, res); path.pop_back(); used[i] = false; } } public: vector<string> generatePalindromes(string s) { unordered_map<char, int> freq; for (char c : s) freq[c]++; int oddCount = 0; string mid = "", half = ""; for (auto& [ch, count] : freq) { if (count % 2 != 0) { oddCount++; mid = ch; } half += string(count / 2, ch); } if (oddCount > 1) return {}; sort(half.begin(), half.end()); vector<string> res; vector<bool> used(half.size(), false); string path; backtrack(half, used, path, mid, res); return res; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 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); } } } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1490. Clone N-ary Tree Сложность: medium Дан корень N-арного дерева, верните глубокую копию (клон) дерева. Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей. class Node { public int val; public List<Node> children; } Сериализация входных данных N-арного дерева представлена в порядке обхода по уровням, каждая группа детей разделена значением null (см. примеры). Пример: Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 👨‍💻 Алгоритм: 1⃣Базовый случай: Проверить, является ли входной узел null. Если да, вернуть null. 2⃣Копирование узла: Создать новый узел с таким же значением, как у входного узла. 3⃣Рекурсивное клонирование детей: Рекурсивно клонировать каждого ребёнка входного узла и добавить клонированных детей в список детей нового узла. Вернуть клонированный узел. 😎 Решение: class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; class Solution { public: Node* cloneTree(Node* root) { if (!root) return nullptr; Node* nodeCopy = new Node(root->val); for (Node* child : root->children) { nodeCopy->children.push_back(cloneTree(child)); } return nodeCopy; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 400. Nth Digit Сложность: medium Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]. Пример: Input: n = 3 Output: 3 👨‍💻 Алгоритм: 1⃣Определение диапазона: Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.). Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра. 2⃣Нахождение конкретного числа: Когда определите диапазон, найдите точное число, содержащее n-ю цифру. Определите индекс цифры в этом числе. 3⃣Возвращение n-й цифры: Извлеките и верните n-ю цифру из найденного числа. 😎 Решение: class Solution { public: int findNthDigit(int n) { long length = 1, count = 9, start = 1; while (n > length * count) { n -= length * count; length++; count *= 10; start *= 10; } start += (n - 1) / length; string s = to_string(start); return s[(n - 1) % length] - '0'; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 835. Image Overlap Сложность: medium Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений. Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1. Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются. Верните максимальное возможное перекрытие. Пример: Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]] Output: 3 Explanation: We translate img1 to right by 1 unit and down by 1 unit. 👨‍💻 Алгоритм: 1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия. 2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift). 3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий. 😎 Решение: #include <vector> #include <algorithm> using namespace std; class Solution { public: int shiftAndCount(int xShift, int yShift, vector<vector<int>>& M, vector<vector<int>>& R) { int leftShiftCount = 0, rightShiftCount = 0; int rRow = 0; for (int mRow = yShift; mRow < M.size(); ++mRow) { int rCol = 0; for (int mCol = xShift; mCol < M.size(); ++mCol) { if (M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol]) leftShiftCount++; if (M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol]) rightShiftCount++; rCol++; } rRow++; } return max(leftShiftCount, rightShiftCount); } int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) { int maxOverlaps = 0; for (int yShift = 0; yShift < A.size(); ++yShift) { for (int xShift = 0; xShift < A.size(); ++xShift) { maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B)); maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A)); } } return maxOverlaps; } }; Ставь 👍 и забирай 📚 Базу знаний

Задача: 1240. Tiling a Rectangle with the Fewest Squares Сложность: hard Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник. Пример: Input: n = 2, m = 3 Output: 3 👨‍💻 Алгоритм: 1⃣Инициализация рекурсивной функции: Функция принимает размеры прямоугольника n x m. 2⃣Базовый случай: Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия. 3⃣Рекурсивный случай: Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m). Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части: Прямоугольник слева от квадрата. Прямоугольник сверху от квадрата. Прямоугольник справа и снизу от квадрата. 😎 Решение: class Solution { public: int tilingRectangle(int n, int m) { vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX)); for (int i = 1; i <= min(n, m); ++i) { dp[i][i] = 1; } for (int h = 1; h <= n; ++h) { for (int w = 1; w <= m; ++w) { if (h == w) continue; for (int i = 1; i <= h / 2; ++i) { dp[h][w] = min(dp[h][w], dp[i][w] + dp[h - i][w]); } for (int j = 1; j <= w / 2; ++j) { dp[h][w] = min(dp[h][w], dp[h][j] + dp[h][w - j]); } } } return dp[n][m]; } }; Ставь 👍 и забирай 📚 Базу знаний