JavaScript
2.39K subscribers
4.01K photos
104 videos
5.34K links
Всё о JavaScript и frontend-разработке.

Проверка своих знаний по языку JavaScript.

Ссылка: @Portal_v_IT

Сотрудничество: @oleginc,
Download Telegram
Задача: 319. Bulb Switcher
Сложность: medium

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.
На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.
Верните количество лампочек, которые будут включены после n раундов.

Пример:
Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм:

1⃣Инициализация
Лампочка остается включенной, если она переключалась нечетное количество раз. Лампочка будет переключаться на каждом делителе её номера.

2
Задача: 494. Target Sum
Сложность: medium

Вам дан массив целых чисел nums и целое число target.
Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.

Пример:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

👨‍💻 Алгоритм:

1⃣Инициализация и вызов рекурсивной функции
Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).

2⃣Рекурсивная функция calculate
Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.

3⃣Возврат результата
После завершения всех рекурсивных вызовов верните значение счетчика решений.

😎 Решение:
class Solution {
constructor() {
this.count = 0;
}

findTargetSumWays(nums, S) {
this.calculate(nums, 0, 0, S);
return this.count;
}

calculate(nums, i, sum, S) {
if (i === nums.length) {
if (sum === S) {
this.count++;
}
} else {
this.calculate(nums, i + 1, sum + nums[i], S);
this.calculate(nums, i + 1, sum - nums[i], S);
}
}
}

JavaScript // чат
Задача: 739. Daily Temperatures
Сложность: medium

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

👨‍💻 Алгоритм:

1⃣Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день.

2⃣Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек.

3⃣Возвращайте массив ответов.

😎 Решение:
var dailyTemperatures = function(T) {
const answer = Array(T.length).fill(0);
const stack = [];

for (let i = 0; i < T.length; i++) {
while (stack.length && T[i] > T[stack[stack.length - 1]]) {
const j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}

return answer;

JavaScript // чат
Задача: 49. Group Anagrams
Сложность: medium

Дан массив строк strs. Сгруппируйте анаграммы вместе. Вы можете вернуть ответ в любом порядке.
Анаграмма — это слово или фраза, сформированная путем перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

👨‍💻 Алгоритм:

1️⃣Поддерживайте карту ans: {String -> List}, где каждый ключ K — это отсортированная строка, а каждое значение — это список строк из исходного ввода, которые при сортировке равны K.

2️⃣В Java ключ будет храниться как строка, например, code. В Python ключ будет храниться как хешируемый кортеж, например, ('c', 'o', 'd', 'e').

3️⃣Используя эту структуру данных, можно легко сгруппировать анаграммы, сопоставляя строки после сортировки их символов с ключами в карте.

😎 Решение:
var groupAnagrams = function (strs) {
let map = new Map();
for (let str of strs) {
let chars = Array.from(str);
chars.sort();
let key = chars.join("");
if (!map.has(key)) map.set(key, []);
map.get(key).push(str);
}
return Array.from(map.values());
};

JavaScript // чат
Задача: 310. Minimum Height Trees
Сложность: medium

Дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любое связное граф без простых циклов является деревом.
Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT).
Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке.
Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом.

Пример:
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

👨‍💻
Задача: 814. Binary Tree Pruning
Сложность: medium

Дан корень бинарного дерева. Верните то же дерево, в котором удалены все поддеревья (данного дерева), не содержащие 1.

Поддерево узла node - это сам узел node и все узлы, являющиеся потомками node.

Пример:
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

👨‍💻 Алгоритм:

1⃣Используем функцию containsOne(node), которая сообщает, содержит ли поддерево в данном узле единицу, и обрезает все поддеревья, не содержащие единицу.

2⃣Например, если поддерево node.left не содержит единицу, то мы должны обрезать его через node.left = null.

3⃣Также нужно проверить родительский узел. Например, если дерево состоит из одного узла 0, то ответом будет пустое дерево.

😎 Решение:
var pruneTree = function(root) {
if (containsOne(root)) {
return root;
}
return null;
};

var containsOne = function(node) {
if (!node) return false;

let leftContainsOne = containsOne(node.left);
let rightContainsOne = containsOne(node.right);

if (!leftContainsOne) node.left = null;
if (!rightContainsOne) node.right = null;

return node.val === 1 || le

JavaScript // чат
Задача: 281. Zigzag Iterator
Сложность: medium

Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно.
Реализуйте класс ZigzagIterator:
ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2.
boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае.
int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу.

Пример:
Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

👨‍💻 Алгоритм:

1⃣Инициализация объекта:
Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors.
Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст.

2⃣Метод next:
Удалите первую пару индексов из очереди.
Извлеките элемент из соответствующего
Задача: 593. Valid Square
Сложность: medium

Даны координаты четырех точек в 2D-пространстве p1, p2, p3 и p4. Верните true, если эти четыре точки образуют квадрат.
Координата точки pi представлена как [xi, yi]. Ввод не дан в каком-либо определенном порядке.
Корректный квадрат имеет четыре равные стороны с положительной длиной и четыре равных угла (по 90 градусов).

Пример:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: true

👨‍💻 Алгоритм:

1⃣Определите функцию для вычисления расстояния между двумя точками.

2⃣Проверьте, равны ли все стороны и диагонали для трех уникальных случаев перестановки точек.

3⃣Верните true, если хотя бы одна из проверок проходит.

😎 Решение:
var dist = function(p1, p2) {
return (p2[1] - p1[1]) ** 2 + (p2[0] - p1[0]) ** 2;
};

var check = function(p1, p2, p3, p4) {
return dist(p1, p2) > 0 &&
dist(p1, p2) === dist(p2, p3) &&
dist(p2, p3) === dist(p3, p4) &&
dist(p3, p4) === dist(p4, p1) &&
dist(p1, p3) === dist(p2, p4);
Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.
Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.

Пример:
Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

👨‍💻 Алгоритм:

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:
class Solution {
wordPatternMatch(pattern, s) {
const symbolMap = new Map();
const wordSet = new Set();
return this.isMatch(s, 0, pattern, 0, symbolMap, wordSet);
}

isMatch(s, sIndex, pattern, pIndex, symbolMap, wordSet) {
if (pIndex
if (pIndex === pattern.length) {
return sIndex === s.length;
}
const symbol = pattern[pIndex];
if (symbolMap.has(symbol)) {
const word = symbolMap.get(symbol);
if (!s.startsWith(word, sIndex)) {
return false;
}
return this.isMatch(s, sIndex + word.length, pattern, pIndex + 1, symbolMap, wordSet);
}
for (let k = sIndex + 1; k <= s.length; k++) {
const newWord = s.substring(sIndex, k);
if (wordSet.has(newWord)) {
continue;
}
symbolMap.set(symbol, newWord);
wordSet.add(newWord);
if (this.isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
return true;
}
symbolMap.delete(symbol);
wordSet.delete(newWord);
}
return false;
}
}

JavaScript // чат
Задача: 293. Flip Game
Сложность: easy

Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните все возможные состояния строки currentState после одного допустимого хода. Вы можете вернуть ответы в любом порядке. Если допустимых ходов нет, верните пустой список [].

Пример:
Input: currentState = "++++"
Output: ["--++","+--+","++--"]

👨‍💻 Алгоритм:

1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода.

2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса:
Если символы на позициях index и index + 1 равны '+':
Создайте новую строку nextState, заменив две последовательные '+' на '--'.
Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--"