JavaScript // чат

Сложность: easy
Задача: 375. Guess Number Higher or Lower II

Мы играем в угадайку. Правила игры следующие:

Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.

Пример:
Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

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

1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к боль

JavaScript // чат

JavaScript // чат

JavaScript // чат

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:
Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:
class Solution {
arrayPairSum(nums) {
nums.sort((a, b) => a - b);
let sum = 0;
for (let i = 0; i < nums.length; i += 2) {
sum += nums[i];
}
return sum;
}
}

JavaScript // чат

JavaScript // чат

JavaScript // чат

Задача: 919. Complete Binary Tree Inserter
Сложность: medium

Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки.

Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева.

Пример:
Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

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

1⃣Инициализация: Проход по дереву и добавление всех узлов в очередь, чтобы отслеживать узлы, у которых есть хотя бы одно пустое место для нового дочернего узла.

2⃣Вставка: Добавление нового узла в первое доступное место слева направо.

3⃣Возвращение корня: Просто возвращает корневой узел.

😎 Решение:
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}

class CBTInserter {
constructor(root) {
this.root = root;
this.deque = [];
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
if (!node.left || !node.right) {
this.deque.push(node);
}
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}

insert(v) {
const node = this.deque[0];
const newNode = new TreeNode(v);
if (!node.left) {
node.left = newNode;
} else {
node.right = newNode;
this.deque.shift();
}
this.deque.push(newNode);
return node.val;
}

get_root() {
return this.root;
}
}

JavaScript // чат

Задача: 559. Maximum Depth of N-ary Tree
Сложность: easy

Дано n-арное дерево, найдите его максимальную глубину.
Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла.
Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры).

Пример:
Input: root = [1,null,3,2,4,null,5,6]
Output: 3

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

1⃣Интуитивный подход заключается в решении задачи с помощью рекурсии.

2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search).

3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину.

😎 Решение:
class Solution {
maxDepth(root) {
if (root === null) {
return 0;
} else if (root.children.length === 0) {
return 1;
} else {
let heights = root.children.map(child => this.maxDepth(child));
return Math.max(...heights) + 1;
}

JavaScript // чат

Задача: 730. Count Different Palindromic Subsequences
Сложность: hard

Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.

Пример:
Input: s = "bccb"
Output: 6

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

1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей.

2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j.

3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок.

😎 Решение:
var countPalindromicSubsequences = function(s) {
const MOD = 10**9 + 7;
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));

for (let i = 0; i < n; i++) {
dp[i][i] = 1;
}

for (let length = 2; length <= n; length++) {
for (let i = 0; i <= n - length; i++) {
const j = i + length - 1;
if (s[i] === s[j]) {
let l = i + 1, r = j - 1;
while (l <= r && s[l] !== s[i]) l++;
while (l <= r && s[r] !== s[j]) r--;
if (l > r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
} else if (l === r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] + MOD) % MOD;
}
}

return dp[0][n - 1];
};

JavaScript // чат

Треш каждый раз одно и то же

JavaScript // чат

Начнем попозже закончим пораньше

JavaScript // чат

Задача: 30. Substring with Concatenation of All Words
Сложность: hard

Дана строка s и массив строк words, где все слова одинаковой длины.
Нужно вернуть все начальные индексы подстрок в s, которые являются конкатенацией всех слов из массива words в любой перестановке.
Слова не могут быть разделены, повторения допустимы.

Пример:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]

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

1️⃣ Вычисляем:
- len — длина одного слова
- windowSize — общее число символов в одной перестановке всех слов
- Если s.length < windowSize, возвращаем []

2️⃣ Заполняем Map m, где ключ — слово из words, значение — количество его вхождений

3️⃣ Двигаемся по строке s посимвольно:
- Для каждого индекса start проверяем, является ли подстрока от start длины windowSize валидной комбинацией слов из m
- Для проверки используем isConcat()

😎 Решение:
var findSubstring = function(s, words) {
const len = words[0].length;
const windowSize = words.length * len;
if (s.length < wi

JavaScript // чат

Спиздила у @theaftertimes он разрешил!

JavaScript // чат

JavaScript // чат