اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
C/C++ | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
نمایش بیشتر3 259
مشترکین
+424 ساعت
-17 روز
-430 روز
آرشیو پست ها
3 259
Задача: 921. Minimum Add to Make Parentheses Valid
Сложность: medium
Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.
Пример:
Input: n = 3, goal = 3, k = 1 Output: 6👨💻 Алгоритм: 1⃣Инициализировать два счетчика open_needed и close_needed. 2⃣Пройти по строке s символ за символом: Если текущий символ - открывающая скобка (, увеличьте open_needed. Если текущий символ - закрывающая скобка ), проверьте: Если open_needed больше 0, уменьшите open_needed. Иначе увеличьте close_needed. 3⃣Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок. 😎 Решение:
class Solution {
public:
int minAddToMakeValid(string s) {
int openNeeded = 0, closeNeeded = 0;
for (char c : s) {
if (c == '(') {
openNeeded++;
} else if (c == ')') {
if (openNeeded > 0) {
openNeeded--;
} else {
closeNeeded++;
}
}
}
return openNeeded + closeNeeded;
}
};3 259
Задача: 923. 3Sum With Multiplicity
Сложность: medium
Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8 Output: 20👨💻 Алгоритм: 1⃣Отсортировать массив arr. 2⃣Инициализировать счетчик для количества кортежей. Пройти по массиву тремя указателями i, j, и k: Для каждого i, установить j на i + 1, и k на конец массива. Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target. 3⃣Вернуть результат по модулю 10^9 + 7. 😎 Решение:
class Solution {
public:
int threeSumMulti(vector<int>& arr, int target) {
sort(arr.begin(), arr.end());
const int MOD = 1'000'000'007;
long long count = 0;
for (int i = 0; i < arr.size(); i++) {
int j = i + 1, k = arr.size() - 1;
while (j < k) {
int sum = arr[i] + arr[j] + arr[k];
if (sum == target) {
if (arr[j] == arr[k]) {
count += (k - j + 1) * (k - j) / 2;
break;
} else {
int left = 1, right = 1;
while (j + 1 < k && arr[j] == arr[j + 1]) {
left++;
j++;
}
while (k - 1 > j && arr[k] == arr[k - 1]) {
right++;
k--;
}
count += (long long)left * right;
j++;
k--;
}
} else if (sum < target) {
j++;
} else {
k--;
}
}
}
return count % MOD;
}
};3 259
Задача: 830. Positions of Large Groups
Сложность: easy
В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.
Верните интервалы каждой большой группы, отсортированные в порядке возрастания начального индекса.
Пример:
Input: s = "abcdddeeeeaabbbcd" Output: [[3,5],[6,9],[12,14]] Explanation: The large groups are "ddd", "eeee", and "bbb".👨💻 Алгоритм: 1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы. 2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат. 3⃣Обновите i = j + 1 и начните новую группу. 😎 Решение:
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<int>> largeGroupPositions(string S) {
vector<vector<int>> ans;
int i = 0, N = S.size();
for (int j = 0; j < N; ++j) {
if (j == N - 1 || S[j] != S[j + 1]) {
if (j - i + 1 >= 3) {
ans.push_back({i, j});
}
i = j + 1;
}
}
return ans;
}
};3 259
Задача: 18. 4Sum
Сложность: medium
Дан массив nums из n целых чисел и целое число target.
Найди все уникальные четверки чисел [nums[a], nums[b], nums[c], nums[d]], такие что сумма равна target, а индексы — различные.
Пример:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]👨💻 Алгоритм: 1⃣Отсортируй массив nums, чтобы можно было применять метод двух указателей. 2⃣Зафиксируй два элемента (a, b) с помощью вложенных циклов, и для оставшихся двух (c, d) используй два указателя. 3⃣Подбирай четверки, сумма которых равна target, и добавляй их в результат, проверяя на уникальность. 😎 Решение:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int a = 0; a < n; a++) {
for (int b = a + 1; b < n; b++) {
int c = b + 1;
int d = n - 1;
while (c < d) {
long long sum = nums[a];
sum += nums[b];
sum += nums[c];
sum += nums[d];
if (sum < target) {
c++;
} else if (sum > target) {
d--;
} else {
vector<int> v = {nums[a], nums[b], nums[c], nums[d]};
if (find(ans.begin(), ans.end(), v) == ans.end()) {
ans.push_back(v);
}
c++;
d--;
}
}
}
}
return ans;
}
};3 259
Задача: 1119. Remove Vowels from a String
Сложность: easy
Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.
Пример:
Input: s = "leetcodeisacommunityforcoders" Output: "ltcdscmmntyfrcdrs"👨💻 Алгоритм: 1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае. 2⃣Инициализируйте пустую строку ans. 3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans. 😎 Решение:
class Solution {
public:
string removeVowels(string s) {
string ans;
for (char c : s) {
if (!isVowel(c)) {
ans += c;
}
}
return ans;
}
private:
bool isVowel(char c) {
return c == 'a' || c == 'i' || c == 'e' || c == 'o' || c == 'u';
}
};3 259
Задача: 1004. Max Consecutive Ones III
Сложность: medium
Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.
Пример:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6👨💻 Алгоритм: 1⃣Инициализация оконного подхода: Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне. 2⃣Перемещение правого указателя и обновление окна: Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k). 3⃣Подсчет максимального количества последовательных единиц: На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом. 😎 Решение:
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, max_ones = 0, zero_count = 0;
for (int right = 0; right < nums.size(); ++right) {
if (nums[right] == 0) {
++zero_count;
}
while (zero_count > k) {
if (nums[left] == 0) {
--zero_count;
}
++left;
}
max_ones = max(max_ones, right - left + 1);
}
return max_ones;
}
};3 259
Задача: 904. Fruit Into Baskets
Сложность: medium
Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.
Пример:
Input: fruits = [1,2,1] Output: 3👨💻 Алгоритм: 1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов. 2⃣Перемещать правый указатель, расширяя окно, и обновлять количество каждого типа фрукта в окне. Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов. 3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге. 😎 Решение:
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> basket;
int left = 0;
int maxFruits = 0;
for (int right = 0; right < fruits.size(); ++right) {
basket[fruits[right]]++;
while (basket.size() > 2) {
basket[fruits[left]]--;
if (basket[fruits[left]] == 0) {
basket.erase(fruits[left]);
}
++left;
}
maxFruits = max(maxFruits, right - left + 1);
}
return maxFruits;
}
};3 259
Задача: 1137. N-th Tribonacci Number
Сложность: easy
Трибоначчи последовательность Tn определяется следующим образом:
T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.
Дано n, вернуть значение Tn.
Пример:
Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4👨💻 Алгоритм: 1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи. 2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1. 3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c. 😎 Решение:
class Solution {
public:
int tribonacci(int n) {
if (n < 3) {
return n > 0 ? 1 : 0;
}
int a = 0, b = 1, c = 1;
for (int i = 0; i < n - 2; ++i) {
int tmp = a + b + c;
a = b;
b = c;
c = tmp;
}
return c;
}
};3 259
Задача: 1086. High Five
Сложность: easy
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]class Solution {
private:
int K = 5;
public:
vector<vector<int>> highFive(vector<vector<int>>& items) {
sort(items.begin(), items.end(),
[](const vector<int> &a, const vector<int> &b) {
if (a[0] != b[0])
return a[0] < b[0];
return a[1] > b[1];
});
vector<vector<int>> solution;
int n = items.size();
int i = 0;
while (i < n) {
int id = items[i][0];
int sum = 0;
for (int k = i; k < i + K; ++k)
sum += items[k][1];
while (i < n && items[i][0] == id)
i++;
solution.push_back({id, sum / K});
}
return solution;
}
};3 259
Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard
Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.
Пример:
Input: stones = [3,2,4,1], k = 2 Output: 20👨💻 Алгоритм: 1⃣Проверка на возможность объединения: Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1. 2⃣Инициализация и динамическое программирование: Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней. Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве. 3⃣Заполнение таблицы dp: Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование. Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения. 😎 Решение:
class Solution {
public:
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
if ((n - 1) % (k - 1) != 0) return -1;
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + stones[i];
}
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int m = k; m <= n; ++m) {
for (int i = 0; i <= n - m; ++i) {
int j = i + m - 1;
dp[i][j] = INT_MAX;
for (int t = i; t < j; t += k - 1) {
dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]);
}
if ((j - i) % (k - 1) == 0) {
dp[i][j] += prefix[j + 1] - prefix[i];
}
}
}
return dp[0][n - 1];
}
};3 259
Задача: 644. Maximum Average Subarray II
Сложность: hard
Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.
Пример:
Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000👨💻 Алгоритм: 1⃣Используйте скользящее окно длины k для нахождения начального среднего значения. 2⃣Перемещайте окно по массиву, добавляя следующий элемент и убирая предыдущий, обновляя текущее среднее значение. 3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон. 😎 Решение:
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
int currSum = accumulate(nums.begin(), nums.begin() + k, 0);
int maxSum = currSum;
for (int i = k; i < n; i++) {
currSum += nums[i] - nums[i - k];
if (currSum > maxSum) {
maxSum = currSum;
}
}
return maxSum / (double) k;
}
};3 259
Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy
Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.
Пример:
Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40] Output: [ "Car 1 Has Passed Road A In Direction 2", // Traffic light on road A is green, car 1 can cross the intersection. "Traffic Light On Road B Is Green", // Car 2 requests green light for road B. "Car 2 Has Passed Road B In Direction 4", // Car 2 crosses as the light is green on road B now. "Car 3 Has Passed Road B In Direction 3", // Car 3 crosses as the light is green on road B now. "Traffic Light On Road A Is Green", // Car 5 requests green light for road A. "Car 5 Has Passed Road A In Direction 1", // Car 5 crosses as the light is green on road A now. "Traffic Light On Road B Is Green", // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B. "Car 4 Has Passed Road B In Direction 3" // Car 4 crosses as the light is green on road B now. ]👨💻 Алгоритм: 1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar. 2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar. 3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков. 😎 Решение:
class TrafficLight {
private:
int greenRoad = 1;
std::mutex mtx;
public:
void carArrived(
int carId,
int roadId,
int direction,
std::function<void()> turnGreen,
std::function<void()> crossCar
) {
std::lock_guard<std::mutex> lock(mtx);
if (greenRoad != roadId) {
turnGreen();
greenRoad = roadId;
}
crossCar();
}
};3 259
Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard
Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.
Пример:
Input: left = 10, right = 15 Output: 5👨💻 Алгоритм: 1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа. 2⃣Создайте функцию для проверки, является ли число простым. 3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом. 😎 Решение:
class Solution {
public:
int countPrimeSetBits(int left, int right) {
int count = 0;
for (int num = left; num <= right; num++) {
if (isPrime(__builtin_popcount(num))) {
count++;
}
}
return count;
}
private:
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
};3 259
Задача: 1406. Stone Game III
Сложность: hard
Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.
Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.
Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.
Пример:
Input: stoneValue = [1,2,3,7] Output: "Bob" Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.👨💻 Алгоритм: 1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0. 2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре. 3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья. 😎 Решение:
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
dp[i] = stoneValue[i] - dp[i + 1];
if (i + 2 <= n) {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2]);
}
if (i + 3 <= n) {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]);
}
}
if (dp[0] > 0) return "Alice";
if (dp[0] < 0) return "Bob";
return "Tie";
}
};3 259
Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard
Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.
Пример:
Input: nums = [1,3,1], k = 1 Output: 0👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Определите минимальное и максимальное возможные расстояния. 3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению. 😎 Решение:
int countPairs(const vector<int>& nums, int mid) {
int count = 0, j = 0;
for (int i = 0; i < nums.size(); i++) {
while (j < nums.size() && nums[j] - nums[i] <= mid) {
j++;
}
count += j - i - 1;
}
return count;
}
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front();
while (left < right) {
int mid = (left + right) / 2;
if (countPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}3 259
Задача: 316. Remove Duplicate Letters
Сложность: medium
Дана строка
s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.
Пример:
Input: s = "bcabc" Output: "abc"👨💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<char> stack;
unordered_set<char> seen;
unordered_map<char, int> lastOccurrence;
for (int i = 0; i < s.size(); ++i) {
lastOccurrence[s[i]] = i;
}
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
if (seen.find(c) == seen.end()) {
while (!stack.empty() && c < stack.back() && i < lastOccurrence[stack.back()]) {
seen.erase(stack.back());
stack.pop_back();
}
seen.insert(c);
stack.push_back(c);
}
}
return string(stack.begin(), stack.end());
}
};3 259
Задача: 724. Find Pivot Index
Сложность: easy
Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.
Пример:
Input: nums = [1,7,3,6,5,6] Output: 3👨💻 Алгоритм: 1⃣Вычислите сумму всех элементов массива. 2⃣Пройдите по массиву, вычисляя текущую сумму элементов слева и проверяя, равна ли она разности между общей суммой и текущей суммой справа. 3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1. 😎 Решение:
int pivotIndex(vector<int>& nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int leftSum = 0;
for (int i = 0; i < nums.size(); i++) {
if (leftSum == totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}3 259
Задача: 774. Minimize Max Distance to Gas Station
Сложность: hard
Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.
Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию.
Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.
Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.
Пример:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000class Solution {
public:
double minmaxGasDist(vector<int>& stations, int K) {
int N = stations.size();
vector<double> deltas(N-1);
for (int i = 0; i < N-1; ++i)
deltas[i] = stations[i+1] - stations[i];
vector<vector<double>> dp(N-1, vector<double>(K+1));
for (int i = 0; i <= K; ++i)
dp[0][i] = deltas[0] / (i+1);
for (int p = 1; p < N-1; ++p)
for (int k = 0; k <= K; ++k) {
double bns = numeric_limits<double>::max();
for (int x = 0; x <= k; ++x)
bns = min(bns, max(deltas[p] / (x+1), dp[p-1][k-x]));
dp[p][k] = bns;
}
return dp[N-2][K];
}
};3 259
Задача: 17. Letter Combinations of a Phone Number
Сложность: medium
Дана строка, содержащая цифры от 2 до 9. Необходимо вернуть все возможные комбинации букв, которые может представлять эта строка, согласно клавиатуре мобильного телефона.
Цифра 1 не используется, и для неё нет соответствующих букв.
Пример:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]👨💻 Алгоритм: 1⃣Используем рекурсию и бэктрекинг. Для каждой цифры подставляем все возможные буквы. 2⃣На каждом шаге рекурсивно добавляем буквы для текущей цифры к текущей строке. 3⃣Когда строка достигла длины исходных digits — добавляем комбинацию в результат. 😎 Решение:
class Solution {
public:
void find(string digits, vector<string> v, vector<string>& res, string s, int k) {
if (k >= digits.size()) {
res.push_back(s);
return;
}
int a = digits[k] - '0';
for (int i = 0; i < v[a].size(); i++) {
s += v[a][i];
find(digits, v, res, s, k + 1);
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty()) return res;
vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string s = "";
find(digits, v, res, s, 0);
return res;
}
};3 259
Задача: 839. Similar String Groups
Сложность: hard
Две строки, X и Y, считаются похожими, если либо они идентичны, либо мы можем сделать их эквивалентными, поменяв местами не более двух букв (в разных позициях) в строке X.
Например, "tars" и "rats" похожи (замена на позициях 0 и 2), и "rats" и "arts" похожи, но "star" не похожа на "tars", "rats" или "arts".
Эти строки образуют две связанные группы по сходству: {"tars", "rats", "arts"} и {"star"}. Обратите внимание, что "tars" и "arts" находятся в одной группе, хотя они не похожи друг на друга. Формально, каждая группа такова, что слово находится в группе, если и только если оно похоже хотя бы на одно другое слово в группе.
Вам дан список строк strs, где каждая строка в списке является анаграммой каждой другой строки в списке. Сколько групп существует?
Пример:
Input: strs = ["tars","rats","arts","star"] Output: 2👨💻 Алгоритм: 1⃣Создайте переменную n, хранящую количество слов в strs, и создайте экземпляр UnionFind размера n. 2⃣Для любых двух слов на индексах i и j, которые ведут себя как узлы, проверьте, являются ли слова strs[i] и strs[j] похожими, и выполните операции find и union для объединения различных компонентов в один, если слова похожи. 3⃣Верните количество оставшихся групп. 😎 Решение:
class UnionFind {
public:
vector<int> parent;
vector<int> rank;
UnionFind(int size) : parent(size), rank(size, 0) {
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union_set(int x, int y) {
int xset = find(x);
int yset = find(y);
if (xset != yset) {
if (rank[xset] < rank[yset]) {
parent[xset] = yset;
} else if (rank[xset] > rank[yset]) {
parent[yset] = xset;
} else {
parent[yset] = xset;
rank[xset]++;
}
}
}
};
class Solution {
public:
bool isSimilar(const string& a, const string& b) {
int diff = 0;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != b[i]) {
diff++;
}
}
return diff == 0 || diff == 2;
}
int numSimilarGroups(vector<string>& strs) {
int n = strs.size();
UnionFind dsu(n);
int count = n;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (isSimilar(strs[i], strs[j]) && dsu.find(i) != dsu.find(j)) {
count--;
dsu.union_set(i, j);
}
}
}
return count;
}
};