This media is not supported in your browser
VIEW IN TELEGRAM
Вот 14 авторских обучающих IT каналов по самым востребованным областям программирования:
Выбирай своё направление:
Please open Telegram to view this post
VIEW IN TELEGRAM
Задача: 314. Binary Tree Vertical Order Traversal
Сложность: medium
Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом).
Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
👨💻 Алгоритм:
1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.
2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.
3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отс
Сложность: medium
Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом).
Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
👨💻 Алгоритм:
1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.
2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.
3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отс
Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium
Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.
Пример:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
👨💻 Алгоритм:
1⃣Представить каждую строку и столбец как узлы в графе.
2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.
3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.
😎 Решение:
var removeStones = function(stones) {
const parent = {};
function find(x) {
if (!(x in parent)) parent[x] = x;
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
parent[find(x)] = find(y);
}
for (const [x, y] of stones) {
union(x, ~y);
}
const uniqueRoots = new Set(Object.keys(parent).map(find));
return stones.length - uniqueRoots.size;
};
JavaScript // чат
Сложность: medium
Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.
Пример:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
👨💻 Алгоритм:
1⃣Представить каждую строку и столбец как узлы в графе.
2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце.
Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.
3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.
😎 Решение:
var removeStones = function(stones) {
const parent = {};
function find(x) {
if (!(x in parent)) parent[x] = x;
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
parent[find(x)] = find(y);
}
for (const [x, y] of stones) {
union(x, ~y);
}
const uniqueRoots = new Set(Object.keys(parent).map(find));
return stones.length - uniqueRoots.size;
};
JavaScript // чат
LeetCode
Most Stones Removed with Same Row or Column - LeetCode
Can you solve this real interview question? Most Stones Removed with Same Row or Column - On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.
A stone can be removed if it shares either the…
A stone can be removed if it shares either the…
Задача: 152. Maximum Product Subarray
Сложность: medium
Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
👨💻 Алгоритм:
1️⃣Инициализация:
Если массив nums пуст, возвращаем 0, так как нет элементов для обработки.
Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.
2️⃣Перебор элементов:
Используем вложенные циклы для обработки всех возможных подмассивов:
Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива.
Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив.
3️⃣Вычисление произведения и обновление результата:
Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого.
Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.
😎 Решение:
var maxProduct = function (nums) {
if (nums.length === 0) return 0;
let result = nums[0];
for (let i = 0; i < nums.length; i++) {
let accu = 1;
for (let j = i; j < nums.length; j++) {
accu *= nums[j];
result = Math.max(result, accu);
}
}
return result;
};
JavaScript // чат
Сложность: medium
Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
👨💻 Алгоритм:
1️⃣Инициализация:
Если массив nums пуст, возвращаем 0, так как нет элементов для обработки.
Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения.
2️⃣Перебор элементов:
Используем вложенные циклы для обработки всех возможных подмассивов:
Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива.
Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив.
3️⃣Вычисление произведения и обновление результата:
Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого.
Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result.
😎 Решение:
var maxProduct = function (nums) {
if (nums.length === 0) return 0;
let result = nums[0];
for (let i = 0; i < nums.length; i++) {
let accu = 1;
for (let j = i; j < nums.length; j++) {
accu *= nums[j];
result = Math.max(result, accu);
}
}
return result;
};
JavaScript // чат
LeetCode
Maximum Product Subarray - LeetCode
Can you solve this real interview question? Maximum Product Subarray - Given an integer array nums, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Note…
The test cases are generated so that the answer will fit in a 32-bit integer.
Note…
Задача: 88. Merge Sorted Array
Сложность: easy
Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.
Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.
Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.
Пример:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
👨💻 Алгоритм:
1️⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух
Сложность: easy
Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.
Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.
Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.
Пример:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
👨💻 Алгоритм:
1️⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух
Уже очевидно, что ВАЙБКОДИНГ — главный навык ближайших лет
Посмотрите сами. ИИ уже забирает на себя работу целых команд: пишет код, закрывает задачи джунов и позволяет стартапам запускать продукты в 2–3 раза меньшим составом. То, на что раньше нужны были несколько разработчиков, сегодня всё чаще делает один человек с ИИ-агентами.
И это только начало. Те, кто освоит вайбкодинг сейчас, смогут быстрее запускать проекты, автоматизировать огромный объём работы, увереннее конкурировать на рынке и зарабатывать больше тех, кто продолжает делать всё вручную.
Начать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 60 тысяч: @vibecoding_tg
Посмотрите сами. ИИ уже забирает на себя работу целых команд: пишет код, закрывает задачи джунов и позволяет стартапам запускать продукты в 2–3 раза меньшим составом. То, на что раньше нужны были несколько разработчиков, сегодня всё чаще делает один человек с ИИ-агентами.
И это только начало. Те, кто освоит вайбкодинг сейчас, смогут быстрее запускать проекты, автоматизировать огромный объём работы, увереннее конкурировать на рынке и зарабатывать больше тех, кто продолжает делать всё вручную.
Начать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 60 тысяч: @vibecoding_tg
Задача: 110. Balanced Binary Tree
Сложность: easy
Дано бинарное дерево, определите, является ли оно
сбалансированным по высоте.
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: true
👨💻 Алгоритм:
1️⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает:
-1, если p является пустым поддеревом, т.е. null;
1 + max(height(p.left), height(p.right)) в противном случае.
2️⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы.
3️⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них:
Если root == NULL, возвращаем true.
Если abs(height(root.left) - height(root.right)) > 1, возвращаем false.
В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).
😎 Решение:
var height
Сложность: easy
Дано бинарное дерево, определите, является ли оно
сбалансированным по высоте.
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: true
👨💻 Алгоритм:
1️⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает:
-1, если p является пустым поддеревом, т.е. null;
1 + max(height(p.left), height(p.right)) в противном случае.
2️⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы.
3️⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них:
Если root == NULL, возвращаем true.
Если abs(height(root.left) - height(root.right)) > 1, возвращаем false.
В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).
😎 Решение:
var height
Задача: 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 для левого и правого дочерних узлов с обновленными параметрами длины и направления.
😎 Решение:
var longestZigZag = function(root) {
let maxLength = 0;
const dfs = (node, isLeft, length) => {
if (!node) return;
maxLength = Math.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);
}
};
dfs(root, true, 0);
dfs(root, false, 0);
return maxLength;
};
JavaScript // чат
Сложность: 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 для левого и правого дочерних узлов с обновленными параметрами длины и направления.
😎 Решение:
var longestZigZag = function(root) {
let maxLength = 0;
const dfs = (node, isLeft, length) => {
if (!node) return;
maxLength = Math.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);
}
};
dfs(root, true, 0);
dfs(root, false, 0);
return maxLength;
};
JavaScript // чат
LeetCode
Longest ZigZag Path in a Binary Tree - LeetCode
Can you solve this real interview question? Longest ZigZag Path in a Binary Tree - You are given the root of a binary tree.
A ZigZag path for a binary tree is defined as follow:
* Choose any node in the binary tree and a direction (right or left).
* If…
A ZigZag path for a binary tree is defined as follow:
* Choose any node in the binary tree and a direction (right or left).
* If…
Задача: 1663. Smallest String With A Given Numeric Value
Сложность: medium
Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.
Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.
Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.
Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.
Пример:
Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.
👨💻 Алгоритм:
1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции.
2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
3⃣Повторять процесс, пока все позиции не будут заполнены.
😎 Решение:
class Solution {
getSmallestString(n, k) {
let result = Array(n).fill('a');
for (let position = 0; position < n; position++) {
let positionsLeft = (n - position - 1);
if (k > positionsLeft * 26) {
let add = k - (positionsLeft * 26);
result[position] = String.fromCharCode(97 + add - 1);
k -= add;
} else {
k -= 1;
}
}
return result.join('');
}
}
JavaScript // чат
Сложность: medium
Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.
Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.
Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.
Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.
Пример:
Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.
👨💻 Алгоритм:
1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции.
2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
3⃣Повторять процесс, пока все позиции не будут заполнены.
😎 Решение:
class Solution {
getSmallestString(n, k) {
let result = Array(n).fill('a');
for (let position = 0; position < n; position++) {
let positionsLeft = (n - position - 1);
if (k > positionsLeft * 26) {
let add = k - (positionsLeft * 26);
result[position] = String.fromCharCode(97 + add - 1);
k -= add;
} else {
k -= 1;
}
}
return result.join('');
}
}
JavaScript // чат
LeetCode
Smallest String With A Given Numeric Value - LeetCode
Can you solve this real interview question? Smallest String With A Given Numeric Value - The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric…