Уже доступно! Исследование Telegram 2025 — ключевые инсайты года 
C/C++ | LeetCode
Открыть в Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
Больше3 251
Подписчики
-324 часа
-107 дней
-1530 день
Архив постов
3 250
#hard
Задача: 218. The Skyline Problem
Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности.
Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:
lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.
Пример:
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] Explanation: Figure A shows the buildings of the input. Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.👨💻 Алгоритм: 1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights. 2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex). 3️⃣ Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат. 😎 Решение:
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
set<int> edgeSet;
for (auto building : buildings) {
int left = building[0], right = building[1];
edgeSet.insert(left);
edgeSet.insert(right);
}
vector<int> edges(edgeSet.begin(), edgeSet.end());
map<int, int> edgeIndexMap;
for (int i = 0; i < edges.size(); ++i) {
edgeIndexMap[edges[i]] = i;
}
vector<int> heights(edges.size());
for (auto building : buildings) {
int left = building[0], right = building[1], height = building[2];
int leftIndex = edgeIndexMap[left], rightIndex = edgeIndexMap[right];
for (int idx = leftIndex; idx < rightIndex; ++idx) {
heights[idx] = max(heights[idx], height);
}
}
vector<vector<int>> answer;
for (int i = 0; i < heights.size(); ++i) {
int currHeight = heights[i], currPos = edges[i];
if (i == 0 || currHeight != heights[i - 1]) {
answer.push_back({currPos, currHeight});
}
}
return answer;
}
};3 250
#easy
Задача: 217. Contains Duplicate
Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.
Пример:
Input: nums = [1,2,3,4] Output: false👨💻 Алгоритм: 1️⃣ Отсортируйте массив nums по возрастанию. 2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим. 3️⃣ Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false. 😎 Решение:
#include <algorithm>
bool containsDuplicate(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
}3 250
#medium
Задача: 275. H-Index II
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.
Пример:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Найти середину массива: Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n]. 2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]: Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть. Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n]. Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1]. 3️⃣Возвращение результата: Продолжать процесс, пока не будет найден h-индекс. Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid]. 😎 Решение:
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (citations[mid] == n - mid) {
return n - mid;
} else if (citations[mid] < n - mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return n - left;
}
};3 250
#medium
Задача: 274. H-Index
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Пример:
Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Отсортировать массив цитирований по убыванию: Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива. 2️⃣Найти наибольшее значение i, для которого citations[i] > i: Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i. Это значение будет индексом, при котором количество цитирований статьи больше индекса. 3️⃣Рассчитать h-индекс: h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге. 😎 Решение:
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
vector<int> papers(n + 1, 0);
for (int c : citations)
papers[min(n, c)]++;
int k = n;
for (int s = papers[n]; k > s; s += papers[k])
k--;
return k;
}
};3 250
#medium
Задача: 216. Combination Sum III
Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:
Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.
Пример:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.👨💻 Алгоритм: 1️⃣ Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2️⃣ Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3️⃣ Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:
class Solution {
public:
void backtrack(int remain, int k, vector<int>& comb, int next_start,
vector<vector<int>>& results) {
if (remain == 0 && comb.size() == k) {
results.push_back(comb);
return;
} else if (remain < 0 || comb.size() == k) {
return;
}
for (int i = next_start; i < 9; ++i) {
comb.push_back(i + 1);
this->backtrack(remain - i - 1, k, comb, i + 1, results);
comb.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> results;
vector<int> comb;
this->backtrack(n, k, comb, 0, results);
return results;
}
};3 250
#medium
Задача: 215. Kth Largest Element in an Array
Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.
Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.
Пример:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4👨💻 Алгоритм: 1️⃣ Отсортируйте массив в порядке убывания: Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее. 2️⃣ Найдите k-й по величине элемент: После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0). 3️⃣ Верните результат: Возвратите найденное значение как результат. 😎 Решение:
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
return nums[k - 1];
}
};3 250
#hard
Задача: 273. Integer to English Words
Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.
Пример:
Input: num = 123 Output: "One Hundred Twenty Three"👨💻 Алгоритм: 1️⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2️⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3️⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:
class Solution {
public:
string numberToWords(int num) {
if (num == 0) return "Zero";
int i = 0;
string result;
while (num > 0) {
if (num % 1000 != 0) {
result = helper(num % 1000) + thousands[i] + " " + result;
}
num /= 1000;
i++;
}
return trim(result);
}
private:
const vector<string> belowTwenty = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
const vector<string> tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
const vector<string> thousands = {"", "Thousand", "Million", "Billion"};
string helper(int num) {
if (num == 0) return "";
else if (num < 20) return belowTwenty[num] + " ";
else if (num < 100) return tens[num / 10] + " " + helper(num % 10);
else return belowTwenty[num / 100] + " Hundred " + helper(num % 100);
}
string trim(const string& str) {
size_t first = str.find_first_not_of(' ');
size_t last = str.find_last_not_of(' ');
return str.substr(first, (last - first + 1));
}
};3 250
#hard
Задача: 214. Shortest Palindrome
Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.
Верните самый короткий палиндром, который можно получить, выполняя это преобразование.
Пример:
Input: s = "aacecaaa" Output: "aaacecaaa"👨💻 Алгоритм: 1️⃣ Создание обратной строки: Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения. 2️⃣ Итерация для поиска наибольшего палиндрома: Перебирайте индекс i от 0 до size(s) - 1. Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки. Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s. 3️⃣ Возврат результата: Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s. 😎 Решение:
class Solution {
public:
string shortestPalindrome(string s) {
int n = s.size();
string rev(s);
reverse(rev.begin(), rev.end());
for (int i = 0; i < n; i++) {
if (s.substr(0, n - i) == rev.substr(i))
return rev.substr(0, i) + s;
}
return "";
}
};3 250
Прокачай свои скилы с Алексеем Рыбаком! 🚀
Надоели скучные задачи по программированию? 💻
Время перейти на новый уровень!
🎖Приглашаем бекендеров и инженеров инфраструктуры на уникальный трехмесячный курс по системному дизайну и архитектуре высоконагруженных систем от Алексея Рыбака, главы разработки Bumble/Badoo с 20-летним опытом в highload проектировании.
В чем ценность этого курса?
✅ Огненная практика с первых дней обучения на реальных кейсах и собственной инфраструктуре
✅ Погружение «под капот» хайлоад систем, изучение паттернов и приемов масштабирования
✅ Топовые фишки и знания по архитектуре проектов и системному дизайну больших проектов (1-100M DAU)
✅ Живые сессии, брейнштормы, проектирование “у доски”
На выходе у вас появится опыт:
✅ Проектирования сложных систем
✅ Нагрузочного тестирования своей инфраструктуры (выжмете 100К запросов)
✅ Планирования ресурсов для проектов с большим количеством пользователей
✅ Масштабирования IT-проектов
✅ Практический опыт работы с кластерами Redis, CockroachDB и шардированными PostgreSQL/MySQL
✅ И многое другое!
➡️ Регистрируйся и погружайся в нескучный хайлоад
Реклама ИП Рыбак А. А. ИНН 771407709607
3 250
#hard
Задача: 272. Closest Binary Search Tree Value II
Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.
Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]👨💻 Алгоритм: 1️⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив: Пройти по дереву в глубину, добавляя каждое значение узла в массив. 2️⃣Отсортировать массив по расстоянию от целевого значения: Использовать пользовательский компаратор, чтобы отсортировать массив по абсолютному значению разности между элементом массива и целевым значением. 3️⃣Вернуть первые k значений из отсортированного массива: Извлечь первые k элементов из отсортированного массива и вернуть их. 😎 Решение:
class Solution {
public:
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> arr;
dfs(root, arr);
sort(arr.begin(), arr.end(), [target](int o1, int o2) {
return abs(o1 - target) < abs(o2 - target);
});
return vector<int>(arr.begin(), arr.begin() + k);
}
private:
void dfs(TreeNode* node, vector<int>& arr) {
if (!node) return;
arr.push_back(node->val);
dfs(node->left, arr);
dfs(node->right, arr);
}
};3 250
#easy
Задача: 270. Closest Binary Search Tree Value
Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4👨💻 Алгоритм: 1️⃣Построить массив с помощью inorder обхода: Выполнить inorder обход дерева и собрать элементы в отсортированный массив. 2️⃣Найти ближайший элемент: Пройти по массиву и определить элемент, наиболее близкий к целевому значению. 3️⃣Выбрать наименьший из ближайших элементов: Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них. 😎 Решение:
class Solution {
public:
int closestValue(TreeNode* root, double target) {
int closest = root->val;
while (root) {
if (abs(root->val - target) < abs(closest - target)) {
closest = root->val;
} else if (abs(root->val - target) == abs(closest - target)) {
closest = min(root->val, closest);
}
root = target < root->val ? root->left : root->right;
}
return closest;
}
};
3 250
#medium
Задача: 213. House Robber II
Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь.
Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию.
Пример 1:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.👨💻 Алгоритм: 1️⃣ Обработка базовых случаев: Если массив nums пуст, возвращаем 0. Если в массиве nums только один дом, возвращаем значение этого дома. 2️⃣ Разделение задачи на две подзадачи: Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и nums.size() - 2. Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и nums.size() - 1. 3️⃣ Сравнение результатов и возврат максимального значения: Вернуть максимальное значение из двух полученных результатов. 😎 Решение:
#include <vector>
#include <algorithm>
class Solution {
public:
int rob(std::vector<int>& nums) {
if (nums.empty()) return 0;
if (nums.size() == 1) return nums[0];
int max1 = rob_simple(nums, 0, nums.size() - 2);
int max2 = rob_simple(nums, 1, nums.size() - 1);
return std::max(max1, max2);
}
private:
int rob_simple(const std::vector<int>& nums, int start, int end) {
int t1 = 0;
int t2 = 0;
for (int i = start; i <= end; ++i) {
int temp = t1;
int current = nums[i];
t1 = std::max(current + t2, t1);
t2 = temp;
}
return t1;
}
};3 250
#hard
Задача: 269. Alien Dictionary
Есть новый инопланетный язык, который использует английский алфавит. Однако порядок букв в нем неизвестен.
Вам дан список строк words из словаря инопланетного языка. Утверждается, что строки в words отсортированы лексикографически по правилам этого нового языка.
Если это утверждение неверно и данное расположение строк в words не может соответствовать никакому порядку букв, верните "".
В противном случае верните строку из уникальных букв нового инопланетного языка, отсортированных в лексикографическом порядке по правилам нового языка. Если существует несколько решений, верните любое из них.
Пример:
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"👨💻 Алгоритм: 1️⃣Извлечение отношений порядка и создание списков смежности: Извлечь отношения порядка между буквами из слов. Вставить их в список смежности, обрабатывая случаи, когда одно слово является префиксом другого. 2️⃣Подсчет числа входящих ребер: Подсчитать количество входящих ребер (in-degree) для каждой буквы. Построить исходящий список смежности и одновременно считать входящие ребра для каждой буквы. 3️⃣Обход в ширину (BFS): Инициализировать очередь буквами с нулевым in-degree. Выполнять BFS, добавляя буквы в результат, когда их in-degree становится нулевым. Продолжать до тех пор, пока очередь не станет пустой. Проверить наличие циклов и вернуть результат. 😎 Решение:
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
class Solution {
public:
std::string alienOrder(std::vector<std::string>& words) {
std::unordered_map<char, std::unordered_set<char>> adjList;
std::unordered_map<char, int> inDegree;
for (const auto& word : words) {
for (char c : word) {
inDegree[c] = 0;
}
}
for (int i = 0; i < words.size() - 1; ++i) {
std::string firstWord = words[i];
std::string secondWord = words[i + 1];
for (int j = 0; j < std::min(firstWord.size(), secondWord.size()); ++j) {
char c = firstWord[j];
char d = secondWord[j];
if (c != d) {
if (adjList[c].insert(d).second) {
inDegree[d]++;
}
break;
}
}
if (secondWord.size() < firstWord.size() && firstWord.find(secondWord) == 0) {
return "";
}
}
std::queue<char> queue;
for (const auto& entry : inDegree) {
if (entry.second == 0) {
queue.push(entry.first);
}
}
std::string output;
while (!queue.empty()) {
char c = queue.front();
queue.pop();
output += c;
for (char d : adjList[c]) {
if (--inDegree[d] == 0) {
queue.push(d);
}
}
}
if (output.size() < inDegree.size()) {
return "";
}
return output;
}
};3 250
#easy
Задача: 268. Missing Number
Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.
Пример:
Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.👨💻 Алгоритм: 1️⃣Сначала отсортируйте массив nums. 2️⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце. 3️⃣Пройдитесь по отсортированному массиву и для каждого индекса проверьте, что число на этом индексе соответствует ожидаемому (предыдущее число плюс один). Как только вы обнаружите несоответствие, верните ожидаемое число. 😎 Решение:
class Solution {
public:
int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
if (nums.back() != nums.size()) {
return nums.size();
} else if (nums.front() != 0) {
return 0;
}
for (int i = 1; i < nums.size(); ++i) {
int expectedNum = nums[i - 1] + 1;
if (nums[i] != expectedNum) {
return expectedNum;
}
}
return -1;
}
};3 250
#medium
Задача: 251. Flatten 2D Vector
Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.
Реализуйте класс Vector2D:
Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.
Пример:
Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false] Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False👨💻 Алгоритм: 1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента. 2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае. 3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next(). 😎 Решение:
#include <vector>
using namespace std;
class Vector2D {
vector<int> nums;
int position;
public:
Vector2D(vector<vector<int>>& v) : position(-1) {
for (auto& innerList : v) {
nums.insert(nums.end(), innerList.begin(), innerList.end());
}
}
int next() {
position++;
return nums[position];
}
bool hasNext() {
return position + 1 < nums.size();
}
};3 250
#medium
Задача: 267. Palindrome Permutation II
Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.
Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список.
Пример:
Input: s = "aabb" Output: ["abba","baab"]👨💻 Алгоритм: 1️⃣Проверка на возможность палиндромной перестановки: Создаем хеш-таблицу, которая хранит количество вхождений каждого символа строки s. Если количество символов с нечетным количеством вхождений превышает 1, то палиндромная перестановка невозможна, и мы возвращаем пустой список. 2️⃣Генерация первой половины палиндромной строки: Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества. Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно. 3️⃣Генерация всех перестановок первой половины и создание палиндромов: Генерируем все перестановки строки st. Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку. Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома. Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку. 😎 Решение:
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Solution {
private:
unordered_set<string> set;
bool canPermutePalindrome(const string &s, vector<int> &map) {
int count = 0;
for (char c : s) {
int index = static_cast<int>(c);
map[index]++;
if (map[index] % 2 == 0) {
count--;
} else {
count++;
}
}
return count <= 1;
}
void swap(vector<char> &s, int i, int j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
void permute(vector<char> &s, int l, char ch) {
if (l == s.size()) {
string perm(s.begin(), s.end());
string rev = perm;
reverse(rev.begin(), rev.end());
set.insert(perm + (ch == '\0' ? "" : string(1, ch)) + rev);
} else {
for (int i = l; i < s.size(); ++i) {
if (s[l] != s[i] || l == i) {
swap(s, l, i);
permute(s, l + 1, ch);
swap(s, l, i);
}
}
}
}
public:
vector<string> generatePalindromes(const string &s) {
vector<int> map(128, 0);
}3 250
🔥 Клад полезных движух! 🔥
Обрати внимание! Если ты хочешь стать тем самым разработчиком с высокой зарплатой, то мы собрали все что тебе нужно в этих телеграм каналах!
• C/C++ | Вопросы собесов
• C/C++ | Тесты
• C/C++ | Удалёнка
Подпишись, чтобы не потерять ☝️
3 250
#medium
Задача: 250. Count Univalue Subtrees
Дан корень бинарного дерева, верните количество поддеревьев с одинаковыми значениями.
Поддерево с одинаковыми значениями означает, что все узлы поддерева имеют одно и то же значение.
Пример:
Input: root = [5,1,5,5,5,null,5] Output: 4👨💻 Алгоритм: 1️⃣Создайте целочисленную переменную count для подсчета количества поддеревьев с одинаковыми значениями. Инициализируйте её значением 0. 2️⃣Выполните обход в глубину (DFS) для данного бинарного дерева. Выполните dfs(root), где dfs — это рекурсивный метод, который принимает узел TreeNode в качестве параметра, от которого начинается обход. Метод возвращает логическое значение, указывающее, является ли поддерево, укоренённое в этом узле, поддеревом с одинаковыми значениями. Выполните следующие действия в этом методе: Если узел равен null, верните true. Рекурсивно проверьте, образует ли левый потомок поддерево с одинаковыми значениями. Выполните isLeftUniValue = dfs(node.left). Рекурсивно проверьте, образует ли правый потомок поддерево с одинаковыми значениями. Выполните isRightUniValue = dfs(node.right). Если оба потомка образуют поддеревья с одинаковыми значениями, т.е. isLeftUniValue && isRightUniValue равно true, сравните значения потомков узла со значением самого узла. Если левый потомок существует и node.left.val != node.val, верните false, так как значения не совпадают и мы не имеем поддерева с одинаковыми значениями. Аналогично, если правый потомок существует и node.right.val != node.val, верните false. В противном случае, увеличьте count на 1 и верните true. В противном случае, одно или оба поддерева потомков не образуют поддеревья с одинаковыми значениями, поэтому дерево, укоренённое в node, также не может быть таким поддеревом. Верните false. 3️⃣Верните count. 😎 Решение:
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int count = 0;
bool dfs(TreeNode* node) {
if (node == nullptr) {
return true;
}
bool isLeftUniValue = dfs(node->left);
bool isRightUniValue = dfs(node->right);
if (isLeftUniValue && isRightUniValue) {
if (node->left != nullptr && node->left->val != node->val) {
return false;
}
if (node->right != nullptr && node->right->val != node->val) {
return false;
}
count++;
return true;
}
return false;
}
int countUnivalSubtrees(TreeNode* root) {
dfs(root);
return count;
}
};