Задача: 231. Power of Two
Сложность: easy

Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.
Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.

Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

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

1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки.

2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций.

3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x.

😎 Решение:

class Solution {
    isPowerOfTwo(n) {
        if (n === 0) return false
        let x = BigInt(n)
        return (x & -x) === x
    }
}

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

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.
Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед.

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
    hammingDistance(x, y) {
        return (x ^ y).toString(2).split('0').join('').length;
    }
}

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

Задача: 1006. Clumsy Factorial
Сложность: medium

Факториал целого положительного числа n - это произведение всех целых положительных чисел, меньших или равных n. Например, факториал(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
Мы составляем неуклюжий факториал, используя целые числа в порядке убывания, заменяя операции умножения на фиксированную последовательность операций с умножением "*", делением "/", сложением "+" и вычитанием "-" в этом порядке. Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка операций арифметики. Мы выполняем все шаги умножения и деления перед шагами сложения и вычитания, а шаги умножения и деления выполняются слева направо. Кроме того, деление, которое мы используем, является делением с полом, так что 10 * 9 / 8 = 90 / 8 = 11. Учитывая целое число n, верните неуклюжий факториал n.

Пример:

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

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

1⃣Инициализация переменных и обработка первых трех чисел:
Создайте переменные для хранения результата и текущего значения.
Если n меньше или равен 3, обработайте случай отдельно, выполняя операции в порядке убывания, и верните результат.

2⃣Выполнение операций в цикле:
Создайте цикл, который будет обрабатывать числа от n до 1 в порядке убывания.
В цикле выполняйте операции *, /, +, и - последовательно.
Обновляйте текущий результат на каждом шаге в зависимости от остатка от деления текущего индекса на 4.

3⃣Учет оставшихся операций и возврат результата:
После завершения цикла добавьте или вычтите оставшиеся числа (если есть) к результату.
Верните окончательный результат.

😎 Решение:

class Solution {
    clumsy(n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2 * 1;
        if (n == 3) return 3 * 2 / 1;
        
        let res = n * (n - 1) / (n - 2);
        n -= 3;
        if (n > 0) res += n--;
        
        while (n > 0) {
            res -= n * (n - 1) / (n - 2);
            n -= 3;
            if (n > 0) res += n--;
        }
        
        return res;
    }
}

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

Задача: 520. Detect Capital
Сложность: easy

Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:
Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

var detectCapitalUse = function(word) {
    let pattern = /^[A-Z]*$|^[a-z]*$|^[A-Z][a-z]*$/;
    return pattern.test(word);
};

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

Задача: 1426. Counting Elements
Сложность: easy

Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно.

Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

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

1⃣Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве.

2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве.

3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика.

😎 Решение:

class Solution {
    countElements(arr) {
        let count = 0;
        for (let x of arr) {
            if (this.integerInArray(arr, x + 1)) {
                count++;
            }
        }
        return count;
    }

    integerInArray(arr, target) {
        for (let x of arr) {
            if (x === target) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 756. Pyramid Transition Matrix
Сложность: medium

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

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

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

3⃣Начните с нижнего уровня пирамиды и используйте рекурсию для построения каждого следующего уровня, проверяя каждый треугольный узор на допустимость.

😎 Решение:

var pyramidTransition = function(bottom, allowed) {
    let allowedDict = {};

    for (let pattern of allowed) {
        let key = pattern.slice(0, 2);
        if (!(key in allowedDict)) {
            allowedDict[key] = [];
        }
        allowedDict[key].push(pattern[2]);
    }

    function canBuild(currentLevel) {
        if (currentLevel.length == 1) return true;

        let nextLevelOptions = [];
        for (let i = 0; i < currentLevel.length - 1; i++) {
            let key = currentLevel.slice(i, i + 2);
            if (!(key in allowedDict)) return false;
            nextLevelOptions.push(allowedDict[key]);
        }

        return canBuildNextLevel(nextLevelOptions, 0, "");
    }

    function canBuildNextLevel(options, index, nextLevel) {
        if (index == options.length) return canBuild(nextLevel);
        for (let option of options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option)) return true;
        }
        return false;
    }

    return canBuild(bottom);
};

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

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.

😎 Решение:

var sortItems = function(n, m, group, beforeItems) {
    let groupId = m;
    for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = groupId++;

    const itemGraph = new Map();
    const groupGraph = new Map();
    const itemIndegree = Array(n).fill(0);
    const groupIndegree = Array(groupId).fill(0);
    for (let i = 0; i < n; i++) itemGraph.set(i, []);
    for (let i = 0; i < groupId; i++) groupGraph.set(i, []);

    for (let curr = 0; curr < n; curr++) {
        for (const prev of beforeItems[curr]) {
            itemGraph.get(prev).push(curr);
            itemIndegree[curr]++;
            if (group[curr] !== group[prev]) {
                groupGraph.get(group[prev]).push(group[curr]);
                groupIndegree[group[curr]]++;
            }
        }
    }

    const itemOrder = topologicalSort(itemGraph, itemIndegree);
    const groupOrder = topologicalSort(groupGraph, groupIndegree);
    if (itemOrder.length === 0 || groupOrder.length === 0) return [];

    const orderedGroups = new Map();
    for (const item of itemOrder) {
        if (!orderedGroups.has(group[item])) orderedGroups.set(group[item], []);
        orderedGroups.get(group[item]).push(item);
    }

    const answerList = [];
    for (const groupIndex of groupOrder) {
        if (orderedGroups.has(groupIndex)) answerList.push(...orderedGroups.get(groupIndex));
    }

    return answerList;
};

function topologicalSort(graph, indegree) {
    const visited = [];
    const stack = [];
    for (const [key] of graph.entries()) if (indegree[key] === 0) stack.push(key);

    while (stack.length > 0) {
        const curr = stack.pop();
        visited.push(curr);
        for (const next of graph.get(curr)) {
            indegree[next]--;
            if (indegree[next] === 0) stack.push(next);
        }
    }

    return visited.length === graph.size ? visited : [];
}

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

Задача: 228. Summary Ranges
Сложность: easy

Вам дан отсортированный массив уникальных целых чисел nums.
Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).
Верните наименьший отсортированный список диапазонов, которые покрывают все числа в массиве точно. То есть, каждый элемент nums покрывается ровно одним из диапазонов, и не существует такого целого числа x, чтобы x находился в одном из диапазонов, но не находился в nums.
Каждый диапазон [a,b] в списке должен быть представлен в формате:
"a->b" если a != b
"a" если a == b

Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

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

1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i].

