اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
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
Задача: 782. Transform to Chessboard
Сложность: hard
Дана бинарная сетка размером n x n. В каждом ходе можно поменять местами любые две строки или любые два столбца.
Верните минимальное количество ходов, чтобы преобразовать сетку в шахматную доску. Если задача невыполнима, верните -1.
Шахматная доска — это доска, на которой ни один 0 и ни одна 1 не соприкасаются друг с другом по вертикали и горизонтали.
Пример:
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]] Output: 2 Explanation: One potential sequence of moves is shown. The first move swaps the first and second column. The second move swaps the second and third row.👨💻 Алгоритм: 1⃣Для каждого набора строк (и столбцов соответственно) убедитесь, что существует только 2 вида линий в правильных количествах, которые являются противоположностями друг друга. 2⃣Затем для каждой возможной идеальной трансформации этой линии найдите минимальное количество перестановок, чтобы преобразовать эту линию в её идеальную и добавьте это к ответу. Например, [0, 1, 1, 1, 0, 0] имеет два идеала [0, 1, 0, 1, 0, 1] или [1, 0, 1, 0, 1, 0]; но [0, 1, 1, 1, 0] имеет только один идеал [1, 0, 1, 0, 1]. 3⃣В Java мы используем целые числа для представления строк как двоичных чисел. Мы проверяем количество различий с [1, 0, 1, 0, 1, 0, ...] с помощью побитового исключающего ИЛИ с 0b010101010101.....01 = 0x55555555. Чтобы убедиться, что мы не добавляем излишне большие элементы. 😎 Решение:
class Solution {
public:
int movesToChessboard(vector<vector<int>>& board) {
int N = board.size(), ans = 0;
for (auto count : {counter(board), counter(transpose(board))}) {
if (count.size() != 2 || !sortedEquals(count, {N/2, (N+1)/2})) return -1;
auto it = count.begin();
vector<int> line1 = it->first, line2 = (++it)->first;
if (!allOpposite(line1, line2)) return -1;
vector<int> starts = (N % 2 == 0) ? vector<int>{0, 1} : vector<int>{(accumulate(line1.begin(), line1.end(), 0) * 2 > N)};
int minSwaps = INT_MAX;
for (int start : starts) {
int swaps = 0;
for (int i = 0; i < N; i++) {
swaps += (line1[i] != (i % 2 == start ? 1 : 0));
}
minSwaps = min(minSwaps, swaps / 2);
}
ans += minSwaps;
}
return ans;
}
private:
map<vector<int>, int> counter(const vector<vector<int>>& board) {
map<vector<int>, int> count;
for (const auto& row : board) {
count[row]++;
}
return count;
}
vector<vector<int>> transpose(const vector<vector<int>>& board) {
int N = board.size();
vector<vector<int>> transposed(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
transposed[j][i] = board[i][j];
}
}
return transposed;
}
bool allOpposite(const vector<int>& line1, const vector<int>& line2) {
for (int i = 0; i < line1.size(); i++) {
if ((line1[i] ^ line2[i]) == 0) {
return false;
}
}
return true;
}
bool sortedEquals(const map<vector<int>, int>& count, const vector<int>& sortedValues) {
vector<int> values;
for (const auto& [key, value] : count) {
values.push_back(value);
}
sort(values.begin(), values.end());
return values == sortedValues;
}
};3 259
Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium
Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.
Пример:
Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15👨💻 Алгоритм: 1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов. 2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. 3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц. 😎 Решение:
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 1) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
}
count += dp[i][j];
}
}
}
return count;
}
};3 259
Задача: 303. Range Sum Query - Immutable
Сложность: easy
Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).
Пример:
Input ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output [null, 1, -1, -3]👨💻 Алгоритм: 1⃣Инициализация: Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums. 2⃣Предварительное вычисление сумм: Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат. 😎 Решение:
class NumArray {
private:
vector<int> sum;
public:
NumArray(vector<int>& nums) {
sum.resize(nums.size() + 1);
for (int i = 0; i < nums.size(); i++) {
sum[i + 1] = sum[i] + nums[i];
}
}
int sumRange(int i, int j) {
return sum[j + 1] - sum[i];
}
};3 259
Задача: 1049. Last Stone Weight II
Сложность: medium
Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.
Пример:
Input: stones = [2,7,4,1,8,1] Output: 1👨💻 Алгоритм: 1⃣Используй метод динамического программирования, чтобы проверить, можно ли разделить камни на две группы с равной суммой. 2⃣Определи, какие веса можно достичь, используя половину суммы всех камней. 3⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек. 😎 Решение:
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int totalSum = accumulate(stones.begin(), stones.end(), 0);
int halfSum = totalSum / 2;
vector<int> dp(halfSum + 1, 0);
for (int stone : stones) {
for (int j = halfSum; j >= stone; j--) {
dp[j] = max(dp[j], dp[j - stone] + stone);
}
}
return totalSum - 2 * dp[halfSum];
}
};3 259
Задача: №27. Remove Element
Сложность: easy
Учитывая массив nums и значение val, удалите все вхождения val на месте. Порядок элементов может быть изменён. Верните количество элементов k, которые не равны val, и убедитесь, что первые k элементов массива содержат именно эти значения.
Пример:
Input: nums = [3,2,2,3], val = 3 Output: 2👨💻Алгоритм: 1⃣Заводим указатель k для отслеживания позиции следующего "валидного" элемента. 2⃣Проходим по массиву: если текущий элемент не равен val, записываем его на позицию k и увеличиваем k. 3⃣После цикла k будет содержать количество элементов, не равных val. 😎 Решение:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] != val) {
nums[k] = nums[i];
k++;
}
}
return k;
}
};3 259
Задача: 246. Strobogrammatic Number
Сложность: easy
Пример:
Input: num = "69" Output: true👨💻 Алгоритм: 1⃣Пройдись по строке с конца, проверяя каждый символ на допустимость (0, 1, 6, 8, 9). 2⃣Построй перевёрнутую строку, заменяя 6 на 9 и наоборот. 3⃣Сравни перевёрнутую строку с исходной — если равны, значит число стробограмматическое. 😎 Решение:
#include <string>
using namespace std;
class Solution {
public:
bool isStrobogrammatic(string num) {
string rotated;
for (int i = num.length() - 1; i >= 0; i--) {
char c = num[i];
if (c == '0' || c == '1' || c == '8') {
rotated.push_back(c);
} else if (c == '6') {
rotated.push_back('9');
} else if (c == '9') {
rotated.push_back('6');
} else {
return false;
}
}
return num == rotated;
}
};3 259
Задача: 1356. Sort Integers by The Number of 1 Bits
Сложность: easy
Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию.
Верните массив после сортировки.
Пример:
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1] Output: [1,2,4,8,16,32,64,128,256,512,1024] Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.👨💻 Алгоритм: 1⃣Создание функции для подсчета единиц: Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении. 2⃣Сортировка массива: Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки. 3⃣Возврат отсортированного массива: Верните отсортированный массив. 😎 Решение:
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<int> sortByBits(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end(), [](int a, int b) {
int countA = __builtin_popcount(a);
int countB = __builtin_popcount(b);
return countA == countB ? a < b : countA < countB;
});
return arr;
}
};3 259
Задача: 1165. Single-Row Keyboard
Сложность: easy
Есть специальная клавиатура, на которой все клавиши расположены в один ряд.
Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.
Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.
Пример:
Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.class Solution {
public:
int calculateTime(string keyboard, string word) {
vector<int> keyIndices(26, -1);
for (int i = 0; i < keyboard.length(); i++)
keyIndices[keyboard[i] - 'a'] = i;
int prev = 0;
int result = 0;
for (char &c : word) {
result += abs(prev - keyIndices[c - 'a']);
prev = keyIndices[c - 'a'];
}
return result;
}
};3 259
Сегодня последний день!
Акция на Пожизненный easyoffer PRO - по цене 1 года заканчивается сегодня.
PRO подписка включает:
– Доступ ко всем профессиям сайта без ограничений
– Все текущие и новые функции, которые будут появляться на сайте
👉 Акция до 31 марта 23:59 по МСК https://easyoffer.ru/pro
3 259
Задача: 1044. Longest Duplicate Substring
Сложность: hard
Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".
Пример:
Input: s = "banana" Output: "ana"👨💻 Алгоритм: 1⃣Использование двоичного поиска для определения длины дублированной подстроки: Двоичный поиск используется для поиска максимальной длины дублированной подстроки. 2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины: Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок. 3⃣Хеширование с помощью функции rolling hash: Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов. 😎 Решение:
string longestDupSubstring(string s) {
auto search = [&](int length) {
unordered_set<string> seen;
for (int i = 0; i <= s.size() - length; ++i) {
string sub = s.substr(i, length);
if (seen.count(sub)) {
return sub;
}
seen.insert(sub);
}
return string("");
};
int left = 1, right = s.size();
string result = "";
while (left < right) {
int mid = left + (right - left) / 2;
string dup = search(mid);
if (!dup.empty()) {
result = dup;
left = mid + 1;
} else {
right = mid;
}
}
return result;
}3 259
Завтра последний день!
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
3 259
Задача: 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 259
Задача: 1089. Duplicate Zeros
Сложность: easy
Дан массив целых чисел фиксированной длины arr, дублируйте каждое вхождение нуля, сдвигая оставшиеся элементы вправо.
Учтите, что элементы за пределами длины исходного массива не записываются. Внесите указанные изменения в массив на месте и ничего не возвращайте.
Пример:
Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int possibleDups = 0;
int length_ = arr.size() - 1;
for (int left = 0; left <= length_ - possibleDups; left++) {
if (arr[left] == 0) {
if (left == length_ - possibleDups) {
arr[length_] = 0;
length_ -= 1;
break;
}
possibleDups++;
}
}
int last = length_ - possibleDups;
for (int i = last; i >= 0; i--) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0;
possibleDups--;
arr[i + possibleDups] = 0;
} else {
arr[i + possibleDups] = arr[i];
}
}
}
};3 259
Задача: 1266. Minimum Time Visiting All Points
Сложность: easy
На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.
Пример:
Input: points = [[1,1],[3,4],[-1,0]] Output: 7👨💻 Алгоритм: 1⃣Инициализируйте переменную для хранения минимального времени. 2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей. 3⃣Суммируйте время переходов для получения общего минимального времени. 😎 Решение:
class Solution {
public:
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int time = 0;
for (int i = 0; i < points.size() - 1; ++i) {
time += distance(points[i], points[i + 1]);
}
return time;
}
private:
int distance(vector<int>& p1, vector<int>& p2) {
return max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]));
}
};3 259
Задача: 1229. Meeting Scheduler
Сложность: medium
Даны массивы доступных временных слотов slots1 и slots2 для двух человек и продолжительность встречи duration, верните самый ранний временной слот, который подходит обоим и имеет продолжительность duration.
Если нет общего временного слота, который удовлетворяет требованиям, верните пустой массив.
Формат временного слота — это массив из двух элементов [start, end], представляющий инклюзивный временной диапазон от start до end.
Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1.
Пример:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]class Solution {
public:
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
sort(slots1.begin(), slots1.end());
sort(slots2.begin(), slots2.end());
int pointer1 = 0, pointer2 = 0;
while (pointer1 < slots1.size() && pointer2 < slots2.size()) {
int intersectLeft = max(slots1[pointer1][0], slots2[pointer2][0]);
int intersectRight = min(slots1[pointer1][1], slots2[pointer2][1]);
if (intersectRight - intersectLeft >= duration) {
return {intersectLeft, intersectLeft + duration};
}
if (slots1[pointer1][1] < slots2[pointer2][1]) {
pointer1++;
} else {
pointer2++;
}
}
return {};
}
};3 259
Задача: 929. Unique Email Addresses
Сложность: easy
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"] Output: 2👨💻 Алгоритм: 1⃣Создать множество для хранения уникальных обработанных адресов электронной почты. 2⃣Для каждого адреса в emails: Разделить адрес на локальное и доменное имя по символу '@'. Обработать локальное имя: Удалить все точки '.'. Обрезать часть после символа '+'. Объединить обработанное локальное имя и доменное имя. Добавить результат в множество уникальных адресов. 3⃣Вернуть количество уникальных адресов в множестве. 😎 Решение:
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> uniqueEmails = new HashSet<>();
for (String email : emails) {
String[] parts = email.split("@");
String local = parts[0].split("\\+")[0].replace(".", "");
uniqueEmails.add(local + "@" + parts[1]);
}
return uniqueEmails.size();
}
}3 259
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 31 марта вы можете купить PRO навсегда. Запускаем акцию, чтобы ускорить развитие сервиса.
Что добавим в PRO в ближайшие полгода:
– Автоотклики
– Агрегатор вакансий
– Проход ATS без отсева
– Уникальные резюме и письма под каждую вакансию
Покупаешь один раз — пользуешься всю жизнь.
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
3 259
Задача: 861. Score After Flipping Matrix
Сложность: medium
Вам дана бинарная матрица grid размером m x n.
Ход состоит из выбора любой строки или столбца и переключения каждого значения в этой строке или столбце (т.е. изменение всех 0 на 1, и всех 1 на 0).
Каждая строка матрицы интерпретируется как двоичное число, и счёт матрицы — это сумма этих чисел.
Верните наивысший возможный счёт после выполнения любого количества ходов (включая ноль ходов).
Пример:
Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39class Solution {
public:
int matrixScore(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
for (int j = 1; j < n; ++j) {
int countZero = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 0) {
countZero++;
}
}
if (countZero > m / 2) {
for (int i = 0; i < m; ++i) {
grid[i][j] ^= 1;
}
}
}
int score = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
score += 1 << (n - j - 1);
}
}
}
return score;
}
};3 259
Задача: 32. Longest Valid Parentheses
Сложность: hard
Учитывая строку, содержащую только символы «(» и «)», верните длину самой длинной допустимой (правильно сформированной) подстроки скобок.
Пример:
Input: s = "(()" Output: 2👨💻 Алгоритм: 1⃣Используем стек для хранения индексов, начальное значение — -1. 2⃣Проходим по строке: если '(', кладем индекс в стек, если ')' — извлекаем элемент. 3⃣Если после извлечения стек пуст — кладем текущий индекс, иначе — обновляем максимум длины как i - stack.top(). 😎 Решение:
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stack;
int m = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
m = max(m, (i - stack.top()));
}
}
}
return m;
}
};3 259
Задача: 1102. Path With Maximum Minimum Value
Сложность: medium
Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.
Значение пути определяется минимальным числом на этом пути.
Пример:
Input: grid = [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path with the maximum score is highlighted in yellow.👨💻 Алгоритм: 1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы. 2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore: Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore. Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди. Если успешно достигли правой нижней ячейки, значит путь существует. Если очередь опустела до достижения правой нижней ячейки, пути не существует. 3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2. В противном случае, верните curScore как ответ. 😎 Решение:
class Solution {
vector<vector<int>> dirs{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public:
int maximumMinimumPath(vector<vector<int>>& grid) {
int R = grid.size(), C = grid[0].size();
int curScore = min(grid[0][0], grid[R - 1][C - 1]);
while (curScore >= 0) {
if (pathExists(grid, curScore)) {
return curScore;
} else {
curScore--;
}
}
return -1;
}
bool pathExists(vector<vector<int>>& grid, int curScore) {
int R = grid.size(), C = grid[0].size();
vector<vector<bool>> visited(R, vector<bool>(C, false));
deque<pair<int, int>> dq{{0, 0}};
visited[0][0] = true;
auto push = [&](int row, int col) {
if (row >= 0 && col >= 0 && row < R && col < C && !visited[row][col] && grid[row][col] >= curScore) {
dq.push_back({row, col});
visited[row][col] = true;
}
};
while (!dq.empty()) {
int curRow = dq.front().first, curCol = dq.front().second;
dq.pop_front();
if (curRow == R - 1 && curCol == C - 1) {
return true;
}
for (auto dir : dirs) {
push(curRow + dir[0], curCol + dir[1]);
}
}
return false;
}
};