Телеграм канал «JavaScript»

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

JavaScript // чат

бизнестрендс — легендарный агрегатор всего, что происходит в бизнесе и маркетинге прямо сейчас. Оперативные новости, вдумчивая аналитика и щепотка мемчиков.

Что задумал Альтман со своей OpenAI, когда грянет страшный кризис, расцветёт ли российская экономика, что на завтрак у Германа Грефа и какие приколы сейчас в почёте у СММщиков.

Изнанку трендов и бизнеса транслируют тут: @business_trends

Задача: 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 // чат

⚡️ В сети начали массово сливать IT-курсы и книги известных онлайн школ

Вот отсортированная база с тонной материала (постепенно пополняется):

(363 видео, 87 книги) — Python
(117 видео, 53 книги) — ВАЙБКОД
(174 видео, 91 книги) — DevOps
(415 видео, 68 книги) — Frontend
(137 видео, 93 книги) — DS/ML
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR

Скачивать ничего не нужно — все выложили в Telegram

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;
}

Задача: 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 // чат