C/C++ | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Mostrar más
Red:3 239
Suscriptores
+124 horas
+27 días
+630 días
Archivo de publicaciones
3 238
Задача: 870. Advantage Shuffle
Сложность: medium
Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i].
Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2.
Пример:
Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
vector<int> sortedA(A);
sort(sortedA.begin(), sortedA.end());
vector<pair<int, int>> sortedB;
for (int i = 0; i < B.size(); ++i)
sortedB.push_back({B[i], i});
sort(sortedB.begin(), sortedB.end());
unordered_map<int, deque<int>> assigned;
for (int b: B) assigned[b] = {};
deque<int> remaining;
int j = 0;
for (int a: sortedA) {
if (a > sortedB[j].first) {
assigned[sortedB[j++].first].push_back(a);
} else {
remaining.push_back(a);
}
}
vector<int> ans(B.size());
for (int i = 0; i < B.size(); ++i) {
if (assigned[B[i]].size() > 0) {
ans[i] = assigned[B[i]].front();
assigned[B[i]].pop_front();
} else {
ans[i] = remaining.front();
remaining.pop_front();
}
}
return ans;
}
};3 238
Задача: 775. Global and Local Inversions
Сложность: medium
Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].
Число глобальных инверсий — это количество различных пар (i, j), где:
0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:
0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.
Пример:
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
int N = A.size();
for (int i = 0; i < N; ++i)
for (int j = i + 2; j < N; ++j)
if (A[i] > A[j]) return false;
return true;
}
};3 238
Задача: 733. Flood Fill
Сложность: easy
Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.
Пример:
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]]👨💻 Алгоритм: 1⃣Получите цвет начального пикселя. 2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет. 3⃣Обновите изображение и верните его. 😎 Решение:
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int originalColor = image[sr][sc];
if (originalColor == color) {
return image;
}
dfs(image, sr, sc, originalColor, color);
return image;
}
private:
void dfs(vector<vector<int>>& image, int x, int y, int originalColor, int newColor) {
if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != originalColor) {
return;
}
image[x][y] = newColor;
dfs(image, x + 1, y, originalColor, newColor);
dfs(image, x - 1, y, originalColor, newColor);
dfs(image, x, y + 1, originalColor, newColor);
dfs(image, x, y - 1, originalColor, newColor);
}
};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;
}
};