JavaScript
前往频道在 Telegram
Всё о JavaScript и frontend-разработке. Проверка своих знаний по языку JavaScript. Ссылка: @Portal_v_IT Сотрудничество: @oleginc,
显示更多
2 399
订阅者
+124 小时
-87 天
-2830 天
帖子存档
2 399
Задача: 677. Map Sum Pairs
Сложность: medium
Создайте карту, которая позволяет выполнять следующие действия:
Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:
MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.
Пример:
Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]
Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
👨💻 Алгоритм:
1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.
2⃣Если ключ начинается с префикса, добавить его значение к ответу.
3⃣Вернуть полученную сумму как результат.
😎 Решение:
class MapSum {
constructor() {
this.map = new Map();
}
insert(key, val) {
this.map.set(key, val);
}
sum(prefix) {
let ans = 0;
for (let [key, val] of this.map) {
if (key.startsWith(prefix)) {
ans += val;
}
}
return ans;
}
}
JavaScript // чат
2 399
Задача: 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 // чат
2 399
Задача: 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 // чат
2 399
Задача: 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
2 399
Уже очевидно, что ВАЙБКОДИНГ — главный навык ближайших лет
Посмотрите сами. ИИ уже забирает на себя работу целых команд: пишет код, закрывает задачи джунов и позволяет стартапам запускать продукты в 2–3 раза меньшим составом. То, на что раньше нужны были несколько разработчиков, сегодня всё чаще делает один человек с ИИ-агентами.
И это только начало. Те, кто освоит вайбкодинг сейчас, смогут быстрее запускать проекты, автоматизировать огромный объём работы, увереннее конкурировать на рынке и зарабатывать больше тех, кто продолжает делать всё вручную.
Начать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 60 тысяч: @vibecoding_tg
2 399
Задача: 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, а затем использовании двух
2 399
Задача: 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 // чат
2 399
Задача: 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 // чат
2 399
Задача: 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 обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отс
