C/C++ | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:3 239
مشترکین
+124 ساعت
+77 روز
-430 روز
آرشیو پست ها
3 239
Задача: 1009. Complement of Base 10 Integer
Сложность: easy
Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.
Пример:
Input: n = 5 Output: 2👨💻 Алгоритм: 1⃣Определение длины двоичного представления: Найдите длину двоичного представления числа n. 2⃣Создание маски: Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n. 3⃣Вычисление дополнения: Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа. 😎 Решение:
class Solution {
public:
int findComplement(int num) {
int length = sizeof(num) * 8 - __builtin_clz(num);
int mask = (1 << length) - 1;
return num ^ mask;
}
};3 239
Задача: 865. Smallest Subtree with all the Deepest Nodes
Сложность: medium
Дан корень бинарного дерева, глубина каждого узла — это кратчайшее расстояние до корня.
Верните наименьшее поддерево, которое содержит все самые глубокие узлы в исходном дереве.
Узел называется самым глубоким, если у него наибольшая возможная глубина среди всех узлов в дереве.
Поддерево узла — это дерево, состоящее из этого узла и всех его потомков.
Пример:
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
unordered_map<TreeNode*, int> depth = {{nullptr, -1}};
dfs(root, nullptr, depth);
int maxDepth = max_element(depth.begin(), depth.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
})->second;
return answer(root, depth, maxDepth);
}
private:
void dfs(TreeNode* node, TreeNode* parent, unordered_map<TreeNode*, int>& depth) {
if (node) {
depth[node] = depth[parent] + 1;
dfs(node->left, node, depth);
dfs(node->right, node, depth);
}
}
TreeNode* answer(TreeNode* node, unordered_map<TreeNode*, int>& depth, int maxDepth) {
if (!node || depth[node] == maxDepth) return node;
TreeNode* L = answer(node->left, depth, maxDepth);
TreeNode* R = answer(node->right, depth, maxDepth);
return L && R ? node : L ? L : R;
}
};3 239
Задача: 1240. Tiling a Rectangle with the Fewest Squares
Сложность: hard
Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник.
Пример:
Input: n = 2, m = 3 Output: 3👨💻 Алгоритм: 1⃣Инициализация рекурсивной функции: Функция принимает размеры прямоугольника n x m. 2⃣Базовый случай: Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия. 3⃣Рекурсивный случай: Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m). Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части: Прямоугольник слева от квадрата. Прямоугольник сверху от квадрата. Прямоугольник справа и снизу от квадрата. 😎 Решение:
class Solution {
public:
int tilingRectangle(int n, int m) {
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
for (int i = 1; i <= min(n, m); ++i) {
dp[i][i] = 1;
}
for (int h = 1; h <= n; ++h) {
for (int w = 1; w <= m; ++w) {
if (h == w) continue;
for (int i = 1; i <= h / 2; ++i) {
dp[h][w] = min(dp[h][w], dp[i][w] + dp[h - i][w]);
}
for (int j = 1; j <= w / 2; ++j) {
dp[h][w] = min(dp[h][w], dp[h][j] + dp[h][w - j]);
}
}
}
return dp[n][m];
}
};3 239
Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium
Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.
Пример:
Input: function_id = 1, z = 5 Output: [[1,4],[2,3],[3,2],[4,1]]👨💻 Алгоритм: 1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y). 2⃣Перемещение указателей: Если 𝑓(𝑥,𝑦)=𝑧 f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x. 3⃣Повторяем шаги до тех пор, пока 𝑥≤1000 x≤1000 и 𝑦≥1y≥1. 😎 Решение:
class CustomFunction {
public:
int f(int x, int y);
};
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
vector<vector<int>> result;
int x = 1;
int y = 1000;
while (x <= 1000 && y >= 1) {
int value = customfunction.f(x, y);
if (value == z) {
result.push_back({x, y});
x++;
} else if (value < z) {
x++;
} else {
y--;
}
}
return result;
}
};3 239
Задача: 942. DI String Match
Сложность: easy
Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них.
Пример:
Input: s = "IDID" Output: [0,4,1,3,2]👨💻 Алгоритм: 1⃣Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке. 2⃣Создать массив perm длиной n + 1. Пройти по строке s: Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low. Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high. Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm. 3⃣Вернуть массив perm. 😎 Решение:
class Solution {
public:
vector<int> diStringMatch(string s) {
int n = s.size();
int low = 0, high = n;
vector<int> perm(n + 1);
for (int i = 0; i < n; ++i) {
if (s[i] == 'I') {
perm[i] = low++;
} else {
perm[i] = high--;
}
}
perm[n] = low;
return perm;
}
};3 239
Задача: 988. Smallest String Starting From Leaf
Сложность: medium
Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.
Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.
Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.
Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.
Пример:
Input: root = [0,1,2,3,4,3,4] Output: "dba"👨💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:
class Solution {
public:
string ans = "~";
string smallestFromLeaf(TreeNode* root) {
dfs(root, "");
return ans;
}
void dfs(TreeNode* node, string path) {
if (!node) return;
path += (char)(node->val + 'a');
if (!node->left && !node->right) {
reverse(path.begin(), path.end());
if (path < ans) {
ans = path;
}
reverse(path.begin(), path.end());
}
dfs(node->left, path);
dfs(node->right, path);
}
};3 239
Задача: 953. Verifying an Alien Dictionary
Сложность: hard
В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке.
Пример:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true👨💻 Алгоритм: 1⃣Создать словарь для хранения порядка каждой буквы в инопланетном языке. Пройти по каждому слову и сравнить его с последующим словом. 2⃣Для каждого слова, сравнить буквы, используя созданный словарь порядка. Если обнаружена пара слов, нарушающая порядок, вернуть false. 3⃣Если все слова отсортированы правильно, вернуть true. 😎 Решение:
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
unordered_map<char, int> orderMap;
for (int i = 0; i < order.length(); i++) {
orderMap[order[i]] = i;
}
for (int i = 0; i < words.size() - 1; i++) {
if (!compare(words[i], words[i + 1], orderMap)) {
return false;
}
}
return true;
}
private:
bool compare(const string& word1, const string& word2, const unordered_map<char, int>& orderMap) {
int minLength = min(word1.length(), word2.length());
for (int i = 0; i < minLength; i++) {
if (orderMap.at(word1[i]) < orderMap.at(word2[i])) {
return true;
} else if (orderMap.at(word1[i]) > orderMap.at(word2[i])) {
return false;
}
}
return word1.length() <= word2.length();
}
};3 239
Задача: 510. Inorder Successor in BST II
Сложность: medium
Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null.
Последующий узла — это узел с наименьшим ключом, большим, чем node.val.
Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}Input: tree = [5,3,6,2,4,null,null,1], node = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null.👨💻 Алгоритм: 1⃣Проверка правого поддерева Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order. 2⃣Поиск предка Если у узла нет правого потомка, поднимайтесь по дереву до тех пор, пока узел не станет левым потомком своего родителя. Родитель этого узла будет следующим узлом в порядке in-order. 3⃣Возвращение результата Верните найденный узел или null, если следующий узел не найден. 😎 Решение:
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
};
class Solution {
public:
Node* inorderSuccessor(Node* x) {
if (x->right) {
x = x->right;
while (x->left) {
x = x->left;
}
return x;
}
while (x->parent && x == x->parent->right) {
x = x->parent;
}
return x->parent;
}
};3 239
Задача: 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 239
Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy
Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.
Пример:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.👨💻 Алгоритм: 1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице. 2⃣Использовать два вложенных цикла для итерации по каждому элементу матрицы grid, и если элемент отрицательный, увеличить count на 1. 3⃣Вернуть count. 😎 Решение:
class Solution {
public:
int countNegatives(vector<vector<int>>& grid) {
int count = 0;
for (const auto& row : grid) {
for (int element : row) {
if (element < 0) {
count++;
}
}
}
return count;
}
};3 239
Задача: 398. Random Pick Index
Сложность: medium
Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.
Пример:
Input ["Solution", "pick", "pick", "pick"] [[[1, 2, 3, 3, 3]], [3], [1], [3]] Output [null, 4, 0, 2]👨💻 Алгоритм: 1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования. 2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным. 3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса. 😎 Решение:
class Solution {
public:
Solution(vector<int>& nums) : nums(nums) {}
int pick(int target) {
int count = 0;
int result = -1;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == target) {
++count;
if (rand() % count == count - 1) {
result = i;
}
}
}
return result;
}
private:
vector<int> nums;
};3 239
Задача: 933. Number of Recent Calls
Сложность: easy
У вас есть класс RecentCounter, который подсчитывает количество последних запросов за определенный промежуток времени. Реализуйте класс RecentCounter: RecentCounter() Инициализирует счетчик нулем последних запросов. int ping(int t) Добавляет новый запрос в момент времени t, где t представляет собой некоторое время в миллисекундах, и возвращает количество запросов, произошедших за последние 3000 миллисекунд (включая новый запрос). Точнее, возвращается количество запросов, произошедших в диапазоне [t - 3000, t]. Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.
Пример:
Input ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] Output [null, 1, 2, 3, 3]👨💻 Алгоритм: 1⃣Создать класс RecentCounter с конструктором для инициализации пустой очереди. 2⃣Реализовать метод ping, который принимает время запроса t: Добавить t в очередь. Удалить из очереди все запросы, которые не попадают в диапазон [t - 3000, t]. 3⃣Вернуть размер очереди. 😎 Решение:
class RecentCounter {
public:
RecentCounter() {}
int ping(int t) {
q.push(t);
while (q.front() < t - 3000) {
q.pop();
}
return q.size();
}
private:
std::queue<int> q;
};3 239
Задача: 491. Non-decreasing Subsequences
Сложность: medium
Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [4,6,7,7] Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]👨💻 Алгоритм: 1⃣Инициализация и запуск функции обратного отслеживания Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0. 2⃣Функция обратного отслеживания Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента. 3⃣Возврат результата После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его. 😎 Решение:
class Solution {
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
set<vector<int>> result;
vector<int> sequence;
backtrack(nums, 0, sequence, result);
return vector<vector<int>>(result.begin(), result.end());
}
private:
void backtrack(vector<int>& nums, int index, vector<int>& sequence, set<vector<int>>& result) {
if (index == nums.size()) {
if (sequence.size() >= 2) {
result.insert(sequence);
}
return;
}
if (sequence.empty() || sequence.back() <= nums[index]) {
sequence.push_back(nums[index]);
backtrack(nums, index + 1, sequence, result);
sequence.pop_back();
}
backtrack(nums, index + 1, sequence, result);
}
};3 239
Задача: 748. Shortest Completing Word
Сложность: easy
Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.
Пример:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps"👨💻 Алгоритм: 1⃣Извлечь все буквы из licensePlate, игнорируя цифры и пробелы, и создать словарь для подсчета частоты каждой буквы. 2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям. 3⃣Найти самое короткое завершающее слово среди подходящих. 😎 Решение:
class Solution {
public:
string shortestCompletingWord(string licensePlate, vector<string>& words) {
unordered_map<char, int> licenseCount = getCharCount(licensePlate);
string result;
for (const string& word : words) {
if (isCompletingWord(word, licenseCount)) {
if (result.empty() || word.length() < result.length()) {
result = word;
}
}
}
return result;
}
private:
unordered_map<char, int> getCharCount(const string& s) {
unordered_map<char, int> count;
for (char c : s) {
if (isalpha(c)) {
count[tolower(c)]++;
}
}
return count;
}
bool isCompletingWord(const string& word, const unordered_map<char, int>& licenseCount) {
unordered_map<char, int> wordCount;
for (char c : word) {
wordCount[c]++;
}
for (const auto& entry : licenseCount) {
if (wordCount[entry.first] < entry.second) {
return false;
}
}
return true;
}
};3 239
Задача: 1023. Camelcase Matching
Сложность: medium
Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.
Пример:
Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB" Output: [true,false,true,true,false]👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив answer для хранения результатов соответствия каждого запроса шаблону. 2⃣Проверка каждого запроса: Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу. Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса. 3⃣Возврат результата: Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false. Верните массив answer. 😎 Решение:
class Solution {
public:
vector<bool> camelMatch(vector<string>& queries, string pattern) {
vector<bool> answer;
auto matches = [](const string& query, const string& pattern) {
int i = 0, j = 0;
while (i < query.size()) {
if (j < pattern.size() && query[i] == pattern[j]) {
j++;
} else if (isupper(query[i])) {
return false;
}
i++;
}
return j == pattern.size();
};
for (const auto& query : queries) {
answer.push_back(matches(query, pattern));
}
return answer;
}
};3 239
Задача: 1066. Campus Bikes II
Сложность: medium
На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.
Мы назначаем каждому рабочему уникальный велосипед таким образом, чтобы сумма Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом была минимальной.
Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом.
Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]class Solution {
public:
int smallestDistanceSum = INT_MAX;
bool visited[10] = {false};
int findDistance(vector<int>& worker, vector<int>& bike) {
return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1]);
}
void minimumDistanceSum(vector<vector<int>>& workers, int workerIndex,
vector<vector<int>>& bikes, int currDistanceSum) {
if (workerIndex >= workers.size()) {
smallestDistanceSum = min(smallestDistanceSum, currDistanceSum);
return;
}
if (currDistanceSum >= smallestDistanceSum) {
return;
}
for (int bikeIndex = 0; bikeIndex < bikes.size(); bikeIndex++) {
if (!visited[bikeIndex]) {
visited[bikeIndex] = true;
minimumDistanceSum(workers, workerIndex + 1, bikes,
currDistanceSum + findDistance(workers[workerIndex], bikes[bikeIndex]));
visited[bikeIndex] = false;
}
}
}
int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
minimumDistanceSum(workers, 0, bikes, 0);
return smallestDistanceSum;
}
};3 239
Задача: 406. Queue Reconstruction by Height
Сложность: medium
Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).
Пример:
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]👨💻 Алгоритм: 1⃣Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki. 2⃣Создайте пустой список для результата. Вставляйте каждого человека из отсортированного массива в список на позицию, соответствующую значению ki. 3⃣Верните список результата. 😎 Решение:
using namespace std;
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] == b[0] ? a[1] < b[1] : b[0] < a[0];
});
vector<vector<int>> result;
for (const auto& person : people) {
result.insert(result.begin() + person[1], person);
}
return result;
}
};3 239
Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard
Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.
Пример:
Input: digits = ["1","3","5","7"], n = 100 Output: 20👨💻 Алгоритм: 1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре. 2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n. 3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел. 😎 Решение:
class Solution {
public:
int atMostNGivenDigitSet(vector<string>& digits, int n) {
string s = to_string(n);
int K = s.length();
vector<int> dp(K + 1);
dp[K] = 1;
for (int i = K - 1; i >= 0; --i) {
for (const string& d : digits) {
if (d[0] < s[i]) {
dp[i] += pow(digits.size(), K - i - 1);
} else if (d[0] == s[i]) {
dp[i] += dp[i + 1];
}
}
}
for (int i = 1; i < K; ++i) {
dp[0] += pow(digits.size(), i);
}
return dp[0];
}
};3 239
Задача: 1463. Cherry Pickup II
Сложность: hard
Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).
У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).
Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.
Пример:
Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(n, 0)));
for (int row = m - 1; row >= 0; row--) {
for (int col1 = 0; col1 < n; col1++) {
for (int col2 = 0; col2 < n; col2++) {
int result = grid[row][col1];
if (col1 != col2) {
result += grid[row][col2];
}
if (row != m - 1) {
int maxCherries = 0;
for (int newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
for (int newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
maxCherries = max(maxCherries, dp[row + 1][newCol1][newCol2]);
}
}
}
result += maxCherries;
}
dp[row][col1][col2] = result;
}
}
}
return dp[0][0][n - 1];
}
};3 239
Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium
Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.
Пример:
Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de"👨💻 Алгоритм: 1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления. 2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления. 3⃣Создайте новую строку, удалив все помеченные скобки. 😎 Решение:
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack<int> stack;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
stack.push(i);
} else if (s[i] == ')') {
if (!stack.empty()) {
stack.pop();
} else {
s[i] = '*';
}
}
}
while (!stack.empty()) {
s[stack.top()] = '*';
stack.pop();
}
s.erase(remove(s.begin(), s.end(), '*'), s.end());
return s;
}
};