2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики.

3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон.

😎 Решение:

class Solution {
    summaryRanges(nums) {
        let ranges = []
        let i = 0
        while (i < nums.length) {
            let start = nums[i]
            while (i + 1 < nums.length && nums[i] + 1 == nums[i + 1]) {
                i++
            }
            if (start != nums[i]) {
                ranges.push(`${start}->${nums[i]}`)
            } else {
                ranges.push(`${start}`)
            }
            i++
        }
        return ranges
    }
}

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

Задача: 443. String Compression
Сложность: medium

Дан массив символов chars, сжать его, используя следующий алгоритм:
Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:
Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.
После того как вы закончите модификацию входного массива, верните новую длину массива.
Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

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

1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.

2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.

3⃣Верните res.

😎 Решение:

var compress = function(chars) {
    let i = 0, res = 0;
    while (i < chars.length) {
        let groupLength = 1;
        while (i + groupLength < chars.length && chars[i + groupLength] === chars[i]) {
            groupLength++;
        }
        chars[res++] = chars[i];
        if (groupLength > 1) {
            let strRepr = groupLength.toString();
            for (let ch of strRepr) {
                chars[res++] = ch;
            }
        }
        i += groupLength;
    }
    return res;
};

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

Задача: 923. 3Sum With Multiplicity
Сложность: medium

Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Отсортировать массив arr.

2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.

3⃣Вернуть результат по модулю 10^9 + 7.

😎 Решение:

var threeSumMulti = function(arr, target) {
    arr.sort((a, b) => a - b);
    const MOD = 10**9 + 7;
    let count = 0;
    
    for (let i = 0; i < arr.length; i++) {
        let j = i + 1, k = arr.length - 1;
        
        while (j < k) {
            let sum = arr[i] + arr[j] + arr[k];
            if (sum === target) {
                if (arr[j] === arr[k]) {
                    count += (k - j + 1) * (k - j) / 2;
                    break;
                } else {
                    let left = 1, right = 1;
                    while (j + 1 < k && arr[j] === arr[j + 1]) {
                        left++;
                        j++;
                    }
                    while (k - 1 > j && arr[k] === arr[k - 1]) {
                        right++;
                        k--;
                    }
                    count += left * right;
                    j++;
                    k--;
                }
            } else if (sum < target) {
                j++;
            } else {
                k--;
            }
        }
    }
    
    return count % MOD;
};

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

Задача: 93. Restore IP Addresses
Сложность: medium

Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:

- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"

Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:

- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)

Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06".

Для данной строки s, содержащей только цифры, верните количество способов декодирования.

Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.

Пример:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

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

1️⃣Входим в рекурсию с данной строкой, начиная с индекса 0.

2️⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов.

3️⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач.


😎 Решение:

var restoreIpAddresses = function (s) {
    var ans = [];
    function valid(s, start, length) {
        return (
            length == 1 ||
            (s.charAt(start) != "0" &&
                (length < 3 || s.substring(start, start + length) <= 255))
        );
    }
    function helper(s, startIndex, dots, ans) {
        var remainingLength = s.length - startIndex;
        var remainingNumberOfIntegers = 4 - dots.length;
        if (
            remainingLength > remainingNumberOfIntegers * 3 ||
            remainingLength < remainingNumberOfIntegers
        ) {
            return;
        }
        if (dots.length == 3) {
            if (valid(s, startIndex, remainingLength)) {
                var temp = "";
                var last = 0;
                for (var dot of dots) {
                    temp += s.substring(last, last + dot) + ".";
                    last += dot;
                }
                temp += s.substring(startIndex);
                ans.push(temp);
            }
            return;
        }
        for (
            var curPos = 1;
            curPos <= 3 && curPos <= remainingLength;
            ++curPos
        ) {
            dots.push(curPos);
            if (valid(s, startIndex, curPos)) {
                helper(s, startIndex + curPos, dots, ans);
            }
            dots.pop();
        }
    }
    helper(s, 0, [], ans);
    return ans;
};

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

Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

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

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

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

var numPermsDISequence = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= i; j++) {
            if (s[i - 1] === 'D') {
                dp[i][j] = dp[i - 1].slice(j, i).reduce((sum, x) => (sum + x) % MOD, 0);
            } else {
                dp[i][j] = dp[i - 1].slice(0, j).reduce((sum, x) => (sum + x) % MOD, 0);
            }
        }
    }

    return dp[n].reduce((sum, x) => (sum + x) % MOD, 0);
};

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

Задача: 1673. Find the Most Competitive Subsequence
Сложность: medium

Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k.

Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива.

Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.

Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

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

1⃣Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность.

2⃣Переберите массив nums, выбирая наиболее конкурентоспособные элементы и добавляя их в очередь. Сравнивайте последний элемент в очереди с текущим элементом, удаляя из очереди более крупные элементы, если можно удалить больше элементов, чем необходимо для достижения размера k.

3⃣ В конце получите первые k элементов из очереди и создайте результирующий массив.

😎 Решение:

var mostCompetitive = function(nums, k) {
    let queue = [];
    let additionalCount = nums.length - k;
    
    for (let num of nums) {
        while (queue.length > 0 && queue[queue.length - 1] > num && additionalCount > 0) {
            queue.pop();
            additionalCount--;
        }
        queue.push(num);
    }
    
    return queue.slice(0, k);
};

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

Задача: 509. Fibonacci Number
Сложность: easy

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

