C/C++ | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر
شبکه:3 218
مشترکین
-124 ساعت
-107 روز
-830 روز
آرشیو پست ها
3 218
Задача: 1033. Moving Stones Until Consecutive
Сложность: medium
На оси X расположены три камня в разных позициях. Вам даны три целых числа a, b и c - позиции камней. За одно движение вы берете камень в конечной точке (т. е. либо в самой низкой, либо в самой высокой позиции камня) и перемещаете его в незанятую позицию между этими конечными точками. Формально, допустим, камни в данный момент находятся в позициях x, y и z, причем x < y < z. Вы берете камень в позиции x или z и перемещаете его в целочисленную позицию k, причем x < k < z и k != y. Игра заканчивается, когда вы больше не можете сделать ни одного хода (то есть камни находятся в трех последовательных позициях). Возвращается целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сыграть, а answer[1] - максимальное количество ходов, которое вы можете сыграть.
Пример:
Input: a = 3, b = 5, c = 1 Output: [1,2]👨💻 Алгоритм: 1⃣Сортировка позиций: Убедитесь, что позиции камней отсортированы в порядке возрастания. Обозначим отсортированные позиции как x, y и z. 2⃣Вычисление минимальных ходов: Если камни уже находятся в последовательных позициях (то есть y - x == 1 и z - y == 1), минимальное количество ходов равно 0. Если два камня находятся в соседних позициях, а третий камень на расстоянии более чем одна позиция, минимальное количество ходов равно 1. В остальных случаях минимальное количество ходов равно 2. 3⃣Вычисление максимальных ходов: Максимальное количество ходов равно сумме расстояний между соседними камнями минус 2, то есть (y - x - 1) + (z - y - 1). 😎 Решение:
vector<int> numMovesStones(int a, int b, int c) {
vector<int> stones = {a, b, c};
sort(stones.begin(), stones.end());
int x = stones[0], y = stones[1], z = stones[2];
int min_moves = (y - x <= 2 || z - y <= 2) ? ((y - x == 1 && z - y == 1) ? 0 : 1) : 2;
int max_moves = (y - x - 1) + (z - y - 1);
return {min_moves, max_moves};
}3 218
Задача: 1168. Optimize Water Distribution in a Village
Сложность: hard
В деревне есть n домов. Мы хотим обеспечить все дома водой, строя колодцы и прокладывая трубы.
Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами.
Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой.
Пример:
Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.class Solution {
public:
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> edgesHeap;
vector<vector<pair<int, int>>> graph(n + 1);
for (int i = 0; i < wells.size(); ++i) {
graph[0].emplace_back(wells[i], i + 1);
edgesHeap.emplace(wells[i], i + 1);
}
for (const auto& pipe : pipes) {
int house1 = pipe[0], house2 = pipe[1], cost = pipe[2];
graph[house1].emplace_back(cost, house2);
graph[house2].emplace_back(cost, house1);
}
unordered_set<int> mstSet{0};
int totalCost = 0;
while (mstSet.size() < n + 1) {
auto [cost, nextHouse] = edgesHeap.top(); edgesHeap.pop();
if (mstSet.count(nextHouse)) continue;
mstSet.insert(nextHouse);
totalCost += cost;
for (const auto& [nextCost, neighbor] : graph[nextHouse]) {
if (!mstSet.count(neighbor)) {
edgesHeap.emplace(nextCost, neighbor);
}
}
}
return totalCost;
}
};3 218
Задача: 680. Valid Palindrome II
Сложность: easy
Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее.
Пример:
Input: s = "aba"
Output: trueclass Solution {
bool checkPalindrome(const string& s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) {
return false;
}
i++;
j--;
}
return true;
}
public:
bool validPalindrome(string s) {
int i = 0;
int j = s.size() - 1;
while (i < j) {
if (s[i] != s[j]) {
return checkPalindrome(s, i, j - 1) || checkPalindrome(s, i + 1, j);
}
i++;
j--;
}
return true;
}
};3 218
Задача: 974. Subarray Sums Divisible by K
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k.
Подмассив — это непрерывная часть массива.
Пример:
Input: nums = [4,5,0,-2,-3,1], k = 5 Output: 7 Explanation: There are 7 subarrays with a sum divisible by k = 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]👨💻 Алгоритм: 1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1. 2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений. 3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k. 😎 Решение:
class Solution {
public:
int subarraysDivByK(vector<int>& nums, int k) {
int prefixMod = 0, result = 0;
vector<int> modGroups(k);
modGroups[0] = 1;
for (int num : nums) {
prefixMod = (prefixMod + num % k + k) % k;
result += modGroups[prefixMod];
modGroups[prefixMod]++;
}
return result;
}
};3 218
Задача: 1801. Number of Orders in the Backlog
Сложность: medium
Дан двумерный целочисленный массив
orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:
- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.
Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.
Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:
- Если это заказ на покупку, вы просматриваете заказ на продажу с наименьшей ценой в списке невыполненных заказов. Если цена этого заказа на продажу меньше или равна цене текущего заказа на покупку, они будут сопоставлены и выполнены, и этот заказ на продажу будет удален из списка. В противном случае заказ на покупку добавляется в список невыполненных заказов.
- Если это заказ на продажу, вы просматриваете заказ на покупку с наибольшей ценой в списке невыполненных заказов. Если цена этого заказа на покупку больше или равна цене текущего заказа на продажу, они будут сопоставлены и выполнены, и этот заказ на покупку будет удален из списка. В противном случае заказ на продажу добавляется в список невыполненных заказов.
Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.
Пример:
Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]] Output: 6👨💻 Алгоритм: 1⃣Обрабатывайте каждый заказ в orders. Для заказа на покупку сравните с самыми дешевыми заказами на продажу в списке и выполняйте их при возможности, иначе добавьте в список. 2⃣Для заказа на продажу сравните с самыми дорогими заказами на покупку в списке и выполняйте их при возможности, иначе добавьте в список. 3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7. 😎 Решение:
class Solution {
public:
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
const int MOD = 1'000'000'007;
priority_queue<pair<int, int>> buyOrders;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> sellOrders;
for (const auto& order : orders) {
int price = order[0], amount = order[1], orderType = order[2];
auto& primaryQueue = orderType == 0 ? sellOrders : buyOrders;
auto& secondaryQueue = orderType == 0 ? buyOrders : sellOrders;
while (amount > 0 && !primaryQueue.empty() &&
(orderType == 0 ? primaryQueue.top().first <= price : primaryQueue.top().first >= price)) {
auto [topPrice, topAmount] = primaryQueue.top();
primaryQueue.pop();
int executedAmount = min(amount, topAmount);
amount -= executedAmount;
if (topAmount > executedAmount)
primaryQueue.emplace(topPrice, topAmount - executedAmount);
}
if (amount > 0)
secondaryQueue.emplace(price, amount);
}
auto countTotalOrders = [](auto& queue) {
long long total = 0;
while (!queue.empty()) {
total = (total + queue.top().second) % MOD;
queue.pop();
}
return total;
};
return (countTotalOrders(buyOrders) + countTotalOrders(sellOrders)) % MOD;
}
};3 218
Задача: 641. Design Circular Deque
Сложность: medium
Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.
Пример:
Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 2, true, true, true, 4]👨💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:
class MyCircularDeque {
public:
MyCircularDeque(int k) : deque(k), front(0), rear(0), size(0), capacity(k) {}
bool insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + capacity) % capacity;
deque[front] = value;
size++;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
deque[rear] = value;
rear = (rear + 1) % capacity;
size++;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
size--;
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + capacity) % capacity;
size--;
return true;
}
int getFront() {
if (isEmpty()) return -1;
return deque[front];
}
int getRear() {
if (isEmpty()) return -1;
return deque[(rear - 1 + capacity) % capacity];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
private:
vector<int> deque;
int front;
int rear;
int size;
int capacity;
};3 218
Задача: 903. Valid Permutations for DI Sequence
Сложность: hard
Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.
Пример:
Input: s = "DID" Output: 5👨💻 Алгоритм: 1⃣Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j. 2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s. 3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1. 😎 Решение:
class Solution {
public:
int numPermsDISequence(string s) {
const int MOD = 1e9 + 7;
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (s[i - 1] == 'D') {
for (int k = j; k < i; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
} else {
for (int k = 0; k < j; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
}
}
}
}
int result = 0;
for (int j = 0; j <= n; j++) {
result = (result + dp[n][j]) % MOD;
}
return result;
}
};3 218
Задача: 58. Length of Last Word
Сложность: easy
Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова.
Слово — это максимальная подстрока без пробелов.
Пример:
Input: s = "Hello World" Output: 5👨💻 Алгоритм: 1⃣Идти с конца строки, пропуская пробелы, чтобы найти конец последнего слова 2⃣Затем считать символы до следующего пробела или начала строки — это и будет длина слова 3⃣Вернуть полученную длину 😎 Решение:
class Solution {
public:
int lengthOfLastWord(string s) {
int p = s.length() - 1;
while (p >= 0 && s[p] == ' ') {
p--;
}
int length = 0;
while (p >= 0 && s[p] != ' ') {
p--;
length++;
}
return length;
}
};3 218
Задача: 846. Hand of Straights
Сложность: medium
У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.
Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.
Пример:
Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]👨💻 Алгоритм: 1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false. 2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand. 3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп: Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount. Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false. Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount. 😎 Решение:
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int groupSize) {
if (hand.size() % groupSize != 0) {
return false;
}
unordered_map<int, int> cardCount;
for (int card : hand) {
cardCount[card]++;
}
sort(hand.begin(), hand.end());
for (int card : hand) {
if (cardCount[card] == 0) {
continue;
}
for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
if (cardCount[nextCard] == 0) {
return false;
}
cardCount[nextCard]--;
}
}
return true;
}
};3 218
Задача: 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 218
Задача: 918. Maximum Sum Circular Subarray
Сложность: medium
Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.
Пример:
Input: nums = [1,-2,3,-2] Output: 3👨💻 Алгоритм: 1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане. 2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива. 3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные). 😎 Решение:
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int kadane(vector<int>& arr) {
int currentSum = arr[0], maxSum = arr[0];
for (int i = 1; i < arr.size(); ++i) {
currentSum = max(arr[i], currentSum + arr[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
int maxKadane = kadane(nums);
int totalSum = accumulate(nums.begin(), nums.end(), 0);
for (int& num : nums) num = -num;
int minKadane = kadane(nums);
return max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
}
};3 218
Задача: 1473. Paint House III
Сложность: hard
Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.
Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.
Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.
Пример:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.class Solution {
public:
int memo[100][100][21];
const int MAX_COST = 1000001;
int findMinCost(vector<int>& houses, vector<vector<int>>& cost, int targetCount, int currIndex, int neighborhoodCount, int prevHouseColor) {
if (currIndex == houses.size()) {
return neighborhoodCount == targetCount ? 0 : MAX_COST;
}
if (neighborhoodCount > targetCount) {
return MAX_COST;
}
if (memo[currIndex][neighborhoodCount][prevHouseColor] != -1) {
return memo[currIndex][neighborhoodCount][prevHouseColor];
}
int minCost = MAX_COST;
if (houses[currIndex] != 0) {
int newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0);
minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
} else {
int totalColors = cost[0].size();
for (int color = 1; color <= totalColors; ++color) {
int newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0);
int currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
minCost = min(minCost, currCost);
}
}
return memo[currIndex][neighborhoodCount][prevHouseColor] = minCost;
}
int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
memset(memo, -1, sizeof(memo));
int answer = findMinCost(houses, cost, target, 0, 0, 0);
return answer == MAX_COST ? -1 : answer;
}
};3 218
Задача: 128. Longest Consecutive Sequence
Сложность: medium
Найти длину самой длинной последовательности последовательных чисел в неотсортированном массиве. Время работы — O(n).
Пример:
Input: [100,4,200,1,3,2] → Output: 4👨💻 Алгоритм: 1⃣Помещаем все числа в unordered_set, чтобы можно было быстро проверять наличие элемента (O(1) время доступа). 2⃣Проходим по каждому числу, и если num - 1 не существует в сете — это начало новой последовательности. Затем увеличиваем currentNum, пока currentNum + 1 есть в сете, считая длину последовательности. 3⃣После проверки каждого числа обновляем longestStreak, если текущая последовательность длиннее. 😎 Решение:
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> numSet(nums.begin(), nums.end());
int longestStreak = 0;
for (int num : numSet) {
if (!numSet.count(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (numSet.count(currentNum + 1)) {
currentNum++;
currentStreak++;
}
longestStreak = max(longestStreak, currentStreak);
}
}
return longestStreak;
}
};3 218
Задача: 100. Same Tree
Сложность: easy
Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.
Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.
Пример:
Input: p = [1,2,3], q = [1,2,3] Output: true👨💻 Алгоритм: 1⃣Если оба узла равны null, значит на этом участке деревья одинаковы. 2⃣Если один из узлов равен null, а второй — нет, или значения узлов различаются, значит деревья не равны. 3⃣Рекурсивно проверьте левое и правое поддерево. 😎 Решение:
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!q || !p) return false;
if (p->val != q->val) return false;
return isSameTree(p->right, q->right) && isSameTree(p->left, q->left);
}
};3 218
Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium
Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.
Пример:
Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)class Solution {
public:
int minFlips(int a, int b, int c) {
int answer = 0;
while (a != 0 || b != 0 || c != 0) {
if ((c & 1) == 1) {
if ((a & 1) == 0 && (b & 1) == 0) {
answer++;
}
} else {
answer += (a & 1) + (b & 1);
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return answer;
}
};3 218
Задача: 1295. Find Numbers with Even Number of Digits
Сложность: easy
Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр.
Пример:
Input: nums = [12,345,2,6,7896] Output: 2 Explanation: 12 contains 2 digits (even number of digits). 345 contains 3 digits (odd number of digits). 2 contains 1 digit (odd number of digits). 6 contains 1 digit (odd number of digits). 7896 contains 4 digits (even number of digits). Therefore only 12 and 7896 contain an even number of digits.👨💻 Алгоритм: 1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false. 2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0. 3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount. 😎 Решение:
class Solution {
public:
bool hasEvenDigits(int num) {
int digitCount = 0;
while (num) {
digitCount++;
num /= 10;
}
return (digitCount & 1) == 0;
}
int findNumbers(vector<int>& nums) {
int evenDigitCount = 0;
for (int num : nums) {
if (hasEvenDigits(num))
evenDigitCount++;
}
return evenDigitCount;
}
};3 218
Задача: 320. Generalized Abbreviation
Сложность: medium
Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.
Например, "abcde" можно сократить следующим образом:
"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:
"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.
Пример:
Input: word = "a" Output: ["1","a"]👨💻 Алгоритм: 1⃣Создание битовых масок Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур. 2⃣Генерация аббревиатур Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик. 3⃣Перебор всех комбинаций Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1. 😎 Решение:
class Solution {
public:
vector<string> generateAbbreviations(string word) {
vector<string> ans;
for (int x = 0; x < (1 << word.length()); ++x)
ans.push_back(abbr(word, x));
return ans;
}
private:
string abbr(const string& word, int x) {
string builder;
int k = 0, n = word.length();
for (int i = 0; i < n; ++i, x >>= 1) {
if ((x & 1) == 0) {
if (k != 0) {
builder += to_string(k);
k = 0;
}
builder += word[i];
} else {
++k;
}
}
if (k != 0) builder += to_string(k);
return builder;
}
};3 218
Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]👨💻 Алгоритм: 1⃣Инициализация указателей: Создать словарь для хранения узлов по их координатам (col, row). Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)). 2⃣Поиск пересечений: Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row). Добавить левый потомок в очередь с координатами (row + 1, col - 1). Добавить правый потомок в очередь с координатами (row + 1, col + 1). 3⃣Возврат результата: Отсортировать ключи словаря по col и затем по row. Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список. 😎 Решение:
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
map<int, vector<pair<int, int>>> colTable;
queue<pair<TreeNode*, pair<int, int>>> queue;
queue.push({root, {0, 0}});
while (!queue.empty()) {
auto [node, pos] = queue.front();
queue.pop();
int row = pos.first, col = pos.second;
colTable[col].emplace_back(row, node->val);
if (node->left) {
queue.push({node->left, {row + 1, col - 1}});
}
if (node->right) {
queue.push({node->right, {row + 1, col + 1}});
}
}
vector<vector<int>> result;
for (auto& [col, pairs] : colTable) {
sort(pairs.begin(), pairs.end());
vector<int> sortedCol;
for (auto& [row, val] : pairs) {
sortedCol.push_back(val);
}
result.push_back(sortedCol);
}
return result;
}
};3 218
Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium
Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.
Пример:
Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм: 1⃣Инициализация Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length). 2⃣Раздвижение окна Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k. 3⃣Обновление максимальной длины На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки. 😎 Решение:
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int left = 0, right = 0;
unordered_map<char, int> charCount;
int maxLength = 0;
while (right < s.length()) {
charCount[s[right]]++;
while (charCount.size() > k) {
charCount[s[left]]--;
if (charCount[s[left]] == 0) {
charCount.erase(s[left]);
}
left++;
}
maxLength = max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
};3 218
Задача: 1256. Encode Number
Сложность: medium
Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.
Пример:
Input: num = 23 Output: "1000"👨💻 Алгоритм: 1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n) 2⃣Из таблицы видно, что последовательность строк соответствует последовательности чисел в двоичной системе счисления за исключением начального значения n = 0. 3⃣Таким образом, можно вывести, что: Для каждого значения n > 0, функция f(n) представляет собой двоичное представление числа (n - 1). 😎 Решение:
class Solution {
public:
string encode(int num) {
if (num == 0) return "";
string binary = "";
num -= 1;
while (num > 0) {
binary = (num % 2 == 0 ? "0" : "1") + binary;
num /= 2;
}
return binary;
}
};