اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
C/C++ | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
نمایش بیشتر3 259
مشترکین
اطلاعاتی وجود ندارد24 ساعت
-17 روز
-430 روز
آرشیو پست ها
3 260
Задача: 1051. Height Checker
Сложность: easy
Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i].
Пример:
Input: heights = [1,1,4,2,1,3] Output: 3👨💻 Алгоритм: 1⃣Создай отсортированную копию массива heights, чтобы получить ожидаемый порядок высот. 2⃣Пройди по обоим массивам и сравни элементы. 3⃣Подсчитай количество индексов, где элементы двух массивов не равны 😎 Решение:
class Solution {
public:
int heightChecker(vector<int>& heights) {
vector<int> expected = heights;
sort(expected.begin(), expected.end());
int count = 0;
for (int i = 0; i < heights.size(); i++) {
if (heights[i] != expected[i]) {
count++;
}
}
return count;
}
};3 260
Задача: 337. House Robber III
Сложность: medium
Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем.
Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь.
Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию.
Пример:
Input: root = [3,4,5,1,3,null,1] Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.👨💻 Алгоритм: 1⃣Инициализация и базовый случай: Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел. Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0]. 2⃣Рекурсивное исследование дерева: В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла. Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся. Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка. 3⃣Возврат результата: В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper. 😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int rob(TreeNode* root) {
auto answer = helper(root);
return max(answer[0], answer[1]);
}
private:
vector<int> helper(TreeNode* node) {
if (node == nullptr) return {0, 0};
auto left = helper(node->left);
auto right = helper(node->right);
int rob = node->val + left[1] + right[1];
int notRob = max(left[0], left[1]) + max(right[0], right[1]);
return {rob, notRob};
}
};3 260
Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium
Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.
A grandparent of a node is the parent of its parent if it exists.
Пример:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.class Solution {
public:
int solve(TreeNode* root, int parent, int gParent) {
if (!root) {
return 0;
}
return solve(root->left, root->val, parent) + solve(root->right, root->val, parent) + (gParent % 2 == 0 ? root->val : 0);
}
int sumEvenGrandparent(TreeNode* root) {
return solve(root, -1, -1);
}
};3 260
Задача: 688. Knight Probability in Chessboard
Сложность: medium
На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1).
Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении.
Каждый раз, когда конь делает ход, он случайным образом выбирает один из восьми возможных ходов (даже если этот ход выведет его за пределы шахматной доски) и перемещается туда.
Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски.
Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы.
Пример:
Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.class Solution {
public:
double knightProbability(int n, int k, int row, int column) {
vector<pair<int, int>> directions = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
{2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
vector dp(k + 1, vector(n, vector<double>(n, 0.0)));
dp[0][row][column] = 1;
for (int moves = 1; moves <= k; moves++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (const auto& direction : directions) {
int prevI = i - direction.first;
int prevJ = j - direction.second;
if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
}
}
}
}
}
double totalProbability = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
totalProbability += dp[k][i][j];
}
}
return totalProbability;
}
};3 260
Задача: 658. Find K Closest Elements
Сложность: easy
Дан отсортированный массив целых чисел arr, два целых числа k и x. Верните k ближайших к x целых чисел в массиве. Результат также должен быть отсортирован в порядке возрастания.
Целое число a ближе к x, чем целое число b, если:
|a - x| < |b - x|, или
|a - x| == |b - x| и a < b.
Пример:
Input: arr = [1,2,3,4,5], k = 4, x = 3 Output: [1,2,3,4]👨💻 Алгоритм: 1⃣Бинарный поиск: Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска. 2⃣Два указателя: Используйте два указателя, чтобы расширять окно, которое содержит k ближайших к x элементов. Начните с ближайших элементов и расширяйте окно, сравнивая элементы слева и справа от текущего окна. 3⃣Сортировка: Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован). 😎 Решение:
class Solution {
public:
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - k;
while (left < right) {
int mid = (left + right) / 2;
if (x - arr[mid] > arr[mid + k] - x) {
left = mid + 1;
} else {
right = mid;
}
}
return vector<int>(arr.begin() + left, arr.begin() + left + k);
}
};3 260
Задача: 915. Partition Array into Disjoint Intervals
Сложность: medium
Задав целочисленный массив nums, разбейте его на два (смежных) подмассива left и right так, чтобы: каждый элемент left был меньше или равен каждому элементу right. left и right были непустыми. left имел наименьший возможный размер. Верните длину left после такого разбиения. Тестовые примеры генерируются такие, что разбиение существует.
Пример:
Input: nums = [5,0,3,8,6] Output: 3👨💻 Алгоритм: 1⃣Создать массив max_left и min_right. 2⃣Заполнить max_left максимальными значениями от начала массива до текущего индекса. Заполнить min_right минимальными значениями от текущего индекса до конца массива. 3⃣Найти индекс, где max_left[i] меньше или равен min_right[i + 1]. Вернуть длину левого подмассива. 😎 Решение:
class Solution {
public:
int partitionDisjoint(vector<int>& nums) {
int n = nums.size();
vector<int> maxLeft(n), minRight(n);
maxLeft[0] = nums[0];
for (int i = 1; i < n; ++i) {
maxLeft[i] = max(maxLeft[i - 1], nums[i]);
}
minRight[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
minRight[i] = min(minRight[i + 1], nums[i]);
}
for (int i = 0; i < n - 1; ++i) {
if (maxLeft[i] <= minRight[i + 1]) {
return i + 1;
}
}
return n;
}
};3 260
Задача: 242. Valid Anagram
Сложность: easy
Даны две строки s и t, вернуть true, если t — анаграмма s
Пример:
Input: s = "anagram", t = "nagaram" Output: true👨💻 Алгоритм: 1⃣Создаем массив из 26 элементов, представляющих счетчики для каждой буквы латинского алфавита 2⃣Увеличиваем счетчик для каждой буквы строки s и уменьшаем для строки t 3⃣Проверяем, что в финале все счетчики равны нулю — значит, строки состоят из одинаковых букв с одинаковыми частотами 😎 Решение:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int count[26] = {0};
for (int i = 0; i < s.size(); ++i) {
count[s[i] - 'a']++;
count[t[i] - 'a']--;
}
for (int i : count) {
if (i != 0) return false;
}
return true;
}3 260
Задача: 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Сложность: medium
Дан прямоугольный торт размером h x w и два массива целых чисел horizontalCuts и verticalCuts, где:
horizontalCuts[i] — это расстояние от верхнего края прямоугольного торта до i-го горизонтального разреза,
verticalCuts[j] — это расстояние от левого края прямоугольного торта до j-го вертикального разреза.
Верните максимальную площадь кусочка торта после разрезания в каждом горизонтальном и вертикальном положении, указанном в массивах horizontalCuts и verticalCuts. Так как ответ может быть очень большим числом, верните его по модулю 10^9 + 7.
Пример:
Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts.
After you cut the cake, the green piece of cake has the maximum area.class Solution {
public:
int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
sort(horizontalCuts.begin(), horizontalCuts.end());
sort(verticalCuts.begin(), verticalCuts.end());
long long maxHeight = max(horizontalCuts[0], h - horizontalCuts.back());
for (int i = 1; i < horizontalCuts.size(); ++i) {
maxHeight = max(maxHeight, (long long)horizontalCuts[i] - horizontalCuts[i - 1]);
}
long long maxWidth = max(verticalCuts[0], w - verticalCuts.back());
for (int i = 1; i < verticalCuts.size(); ++i) {
maxWidth = max(maxWidth, (long long)verticalCuts[i] - verticalCuts[i - 1]);
}
return (maxHeight * maxWidth) % 1000000007;
}
};3 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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 260
Задача: 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;
};