C/C++ | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:3 238
مشترکین
اطلاعاتی وجود ندارد24 ساعت
اطلاعاتی وجود ندارد7 روز
+730 روز
آرشیو پست ها
3 238
Задача: 541. Reverse String II
Сложность: easy
Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.
Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.
Пример:
Input: s = "abcdefg", k = 2 Output: "bacdfeg"👨💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:
class Solution {
public:
string reverseStr(string s, int k) {
vector<char> a(s.begin(), s.end());
for (int start = 0; start < a.size(); start += 2 * k) {
int i = start, j = min(start + k - 1, (int)a.size() - 1);
while (i < j) {
char tmp = a[i];
a[i++] = a[j];
a[j--] = tmp;
}
}
return string(a.begin(), a.end());
}
};3 238
Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium
Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.
Пример:
Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.👨💻 Алгоритм: 1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов. 2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s: Для каждого индекса i: Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа. Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот. Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию. Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1. 3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k. 😎 Решение:
class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
if (k > 26) return 0;
int answer = 0;
int n = s.size();
for (int i = 0; i <= n - k; i++) {
int freq[26] = {0};
bool isUnique = true;
for (int j = i; j < i + k; j++) {
freq[s[j] - 'a']++;
if (freq[s[j] - 'a'] > 1) {
isUnique = false;
break;
}
}
if (isUnique) answer++;
}
return answer;
}
};3 238
Задача: 844. Backspace String Compare
Сложность: easy
Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.
Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.
Пример:
Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac".👨💻 Алгоритм: 1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы. 2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены. 3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false. 😎 Решение:
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] == '#') { skipS++; i--; }
else if (skipS > 0) { skipS--; i--; }
else break;
}
while (j >= 0) {
if (T[j] == '#') { skipT++; j--; }
else if (skipT > 0) { skipT--; j--; }
else break;
}
if (i >= 0 && j >= 0 && S[i] != T[j]) {
return false;
}
if ((i >= 0) != (j >= 0)) {
return false;
}
i--; j--;
}
return true;
}
};3 238
Задача: 1094. Car Pooling
Сложность: medium
Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).
Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.
Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае.
Пример:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false👨💻 Алгоритм: 1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity. 2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени. 3⃣Мы можем сохранить изменения количества пассажиров в каждый момент времени, отсортировать их по меткам времени и, наконец, пройтись по ним, чтобы проверить фактическую вместимость. 😎 Решение:
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
map<int, int> timestamp;
for (auto& trip : trips) {
timestamp[trip[1]] += trip[0];
timestamp[trip[2]] -= trip[0];
}
int usedCapacity = 0;
for (auto& change : timestamp) {
usedCapacity += change.second;
if (usedCapacity > capacity) {
return false;
}
}
return true;
}
};3 238
Задача: 1260. Shift 2D Grid
Сложность: easy
Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.
Пример:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[9,1,2],[3,4,5],[6,7,8]]👨💻 Алгоритм: 1⃣Преобразовать двумерную сетку в одномерный массив. 2⃣Выполнить сдвиг элементов в одномерном массиве. 3⃣Преобразовать одномерный массив обратно в двумерную сетку. 😎 Решение:
class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
int total = m * n;
k = k % total;
if (k == 0) {
return grid;
}
vector<int> flatArray(total);
for (int i = 0; i < total; ++i) {
flatArray[i] = grid[i / n][i % n];
}
vector<int> newArray(total);
for (int i = 0; i < total; ++i) {
newArray[(i + k) % total] = flatArray[i];
}
vector<vector<int>> newGrid(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
newGrid[i][j] = newArray[i * n + j];
}
}
return newGrid;
}
};3 238
Задача: №30. Substring with Concatenation of All Words
Сложность: hard
Вам дана строка s и массив строк words, где все слова одинаковой длины. Найдите все стартовые индексы подстрок в s, которые являются конкатенацией всех слов из массива (в любом порядке, без дополнительных символов между ними).
Пример:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]👨💻 Алгоритм: 1⃣Вычисляем длину каждого слова и общее количество слов. 2⃣Используем скользящее окно с шагом = длине слова, и на каждом шаге проверяем, входят ли текущие слова в заданный набор. 3⃣Отслеживаем, сколько раз каждое слово встречается, используя unordered_map. 😎 Решение:
vector<int> findSubstring(string str, vector<string>& words) {
int len = words[0].length();
unordered_map<string, int> contain;
for (string s : words) contain[s]++;
vector<int> res;
for (int j = 0; j < len; j++) {
unordered_map<string, int> found;
int st = j;
for (int i = j; i <= str.size() - len; i += len) {
string curr = str.substr(i, len);
if (contain.find(curr) != contain.end()) {
found[curr]++;
while (found[curr] > contain[curr]) {
found[str.substr(st, len)]--;
st += len;
}
int size = (i - st + len) / len;
if (size == words.size()) {
res.push_back(st);
}
} else {
found.clear();
st = i + len;
}
}
}
return res;
}3 238
Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium
Вам дан корень бинарного дерева.
Зигзагообразный путь для бинарного дерева определяется следующим образом:
Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).
Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.
Пример:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.👨💻 Алгоритм: 1⃣Рекурсивная функция DFS: Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо). 2⃣Обновление максимальной длины пути: При каждом вызове рекурсивной функции обновляйте максимальную длину зигзагообразного пути, если текущая длина больше текущего максимума. 3⃣Рекурсивный вызов для левого и правого дочерних узлов: Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления. 😎 Решение:
#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxLength = 0;
int longestZigZag(TreeNode* root) {
dfs(root, true, 0);
dfs(root, false, 0);
return maxLength;
}
void dfs(TreeNode* node, bool isLeft, int length) {
if (!node) return;
maxLength = std::max(maxLength, length);
if (isLeft) {
dfs(node->left, false, length + 1);
dfs(node->right, true, 1);
} else {
dfs(node->right, true, length + 1);
dfs(node->left, false, 1);
}
}
};3 238
Задача: 347. Top K Frequent Elements
Сложность: medium
Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]👨💻 Алгоритм: 1⃣Подсчет частоты: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums. 2⃣Создание кучи: Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов. 3⃣Возврат результата: Верните k самых частых элементов. 😎 Решение:
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
priority_queue<pair<int, int>> heap;
for (const auto& [num, freq] : count) {
heap.emplace(freq, num);
}
vector<int> result;
for (int i = 0; i < k; ++i) {
result.push_back(heap.top().second);
heap.pop();
}
return result;
}
};3 238
Задача: 763. Partition Labels
Сложность: medium
Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей.
Пример:
Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8]👨💻 Алгоритм: 1⃣Создайте словарь для хранения последней позиции каждой буквы в строке. 2⃣Пройдите по строке, отслеживая максимальную позицию текущей части. 3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую. 😎 Решение:
class Solution {
public:
vector<int> partitionLabels(string s) {
vector<int> lastPos(26, 0);
for (int i = 0; i < s.size(); i++) {
lastPos[s[i] - 'a'] = i;
}
vector<int> partitions;
int j = 0, anchor = 0;
for (int i = 0; i < s.size(); i++) {
j = max(j, lastPos[s[i] - 'a']);
if (i == j) {
partitions.push_back(i - anchor + 1);
anchor = i + 1;
}
}
return partitions;
}
};3 238
Задача: 267. Palindrome Permutation II
Сложность: medium
Пример:
Input: s = "aabb" Output: ["abba","baab"]👨💻 Алгоритм: 1⃣Подсчёт частоты символов Создаем хеш-таблицу частот. Если количество символов с нечетной частотой больше 1 — палиндром невозможен. 2⃣Формирование первой половины Из каждого символа берём его частоту пополам и формируем строку half. Символ с нечетной частотой (если есть) сохраняем как центральный. 3⃣Генерация палиндромов С помощью backtracking создаём все уникальные перестановки строки half, дополняем их зеркально. Если есть центральный символ — добавляем его в середину. 😎 Решение:
class Solution {
private:
void backtrack(string& half, vector<bool>& used, string& path, string& mid, vector<string>& res) {
if (path.size() == half.size()) {
string rev = path;
reverse(rev.begin(), rev.end());
res.push_back(path + mid + rev);
return;
}
for (int i = 0; i < half.size(); ++i) {
if (used[i]) continue;
if (i > 0 && half[i] == half[i - 1] && !used[i - 1]) continue;
used[i] = true;
path.push_back(half[i]);
backtrack(half, used, path, mid, res);
path.pop_back();
used[i] = false;
}
}
public:
vector<string> generatePalindromes(string s) {
unordered_map<char, int> freq;
for (char c : s) freq[c]++;
int oddCount = 0;
string mid = "", half = "";
for (auto& [ch, count] : freq) {
if (count % 2 != 0) {
oddCount++;
mid = ch;
}
half += string(count / 2, ch);
}
if (oddCount > 1) return {};
sort(half.begin(), half.end());
vector<string> res;
vector<bool> used(half.size(), false);
string path;
backtrack(half, used, path, mid, res);
return res;
}
};3 238
Задача: 681. Next Closest Time
Сложность: medium
Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.
Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.
Пример:
Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.class Solution {
public:
string nextClosestTime(string time) {
int cur = 60 * stoi(time.substr(0, 2)) + stoi(time.substr(3));
unordered_set<int> allowed;
for (char c : time) if (c != ':') {
allowed.insert(c - '0');
}
while (true) {
cur = (cur + 1) % (24 * 60);
vector<int> digits = {cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10};
bool valid = true;
for (int d : digits) {
if (!allowed.count(d)) {
valid = false;
break;
}
}
if (valid) {
return (cur / 60 < 10 ? "0" : "") + to_string(cur / 60) + ":" + (cur % 60 < 10 ? "0" : "") + to_string(cur % 60);
}
}
}
};3 238
Задача: 1490. Clone N-ary Tree
Сложность: medium
Дан корень N-арного дерева, верните глубокую копию (клон) дерева.
Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей.
class Node {
public int val;
public List<Node> children;
}Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
class Solution {
public:
Node* cloneTree(Node* root) {
if (!root) return nullptr;
Node* nodeCopy = new Node(root->val);
for (Node* child : root->children) {
nodeCopy->children.push_back(cloneTree(child));
}
return nodeCopy;
}
};3 238
Задача: 400. Nth Digit
Сложность: medium
Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].
Пример:
Input: n = 3 Output: 3👨💻 Алгоритм: 1⃣Определение диапазона: Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.). Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра. 2⃣Нахождение конкретного числа: Когда определите диапазон, найдите точное число, содержащее n-ю цифру. Определите индекс цифры в этом числе. 3⃣Возвращение n-й цифры: Извлеките и верните n-ю цифру из найденного числа. 😎 Решение:
class Solution {
public:
int findNthDigit(int n) {
long length = 1, count = 9, start = 1;
while (n > length * count) {
n -= length * count;
length++;
count *= 10;
start *= 10;
}
start += (n - 1) / length;
string s = to_string(start);
return s[(n - 1) % length] - '0';
}
};3 238
Задача: 835. Image Overlap
Сложность: medium
Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.
Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.
Верните максимальное возможное перекрытие.
Пример:
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]] Output: 3 Explanation: We translate img1 to right by 1 unit and down by 1 unit.👨💻 Алгоритм: 1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия. 2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift). 3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий. 😎 Решение:
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int shiftAndCount(int xShift, int yShift, vector<vector<int>>& M, vector<vector<int>>& R) {
int leftShiftCount = 0, rightShiftCount = 0;
int rRow = 0;
for (int mRow = yShift; mRow < M.size(); ++mRow) {
int rCol = 0;
for (int mCol = xShift; mCol < M.size(); ++mCol) {
if (M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol])
leftShiftCount++;
if (M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol])
rightShiftCount++;
rCol++;
}
rRow++;
}
return max(leftShiftCount, rightShiftCount);
}
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
int maxOverlaps = 0;
for (int yShift = 0; yShift < A.size(); ++yShift) {
for (int xShift = 0; xShift < A.size(); ++xShift) {
maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B));
maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A));
}
}
return maxOverlaps;
}
};3 238
Задача: 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 238
Задача: 1032. Stream of Characters
Сложность: hard
Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.
Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.
Пример:
Input ["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"] [[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]] Output [null, false, false, false, true, false, true, false, false, false, false, false, true]👨💻 Алгоритм: 1⃣Построение суффиксного Trie: Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов. 2⃣Проверка суффиксов: Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы. 3⃣Сравнение двух случаев: Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая. 😎 Решение:
class TrieNode {
public:
TrieNode* children[26] = {};
bool is_end_of_word = false;
};
class StreamChecker {
public:
StreamChecker(vector<string>& words) {
root = new TrieNode();
for (const string& word : words) {
TrieNode* node = root;
for (int i = word.size() - 1; i >= 0; --i) {
if (!node->children[word[i] - 'a']) {
node->children[word[i] - 'a'] = new TrieNode();
}
node = node->children[word[i] - 'a'];
}
node->is_end_of_word = true;
}
}
bool query(char letter) {
stream.push_front(letter);
TrieNode* node = root;
for (char c : stream) {
if (!node->children[c - 'a']) return false;
node = node->children[c - 'a'];
if (node->is_end_of_word) return true;
}
return false;
}
private:
TrieNode* root;
deque<char> stream;
};3 238
Задача: 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 238
Задача: 291. Word Pattern II
Сложность: medium
Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Биекция между символами шаблона и подстроками строки: каждый символ → уникальная подстрока и наоборот.
Пример:
Input: pattern = "abab", s = "redblueredblue" Output: true👨💻 Алгоритм 1⃣Создайте отображения: symbolMap: символ шаблона → строка wordSet: множество уже использованных строк Запустите рекурсивную функцию isMatch с текущими индексами строки и шаблона. 2⃣Базовые случаи: Если дошли до конца шаблона и строки одновременно — верните true. Если один из них завершился, а другой — нет, верните false. Если символ шаблона уже связан со строкой: Проверьте, начинается ли s с этой подстроки — если нет, верните false Иначе продолжайте рекурсию с обновлённым индексом 3⃣Если символ ещё не связан: Переберите возможные подстроки из s, начиная с текущего индекса Пропустите уже использованные строки (из wordSet) Свяжите символ с подстрокой, запустите рекурсию Если вернулась true — победа Иначе — backtrack (удалите из отображения и множества) 😎 Решение
#include <unordered_map>
#include <unordered_set>
#include <string>
class Solution {
public:
bool wordPatternMatch(std::string pattern, std::string s) {
std::unordered_map<char, std::string> symbolMap;
std::unordered_set<std::string> wordSet;
return isMatch(s, 0, pattern, 0, symbolMap, wordSet);
}
private:
bool isMatch(const std::string& s, int sIndex, const std::string& pattern, int pIndex,
std::unordered_map<char, std::string>& symbolMap, std::unordered_set<std::string>& wordSet) {
if (pIndex == pattern.size()) return sIndex == s.size();
char symbol = pattern[pIndex];
if (symbolMap.count(symbol)) {
const std::string& word = symbolMap[symbol];
if (s.substr(sIndex, word.size()) != word) return false;
return isMatch(s, sIndex + word.size(), pattern, pIndex + 1, symbolMap, wordSet);
}
for (int end = sIndex + 1; end <= s.size(); ++end) {
std::string candidate = s.substr(sIndex, end - sIndex);
if (wordSet.count(candidate)) continue;
symbolMap[symbol] = candidate;
wordSet.insert(candidate);
if (isMatch(s, end, pattern, pIndex + 1, symbolMap, wordSet)) return true;
symbolMap.erase(symbol);
wordSet.erase(candidate);
}
return false;
}
};3 238
Задача: 200. Number of Islands
Сложность: medium
Дана двумерная бинарная сетка m x n, где '1' — земля, а '0' — вода.
Необходимо вернуть количество островов — соединённых участков земли, соседствующих по горизонтали или вертикали.
Предполагается, что все четыре края сетки окружены водой.
Пример:
Input: grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]] Output: 1👨💻 Алгоритм: 1⃣Пройти по каждому элементу сетки. Если найдена '1', это старт нового острова. Запустить DFS от этой ячейки. 2⃣Внутри DFS заменять каждую посещённую '1' на '0', чтобы избежать повторного подсчёта. 3⃣Каждый запуск DFS соответствует одному острову — увеличиваем счётчик. Решение:
class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
};3 238
Задача: 1064. Fixed Point
Сложность: easy
Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.
Пример:
Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.class Solution {
public:
int fixedPoint(vector<int>& arr) {
int left = 0, right = arr.size() - 1;
int answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == mid) {
answer = mid;
right = mid - 1;
} else if (arr[mid] < mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return answer;
}
};