Available now! Telegram Research 2025 — the year's key insights 
C/C++ | LeetCode
Open in Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
Show more3 252
Subscribers
No data24 hours
-57 days
-1230 days
Posts Archive
3 251
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
#реклама
yandex.ru
О рекламодателе
3 251
Задача: 37. Sudoku Solver
Сложность: hard
Напишите программу, которая решает судоку, заполняя пустые клетки, соблюдая правила: цифры от 1 до 9 должны встречаться ровно один раз в каждой строке, столбце и каждом из девяти 3×3 блоков.
Пример:
Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]👨💻 Алгоритм: 1⃣Создаем матрицы для отслеживания наличия цифр 1–9 в строках, столбцах и блоках 3×3. Заполняем их по уже заданным цифрам на доске. 2⃣Запускаем рекурсивную функцию backtrack, которая ищет пустые клетки и пытается поместить туда цифры от 1 до 9, проверяя допустимость по строке, столбцу и блоку. 3⃣Если дошли до конца доски — судоку решено. Иначе откатываемся (backtrack) и пробуем другие варианты. 😎 Решение:
class Solution {
int n = 3;
int N = n * n;
std::vector<std::vector<int>> rows, cols, boxes;
std::vector<std::vector<char>> board;
bool sudoku_solved = false;
public:
Solution() : rows(N, std::vector<int>(N + 1, 0)), cols(N, std::vector<int>(N + 1, 0)), boxes(N, std::vector<int>(N + 1, 0)) {}
bool could_place(int d, int row, int col) {
int idx = (row / n) * n + col / n;
return rows[row][d] == 0 && cols[col][d] == 0 && boxes[idx][d] == 0;
}
void place_or_remove(int d, int row, int col, bool place) {
int idx = (row / n) * n + col / n;
int delta = place ? 1 : -1;
rows[row][d] += delta;
cols[col][d] += delta;
boxes[idx][d] += delta;
board[row][col] = place ? d + '0' : '.';
}
void backtrack(int row = 0, int col = 0) {
if (col == N) col = 0, row++;
if (row == N) {
sudoku_solved = true;
return;
}
if (board[row][col] == '.') {
for (int d = 1; d <= 9 && !sudoku_solved; d++) {
if (could_place(d, row, col)) {
place_or_remove(d, row, col, true);
backtrack(row, col + 1);
if (!sudoku_solved) place_or_remove(d, row, col, false);
}
}
} else
backtrack(row, col + 1);
}
void solveSudoku(std::vector<std::vector<char>>& in_board) {
board = in_board;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] != '.') {
int d = board[i][j] - '0';
place_or_remove(d, i, j, true);
}
}
}
backtrack();
in_board = board;
}
};3 251
Tefal X-Clean 10: Умные технологии для комфортной уборки
Tefal X-Clean 10 — беспроводной моющий вертикальный пылесос для влажной уборки.
Главная изюминка — система самоочистки роликовой щётки и сушка горячим воздухом до 65°C
Узнать больше
#реклама
tefal.ru
О рекламодателе
3 251
Задача: 99. Recover Binary Search Tree
Сложность: medium
Вам дан корень бинарного дерева поиска (BST), в котором значения ровно двух узлов дерева были поменяны местами по ошибке. Восстановите дерево, не изменяя его структуру.
Пример:
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2]👨💻 Алгоритм: 1⃣Сделайте симметричный обход дерева, чтобы получить почти отсортированный список. 2⃣Найдите два нарушающих порядок элемента (x и y), используя один проход. 3⃣Повторно обойдите дерево и поменяйте значения x и y в узлах. 😎 Решение:
class Solution {
public:
void inorder(TreeNode* root, vector<int>& nums) {
if (root == nullptr) return;
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}
vector<int> findTwoSwapped(vector<int> nums) {
int n = nums.size();
int x = -1, y = -1;
bool swapped_first_occurrence = false;
for (int i = 0; i < n - 1; ++i) {
if (nums[i + 1] < nums[i]) {
y = nums[i + 1];
if (!swapped_first_occurrence) {
x = nums[i];
swapped_first_occurrence = true;
} else {
break;
}
}
}
return vector<int>{x, y};
}
void recover(TreeNode* r, int count, int x, int y) {
if (r != nullptr) {
if (r->val == x || r->val == y) {
r->val = r->val == x ? y : x;
if (--count == 0) return;
}
recover(r->left, count, x, y);
recover(r->right, count, x, y);
}
}
void recoverTree(TreeNode* root) {
vector<int> nums;
inorder(root, nums);
vector<int> swapped = findTwoSwapped(nums);
recover(root, 2, swapped[0], swapped[1]);
}
};3 251
Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля
Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰
Научись ей бесплатно!
- Бесплатный доступ
- Разбор ДЗ от наставника
- Мощные кейсы в портфолио
Узнать больше
#реклама 16+
yudaevschool24.online
О рекламодателе
3 251
Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium
Вам дан массив целых чисел
nums и целое число target.
Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int mod = 1'000'000'007;
vector<int> power(n, 1);
for (int i = 1; i < n; ++i) {
power[i] = (power[i - 1] * 2) % mod;
}
int answer = 0;
int left = 0, right = n - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
answer = (answer + power[right - left]) % mod;
left++;
} else {
right--;
}
}
return answer;
}
};3 251
Задача: 913. Cat and Mouse
Сложность: hard
В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.
Пример:
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0👨💻 Алгоритм: 1⃣Использовать динамическое программирование с мемоизацией для хранения результатов игры для каждой комбинации позиций мыши, кота и текущего игрока. 2⃣Проверить три условия окончания игры: Мышь достигает дырки (победа мыши). Кот достигает мыши (победа кота). Позиция повторяется (ничья). 3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад. 😎 Решение:
class Solution {
public:
int catMouseGame(vector<vector<int>>& graph) {
int n = graph.size();
const int DRAW = 0, MOUSE = 1, CAT = 2;
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, DRAW)));
queue<array<int, 4>> q;
for (int i = 1; i < n; i++) {
dp[0][i][0] = MOUSE;
dp[0][i][1] = MOUSE;
dp[i][i][0] = CAT;
dp[i][i][1] = CAT;
q.push({0, i, 0, MOUSE});
q.push({0, i, 1, MOUSE});
q.push({i, i, 0, CAT});
q.push({i, i, 1, CAT});
}
while (!q.empty()) {
auto [mouse, cat, turn, winner] = q.front();
q.pop();
for (auto [m, c, t] : parents(graph, mouse, cat, turn)) {
if (dp[m][c][t] == DRAW) {
if ((t == 0 && winner == MOUSE) || (t == 1 && winner == CAT)) {
dp[m][c][t] = winner;
q.push({m, c, t, winner});
} else {
int degrees = 0;
for (auto _ : parents(graph, m, c, t)) degrees++;
if (degrees == 0) {
dp[m][c][t] = winner;
q.push({m, c, t, winner});
}
}
}
}
}
return dp[1][2][0];
}
private:
vector<array<int, 3>> parents(const vector<vector<int>>& graph, int mouse, int cat, int turn) {
vector<array<int, 3>> res;
if (turn == 1) {
for (int m : graph[mouse]) {
res.push_back({m, cat, 0});
}
} else {
for (int c : graph[cat]) {
if (c > 0) res.push_back({mouse, c, 1});
}
}
return res;
}
};3 251
Задача: 331. Verify Preorder Serialization of a Binary Tree
Сложность: medium
Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.
Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.
Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.
Пример:
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#" Output: true👨💻 Алгоритм: 1⃣Инициализация и разбор строки: Инициализируйте переменную slots значением 1, представляющую количество доступных слотов. Разделите строку по запятым, чтобы получить массив элементов. 2⃣Итерация по элементам и проверка: Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1. Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию. Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота. 3⃣Проверка завершения: После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false. 😎 Решение:
class Solution {
public:
bool isValidSerialization(string preorder) {
int slots = 1;
stringstream ss(preorder);
string node;
while (getline(ss, node, ',')) {
slots -= 1;
if (slots < 0) {
return false;
}
if (node != "#") {
slots += 2;
}
}
return slots == 0;
}
};3 251
Задача: 25. Reverse Nodes in k-Group
Сложность: hard
Учитывая заголовок связанного списка, поменяйте местами узлы списка по k за раз и верните измененный список. Если количество узлов не кратно k, то оставшиеся узлы должны остаться в исходном порядке. Значения в узлах менять нельзя — разрешено только изменять указатели.
Пример:
Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]👨💻 Алгоритм: 1⃣Подсчитываем количество узлов — если их меньше k, возвращаем head без изменений. 2⃣Разворачиваем первые k узлов обычным способом с помощью трех указателей. 3⃣Рекурсивно обрабатываем оставшуюся часть списка и присоединяем к текущему развороту. 😎 Решение:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int count(ListNode* head){
int n = 0;
while (head) {
head = head->next;
n++;
}
return n;
}
ListNode* reverseKGroup(ListNode* head, int k) {
int num = count(head);
if (num < k) return head;
ListNode *next, *prev = NULL;
ListNode *curr = head;
int x = k;
while (x--) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = reverseKGroup(next, k);
return prev;
}
};3 251
Задача: 723. Candy Crush
Сложность: medium
Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.
Пример:
Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]] Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]👨💻 Алгоритм: 1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления. 2⃣Удалите отмеченные конфеты, установив их значение в 0. 3⃣Переместите конфеты вниз, чтобы заполнить пустые ячейки, и повторите процесс, пока не останется групп конфет для удаления. 😎 Решение:
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
int m = board.size();
int n = board[0].size();
bool stable = false;
while (!stable) {
stable = true;
vector<vector<bool>> crush(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n - 2; ++j) {
int v = abs(board[i][j]);
if (v != 0 && v == abs(board[i][j + 1]) && v == abs(board[i][j + 2])) {
stable = false;
crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = true;
}
}
}
for (int i = 0; i < m - 2; ++i) {
for (int j = 0; j < n; ++j) {
int v = abs(board[i][j]);
if (v != 0 && v == abs(board[i + 1][j]) && v == abs(board[i + 2][j])) {
stable = false;
crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = true;
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (crush[i][j]) {
board[i][j] = 0;
}
}
}
for (int j = 0; j < n; ++j) {
int idx = m - 1;
for (int i = m - 1; i >= 0; --i) {
if (board[i][j] != 0) {
board[idx][j] = board[i][j];
idx--;
}
}
for (int i = idx; i >= 0; --i) {
board[i][j] = 0;
}
}
}
return board;
}3 251
Задача: 79. Word Search
Сложность: medium
Дана сетка символов board размером m на n и строка word.
Верните true, если word существует в сетке.
Слово можно составить из букв смежных ячеек по вертикали или горизонтали.
Одна ячейка не может быть использована более одного раза.
Пример:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true👨💻 Алгоритм: 1⃣Проходим по всем ячейкам сетки и вызываем backtrack() на каждой, начиная поиск слова с этой позиции. 2⃣В backtrack() проверяем: Достигнут ли конец слова (index == word.length()) — вернуть true Не вышли ли за границы или текущий символ не совпадает — вернуть false 3⃣Если текущий символ совпадает — временно помечаем его (например, '#'), запускаем DFS в 4 направлениях, а после — восстанавливаем значение ячейки. Если из одного из направлений вернётся true, значит слово найдено. 😎 Решение:
class Solution {
private:
vector<vector<char>> board;
int ROWS;
int COLS;
public:
bool exist(vector<vector<char>>& board, string word) {
this->board = board;
ROWS = board.size();
COLS = board[0].size();
for (int row = 0; row < ROWS; ++row)
for (int col = 0; col < COLS; ++col)
if (backtrack(row, col, word, 0)) return true;
return false;
}
protected:
bool backtrack(int row, int col, const string& word, int index) {
if (index >= word.length()) return true;
if (row < 0 || row == ROWS || col < 0 || col == COLS ||
board[row][col] != word[index])
return false;
bool ret = false;
board[row][col] = '#';
int rowOffsets[4] = {0, 1, 0, -1};
int colOffsets[4] = {1, 0, -1, 0};
for (int d = 0; d < 4; ++d) {
ret = backtrack(row + rowOffsets[d], col + colOffsets[d], word, index + 1);
if (ret) break;
}
board[row][col] = word[index];
return ret;
}
};3 251
Задача: 1325. Delete Leaves With a Given Value
Сложность: medium
Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.
Обратите внимание, что после удаления листового узла со значением target, если его родительский узел становится листовым узлом и имеет значение target, он также должен быть удален (необходимо продолжать делать это, пока это возможно).
Пример:
Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left).
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).class Solution {
public:
TreeNode* removeLeafNodes(TreeNode* root, int target) {
if (root == nullptr) {
return nullptr;
}
root->left = removeLeafNodes(root->left, target);
root->right = removeLeafNodes(root->right, target);
if (root->left == nullptr && root->right == nullptr && root->val == target) {
return nullptr;
}
return root;
}
};3 251
Задача: 750. Number Of Corner Rectangles
Сложность: medium
Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.
Пример:
Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]] Output: 1👨💻 Алгоритм: 1⃣Пройдите по строкам матрицы. Для каждой пары строк, найдите все столбцы, где оба значения равны 1. 2⃣Подсчитайте количество таких столбцов. Если их больше одного, то они образуют прямоугольники. 3⃣Для каждой пары строк добавьте количество возможных прямоугольников в общий счетчик. 😎 Решение:
class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = i + 1; j < grid.size(); j++) {
int numPairs = 0;
for (int k = 0; k < grid[0].size(); k++) {
if (grid[i][k] == 1 && grid[j][k] == 1) {
numPairs++;
}
}
if (numPairs > 1) {
count += numPairs * (numPairs - 1) / 2;
}
}
}
return count;
}
};3 251
Задача: 67. Add Binary
Сложность: easy
Даны две строки a и b, представляющие двоичные числа. Верните их сумму также в виде двоичной строки.
Пример:
Input: a = "11", b = "1" Output: "100"👨💻 Алгоритм: 1⃣Инициализируем переменные: carry = 0, указатели на последние символы строк a и b, и пустую строку result 2⃣Идем с конца строк, складываем соответствующие биты и carry, добавляем результат по модулю 2 в result, переносим carry на следующий разряд 3⃣После завершения всех итераций, если carry == 1, добавляем '1' в result, затем переворачиваем строку и возвращаем результат 😎 Решение:
class Solution {
public:
string addBinary(string a, string b) {
int n = a.size(), m = b.size();
if (n < m)
return addBinary(b, a);
string result;
int carry = 0, j = m - 1;
for (int i = n - 1; i >= 0; --i) {
if (a[i] == '1') ++carry;
if (j >= 0 && b[j--] == '1') ++carry;
result.push_back((carry % 2) ? '1' : '0');
carry /= 2;
}
if (carry == 1) result.push_back('1');
reverse(result.begin(), result.end());
return result;
}
};3 251
Задача: 231. Power of Two
Сложность: easy
Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.
Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.
Пример:
Input: n = 1 Output: true Explanation: 2^0 = 1👨💻 Алгоритм: 1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки. 2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций. 3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x. 😎 Решение:
class Solution {
public:
bool isPowerOfTwo(int n) {
if (n == 0) return false;
long x = n;
return (x & (-x)) == x;
}
};3 251
Задача: 425. Word Squares
Сложность: hard
Дан массив уникальных строк words, верните все квадраты слов, которые можно построить из этих слов. Одно и то же слово из words можно использовать несколько раз. Вы можете вернуть ответ в любом порядке.
Последовательность строк образует допустимый квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(количество строк, количество столбцов).
Например, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали.
Пример:
Input: words = ["area","lead","wall","lady","ball"] Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]] Explanation: The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).👨💻 Алгоритм: 1⃣Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов. 2⃣При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов. 3⃣Используйте алгоритм с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, вернитесь к предыдущему состоянию и попробуйте другое слово. 😎 Решение:
#include <vector>
#include <unordered_map>
#include <string>
#include <list>
#include <algorithm>
using namespace std;
class Solution {
private:
int N = 0;
vector<string> words;
unordered_map<string, vector<string>> prefixHashTable;
void buildPrefixHashTable(vector<string>& words) {
for (auto& word : words) {
for (int i = 1; i < N; ++i) {
string prefix = word.substr(0, i);
prefixHashTable[prefix].push_back(word);
}
}
}
vector<string> getWordsWithPrefix(string prefix) {
if (prefixHashTable.find(prefix) != prefixHashTable.end()) {
return prefixHashTable[prefix];
}
return {};
}
void backtracking(int step, list<string>& wordSquares, vector<vector<string>>& results) {
if (step == N) {
results.push_back(vector<string>(wordSquares.begin(), wordSquares.end()));
return;
}
string prefix;
for (auto& word : wordSquares) {
prefix += word[step];
}
for (auto& candidate : getWordsWithPrefix(prefix)) {
wordSquares.push_back(candidate);
backtracking(step + 1, wordSquares, results);
wordSquares.pop_back();
}
}
public:
vector<vector<string>> wordSquares(vector<string>& words) {
this->words = words;
this->N = words[0].length();
vector<vector<string>> results;
buildPrefixHashTable(words);
for (auto& word : words) {
list<string> wordSquares;
wordSquares.push_back(word);
backtracking(1, wordSquares, results);
}
return results;
}
};3 251
Repost from easyoffer
Новая фича на easyoffer – Автоотлики
Вы автоматически откликаетесь на подходящие вам вакансии. Попробуйте её бесплатно и начните получать больше предложений о работе.
🚀 Запуск занимаем всего 3 минуты, а экономит очень много времени
🛡 Это безопасно: easyoffer официально одобрен HeadHunter и прошел его модерацию.
🥷🏻 Автоотклик незаметен для рекртера. Автоотклик ничем не отличается от обычного отклика, который вы делаете вручную
Рекрутеры давно используют автоматизацию для поиска кандидатов. Так почему вы должны откликаться вручную?
💡Совет – Добавьте шаблон сопроводительного письма, чтобы откликаться на большее количество вакансий (на некоторые вакансии нельзя откликнуться без сопроводительного)
Попробовать бесплатно → https://easyoffer.ru/autoapply
3 251
Задача: 498. Diagonal Traverse
Сложность: medium
Дан массив m x n матрицы mat, верните массив всех элементов матрицы в диагональном порядке.
Пример:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,4,7,5,3,6,8,9]👨💻 Алгоритм: 1⃣Инициализация и подготовка Проверьте, пуста ли матрица. Инициализируйте переменные для хранения размеров матрицы. Создайте массив result для хранения окончательных результатов и временный список intermediate для промежуточных значений диагоналей. 2⃣Итерация по диагоналям Внешний цикл для прохождения по всем диагоналям. Головы диагоналей находятся в первой строке и последнем столбце. Внутренний цикл для итерации по элементам каждой диагонали. Индексы элементов диагонали изменяются до выхода за пределы матрицы. 3⃣Обработка диагоналей Для каждой диагонали сохраните её элементы в списке intermediate. Переверните элементы диагонали, если её номер чётный. Добавьте элементы диагонали в массив result. 😎 Решение:
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
if (mat.empty() || mat[0].empty()) return {};
int N = mat.size(), M = mat[0].size();
vector<int> result;
for (int d = 0; d < N + M - 1; ++d) {
vector<int> intermediate;
int r = d < M ? 0 : d - M + 1;
int c = d < M ? d : M - 1;
while (r < N && c >= 0) {
intermediate.push_back(mat[r][c]);
++r;
--c;
}
if (d % 2 == 0) {
reverse(intermediate.begin(), intermediate.end());
}
result.insert(result.end(), intermediate.begin(), intermediate.end());
}
return result;
}
};3 251
REKONFA Live
6 ноября приглашаем рекламодателей, агентства и рекламные площадки обсудить технологии, маркетинговые инструменты и актуальные новинки. Ключевые участники рынка поделятся опытом и расскажут:
— О ситуации на рынке рекламы
— Как продвигать и продавать в интернете в 2025 году
— Как бизнесу адаптироваться к меняющимся условиям
Вас ждут доклады на актуальные темы, классный нетворкинг, вдохновляющая атмосфера для творчества и креатива.
Встречаемся 6 ноября в Москве. Для тех, кто не сможет приехать, организуем интерактивное digital-шоу. Мероприятие бесплатное, нужно только зарегистрироваться.
Зарегистрироваться
#реклама 18+
ya.rekonfa.ru
О рекламодателе
3 251
Задача: 80. Remove Duplicates from Sorted Array II
Сложность: medium
Дан массив nums, отсортированный в неубывающем порядке.
Удалите дубликаты на месте, чтобы каждый элемент встречался не более двух раз.
Порядок должен сохраниться. Использовать можно только O(1) дополнительной памяти.
Пример:
Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3,_]👨💻 Алгоритм: 1⃣Если nums.size() < 3, сразу возвращаем длину — все элементы допустимы. 2⃣Инициализируем указатель j = 2, который будет указывать, куда вставлять следующий допустимый элемент. 3⃣Проходим по массиву с i = 2. Если nums[i] != nums[j - 2], это означает, что текущий элемент встречается не более двух раз — копируем его на позицию j и увеличиваем j. Возвращаем j — это количество допустимых элементов в массиве. 😎 Решение:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() < 3) return nums.size();
int j = 2;
for (int i = 2; i < nums.size(); i++) {
if (nums[i] != nums[j - 2]) {
nums[j++] = nums[i];
}
}
return j;
}
};