C/C++ | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Показати більше
Сітка:3 211
Підписники
-224 години
-127 днів
-1730 днів
Архів дописів
3 211
Задача: 949. Largest Time for Given Digits
Сложность: medium
Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.
Пример:
Input: arr = [1,2,3,4] Output: "23:41"👨💻 Алгоритм: 1⃣Перебрать все возможные перестановки массива arr. 2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время. Найти самое позднее допустимое время среди всех перестановок. 3⃣Алгоритм Перебрать все возможные перестановки массива arr. Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время. Найти самое позднее допустимое время среди всех перестановок. Вернуть найденное время в формате "HH ". Если допустимое время не найдено, вернуть пустую строку. 😎 Решение:
class Solution {
public:
string largestTimeFromDigits(vector<int>& arr) {
sort(arr.begin(), arr.end());
int maxTime = -1;
do {
int hours = arr[0] * 10 + arr[1];
int minutes = arr[2] * 10 + arr[3];
if (hours < 24 && minutes < 60) {
maxTime = max(maxTime, hours * 60 + minutes);
}
} while (next_permutation(arr.begin(), arr.end()));
if (maxTime == -1) {
return "";
}
char buffer[6];
sprintf(buffer, "%02d:%02d", maxTime / 60, maxTime % 60);
return string(buffer);
}
};3 211
Задача: 972. Equal Rational Numbers
Сложность: hard
Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.
Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:
<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:
1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).
Пример:
Input: s = "0.(52)", t = "0.5(25)" Output: true Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.👨💻 Алгоритм: 1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина. 2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии. 3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения. 😎 Решение:
class Fraction {
public:
long n, d;
Fraction(long n, long d) {
long g = gcd(n, d);
this->n = n / g;
this->d = d / g;
}
void iadd(const Fraction& other) {
long numerator = this->n * other.d + this->d * other.n;
long denominator = this->d * other.d;
long g = gcd(numerator, denominator);
this->n = numerator / g;
this->d = denominator / g;
}
static long gcd(long x, long y) {
return x != 0 ? gcd(y % x, x) : y;
}
};
class Solution {
public:
bool isRationalEqual(string S, string T) {
Fraction f1 = convert(S);
Fraction f2 = convert(T);
return f1.n == f2.n && f1.d == f2.d;
}
Fraction convert(string S) {
int state = 0;
Fraction ans(0, 1);
int decimal_size = 0;
vector<string> parts = split(S, ".()");
for (string& part : parts) {
state++;
if (part.empty()) continue;
long x = stol(part);
int sz = part.length();
if (state == 1) {
ans.iadd(Fraction(x, 1));
} else if (state == 2) {
ans.iadd(Fraction(x, pow(10, sz)));
decimal_size = sz;
} else {
long denom = pow(10, decimal_size);
denom *= pow(10, sz) - 1;
ans.iadd(Fraction(x, denom));
}
}
return ans;
}
private:
vector<string> split(const string& s, const string& delimiters) {
vector<string> tokens;
size_t start = 0;
size_t end = s.find_first_of(delimiters);
while (end != string::npos) {
if (end > start)
tokens.push_back(s.substr(start, end - start));
start = end + 1;
end = s.find3 211
Задача: 1002. Find Common Characters
Сложность: easy
Если задан массив строк words, верните массив всех символов, которые встречаются во всех строках внутри слов (включая дубликаты). Вы можете вернуть ответ в любом порядке.
Пример:
Input: words = ["bella","label","roller"] Output: ["e","l","l"]👨💻 Алгоритм: 1⃣Инициализация частотного массива: Создайте массив для хранения минимальной частоты каждого символа, который будет встречаться во всех словах. 2⃣Обработка каждого слова: Для каждого слова создайте временный массив для хранения частоты каждого символа в этом слове. Обновите основной частотный массив, сравнивая его с временным массивом и сохраняя минимальные частоты каждого символа. 3⃣Формирование результата: Создайте результирующий массив, добавляя каждый символ столько раз, сколько его минимальная частота. 😎 Решение:
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
vector<int> min_freq(26, INT_MAX);
for (const string& word : words) {
vector<int> freq(26, 0);
for (char c : word) {
freq[c - 'a']++;
}
for (int i = 0; i < 26; ++i) {
min_freq[i] = min(min_freq[i], freq[i]);
}
}
vector<string> result;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < min_freq[i]; ++j) {
result.push_back(string(1, 'a' + i));
}
}
return result;
}
};3 211
Задача: 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 211
Задача: 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 211
Задача: 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 211
Задача: 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 211
Задача: №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 211
Задача: 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 211
Задача: 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 211
Задача: 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 211
Сегодня последний день!
Акция на Пожизненный easyoffer PRO - по цене 1 года заканчивается сегодня.
PRO подписка включает:
– Доступ ко всем профессиям сайта без ограничений
– Все текущие и новые функции, которые будут появляться на сайте
👉 Акция до 31 марта 23:59 по МСК https://easyoffer.ru/pro
3 211
Задача: 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 211
Завтра последний день!
Успей купить пожизненный easyoffer PRO - по цене 1 года
Покупаешь один раз — пользуешься всю жизнь.
👉 Акция до 31 марта: https://easyoffer.ru/pro
3 211
Задача: 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 211
Задача: 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 211
Задача: 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 211
Задача: 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 211
Задача: 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 211
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 31 марта вы можете купить PRO навсегда. Запускаем акцию, чтобы ускорить развитие сервиса.
Что добавим в PRO в ближайшие полгода:
– Автоотклики
– Агрегатор вакансий
– Проход ATS без отсева
– Уникальные резюме и письма под каждую вакансию
Покупаешь один раз — пользуешься всю жизнь.
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