var fib = function(N) {
    if (N <= 1) return N;
    let current = 0, prev1 = 1, prev2 = 0;
    for (let i = 2; i <= N; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
};

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

Задача: 1232. Check If It Is a Straight Line
Сложность: easy

Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.

Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

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

1⃣Определение наклона:
Вычисляем наклон между первыми двумя точками и используем его как эталон.

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

3⃣Если все наклоны совпадают, то все точки лежат на одной прямой.

😎 Решение:

var checkStraightLine = function(coordinates) {
    const [x0, y0] = coordinates[0];
    const [x1, y1] = coordinates[1];
    
    for (const [x, y] of coordinates) {
        if ((x1 - x0) * (y - y0) !== (y1 - y0) * (x - x0)) {
            return false;
        }
    }
    return true;
};

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

Задача: 139. Word Break
Сложность: medium

Дана строка s и словарь строк wordDict. Верните true, если строку s можно разделить на последовательность одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.

Пример:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

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

1️⃣Инициализация структур данных:
Преобразуйте wordDict в множество words для быстрой проверки вхождения.
Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов.

2️⃣Обход в ширину (BFS):
Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start.
Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря.
Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже.

3️⃣Проверка подстроки и обновление структур:
Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый.
Если BFS завершается и конечный узел не достигнут, возвращайте false.

😎 Решение:

var wordBreak = function (s, wordDict) {
    let words = new Set(wordDict);
    let queue = [0];
    let seen = new Set();
    while (queue.length != 0) {
        let start = queue.shift();
        if (start == s.length) return true;
        for (let end = start + 1; end <= s.length; end++) {
            if (seen.has(end)) continue;
            if (words.has(s.substring(start, end))) {
                queue.push(end);
                seen.add(end);
            }
        }
    }
    return false;
};

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

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

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

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

2⃣Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.

3⃣Вернуть count.

😎 Решение:

var minDeletionSize = function(strs) {
    let count = 0;
    for (let col = 0; col < strs[0].length; col++) {
        for (let row = 1; row < strs.length; row++) {
            if (strs[row][col] < strs[row - 1][col]) {
                count++;
                break;
            }
        }
    }
    return count;
};

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

Задача: 502. IPO
Сложность: hard

LeetCode планирует IPO и хочет увеличить капитал, выполняя проекты. У компании ограниченные ресурсы, поэтому она может завершить до k проектов. Помогите LeetCode максимизировать капитал после завершения этих проектов.
У вас есть n проектов с чистой прибылью profits[i] и минимальным капиталом capital[i] для начала.
Изначально у вас есть капитал w. Завершив проект, вы получаете его прибыль, которая добавляется к вашему капиталу.
Выберите до k проектов, чтобы максимально увеличить капитал, и верните его окончательное значение. Ответ гарантированно поместится в 32-битное целое число.

Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

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

1⃣Сортировка и инициализация
Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста.

2⃣Выбор проектов
Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм.

3⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.

😎 Решение:

class MaxHeap {
    constructor(compare) {
        this.heap = [];
        this.compare = compare;
    }

    insert(value) {
        this.heap.push(value);
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.compare(this.heap[index], this.heap[parentIndex]) <= 0) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    extract() {
        const max = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            let index = 0;
            const length = this.heap.length;
            while (true) {
                let left = 2 * index + 1;
                let right = 2 * index + 2;
                let largest = index;

                if (left < length && this.compare(this.heap[left], this.heap[largest]) > 0) largest = left;
                if (right < length && this.compare(this.heap[right], this.heap[largest]) > 0) largest = right;
                if (largest === index) break;
                [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
                index = largest;
            }
        }
        return max;
    }

    get size() {
        return this.heap.length;
    }
}

const findMaximizedCapital = (k, w, profits, capital) => {
    const projects = capital.map((cap, i) => [cap, profits[i]]).sort((a, b) => a[0] - b[0]);
    const maxHeap = new MaxHeap((a, b) => b - a);
    let ptr = 0;

    for (let i = 0; i < k; i++) {
        while (ptr < projects.length && projects[ptr][0] <= w) {
            maxHeap.insert(projects[ptr][1]);
            ptr++;
        }
        if (maxHeap.size === 0) break;
        w += maxHeap.extract();
    }

    return w;
};

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

Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: nums = [4,6,15,35]
Output: 4

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

1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1.

2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.

3⃣Найти размер наибольшей связной компоненты.

😎 Решение:

var largestComponentSize = function(nums) {
    const parent = {};
    const rank = {};
    
    nums.forEach(num => {
        parent[num] = num;
        rank[num] = 0;
    });
    
    const find = (x) => {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    };
    
    const union = (x, y) => {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX !== rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    };
    
    const primeFactors = (n) => {
        const factors = new Set();
        let d = 2;
        while (d * d <= n) {
            while (n % d === 0) {
                factors.add(d);
                n = Math.floor(n / d);
            }
            d++;
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    };
    
    const primeToIndex = {};
    nums.forEach(num => {
        const primes = primeFactors(num);
        primes.forEach(prime => {
            if (!primeToIndex[prime]) {
                primeToIndex[prime] = [];
            }
            primeToIndex[prime].push(num);
        });
    });
    
    for (const primes of Object.values(primeToIndex)) {
        for (let i = 1; i < primes.length; i++) {
            union(primes[0], primes[i]);
        }
    }
    
    const size = {};
    nums.forEach(num => {
        const root = find(num);
        if (!size[root]) {
            size[root] = 0;
        }
        size[root]++;
    });
    
    return Math.max(...Object.values(size));
};

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

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

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

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

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

😎 Решение:

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    let dp = matrix[0].slice();
    
    for (let i = 1; i < n; i++) {
        const newDp = new Array(n).fill(0);
        for (let j = 0; j < n; j++) {
            newDp[j] = matrix[i][j] + Math.min(dp[j], dp[j-1] !== undefined ? dp[j-1] : Infinity, dp[j+1] !== undefined ? dp[j+1] : Infinity);
        }
        dp = newDp;
    }
    
    return Math.min(...dp);
};

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