C/C++ | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Показати більше
Сітка:3 237
Підписники
+124 години
+77 днів
-430 день
Архів дописів
3 237
Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard
Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.
Пример:
Input: stones = [3,2,4,1], k = 2 Output: 20👨💻 Алгоритм: 1⃣Проверка на возможность объединения: Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1. 2⃣Инициализация и динамическое программирование: Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней. Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве. 3⃣Заполнение таблицы dp: Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование. Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения. 😎 Решение:
class Solution {
public:
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
if ((n - 1) % (k - 1) != 0) return -1;
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + stones[i];
}
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int m = k; m <= n; ++m) {
for (int i = 0; i <= n - m; ++i) {
int j = i + m - 1;
dp[i][j] = INT_MAX;
for (int t = i; t < j; t += k - 1) {
dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]);
}
if ((j - i) % (k - 1) == 0) {
dp[i][j] += prefix[j + 1] - prefix[i];
}
}
}
return dp[0][n - 1];
}
};3 237
Задача: 644. Maximum Average Subarray II
Сложность: hard
Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.
Пример:
Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000👨💻 Алгоритм: 1⃣Используйте скользящее окно длины k для нахождения начального среднего значения. 2⃣Перемещайте окно по массиву, добавляя следующий элемент и убирая предыдущий, обновляя текущее среднее значение. 3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон. 😎 Решение:
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
int currSum = accumulate(nums.begin(), nums.begin() + k, 0);
int maxSum = currSum;
for (int i = k; i < n; i++) {
currSum += nums[i] - nums[i - k];
if (currSum > maxSum) {
maxSum = currSum;
}
}
return maxSum / (double) k;
}
};3 237
Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy
Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.
Пример:
Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40] Output: [ "Car 1 Has Passed Road A In Direction 2", // Traffic light on road A is green, car 1 can cross the intersection. "Traffic Light On Road B Is Green", // Car 2 requests green light for road B. "Car 2 Has Passed Road B In Direction 4", // Car 2 crosses as the light is green on road B now. "Car 3 Has Passed Road B In Direction 3", // Car 3 crosses as the light is green on road B now. "Traffic Light On Road A Is Green", // Car 5 requests green light for road A. "Car 5 Has Passed Road A In Direction 1", // Car 5 crosses as the light is green on road A now. "Traffic Light On Road B Is Green", // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B. "Car 4 Has Passed Road B In Direction 3" // Car 4 crosses as the light is green on road B now. ]👨💻 Алгоритм: 1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar. 2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar. 3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков. 😎 Решение:
class TrafficLight {
private:
int greenRoad = 1;
std::mutex mtx;
public:
void carArrived(
int carId,
int roadId,
int direction,
std::function<void()> turnGreen,
std::function<void()> crossCar
) {
std::lock_guard<std::mutex> lock(mtx);
if (greenRoad != roadId) {
turnGreen();
greenRoad = roadId;
}
crossCar();
}
};3 237
Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard
Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.
Пример:
Input: left = 10, right = 15 Output: 5👨💻 Алгоритм: 1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа. 2⃣Создайте функцию для проверки, является ли число простым. 3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом. 😎 Решение:
class Solution {
public:
int countPrimeSetBits(int left, int right) {
int count = 0;
for (int num = left; num <= right; num++) {
if (isPrime(__builtin_popcount(num))) {
count++;
}
}
return count;
}
private:
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
};3 237
Задача: 1406. Stone Game III
Сложность: hard
Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.
Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.
Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.
Пример:
Input: stoneValue = [1,2,3,7] Output: "Bob" Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.👨💻 Алгоритм: 1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0. 2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре. 3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья. 😎 Решение:
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
dp[i] = stoneValue[i] - dp[i + 1];
if (i + 2 <= n) {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2]);
}
if (i + 3 <= n) {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]);
}
}
if (dp[0] > 0) return "Alice";
if (dp[0] < 0) return "Bob";
return "Tie";
}
};3 237
Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard
Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.
Пример:
Input: nums = [1,3,1], k = 1 Output: 0👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Определите минимальное и максимальное возможные расстояния. 3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению. 😎 Решение:
int countPairs(const vector<int>& nums, int mid) {
int count = 0, j = 0;
for (int i = 0; i < nums.size(); i++) {
while (j < nums.size() && nums[j] - nums[i] <= mid) {
j++;
}
count += j - i - 1;
}
return count;
}
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front();
while (left < right) {
int mid = (left + right) / 2;
if (countPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}3 237
Задача: 316. Remove Duplicate Letters
Сложность: medium
Дана строка
s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.
Пример:
Input: s = "bcabc" Output: "abc"👨💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<char> stack;
unordered_set<char> seen;
unordered_map<char, int> lastOccurrence;
for (int i = 0; i < s.size(); ++i) {
lastOccurrence[s[i]] = i;
}
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
if (seen.find(c) == seen.end()) {
while (!stack.empty() && c < stack.back() && i < lastOccurrence[stack.back()]) {
seen.erase(stack.back());
stack.pop_back();
}
seen.insert(c);
stack.push_back(c);
}
}
return string(stack.begin(), stack.end());
}
};3 237
Задача: 724. Find Pivot Index
Сложность: easy
Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.
Пример:
Input: nums = [1,7,3,6,5,6] Output: 3👨💻 Алгоритм: 1⃣Вычислите сумму всех элементов массива. 2⃣Пройдите по массиву, вычисляя текущую сумму элементов слева и проверяя, равна ли она разности между общей суммой и текущей суммой справа. 3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1. 😎 Решение:
int pivotIndex(vector<int>& nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int leftSum = 0;
for (int i = 0; i < nums.size(); i++) {
if (leftSum == totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}3 237
Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard
Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.
Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.
Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.
Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.
Пример:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000class Solution {
public:
double minmaxGasDist(vector<int>& stations, int K) {
int N = stations.size();
vector<double> deltas(N-1);
for (int i = 0; i < N-1; ++i)
deltas[i] = stations[i+1] - stations[i];
vector<vector<double>> dp(N-1, vector<double>(K+1));
for (int i = 0; i <= K; ++i)
dp[0][i] = deltas[0] / (i+1);
for (int p = 1; p < N-1; ++p)
for (int k = 0; k <= K; ++k) {
double bns = numeric_limits<double>::max();
for (int x = 0; x <= k; ++x)
bns = min(bns, max(deltas[p] / (x+1), dp[p-1][k-x]));
dp[p][k] = bns;
}
return dp[N-2][K];
}
};3 237
Задача: 17. Letter Combinations of a Phone Number
Сложность: medium
Дана строка, содержащая цифры от 2 до 9. Необходимо вернуть все возможные комбинации букв, которые может представлять эта строка, согласно клавиатуре мобильного телефона.
Цифра 1 не используется, и для неё нет соответствующих букв.
Пример:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]👨💻 Алгоритм: 1⃣Используем рекурсию и бэктрекинг. Для каждой цифры подставляем все возможные буквы. 2⃣На каждом шаге рекурсивно добавляем буквы для текущей цифры к текущей строке. 3⃣Когда строка достигла длины исходных digits — добавляем комбинацию в результат. 😎 Решение:
class Solution {
public:
void find(string digits, vector<string> v, vector<string>& res, string s, int k) {
if (k >= digits.size()) {
res.push_back(s);
return;
}
int a = digits[k] - '0';
for (int i = 0; i < v[a].size(); i++) {
s += v[a][i];
find(digits, v, res, s, k + 1);
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty()) return res;
vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string s = "";
find(digits, v, res, s, 0);
return res;
}
};3 237
Задача: 839. Similar String Groups
Сложность: hard
Две строки, X и Y, считаются похожими, если либо они идентичны, либо мы можем сделать их эквивалентными, поменяв местами не более двух букв (в разных позициях) в строке X.
Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.
Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?
Пример:
Input: strs = ["tars","rats","arts","star"] Output: 2👨💻 Алгоритм: 1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n. 2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи. 3⃣Верните количество оставшихся групп. 😎 Решение:
class UnionFind {
public:
vector<int> parent;
vector<int> rank;
UnionFind(int size) : parent(size), rank(size, 0) {
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union_set(int x, int y) {
int xset = find(x);
int yset = find(y);
if (xset != yset) {
if (rank[xset] < rank[yset]) {
parent[xset] = yset;
} else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
} else {
parent[yset] = xset;
rank[xset]++;
}
}
}
};
class Solution {
public:
bool isSimilar(const string& a, const string& b) {
int diff = 0;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != b[i]) {
diff++;
}
}
return diff == 0 || diff == 2;
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
UnionFind dsu(n);
int count = n;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (isSimilar(strs[i], strs[j]) && dsu.find(i) != dsu.find(j)) {
count--;
dsu.union_set(i, j);
}
}
}
return count;
}
};3 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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;
}
};