C/C++ | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
إظهار المزيد
الشبكة:3 210
المشتركون
-224 ساعات
-127 أيام
-1730 أيام
أرشيف المشاركات
3 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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;
}
};3 210
Задача: 1025. Divisor Game
Сложность: easy
Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально.
Пример:
Input: n = 2
Output: trueclass Solution {
public:
bool divisorGame(int n) {
return n % 2 == 0;
}
};3 210
Задача: 1272. Remove Interval
Сложность: medium
Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.
Пример:
Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6] Output: [[0,1],[6,7]]👨💻 Алгоритм: 1⃣Итерируйтесь по каждому интервалу в списке intervals. 2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов. 3⃣Добавляйте непересекающиеся части текущего интервала в результат. 😎 Решение:
class Solution {
public:
vector<vector<double>> removeInterval(vector<vector<double>>& intervals, vector<double>& toBeRemoved) {
vector<vector<double>> result;
for (auto& interval : intervals) {
if (interval[0] < toBeRemoved[0]) {
result.push_back({interval[0], min(interval[1], toBeRemoved[0])});
}
if (interval[1] > toBeRemoved[1]) {
result.push_back({max(interval[0], toBeRemoved[1]), interval[1]});
}
}
return result;
}
};3 210
Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Сложность: medium
Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit.
Пример:
Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff |7-7| = 0 <= 4. Therefore, the size of the longest subarray is 2.👨💻 Алгоритм: 1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна. 2⃣Итеративно добавлять элементы в дек, поддерживая условие абсолютной разницы между максимальным и минимальным элементом в окне, чтобы она была не больше limit, при необходимости сдвигая left. 3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат. 😎 Решение:
#include <queue>
#include <vector>
class Solution {
public:
int longestSubarray(std::vector<int>& nums, int limit) {
std::priority_queue<std::pair<int, int>> maxHeap;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> minHeap;
int left = 0, maxLength = 0;
for (int right = 0; right < nums.size(); ++right) {
maxHeap.push({nums[right], right});
minHeap.push({nums[right], right});
while (maxHeap.top().first - minHeap.top().first > limit) {
left = std::min(maxHeap.top().second, minHeap.top().second) + 1;
while (maxHeap.top().second < left) {
maxHeap.pop();
}
while (minHeap.top().second < left) {
minHeap.pop();
}
}
maxLength = std::max(maxLength, right - left + 1);
}
return maxLength;
}
};3 210
Задача: 647. Palindromic Substrings
Сложность: medium
Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.
Пример:
Input: s = "abc" Output: 3👨💻 Алгоритм: 1⃣Инициализируйте счетчик для подсчета палиндромных подстрок. 2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины. 3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется. 😎 Решение:
int expandAroundCenter(const string& s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s[left] == s[right]) {
count++;
left--;
right++;
}
return count;
}
int countSubstrings(string s) {
int totalCount = 0;
for (int i = 0; i < s.length(); i++) {
totalCount += expandAroundCenter(s, i, i);
totalCount += expandAroundCenter(s, i, i + 1);
}
return totalCount;
}3 210
Задача: 813. Largest Sum of Averages
Сложность: medium
Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива.
Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом.
Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.
Пример:
Input: nums = [9,1,2,3,9], k = 3 Output: 20.00000 Explanation: The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20. We could have also partitioned nums into [9, 1], [2], [3, 9], for example. That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.👨💻 Алгоритм: 1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N). 2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i). 3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)). 😎 Решение:
class Solution {
public:
double largestSumOfAverages(vector<int>& A, int K) {
int N = A.size();
vector<double> P(N + 1);
for (int i = 0; i < N; ++i)
P[i + 1] = P[i] + A[i];
vector<double> dp(N);
for (int i = 0; i < N; ++i)
dp[i] = (P[N] - P[i]) / (N - i);
for (int k = 0; k < K - 1; ++k) {
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
dp[i] = max(dp[i], (P[j] - P[i]) / (j - i) + dp[j]);
}
}
}
return dp[0];
}
};3 210
Задача: 1357. Apply Discount Every n Orders
Сложность: medium
В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].
Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).
Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).
Реализуйте класс Cashier:
Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.
Пример:
Input ["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"] [[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]] Output [null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]👨💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами. 2⃣Обработка каждого счета: Создайте метод getBill, который принимает массивы product и amount. Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты. Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу. 3⃣Верните итоговую сумму счета. 😎 Решение:
#include <unordered_map>
#include <vector>
class Cashier {
public:
Cashier(int n, int discount, std::vector<int>& products, std::vector<int>& prices)
: n(n), discount(discount), customerCount(0) {
for (size_t i = 0; i < products.size(); ++i) {
productsPrices[products[i]] = prices[i];
}
}
double getBill(std::vector<int>& product, std::vector<int>& amount) {
customerCount++;
double bill = 0.0;
for (size_t i = 0; i < product.size(); ++i) {
bill += productsPrices[product[i]] * amount[i];
}
if (customerCount % n == 0) {
bill *= (100.0 - discount) / 100.0;
}
return bill;
}
private:
int n;
int discount;
int customerCount;
std::unordered_map<int, int> productsPrices;
};3 210
Задача: 109. Convert Sorted List to Binary Search Tree
Сложность: medium
Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска.
Пример:
Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5]👨💻 Алгоритм: 1⃣Так как список односвязный, для нахождения середины используем два указателя: slow_ptr (двигается на 1 узел) и fast_ptr (на 2 узла). Когда fast_ptr дойдёт до конца, slow_ptr будет в середине. 2⃣Для отделения левой части от средней сохраняем prev_ptr, который указывает на узел перед slow_ptr. Затем делаем prev_ptr->next = nullptr, чтобы отсоединить левую часть списка. 3⃣Рекурсивно строим левое поддерево из головы списка, правое — из mid->next. Базовый случай — если head == mid, это лист, возвращаем его как TreeNode. 😎 Решение:
class Solution {
public:
ListNode* findMiddleElement(ListNode* head) {
ListNode* prevPtr = nullptr;
ListNode* slowPtr = head;
ListNode* fastPtr = head;
while (fastPtr != nullptr && fastPtr->next != nullptr) {
prevPtr = slowPtr;
slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
}
if (prevPtr != nullptr) {
prevPtr->next = nullptr;
}
return slowPtr;
}
TreeNode* sortedListToBST(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode* mid = this->findMiddleElement(head);
TreeNode* node = new TreeNode(mid->val);
if (head == mid) {
return node;
}
node->left = this->sortedListToBST(head);
node->right = this->sortedListToBST(mid->next);
return node;
}
};3 210
Задача: 64. Minimum Path Sum
Сложность: medium
На сетке m x n, заполненной неотрицательными числами, найдите путь от (0, 0) до (m - 1, n - 1) с минимальной суммой.
Можно двигаться только вправо или вниз.
Пример:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7👨💻 Алгоритм: 1⃣Инициализировать матрицу dp такого же размера, где dp[i][j] будет хранить минимальную сумму пути до конца из позиции (i, j) 2⃣Заполнить dp в обратном порядке, начиная с правого нижнего угла. Для каждой ячейки: dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1]) — если оба пути доступны Учитывать границы (последняя строка и столбец) отдельно 3⃣Вернуть dp[0][0] — минимальную сумму пути из начала в конец 😎 Решение:
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i == m - 1 && j != n - 1)
dp[i][j] = grid[i][j] + dp[i][j + 1];
else if (j == n - 1 && i != m - 1)
dp[i][j] = grid[i][j] + dp[i + 1][j];
else if (j != n - 1 && i != m - 1)
dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);
else
dp[i][j] = grid[i][j];
}
}
return dp[0][0];
}
};3 210
Задача: 23. Merge k Sorted Lists
Сложность: medium
Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его.
Пример:
Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6]👨💻 Алгоритм: 1⃣Создаем min-кучу, где приоритетом будет минимальное значение узлов. 2⃣Помещаем в кучу первые элементы всех непустых списков. 3⃣Извлекаем минимальный элемент, добавляем в результат, и если у него есть следующий элемент — помещаем его в кучу. 😎 Решение:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class compare {
public:
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return NULL;
priority_queue<ListNode*, vector<ListNode*>, compare> minheap;
for (int i = 0; i < lists.size(); i++) {
if (lists[i] != NULL)
minheap.push(lists[i]);
}
ListNode* head = NULL;
ListNode* temp1;
while (!minheap.empty()) {
ListNode* temp = minheap.top();
minheap.pop();
if (head == NULL) {
head = temp;
temp1 = temp;
} else {
temp1->next = temp;
temp1 = temp;
}
if (temp->next != NULL) {
minheap.push(temp->next);
}
}
if (temp1 != NULL)
temp1->next = NULL;
return head;
}
};3 210
Задача: 1007. Minimum Domino Rotations For Equal Row
Сложность: medium
В ряду домино, tops[i] и bottoms[i] представляют собой верхнюю и нижнюю половинки i-го домино. (Домино - это плитка с двумя числами от 1 до 6 - по одному на каждой половине плитки.) Мы можем повернуть i-е домино так, чтобы tops[i] и bottoms[i] поменялись значениями. Верните минимальное количество поворотов, чтобы все значения tops были одинаковыми или все значения bottoms были одинаковыми. Если это невозможно сделать, верните -1.
Пример:
Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2] Output: 2👨💻 Алгоритм: 1⃣Проверка кандидатов: Для начала рассмотрим два кандидата для достижения цели: tops[0] и bottoms[0]. Это кандидаты для унификации значений в ряду домино, поскольку если есть решение, один из этих двух кандидатов должен быть в верхней или нижней строке всех домино. 2⃣Подсчет поворотов для каждого кандидата: Для каждого из кандидатов (tops[0] и bottoms[0]) подсчитайте количество поворотов, необходимых для унификации значений во всех tops или во всех bottoms. Если какой-либо домино не может быть повернут для достижения требуемого кандидата, этот кандидат исключается из рассмотрения. 3⃣Возврат минимального количества поворотов: Верните минимальное количество поворотов из всех возможных кандидатов. Если ни один кандидат не подходит, верните -1. 😎 Решение:
class Solution {
public:
int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
auto check = [&](int x) {
int rotations_a = 0, rotations_b = 0;
for (int i = 0; i < tops.size(); ++i) {
if (tops[i] != x && bottoms[i] != x) {
return -1;
} else if (tops[i] != x) {
rotations_a++;
} else if (bottoms[i] != x) {
rotations_b++;
}
}
return min(rotations_a, rotations_b);
};
int rotations = check(tops[0]);
if (rotations != -1 || tops[0] == bottoms[0]) {
return rotations;
} else {
return check(bottoms[0]);
}
}
};3 210
Задача: 728. Self Dividing Numbers
Сложность: hard
Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].
Пример:
Input: left = 1, right = 22 Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]👨💻 Алгоритм: 1⃣Переберите все числа в диапазоне от left до right. 2⃣Для каждого числа проверьте, является ли оно саморазделяющимся: Разделите число на его цифры. Убедитесь, что ни одна цифра не равна нулю и число делится на каждую из своих цифр без остатка. 3⃣Добавьте саморазделяющиеся числа в результативный список и верните его. 😎 Решение:
#include <vector>
using namespace std;
class Solution {
public:
vector<int> selfDividingNumbers(int left, int right) {
vector<int> result;
for (int num = left; num <= right; num++) {
if (isSelfDividing(num)) {
result.push_back(num);
}
}
return result;
}
private:
bool isSelfDividing(int num) {
int n = num;
while (n > 0) {
int digit = n % 10;
if (digit == 0 || num % digit != 0) {
return false;
}
n /= 10;
}
return true;
}
};3 210
Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium
Вам дан массив строк arr. Строка s образуется конкатенацией подпоследовательности arr, содержащей уникальные символы. Верните максимально возможную длину s. Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов.
Пример:
Input: arr = ["un","iq","ue"] Output: 4👨💻 Алгоритм: 1⃣Использование рекурсивного подхода: Для каждой строки в массиве arr проверяем, можем ли мы добавить ее к текущей комбинации уникальных символов. Если можем, добавляем ее и продолжаем рекурсивный вызов для следующей строки. Если не можем, пропускаем текущую строку и переходим к следующей. 2⃣Проверка уникальности символов: Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку. 3⃣Поиск максимальной длины: На каждом шаге обновляем максимальную длину, если текущая комбинация уникальных символов длиннее предыдущей максимальной длины. 😎 Решение:
class Solution {
public:
int maxLength(vector<string>& arr) {
return backtrack(arr, 0, "");
}
private:
bool isUnique(const string& s) {
unordered_set<char> char_set(s.begin(), s.end());
return char_set.size() == s.size();
}
int backtrack(const vector<string>& arr, int index, const string& current) {
if (!isUnique(current)) return 0;
int max_length = current.size();
for (int i = index; i < arr.size(); ++i) {
max_length = max(max_length, backtrack(arr, i + 1, current + arr[i]));
}
return max_length;
}
};3 210
Задача: 89. Gray Code
Сложность: medium
Последовательность Грея длины n — это последовательность 2^n чисел от 0 до 2^n - 1,
в которой каждое следующее число отличается от предыдущего ровно на один бит,
и ни одно число не повторяется.
Пример:
Input: n = 2 Output: [0,1,3,2] Пояснение: бинарный вид: [00, 01, 11, 10]👨💻 Алгоритм: 1⃣Начинаем с добавления 0 в результат — все коды Грея начинаются с нуля. 2⃣Используем DFS с backtracking: перебираем числа, которые отличаются от текущего на один бит (используя current ^ (1 << i)). 3⃣Храним уже использованные числа в unordered_set, чтобы не добавлять повторения. Если длина результата достигла 2^n, возвращаем true. Иначе пробуем добавить подходящее следующее число. Если неудачно — откатываемся назад. 😎 Решение:
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result;
result.push_back(0);
unordered_set<int> isPresent;
isPresent.insert(0);
grayCodeHelper(result, n, isPresent);
return result;
}
private:
bool grayCodeHelper(vector<int> &result, int n,
unordered_set<int> &isPresent) {
if (result.size() == (1 << n)) return true;
int current = result.back();
for (int i = 0; i < n; i++) {
int next = current ^ (1 << i);
if (isPresent.find(next) == isPresent.end()) {
result.push_back(next);
isPresent.insert(next);
if (grayCodeHelper(result, n, isPresent)) return true;
isPresent.erase(next);
result.pop_back();
}
}
return false;
}
};3 210
Задача: 775. Global and Local Inversions
Сложность: medium
Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].
Число глобальных инверсий — это количество различных пар (i, j), где:
0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:
0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.
Пример:
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
int N = A.size();
for (int i = 0; i < N; ++i)
for (int j = i + 2; j < N; ++j)
if (A[i] > A[j]) return false;
return true;
}
};3 210
Задача: 1283. Find the Smallest Divisor Given a Threshold
Сложность: medium
Дан массив целых чисел nums и целое число threshold. Мы выберем положительный целый делитель, разделим все элементы массива на него и суммируем результат деления. Найдите наименьший делитель, такой что результат, упомянутый выше, меньше или равен threshold.
Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).
Гарантируется, что решение существует.
Пример:
Input: nums = [1,2,5,9], threshold = 6 Output: 5 Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).👨💻 Алгоритм: 1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement. 2⃣Итерация по всем делителям от 1 до maxElement: Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог. Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums. 3⃣Проверьте, был ли превышен порог: Если порог не был превышен, текущий делитель является наименьшим делителем, поэтому верните его. Если не найдено возможного делителя, верните -1. 😎 Решение:
class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int maxElement = *max_element(nums.begin(), nums.end());
for (int divisor = 1; divisor <= maxElement; ++divisor) {
int sumOfDivisionResults = 0;
bool thresholdExceeded = true;
for (int num : nums) {
sumOfDivisionResults += (num + divisor - 1) / divisor;
if (sumOfDivisionResults > threshold) {
thresholdExceeded = false;
break;
}
}
if (thresholdExceeded) {
return divisor;
}
}
return -1;
}
};