现已上线！2025 年 Telegram 研究 — 年度关键洞察 
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 260
Задача: 994. Rotting Oranges
Сложность: medium
Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:
0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.
Верните минимальное количество минут, которые должны пройти, пока в ячейке не останется свежих апельсинов. Если это невозможно, верните -1.
Пример:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.👨💻 Алгоритм: 1⃣Инициализация очереди и подсчет апельсинов: Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов. Если нет свежих апельсинов, верните 0. 2⃣Использование BFS для распространения гнили: Выполняйте BFS, начиная с всех гнилых апельсинов, добавленных в очередь. Каждый раз, когда апельсин становится гнилым, уменьшайте счетчик свежих апельсинов. Если свежих апельсинов больше не осталось, верните текущее количество минут. 3⃣Проверка оставшихся свежих апельсинов: Если после завершения BFS все еще остаются свежие апельсины, верните -1. 😎 Решение:
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
queue<pair<int, int>> q;
int freshCount = 0;
int minutes = 0;
vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 2) {
q.push({i, j});
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
if (freshCount == 0) return 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
auto [x, y] = q.front(); q.pop();
for (auto dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == 1) {
grid[nx][ny] = 2;
freshCount--;
q.push({nx, ny});
}
}
}
if (!q.empty()) {
minutes++;
}
}
return freshCount == 0 ? minutes : -1;
}
};3 260
Задача: 234. Palindrome Linked List
Сложность: easy
Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае.
Пример:
Input: head = [1,2,2,1] Output: true👨💻 Алгоритм: 1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null. 2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся. 3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата. 😎 Решение:
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals;
ListNode* currentNode = head;
while (currentNode != nullptr) {
vals.push_back(currentNode->val);
currentNode = currentNode->next;
}
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (vals[front] != vals[back]) {
return false;
}
front++;
back--;
}
return true;
}
};3 260
Задача: 567. Permutation in String
Сложность: medium
Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.
Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.
Пример:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").
👨💻 Алгоритм:
1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.
2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.
3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.
😎 Решение:
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int s1Len = s1.size(), s2Len = s2.size();
if (s1Len > s2Len) return false;
vector<int> s1Count(26, 0), s2Count(26, 0);
for (int i = 0; i < s1Len; i++) {
s1Count[s1[i] - 'a']++;
s2Count[s2[i] - 'a']++;
}
for (int i = 0; i < s2Len - s1Len; i++) {
if (s1Count == s2Count) return true;
s2Count[s2[i] - 'a']--;
s2Count[s2[i + s1Len] - 'a']++;
}
return s1Count == s2Count;
}
};3 260
Задача: 736. Parse Lisp Expression
Сложность: hard
Нам дан массив asteroids, состоящий из целых чисел, представляющих астероиды в ряд. Для каждого астероида абсолютное значение обозначает его размер, а знак - направление движения (положительное - вправо, отрицательное - влево). Каждый астероид движется с одинаковой скоростью. Определите состояние астероидов после всех столкновений. Если два астероида столкнутся, меньший из них взорвется. Если оба одинакового размера, то взорвутся оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример:
Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))" Output: 14👨💻 Алгоритм: 1⃣Определите функцию для оценки выражений. 2⃣Используйте рекурсивный подход для обработки различных типов выражений (let, add, mult, и переменных). 3⃣Используйте словарь для отслеживания значений переменных с учетом области видимости. 😎 Решение:
class Solution {
public:
int evaluate(string expression) {
return evaluate(expression, {});
}
private:
int evaluate(string expression, unordered_map<string, int> env) {
if (expression[0] != '(') {
if (isdigit(expression[0]) || expression[0] == '-') {
return stoi(expression);
}
return env[expression];
}
vector<string> tokens = tokenize(expression);
if (tokens[0] == "let") {
for (size_t i = 1; i < tokens.size() - 2; i += 2) {
env[tokens[i]] = evaluate(tokens[i + 1], env);
}
return evaluate(tokens.back(), env);
} else if (tokens[0] == "add") {
return evaluate(tokens[1], env) + evaluate(tokens[2], env);
} else if (tokens[0] == "mult") {
return evaluate(tokens[1], env) * evaluate(tokens[2], env);
}
return 0;
}
vector<string> tokenize(const string& expression) {
vector<string> tokens;
string token;
int parens = 0;
istringstream iss(expression);
char c;
while (iss >> c) {
if (c == '(') {
parens++;
if (parens == 1) continue;
} else if (c == ')') {
parens--;
if (parens == 0) {
tokens.push_back(tokenize(token));
token = "";
continue;
}
} else if (c == ' ' && parens == 1) {
if (!token.empty()) {
tokens.push_back(token);
token = "";
}
continue;
}
token += c;
}
if (!token.empty()) {
tokens.push_back(token);
}
return tokens;
}
};3 260
Задача: 482. License Key Formatting
Сложность: easy
Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.
Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные.
Верните переформатированный лицензионный ключ.
Пример:
Input: s = "5F3Z-2e-9-w", k = 4 Output: "5F3Z-2E9W" Explanation: The string s has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed.👨💻 Алгоритм: 1⃣Инициализация Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата. 2⃣Итерация по входной строке в обратном порядке Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count. 3⃣Завершение Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её. 😎 Решение:
class Solution {
public:
string licenseKeyFormatting(string s, int k) {
int count = 0;
string ans;
for (int i = s.length() - 1; i >= 0; i--) {
if (s[i] != '-') {
ans.push_back(toupper(s[i]));
count++;
if (count == k) {
ans.push_back('-');
count = 0;
}
}
}
if (!ans.empty() && ans.back() == '-') {
ans.pop_back();
}
reverse(ans.begin(), ans.end());
return ans;
}
};3 260
Задача: 376. Wiggle Subsequence
Сложность: medium
Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями.
Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными.
В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю.
Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке.
Дан целочисленный массив nums, верните длину самой длинной колеблющейся подпоследовательности из nums.
Пример:
Input: nums = [1,7,4,9,2,5] Output: 6 Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).👨💻 Алгоритм: 1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием. 2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием. 3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания. 😎 Решение:
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2)
return nums.size();
vector<int> up(nums.size(), 0);
vector<int> down(nums.size(), 0);
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
up[i] = max(up[i], down[j] + 1);
} else if (nums[i] < nums[j]) {
down[i] = max(down[i], up[j] + 1);
}
}
}
return 1 + max(down[nums.size() - 1], up[nums.size() - 1]);
}
};3 260
Задача: 1197. Minimum Knight Moves
Сложность: medium
На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0].
У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении.
Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует.
Пример:
Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]👨💻 Алгоритм: 1⃣Инициализация структур данных: Инициализируйте две очереди для хранения координат и расстояний: одну для движения от начальной точки, другую — от конечной точки. Инициализируйте две карты для хранения посещенных координат и расстояний: одну для движения от начальной точки, другую — от конечной точки. 2⃣Реализация двунаправленного поиска в ширину (BFS): Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки. Если круги пересекаются, возвращайте сумму расстояний до точки пересечения. 3⃣Расширение кругов поиска: Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня. Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены. Увеличивайте units на значение, извлеченное из кучи. 😎 Решение:
#include <deque>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int minKnightMoves(int x, int y) {
vector<vector<int>> offsets = {{1, 2}, {2, 1}, {2, -1}, {1, -2},
{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
deque<vector<int>> originQueue = {{0, 0, 0}};
unordered_map<string, int> originDistance = {{"0,0", 0}};
deque<vector<int>> targetQueue = {{x, y, 0}};
unordered_map<string, int> targetDistance = {{to_string(x) + "," + to_string(y), 0}};
while (true) {
auto origin = originQueue.front();
originQueue.pop_front();
string originKey = to_string(origin[0]) + "," + to_string(origin[1]);
if (targetDistance.find(originKey) != targetDistance.end()) {
return origin[2] + targetDistance[originKey];
}
auto target = targetQueue.front();
targetQueue.pop_front();
string targetKey = to_string(target[0]) + "," + to_string(target[1]);
if (originDistance.find(targetKey) != originDistance.end()) {
return target[2] + originDistance[targetKey];
}
for (auto& offset : offsets) {
vector<int> nextOrigin = {origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1};
string nextOriginKey = to_string(nextOrigin[0]) + "," + to_string(nextOrigin[1]);
if (originDistance.find(nextOriginKey) == originDistance.end()) {
originQueue.push_back(nextOrigin);
originDistance[nextOriginKey] = nextOrigin[2];
}
vector<int> nextTarget = {target[0] + offset[0], target[1] + offset[1], target[2] + 1};
string nextTargetKey = to_string(nextTarget[0]) + "," + to_string(nextTarget[1]);
if (targetDistance.find(nextTargetKey) == targetDistance.end()) {
targetQueue.push_back(nextTarget);
targetDistance[nextTargetKey] = nextTarget[2];
}
}
}
}
};3 260
Задача: 1041. Robot Bounded In Circle
Сложность: medium
На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.
Пример:
Input: instructions = "GGLLGG" Output: true👨💻 Алгоритм: 1⃣Понимание поведения робота: Мы анализируем, как робот движется в пределах одной серии команд. Если он вернется в начальную точку или изменит направление после выполнения всех команд, значит, он будет двигаться по замкнутой траектории, что соответствует условию задачи. 2⃣Изменение направления: Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0). 3⃣Обработка команд: Пройдите по всем командам и обновите позицию робота и направление, в котором он движется. Проверка состояния робота: После выполнения всех команд проверьте, вернулся ли робот в начальную точку (0, 0) или изменил направление. Если одно из этих условий выполнено, робот будет двигаться по замкнутой траектории. 😎 Решение:
class Solution {
public:
bool isRobotBounded(string instructions) {
vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int x = 0, y = 0, direction = 0;
for (char instruction : instructions) {
if (instruction == 'G') {
x += directions[direction][0];
y += directions[direction][1];
} else if (instruction == 'L') {
direction = (direction + 3) % 4;
} else if (instruction == 'R') {
direction = (direction + 1) % 4;
}
}
return (x == 0 && y == 0) || direction != 0;
}
};3 260
Задача: 838. Push Dominoes
Сложность: medium
Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо.
Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа.
Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил.
В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.
Пример:
Input: dominoes = ".L.R...LR..L.." Output: "LL.RR.LLRRLL.."👨💻 Алгоритм: 1⃣Пройдите по строке и сохраните индексы и символы не пустых домино в массивы. 2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики. 3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам. 😎 Решение:
class Solution {
public:
string pushDominoes(string dominoes) {
int N = dominoes.size();
vector<int> indexes = {-1};
vector<char> symbols = {'L'};
for (int i = 0; i < N; ++i) {
if (dominoes[i] != '.') {
indexes.push_back(i);
symbols.push_back(dominoes[i]);
}
}
indexes.push_back(N);
symbols.push_back('R');
string ans = dominoes;
for (int idx = 0; idx < indexes.size() - 1; ++idx) {
int i = indexes[idx], j = indexes[idx + 1];
char x = symbols[idx], y = symbols[idx + 1];
if (x == y) {
for (int k = i + 1; k < j; ++k) {
ans[k] = x;
}
} else if (x == 'R' && y == 'L') {
for (int k = i + 1; k < j; ++k) {
if (k - i == j - k) {
ans[k] = '.';
} else if (k - i < j - k) {
ans[k] = 'R';
} else {
ans[k] = 'L';
}
}
}
}
return ans;
}
};3 260
Задача: 375. Guess Number Higher or Lower II
Сложность: easy
Мы играем в угадайку. Правила игры следующие:
Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.
Пример:
Input: n = 1 Output: 0 Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.👨💻 Алгоритм: 1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента. 2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость. 3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы. 😎 Решение:
class Solution {
public:
int calculate(int low, int high) {
if (low >= high)
return 0;
int minres = INT_MAX;
for (int i = low; i <= high; i++) {
int res = i + max(calculate(i + 1, high), calculate(low, i - 1));
minres = min(res, minres);
}
return minres;
}
int getMoneyAmount(int n) {
return calculate(1, n);
}
};3 260
Задача: 653. Two Sum IV - Input is a BST
Сложность: easy
Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.
Пример:
Input: root = [5,3,6,2,4,null,7], k = 9 Output: true👨💻 Алгоритм: 1⃣Выполните обход BST и сохраните все значения узлов в набор. 2⃣Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла. 3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false. 😎 Решение:
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_set<int> seen;
return find(root, k, seen);
}
private:
bool find(TreeNode* node, int k, unordered_set<int>& seen) {
if (!node) return false;
if (seen.count(k - node->val)) return true;
seen.insert(node->val);
return find(node->left, k, seen) || find(node->right, k, seen);
}
};3 260
Задача: 568. Maximum Vacation Days
Сложность: hard
LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения.
Правила и ограничения:
Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник.
Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0.
У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается.
Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j.
Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель.
Пример:
Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]] Output: 12 Explanation: One of the best strategies is: 1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day. (Although you start at city 0, we could also fly to and start at other cities since it is Monday.) 2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days. 3rd week : stay at city 2, and play 3 days and work 4 days. Ans = 6 + 3 + 3 = 12.👨💻 Алгоритм: 1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i]. 2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1). 3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs. 😎 Решение:
class Solution {
public:
int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
int n = flights.size(), k = days[0].size();
vector<vector<int>> memo(n, vector<int>(k, -1));
return dfs(flights, days, memo, 0, 0);
}
private:
int dfs(vector<vector<int>>& flights, vector<vector<int>>& days, vector<vector<int>>& memo, int curCity, int weekNo) {
int n = flights.size(), k = days[0].size();
if (weekNo == k) return 0;
if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
int maxVac = 0;
for (int nextCity = 0; nextCity < n; nextCity++) {
if (curCity == nextCity || flights[curCity][nextCity] == 1) {
maxVac = max(maxVac, days[nextCity][weekNo] + dfs(flights, days, memo, nextCity, weekNo + 1));
}
}
memo[curCity][weekNo] = maxVac;
return maxVac;
}
};3 260
Задача: 359. Logger Rate Limiter
Сложность: easy
Создайте систему логирования, которая получает поток сообщений вместе с их временными метками. Каждое уникальное сообщение должно печататься не чаще, чем раз в 10 секунд (то есть, сообщение, напечатанное во временной метке t, предотвратит печать других идентичных сообщений до временной метки t + 10).
Все сообщения будут приходить в хронологическом порядке. Несколько сообщений могут поступить в одно и то же время.
Реализуйте класс Logger:
Logger() Инициализирует объект логгера.
bool shouldPrintMessage(int timestamp, string message) Возвращает true, если сообщение должно быть напечатано в данной временной метке, в противном случае возвращает false.
Пример:
Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]
Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo"); // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar"); // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo"); // 3 < 11, return false
logger.shouldPrintMessage(8, "bar"); // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21#include <unordered_map>
#include <string>
class Logger {
private:
std::unordered_map<std::string, int> msgDict;
public:
Logger() {}
bool shouldPrintMessage(int timestamp, const std::string& message) {
if (msgDict.find(message) == msgDict.end() || timestamp - msgDict[message] >= 10) {
msgDict[message] = timestamp;
return true;
}
return false;
}
};3 260
📺 База 1000+ реальных собеседований
На программиста, тестировщика, аналитика, проджекта и другие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
3 260
Задача: 1271. Hexspeak
Сложность: easy
Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".
Пример:
Input: num = "257" Output: "IOI"👨💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение:
class Solution {
public:
string toHexString(string num) {
stringstream ss;
ss << hex << uppercase << stol(num);
string hexStr = ss.str();
for (char& c : hexStr) {
if (c == '0') c = 'O';
else if (c == '1') c = 'I';
else if (string("ABCDEFIO").find(c) == string::npos) return "ERROR";
}
return hexStr;
}
};3 260
Задача: 422. Valid Word Square
Сложность: easy
Дан массив строк words, верните true, если он образует правильный квадрат слов.
Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns).
Пример:
Input: words = ["abcd","bnrt","crmy","dtye"] Output: true Explanation: The 1st row and 1st column both read "abcd". The 2nd row and 2nd column both read "bnrt". The 3rd row and 3rd column both read "crmy". The 4th row and 4th column both read "dtye". Therefore, it is a valid word square.👨💻 Алгоритм: 1⃣Инициализируйте переменные: cols для максимальной длины слов в массиве, rows для количества строк в массиве words, и пустой массив newWords для хранения новых слов, представленных каждым столбцом. 2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false. 3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false. 😎 Решение:
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool validWordSquare(vector<string>& words) {
int cols = 0;
int rows = words.size();
vector<string> newWords;
for (auto& word : words) {
cols = max(cols, (int)word.size
}
if (cols != words[0].size() || rows != cols) {
return false;
}
for (int col = 0; col < cols; ++col) {
string newWord;
for (int row = 0; row < rows; ++row) {
if (col < words[row].size()) {
newWord += words[row][col];
}
}
newWords.push_back(newWord);
}
return words == newWords;
}
};3 260
Задача: 245. Shortest Word Distance III
Сложность: medium
Пример:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1👨💻 Алгоритм: 1⃣Пройди по массиву и запоминай индексы, когда встречаются word1 и word2. 2⃣Если слова разные, просто сравнивай текущие позиции и обновляй минимальное расстояние. 3⃣Если слова одинаковые, то для каждого нового вхождения сравнивай с предыдущим и обновляй расстояние. 😎 Решение:
class Solution {
public:
int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
int idx1 = -1, idx2 = -1, minDist = INT_MAX;
bool same = (word1 == word2);
for (int i = 0; i < wordsDict.size(); ++i) {
string word = wordsDict[i];
if (word == word1) {
if (same) {
if (idx1 != -1) {
minDist = min(minDist, i - idx1);
}
idx1 = i;
} else {
idx1 = i;
}
} else if (word == word2) {
idx2 = i;
}
if (idx1 != -1 && idx2 != -1 && !same) {
minDist = min(minDist, abs(idx1 - idx2));
}
}
return minDist;
}
};3 260
Задача: 505. The Maze II
Сложность: medium
В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, верните -1.
Расстояние — это количество пройденных пустых пространств мячиком от начальной позиции (исключительно) до пункта назначения (включительно).
Предположим, что границы лабиринта — это стены. В примере ниже они не указаны.
Пример:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] Output: 12 Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right. The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.👨💻 Алгоритм: 1⃣Инициализация Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь. 2⃣Обход лабиринта Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов. 3⃣Обновление расстояний Если достигнутая новая позиция может быть достигнута меньшим числом шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода верните минимальное расстояние до пункта назначения или -1, если его нельзя достичь. 😎 Решение:
#include <vector>
#include <queue>
#include <array>
using namespace std;
class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size(), n = maze[0].size();
vector<vector<int>> distance(m, vector<int>(n, INT_MAX));
distance[start[0]][start[1]] = 0;
array<array<int, 2>, 4> directions = {{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}};
queue<array<int, 2>> q;
q.push({start[0], start[1]});
while (!q.empty()) {
auto s = q.front(); q.pop();
for (auto& dir : directions) {
int x = s[0] + dir[0], y = s[1] + dir[1], count = 0;
while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
count++;
}
x -= dir[0];
y -= dir[1];
if (distance[s[0]][s[1]] + count < distance[x][y]) {
distance[x][y] = distance[s[0]][s[1]] + count;
q.push({x, y});
}
}
}
return distance[destination[0]][destination[1]] == INT_MAX ? -1 : distance[destination[0]][destination[1]];
}
};3 260
Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium
Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.
Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.
Пример:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = [] Output: [0,1,-1]👨💻 Алгоритм: 1⃣Создание структуры данных и инициализация: Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла. Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла. Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета. 2⃣Инициализация очереди и начальных условий: Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра). Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно. 3⃣Обработка очереди и обновление результата: Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра). Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь. 😎 Решение:
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
unordered_map<int, vector<pair<int, int>>> adj;
for (const auto& edge : redEdges) {
adj[edge[0]].emplace_back(edge[1], 0);
}
for (const auto& edge : blueEdges) {
adj[edge[0]].emplace_back(edge[1], 1);
}
vector<int> answer(n, -1);
vector<vector<bool>> visit(n, vector<bool>(2, false));
queue<tuple<int, int, int>> q;
q.emplace(0, 0, -1);
answer[0] = 0;
visit[0][0] = visit[0][1] = true;
while (!q.empty()) {
auto [node, steps, prevColor] = q.front();
q.pop();
for (const auto& [neighbor, color] : adj[node]) {
if (!visit[neighbor][color] && color != prevColor) {
if (answer[neighbor] == -1) {
answer[neighbor] = steps + 1;
}
visit[neighbor][color] = true;
q.emplace(neighbor, steps + 1, color);
}
}
}
return answer;
}
};3 260
Задача: 589. N-ary Tree Preorder Traversal
Сложность: easy
Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода 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,2,3,6,7,11,14,4,8,12,5,9,13,10]👨💻 Алгоритм: 1⃣Инициализация Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack. 2⃣Итеративный обход Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack. 3⃣Возврат результата Верните список output как результат. 😎 Решение:
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
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:
vector<int> preorder(Node* root) {
vector<int> output;
if (root == nullptr) return output;
stack<Node*> stack;
stack.push(root);
while (!stack.empty()) {
Node* node = stack.top();
stack.pop();
output.push_back(node->val);
for (auto it = node->children.rbegin(); it != node->children.rend(); ++it) {
stack.push(*it);
}
}
return output;
}
};