C/C++ | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد
الشبكة:3 232
المشتركون
-124 ساعات
-97 أيام
-630 أيام
أرشيف المشاركات
3 233
Задача: 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 233
Задача: 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 233
Задача: №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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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 233
Задача: 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;
}
};3 233
Задача: 1329. Sort the Matrix Diagonally
Сложность: medium
Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].
Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.
Пример:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
size_t m = mat.size();
size_t n = mat[0].size();
map<int, priority_queue<int, vector<int>, greater<int>>> diagonals;
for (size_t row = 0; row < m; row++) {
for (size_t col = 0; col < n; col++) {
diagonals[row - col].push(mat[row][col]);
}
}
for (size_t row = 0; row < m; row++) {
for (size_t col = 0; col < n; col++) {
mat[row][col] = diagonals[row - col].top();
diagonals[row - col].pop();
}
}
return mat;
}
};3 233
АЙТИШНИКИ, ХВАТИТ сливать время на прилизанные новости и бесполезные курсы
Проект «ИИнтеллигенция» стал главным каналом для тех, кто использует нейросети на уровне разработки, автоматизации и опенсорса, а не просто балуется в чатах. Здесь собирают только то, что реально экономит человеко-часы и работает в проде.
🎓 Готовые ИИ-сервисы, промпты и ИИ-агенты для автоматизации рутины
📚 Разборы полезных ИИ-инструментов, локальных LLM и опенсорс-репозиториев
🛠 Практические кейсы, гайды по деплою моделей и интеграции ИИ в пайплайны
⚡️ Технические ИТ-новости без маркетинговой воды и душных отчетов
Обучение и прокачка в реальном времени: работа с API (Claude, GPT), локалки (Ollama, vLLM), автоматизация кода, опенсорс-утилиты, AI-агенты и др.
Ценишь время и работаешь с ИИ, подпишись: @clucai
3 233
Задача: 41. First Missing Positive
Сложность: hard
Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums.
Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти.
Пример:
Input: nums = [3,4,-1,1] Output: 2👨💻 Алгоритм: 1⃣Перебрать массив и попытаться разместить каждое число в правильной позиции: nums[i] должен быть равен i + 1 2⃣Используем swap, чтобы поставить каждый элемент на его "правильное" место, если это возможно 3⃣После расстановки — находим первый индекс, где nums[i] != i + 1. Возвращаем i + 1 😎 Решение:
int firstMissingPositive(std::vector<int>& nums) {
for (int i = 0; i < nums.size(); ) {
if (nums[i] <= 0 || nums[i] > nums.size()) {
++i;
continue;
}
if (nums[i] == i + 1) {
++i;
continue;
}
int j = nums[i];
if (nums[j - 1] == nums[i]) {
++i;
continue;
}
std::swap(nums[j - 1], nums[i]);
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.size() + 1;
}