Задача: 78. Subsets
Сложность: medium

Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).

Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.

Пример:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

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

1️⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2️⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3️⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

var subsets = function (nums) {
    let output = [];
    let n = nums.length;
    function backtrack(first = 0, curr = [], k) {
        if (curr.length == k) {
            output.push([...curr]);
            return;
        }
        for (let i = first; i < n; i++) {
            curr.push(nums[i]);
            backtrack(i + 1, curr, k);
            curr.pop();
        }
    }
    for (let k = 0; k < n + 1; k++) {
        backtrack(0, [], k);
    }
    return output;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

1⃣Инициализировать пустой стек.
Использовать указатель j для отслеживания текущей позиции в массиве popped.

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

var validateStackSequences = function(pushed, popped) {
    const stack = [];
    let j = 0;
    for (let x of pushed) {
        stack.push(x);
        while (stack.length && j < popped.length && stack[stack.length - 1] === popped[j]) {
            stack.pop();
            j++;
        }
    }
    return j === popped.length;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 958. Check Completeness of a Binary Tree
Сложность: medium

Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.

В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.

Пример:

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

1⃣Если корень дерева равен null, верните true.

2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.

3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.

😎 Решение:

var isCompleteTree = function(root) {
    if (root === null) {
        return true;
    }

    let queue = [root];
    let nullNodeFound = false;

    while (queue.length > 0) {
        let node = queue.shift();
        
        if (node === null) {
            nullNodeFound = true;
        } else {
            if (nullNodeFound) {
                return false;
            }
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    return true;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 166. Fraction to Recurring Decimal
Сложность: medium

Даны два целых числа, представляющих числитель и знаменатель дроби. Верните дробь в строковом формате.
Если дробная часть повторяется, заключите повторяющуюся часть в скобки.
Если возможны несколько ответов, верните любой из них.
Гарантируется, что длина строки ответа будет меньше 10^4 для всех предоставленных входных данных.

Пример:

Input: numerator = 1, denominator = 2
Output: "0.5"

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

1️⃣Использование хеш-таблицы для отслеживания остатков:
Создайте хеш-таблицу для хранения соответствия между остатком от деления и его позицией в дробной части. Это поможет определить начало повторяющейся части.
Для каждого нового остатка вычислите следующую цифру результата деления и проверьте, был ли такой остаток уже получен ранее.

2️⃣Обработка нулевого остатка:
Если в процессе деления остаток становится равным нулю, это означает, что дробная часть не повторяется и процесс можно завершать.

3️⃣Учет особенностей:
Будьте осторожны с крайними случаями, такими как отрицательные дроби или особо сложные случаи, например, деление −1 на −2147483648. В этих случаях следует корректно обрабатывать знаки и возможные переполнения.

😎 Решение:

var fractionToDecimal = function (numerator, denominator) {
    if (numerator === 0) {
        return "0";
    }
    var fraction = [];
    if ((numerator < 0) ^ (denominator < 0)) {
        fraction.push("-");
    }
   
    var dividend = Math.abs(numerator);
    var divisor = Math.abs(denominator);
    fraction.push(Math.floor(dividend / divisor).toString());
    var remainder = dividend % divisor;
    if (remainder === 0) {
        return fraction.join("");
    }
    fraction.push(".");
    var map = {};
    while (remainder !== 0) {
        if (remainder in map) {
            fraction.splice(map[remainder], 0, "(");
            fraction.push(")");
            break;
        }
        map[remainder] = fraction.length;
        remainder *= 10;
        fraction.push(Math.floor(remainder / divisor).toString());
        remainder %= divisor;
    }
    return fraction.join("");
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.

3⃣Создание нового дерева:
После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева.

😎 Решение:

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    insertIntoMaxTree(root, val) {
        if (!root || val > root.val) {
            return new TreeNode(val, root, null);
        }
        root.right = this.insertIntoMaxTree(root.right, val);
        return root;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 652. Find Duplicate Subtrees
Сложность: medium

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

Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

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

1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.

2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.

😎 Решение:

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var findDuplicateSubtrees = function(root) {
    const count = new Map();
    const result = [];
    
    const serialize = (node) => {
        if (!node) return "#";
        const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
        count.set(serial, (count.get(serial) || 0) + 1);
        if (count.get(serial) === 2) {
            result.push(node);
        }
        return serial;
    };
    
    serialize(root);
    return result;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 318. Maximum Product of Word Lengths
Сложность: medium

Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.

Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

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

1⃣Предварительная обработка масок и длин
Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens.

2⃣Сравнение слов и проверка общих букв
Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd.

3⃣Возврат результата
Верните максимальное значение произведения maxProd.

😎 Решение:

var maxProduct = function(words) {
    const n = words.length;
    const masks = new Array(n).fill(0);
    const lens = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        let bitmask = 0;
        for (const ch of words[i]) {
            bitmask |= 1 << (ch.charCodeAt(0) - 'a'.charCodeAt(0));
        }
        masks[i] = bitmask;
        lens[i] = words[i].length;
    }
    
    let maxVal = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if ((masks[i] & masks[j]) === 0) {
                maxVal = Math.max(maxVal, lens[i] * lens[j]);
            }
        }
    }
    return maxVal;
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 740. Delete and Earn
Сложность: medium

Вам дан целочисленный массив nums. Вы хотите максимизировать количество очков, выполнив следующую операцию любое количество раз: Выберите любой элемент nums[i] и удалите его, чтобы заработать nums[i] очков. После этого вы должны удалить каждый элемент, равный nums[i] - 1, и каждый элемент, равный nums[i] + 1. Верните максимальное количество очков, которое вы можете заработать, применив вышеуказанную операцию некоторое количество раз.

Пример:

Input: nums = [3,4,2]
Output: 6

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

1⃣Подсчитайте количество каждого числа в массиве nums.

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

3⃣Для каждого числа num в nums, учитывайте два случая: не брать число или взять число и добавить его очки.

😎 Решение:

var deleteAndEarn = function(nums) {
    const count = {};
    nums.forEach(num => count[num] = (count[num] || 0) + 1);
    
    let prev = null;
    let avoid = 0, using = 0;
    
    Object.keys(count).sort((a, b) => a - b).forEach(num => {
        num = parseInt(num);
        if (num - 1 !== prev) {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + Math.max(avoid, using);
            avoid = newAvoid;
        } else {
            const newAvoid = Math.max(avoid, using);
            using = num * count[num] + avoid;
            avoid = newAvoid;
        }
        prev = num;
    });
    
    return Math.max(avoid, using);
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1250. Check If It Is a Good Array
Сложность: hard

Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False.

Пример:

Input: nums = [12,5,7,23]
Output: true

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

1⃣Если наибольший общий делитель (НОД) всех чисел в массиве равен 1, то массив считается хорошим.

2⃣Если НОД всех чисел больше 1, то массив не считается хорошим

3⃣Получить сумму, равную 1, умножая и складывая элементы.

😎 Решение:

var isGoodArray = function(nums) {
    let gcd = nums[0];
    for (let num of nums) {
        gcd = gcdFunc(gcd, num);
        if (gcd === 1) return true;
    }
    return gcd === 1;
};

function gcdFunc(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1054. Distant Barcodes
Сложность: medium

На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.

Пример:

Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

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

1⃣Подсчитай частоту каждого штрих-кода.
Помести все штрих-коды в максимальную кучу на основе их частоты.

2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми.

3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.

😎 Решение:

function rearrangeBarcodes(barcodes) {
    const count = new Map();
    for (const barcode of barcodes) {
        count.set(barcode, (count.get(barcode) || 0) + 1);
    }

    const maxHeap = [];
    for (const [barcode, freq] of count) {
        maxHeap.push([-freq, barcode]);
    }
    maxHeap.sort((a, b) => a[0] - b[0]);

    const result = [];
    let prevFreq = 0;
    let prevBarcode = null;

    while (maxHeap.length) {
        const [freq, barcode] = maxHeap.pop();
        result.push(barcode);
        if (prevFreq < 0) {
            maxHeap.push([prevFreq, prevBarcode]);
            maxHeap.sort((a, b) => a[0] - b[0]);
        }
        prevFreq = freq + 1;
        prevBarcode = barcode;
    }

    return result;
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 45. Jump Game II
Сложность: medium

Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].
Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:
0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].

Пример:

Input: nums = [2,3,0,1,4]
Output: 2

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

1️⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0.

2️⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]).

3️⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2.

😎 Решение:

var jump = function (nums) {
    let answer = 0,
        n = nums.length;
    let curEnd = 0,
        curFar = 0;
    for (let i = 0; i < n - 1; ++i) {
        curFar = Math.max(curFar, i + nums[i]);
        if (i === curEnd) {
            ++answer;
            curEnd = curFar;
        }
    }
    return answer;
};

Ставь 👍 и забирай 📚 Базу знаний