C/C++ | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد
الشبكة:3 232
المشتركون
-324 ساعات
-27 أيام
-830 أيام
أرشيف المشاركات
3 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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;
}
};3 232
Задача: 1370. Increasing Decreasing String
Сложность: easy
Дана строка s. Переставьте символы строки, используя следующий алгоритм:
Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.
Верните результирующую строку после сортировки s с помощью этого алгоритма.
Пример:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.👨💻 Алгоритм: 1⃣Инициализация и сортировка: Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result. 2⃣Перебор и добавление символов: Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре. 3⃣Проверка завершения: Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result. 😎 Решение:
#include <string>
#include <vector>
class Solution {
public:
std::string sortString(std::string s) {
std::vector<int> charCount(26, 0);
for (char c : s) {
charCount[c - 'a']++;
}
std::string result;
while (result.size() < s.size()) {
for (char c = 'a'; c <= 'z'; c++) {
if (charCount[c - 'a'] > 0) {
result += c;
charCount[c - 'a']--;
}
}
for (char c = 'z'; c >= 'a'; c--) {
if (charCount[c - 'a'] > 0) {
result += c;
charCount[c - 'a']--;
}
}
}
return result;
}
};3 232
Задача: 1271. Hexspeak
Сложность: easy
Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".
Пример:
Input: num = "257" Output: "IOI"👨💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение:
class Solution {
public:
string toHexString(string num) {
stringstream ss;
ss << hex << uppercase << stol(num);
string hexStr = ss.str();
for (char& c : hexStr) {
if (c == '0') c = 'O';
else if (c == '1') c = 'I';
else if (string("ABCDEFIO").find(c) == string::npos) return "ERROR";
}
return hexStr;
}
};3 232
🚨60 минут
Пожизненный PRO-доступ на easyoffer (подготовка к IT-собесам + поиск оффера) по цене одного года закрывается прямо сейчас. Один платёж — доступ навсегда.
Последнее напоминание 👇
👉 https://easyoffer.ru/pro
3 232
⚠️ 3 часа до конца акции.
Последний шанс забрать пожизненный PRO на easyoffer по цене одного года. Это полный доступ к подготовке к собесам и инструментам поиска работы (вопросы с реальных интервью, ответы сеньоров, автоотклики, тренажёры) — один раз и навсегда, вместо ежегодной оплаты.
В полночь цена возвращается к обычной.
👉 https://easyoffer.ru/pro
3 232
Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard
У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: steps = 3, arrLen = 2 Output: 4👨💻 Алгоритм: 1⃣Инициализируйте массив для хранения количества способов достижения каждого индекса на каждом шаге. 2⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 3⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 😎 Решение:
class Solution {
public:
int numWays(int steps, int arrLen) {
const int mod = 1e9 + 7;
int max_pos = min(arrLen - 1, steps);
vector<int> dp(max_pos + 1, 0);
dp[0] = 1;
for (int step = 0; step < steps; ++step) {
vector<int> new_dp(max_pos + 1, 0);
for (int i = 0; i <= max_pos; ++i) {
new_dp[i] = dp[i] % mod;
if (i > 0) new_dp[i] = (new_dp[i] + dp[i - 1]) % mod;
if (i < max_pos) new_dp[i] = (new_dp[i] + dp[i + 1]) % mod;
}
dp = new_dp;
}
return dp[0];
}
};