متاح الآن! بحث تيليغرام 2025 — أهم رؤى العام 
C/C++ | LeetCode
الذهاب إلى القناة على Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
إظهار المزيد3 259
المشتركون
لا توجد بيانات24 ساعات
-17 أيام
-430 أيام
أرشيف المشاركات
3 259
Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed
Сложность: hard
RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента.
Реализуйте класс RandomizedCollection:
RandomizedCollection(): Инициализирует пустой объект RandomizedCollection.
bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае.
bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них.
int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество.
Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени.
Пример:
Input ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"] [[], [1], [1], [2], [], [1], []] Output [null, true, false, true, 2, true, 1]👨💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества. 2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае. Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента. 😎 Решение:
using namespace std;
class RandomizedCollection {
public:
RandomizedCollection() {}
bool insert(int val) {
bool exists = dict.find(val) != dict.end();
if (!exists) {
dict[val] = unordered_set<int>();
}
dict[val].insert(list.size());
list.push_back(val);
return !exists;
}
bool remove(int val) {
if (dict.find(val) == dict.end() || dict[val].empty()) {
return false;
}
int index = *dict[val].begin();
dict[val].erase(index);
int lastElement = list.back();
list[index] = lastElement;
dict[lastElement].insert(index);
dict[lastElement].erase(list.size() - 1);
list.pop_back();
if (dict[val].empty()) {
dict.erase(val);
}
return true;
}
int getRandom() {
int randomIndex = rand() % list.size();
return list[randomIndex];
}
private:
unordered_map<int, unordered_set<int>> dict;
vector<int> list;
};3 259
Задача: 1036. Escape a Large Maze
Сложность: hard
Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false👨💻 Алгоритм: 1⃣Обработка входных данных: Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked. 2⃣Проверка простого случая: Если список blocked пуст, верните true, так как путь не будет заблокирован. Проверка начальной или целевой клетки: Если исходная или целевая клетка заблокированы, верните false. 3⃣Поиск пути с использованием BFS или DFS: Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток. Если обнаружен путь, верните true, в противном случае верните false. 😎 Решение:
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
set<pair<int, int>> blocked_set;
for (const auto& b : blocked) {
blocked_set.emplace(b[0], b[1]);
}
if (blocked_set.count({source[0], source[1]}) || blocked_set.count({target[0], target[1]})) {
return false;
}
auto bfs = [&](vector<int>& start, vector<int>& end) {
queue<pair<int, int>> q;
q.push({start[0], start[1]});
set<pair<int, int>> visited;
visited.emplace(start[0], start[1]);
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int max_area = blocked.size() * (blocked.size() - 1) / 2;
while (!q.empty()) {
if (visited.size() > max_area) {
return true;
}
auto [x, y] = q.front();
q.pop();
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < 1'000'000 && ny >= 0 && ny < 1'000'000 && !visited.count({nx, ny}) && !blocked_set.count({nx, ny})) {
if (nx == end[0] && ny == end[1]) {
return true;
}
q.push({nx, ny});
visited.emplace(nx, ny);
}
}
}
return false;
};
return bfs(source, target) && bfs(target, source);
}
};3 259
Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard
Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.
Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.
Пример:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
int groupId = m;
for (int i = 0; i < n; ++i) if (group[i] == -1) group[i] = groupId++;
vector<vector<int>> itemGraph(n), groupGraph(groupId);
vector<int> itemIndegree(n, 0), groupIndegree(groupId, 0);
for (int curr = 0; curr < n; ++curr) {
for (int prev : beforeItems[curr]) {
itemGraph[prev].push_back(curr);
itemIndegree[curr]++;
if (group[curr] != group[prev]) {
groupGraph[group[prev]].push_back(group[curr]);
groupIndegree[group[curr]]++;
}
}
}
vector<int> itemOrder = topologicalSort(itemGraph, itemIndegree);
vector<int> groupOrder = topologicalSort(groupGraph, groupIndegree);
if (itemOrder.empty() || groupOrder.empty()) return {};
unordered_map<int, vector<int>> orderedGroups;
for (int item : itemOrder) orderedGroups[group[item]].push_back(item);
vector<int> answerList;
for (int groupIndex : groupOrder) answerList.insert(answerList.end(), orderedGroups[groupIndex].begin(), orderedGroups[groupIndex].end());
return answerList;
}
private:
vector<int> topologicalSort(const vector<vector<int>>& graph, vector<int>& indegree) {
vector<int> visited;
stack<int> stack;
for (int i = 0; i < graph.size(); ++i) if (indegree[i] == 0) stack.push(i);
while (!stack.empty()) {
int curr = stack.top();
stack.pop();
visited.push_back(curr);
for (int next : graph[curr]) if (--indegree[next] == 0) stack.push(next);
}
return visited.size() == graph.size() ? visited : vector<int>();
}
};3 259
Задача: 909. Snakes and Ladders
Сложность: medium
Вам дана доска с целочисленной матрицей n x n, клетки которой помечены метками от 1 до n2 в стиле Бустрофедона, начиная с левого нижнего края доски (т.е. board[n - 1][0]) и чередуя направление в каждой строке. Вы начинаете на клетке 1 доски. В каждый ход, начиная с клетки curr, вы делаете следующее: выбираете клетку назначения next с меткой в диапазоне [curr + 1, min(curr + 6, n2)]. Этот выбор имитирует результат стандартного броска 6-гранного кубика: то есть всегда существует не более 6 мест назначения, независимо от размера доски. Если next имеет змейку или лестницу, вы должны двигаться к месту назначения этой змейки или лестницы. В противном случае вы переходите на следующий. Игра заканчивается, когда вы достигаете клетки n2. Клетка доски в строке r и столбце c имеет змейку или лестницу, если board[r][c] != -1. Местом назначения этой змейки или лестницы является доска[r][c]. В клетках 1 и n2 нет змейки или лестницы. Обратите внимание, что вы можете взять змейку или лестницу не более одного раза за ход. Если конечный пункт змейки или лестницы является началом другой змейки или лестницы, вы не ходите по последующей змейке или лестнице. Например, предположим, что доска имеет вид [[-1,4],[-1,3]], и на первом ходу ваш конечный квадрат - 2. Вы ходите по лестнице до квадрата 3, но не ходите по последующей лестнице до 4. Верните наименьшее количество ходов, необходимое для достижения квадрата n2. Если достичь квадрата невозможно, верните -1.
Пример:
Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]] Output: 4👨💻 Алгоритм: 1⃣Представить доску в виде одномерного массива, чтобы легко определить позицию следующего хода. 2⃣Использовать BFS (поиск в ширину) для минимизации количества ходов до клетки n2. В каждом ходе проверять клетки от curr + 1 до min(curr + 6, n2) и перемещаться по змейкам и лестницам, если они существуют. 3⃣Если достижение клетки n2 невозможно, вернуть -1. 😎 Решение:
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
auto getPos = [&](int x) {
int quot = (x - 1) / n;
int rem = (x - 1) % n;
int row = n - 1 - quot;
int col = (row % 2 != n % 2) ? rem : n - 1 - rem;
return make_pair(row, col);
};
unordered_set<int> visited;
queue<pair<int, int>> q;
q.push({1, 0});
while (!q.empty()) {
auto [pos, steps] = q.front();
q.pop();
for (int i = 1; i <= 6; i++) {
int nextPos = pos + i;
if (nextPos > n * n) continue;
auto [r, c] = getPos(nextPos);
if (board[r][c] != -1) {
nextPos = board[r][c];
}
if (nextPos == n * n) {
return steps + 1;
}
if (!visited.count(nextPos)) {
visited.insert(nextPos);
q.push({nextPos, steps + 1});
}
}
}
return -1;
}
};3 259
Задача: 232. Implement Queue using Stacks
Сложность: easy
Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty).
Реализуйте класс MyQueue:
void push(int x) добавляет элемент x в конец очереди.
int pop() удаляет элемент из начала очереди и возвращает его.
int peek() возвращает элемент из начала очереди.
boolean empty() возвращает true, если очередь пуста, и false в противном случае.
Пример:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
class MyQueue {
private:
stack<int> s1, s2;
int front;
public:
void push(int x) {
if (s1.empty())
front = x;
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
s2.push(x);
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
int pop() {
int res = s1.top();
s1.pop();
if (!s1.empty())
front = s1.top();
return res;
}
bool empty() {
return s1.empty();
}
int peek() {
return front;
}
};3 259
Задача: 1027. Longest Arithmetic Subsequence
Сложность: medium
Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).
Пример:
Input: nums = [3,6,9,12] Output: 4👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на элементе i с разностью d. 2⃣Заполнение массива dp: Пройдитесь по каждому элементу массива nums. Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j]. Обновите dp[i][d] на основе значения dp[j][d]. 3⃣Поиск максимальной длины: Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d]. 😎 Решение:
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
vector<unordered_map<int, int>> dp(n);
int max_length = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int diff = nums[i] - nums[j];
if (dp[j].count(diff)) {
dp[i][diff] = dp[j][diff] + 1;
} else {
dp[i][diff] = 2; // Start a new sequence
}
max_length = max(max_length, dp[i][diff]);
}
}
return max_length;
}
};3 259
Задача: 973. K Closest Points to Origin
Сложность: medium
Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).
Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).
Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).
Пример:
Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].👨💻 Алгоритм: 1⃣Отсортируйте массив с помощью функции компаратора. 2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек. 3⃣Верните первые k элементов массива. 😎 Решение:
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
sort(points.begin(), points.end(), [&](vector<int>& a, vector<int>& b) {
return squaredDistance(a) < squaredDistance(b);
});
return vector<vector<int>>(points.begin(), points.begin() + k);
}
private:
int squaredDistance(vector<int>& point) {
return point[0] * point[0] + point[1] * point[1];
}
};3 259
Задача: 849. Maximize Distance to Closest Person
Сложность: medium
Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).
Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.
Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.
Верните это максимальное расстояние до ближайшего человека.
Пример:
Input: seats = [1,0,0,0,1,0,1] Output: 2 Explanation: If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2. If Alex sits in any other open seat, the closest person has distance 1. Thus, the maximum distance to the closest person is 2.👨💻 Алгоритм: 1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i. 2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места. 3⃣Найдите и верните максимальное расстояние до ближайшего занятого места. 😎 Решение:
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int N = seats.size();
int prev = -1, future = 0;
int ans = 0;
for (int i = 0; i < N; ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < N && (seats[future] == 0 || future < i)) {
future++;
}
int left = prev == -1 ? N : i - prev;
int right = future == N ? N : future - i;
ans = max(ans, min(left, right));
}
}
return ans;
}
};3 259
Задача: 292. Nim Game
Сложность: easy
Вы играете в игру, где по очереди с другом берёте от 1 до 3 камней из кучи. Побеждает тот, кто берёт последний камень. Определите, можете ли вы выиграть, если ходите первым и оба играете оптимально.
Пример:
Input: n = 4 Output: false👨💻 Алгоритм 1⃣Если n % 4 == 0, вы не можете выиграть. Независимо от вашего хода, друг сможет вернуть ситуацию к кратному 4 и в итоге победить. 2⃣Если n % 4 != 0, вы можете начать с такого хода, чтобы оставить другу 4, и после этого повторять стратегию. 3⃣Решение тривиальное: просто верните n % 4 != 0. 😎 Решение
class Solution {
public:
bool canWinNim(int n) {
return n % 4 != 0;
}
};3 259
Задача: 1259. Handshakes That Don't Cross
Сложность: hard
Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.
Пример:
Input: numPeople = 4 Output: 2👨💻 Алгоритм: 1⃣Определим массив для хранения каталановых чисел. 2⃣Заполним массив каталановых чисел с помощью рекуррентной формулы. 3⃣Вернем 𝐶𝑛𝑢𝑚𝑃𝑒𝑜𝑝𝑙𝑒/2C. 😎 Решение:
class Solution {
public:
int numHandshakes(int numPeople) {
int n = numPeople / 2;
vector<int> catalan(n + 1, 0);
catalan[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
catalan[i] += catalan[j] * catalan[i - 1 - j];
}
}
return catalan[n];
}
};3 259
Задача: 635. Design Log Storage System
Сложность: medium
Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.
Пример:
Input ["LogSystem", "put", "put", "put", "retrieve", "retrieve"] [[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]] Output [null, null, null, null, [3, 2, 1], [2, 1]]👨💻 Алгоритм: 1⃣Инициализация и хранение журналов: Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения. 2⃣Формирование диапазона: Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity. 3⃣Фильтрация и возврат результатов: Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон. 😎 Решение:
class LogSystem {
public:
LogSystem() {
granularity = {{"Year", 4}, {"Month", 7}, {"Day", 10}, {"Hour", 13}, {"Minute", 16}, {"Second", 19}};
}
void put(int id, string timestamp) {
logs.push_back({id, timestamp});
}
vector<int> retrieve(string start, string end, string granularity) {
int length = this->granularity[granularity];
start = start.substr(0, length);
end = end.substr(0, length);
vector<int> result;
for (const auto& log : logs) {
string ts = log.timestamp.substr(0, length);
if (start <= ts && ts <= end) {
result.push_back(log.id);
}
}
return result;
}
private:
struct Log {
int id;
string timestamp;
};
vector<Log> logs;
unordered_map<string, int> granularity;
};3 259
Задача: 916. Word Subsets
Сложность: medium
Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.
Пример:
Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"] Output: ["facebook","google","leetcode"]👨💻 Алгоритм: 1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2. 2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2. 3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию. 😎 Решение:
class Solution {
public:
vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
vector<int> maxCount(26, 0);
for (const string& word : words2) {
vector<int> count = getCount(word);
for (int i = 0; i < 26; ++i) {
maxCount[i] = max(maxCount[i], count[i]);
}
}
vector<string> result;
for (const string& word : words1) {
vector<int> count = getCount(word);
if (isUniversal(count, maxCount)) {
result.push_back(word);
}
}
return result;
}
private:
vector<int> getCount(const string& word) {
vector<int> count(26, 0);
for (char c : word) {
count[c - 'a']++;
}
return count;
}
bool isUniversal(const vector<int>& count, const vector<int>& maxCount) {
for (int i = 0; i < 26; ++i) {
if (count[i] < maxCount[i]) {
return false;
}
}
return true;
}
};3 259
Задача: 720. Longest Word in Dictionary
Сложность: medium
Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.
Пример:
Input: words = ["w","wo","wor","worl","world"] Output: "world"👨💻 Алгоритм: 1⃣Отсортируйте массив слов по длине и лексикографическому порядку. 2⃣Используйте множество для отслеживания слов, которые можно построить. 3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве. 😎 Решение:
string longestWord(vector<string>& words) {
sort(words.begin(), words.end());
unordered_set<string> validWords;
validWords.insert("");
string longest = "";
for (const string& word : words) {
if (validWords.count(word.substr(0, word.size() - 1))) {
validWords.insert(word);
if (word.size() > longest.size()) {
longest = word;
}
}
}
return longest;
}3 259
🔥Стажировки и вакансии для IT специалистов
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
🤖 ML & DS 👩💻 DevOps
👨✈️ ИБ & OSINT 👣 Go
👩💻 Mobile 👩💻 C#
👩💻 Node.js 👩💻 Python
🔎 QA 👩💻 Java
👩💻 UX/UI 👩💻 Frontend
🖼️ PHP 📋 Analyst
💼 1C 🖥 SQL
👩💻 IT HR
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
3 259
Задача: 737. Sentence Similarity II
Сложность: medium
Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].
Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.
Пример:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]] Output: true👨💻 Алгоритм: 1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false. 2⃣Построить граф схожести слов с использованием словаря. 3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях. 😎 Решение:
class Solution {
public:
bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
if (sentence1.size() != sentence2.size()) {
return false;
}
unordered_map<string, vector<string>> graph;
for (const auto& pair : similarPairs) {
graph[pair[0]].push_back(pair[1]);
graph[pair[1]].push_back(pair[0]);
}
for (size_t i = 0; i < sentence1.size(); ++i) {
if (sentence1[i] != sentence2[i] && !dfs(sentence1[i], sentence2[i], graph, unordered_set<string>())) {
return false;
}
}
return true;
}
private:
bool dfs(const string& word1, const string& word2, unordered_map<string, vector<string>>& graph, unordered_set<string> visited) {
if (word1 == word2) {
return true;
}
visited.insert(word1);
for (const string& neighbor : graph[word1]) {
if (visited.find(neighbor) == visited.end() && dfs(neighbor, word2, graph, visited)) {
return true;
}
}
return false;
}
};3 259
Задача: 405. Convert a Number to Hexadecimal
Сложность: easy
Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи.
Пример:
Input: num = 26 Output: "1a"👨💻 Алгоритм: 1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF. 2⃣Создайте строку с шестнадцатеричными символами. Последовательно делите число на 16 и добавляйте соответствующий символ к результату, пока число не станет равным нулю. 3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0". 😎 Решение:
using namespace std;
class Solution {
public:
string toHex(int num) {
if (num == 0) return "0";
string hexChars = "0123456789abcdef";
unsigned int n = num;
string result;
while (n > 0) {
result.push_back(hexChars[n % 16]);
n /= 16;
}
reverse(result.begin(), result.end());
return result;
}
};3 259
Задача: 1252. Cells with Odd Values in a Matrix
Сложность: easy
Имеется матрица m x n, которая инициализирована всеми 0. Имеется двумерный массив indices, в котором каждый indices[i] = [ri, ci] представляет собой местоположение с индексом 0 для выполнения некоторых операций инкремента над матрицей. Для каждого местоположения indices[i] выполните оба следующих действия: увеличьте все ячейки в строке ri. Увеличьте все ячейки в столбце ci. Учитывая m, n и indices, верните количество нечетных ячеек в матрице после применения инкремента ко всем местоположениям в indices.
Пример:
Input: nums = [12,5,7,23] Output: true👨💻 Алгоритм: 1⃣Инициализируйте два массива: один для подсчета количества инкрементов каждой строки, другой - каждого столбца. 2⃣Для каждого элемента в indices увеличьте счетчики соответствующих строк и столбцов. 3⃣Подсчитайте количество нечетных ячеек, используя информацию о количестве инкрементов каждой строки и столбца. 😎 Решение:
class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& indices) {
vector<int> row_count(m, 0);
vector<int> col_count(n, 0);
for (auto& index : indices) {
row_count[index[0]]++;
col_count[index[1]]++;
}
int odd_count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if ((row_count[i] + col_count[j]) % 2 == 1) {
odd_count++;
}
}
}
return odd_count;
}
};3 259
Задача: 489. Robot Room Cleaner
Сложность: hard
Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.
Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.
Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.
Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.
Разработайте алгоритм для очистки всей комнаты, используя следующие API:
interface Robot {
// возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
// возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
boolean move();
// Робот останется на той же ячейке после вызова turnLeft/turnRight.
// Каждый поворот составляет 90 градусов.
void turnLeft();
void turnRight();
// Очистить текущую ячейку.
void clean();
}Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3 Output: Robot cleaned all rooms. Explanation: All grids in the room are marked by either 0 or 1. 0 means the cell is blocked, while 1 means the cell is accessible. The robot initially starts at the position of row=1, col=3. From the top left corner, its position is one row below and three columns right.👨💻 Алгоритм: 1⃣Пометьте текущую ячейку как посещенную и очистите её. 2⃣Исследуйте четыре направления (вверх, вправо, вниз, влево) последовательно, двигаясь и очищая новые ячейки, если возможно. 3⃣Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо. 😎 Решение:
class Solution {
public:
Robot* robot;
set<pair<int, int>> visited;
vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
void goBack() {
robot->turnRight();
robot->turnRight();
robot->move();
robot->turnRight();
robot->turnRight();
}
void backtrack(int row, int col, int d) {
visited.insert({row, col});
robot->clean();
for (int i = 0; i < 4; ++i) {
int newD = (d + i) % 4;
int newRow = row + directions[newD].first;
int newCol = col + directions[newD].second;
if (visited.find({newRow, newCol}) == visited.end() && robot->move()) {
backtrack(newRow, newCol, newD);
goBack();
}
robot->turnRight();
}
}
void cleanRoom(Robot* robot) {
this->robot = robot;
backtrack(0, 0, 0);
}
};3 259
Задача: 959. Regions Cut By Slashes
Сложность: medium
n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.
Дана сетка grid, представленная в виде строкового массива. Верните количество областей.
Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.
Пример:
Input: grid = [" /","/ "] Output: 2👨💻 Алгоритм: 1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием. 2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов. 3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей. 😎 Решение:
class DSU {
public:
vector<int> parent;
DSU(int N) : parent(N) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unionSet(int x, int y) {
parent[find(x)] = find(y);
}
};
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
int N = grid.size();
DSU dsu(4 * N * N);
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
int root = 4 * (r * N + c);
char val = grid[r][c];
if (val != '\\') {
dsu.unionSet(root + 0, root + 1);
dsu.unionSet(root + 2, root + 3);
}
if (val != '/') {
dsu.unionSet(root + 0, root + 2);
dsu.unionSet(root + 1, root + 3);
}
if (r + 1 < N) {
dsu.unionSet(root + 3, (root + 4 * N) + 0);
}
if (r - 1 >= 0) {
dsu.unionSet(root + 0, (root - 4 * N) + 3);
}
if (c + 1 < N) {
dsu.unionSet(root + 2, (root + 4) + 1);
}
if (c - 1 >= 0) {
dsu.unionSet(root + 1, (root - 4) + 2);
}
}
}
int ans = 0;
for (int x = 0; x < 4 * N * N; ++x) {
if (dsu.find(x) == x) {
++ans;
}
}
return ans;
}
};3 259
Задача: 317. Shortest Distance from All Buildings
Сложность: hard
Дана сетка m x n, содержащая значения 0, 1 или 2, где:
каждое 0 обозначает пустую землю, по которой можно свободно проходить,
каждое 1 обозначает здание, через которое нельзя пройти,
каждое 2 обозначает препятствие, через которое нельзя пройти.
Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо.
Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1.
Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи.
Пример:
Input: grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]] Output: 7👨💻 Алгоритм: 1⃣Инициализация и запуск BFS Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки. 2⃣Обработка BFS и обновление расстояний При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX. 3⃣Обновление и возврат минимального расстояния Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1. 😎 Решение:
#include <vector>
#include <queue>
#include <climits>
using namespace std;
class Solution {
private:
int bfs(vector<vector<int>>& grid, int row, int col, int totalHouses) {
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int rows = grid.size(), cols = grid[0].size();
int distanceSum = 0, housesReached = 0, steps = 0;
queue<pair<int, int>> q;
q.push({row, col});
vector<vector<bool>> vis(rows, vector<bool>(cols, false));
vis[row][col] = true;
while (!q.empty() && housesReached != totalHouses) {
int size = q.size();
while (size-- > 0) {
auto curr = q.front();
q.pop();
int r = curr.first, c = curr.second;
if (grid[r][c] == 1) {
distanceSum += steps;
housesReached++;
continue;
}
for (auto& dir : dirs) {
int nr = r + dir[0], nc = c + dir[1];
if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] != 2) {
vis[nr][nc] = true;
q.push({nr, nc});
}
}
}
steps++;
}
if (housesReached != totalHouses) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 0 && vis[r][c]) grid[r][c] = 2;
}
}
return INT_MAX;
}
return distanceSum;
}
public:
int shortestDistance(vector<vector<int>>& grid) {
int minDistance = INT_MAX, rows = grid.size(), cols = grid[0].size(), totalHouses = 0;
for (const auto& row : grid) for (const auto& cell : row) if (cell == 1) totalHouses++;
for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = min(minDistance, bfs(grid, r, c, totalHouses));
return minDistance == INT_MAX ? -1 : minDistance;
}
};