Сложность: medium
Задача: 237. Delete Node in a Linked List

Дан односвязный список с головой head, и требуется удалить узел node в этом списке.
Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head.
Все значения в односвязном списке уникальны, и гарантируется, что данный узел node не является последним узлом в списке.
Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду:
- Значение данного узла не должно существовать в односвязном списке.
- Количество узлов в односвязном списке должно уменьшиться на один.
- Все значения перед узлом должны оставаться в том же порядке.
- Все значения после узла должны оставаться в том же порядке.

Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

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

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка.

😎 Решение:

class Solution {
    deleteNode(node) {
        node.val = node.next.val
        node.next = node.next.next
    }
}

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

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

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 16
Output: true

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

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

2⃣Проверка логарифмом:
Используйте логарифм для проверки, является ли число степенью четырех. Число n является степенью четырех, если логарифм n по основанию 4 является целым числом.

3⃣Проверка побитовым оператором:
Число является степенью четырех, если оно является степенью двух (только один бит установлен) и количество нулей после этого бита четно.

😎 Решение:

var isPowerOfFour = function(n) {
    if (n <= 0) return false;
    const log_n_base_4 = Math.log(n) / Math.log(4);
    return log_n_base_4 === Math.floor(log_n_base_4);
};

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

Задача: 400. Nth Digit
Сложность: medium

Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Пример:

Input: n = 3
Output: 3

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

1⃣Определение диапазона
Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.).
Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра.

2⃣Нахождение конкретного числа
Когда определите диапазон, найдите точное число, содержащее n-ю цифру.
Определите индекс цифры в этом числе.

3⃣Возвращение n-й цифры
Извлеките и верните n-ю цифру из найденного числа.

😎 Решение:

class Solution {
    findNthDigit(n) {
        let length = 1, count = 9, start = 1;
        
        while (n > length * count) {
            n -= length * count;
            length++;
            count *= 10;
            start *= 10;
        }
        
        start += Math.floor((n - 1) / length);
        const s = start.toString();
        return parseInt(s[(n - 1) % length]);
    }
}

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

Задача: 537. Complex Number Multiplication
Сложность: medium

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

var complexNumberMultiply = function(a, b) {
    const x = a.split('+');
    const y = b.split('+');
    const a_real = parseInt(x[0]);
    const a_img = parseInt(x[1].slice(0, -1));
    const b_real = parseInt(y[0]);
    const b_img = parseInt(y[1].slice(0, -1));
    const realPart = a_real * b_real - a_img * b_img;
    const imaginaryPart = a_real * b_img + a_img * b_real;
    return realPart + "+" + imaginaryPart + "i";
};

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

Задача: 253. Meeting Rooms II
Сложность: medium

Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

1️⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

2️⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче):
Если свободна, обновите время окончания этой комнаты.
Если не свободна, добавьте новое время окончания в кучу.

3️⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.

😎 Решение:

class Solution {
    minMeetingRooms(intervals) {
        intervals.sort((a, b) => a[0] - b[0])
        const heap = [intervals[0][1]]
        
        for (let i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= heap[0]) {
                heap.shift()
            }
            heap.push(intervals[i][1])
            heap.sort((a, b) => a - b)
        }
        return heap.length
    }
}

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

Задача: 468. Validate IP Address
Сложность: medium

Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "[email protected]" являются недопустимыми IPv4-адресами.
Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7
", где:
1 <= xi.length <= 4
xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F').
Ведущие нули в xi допускаются.

Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

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

1⃣Для проверки адреса IPv4:
Разделить IP на четыре части по разделителю ".".
Проверить каждую подстроку:
Является ли она целым числом между 0 и 255.
Не содержит ли она ведущих нулей (исключение — число "0").

2⃣Для проверки адреса IPv6:
Разделить IP на восемь частей по разделителю ":".
Проверить каждую подстроку:
Является ли она шестнадцатеричным числом длиной от 1 до 4 символов.

3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither".

😎 Решение:

class Solution {
    validateIPv4(IP) {
        const nums = IP.split(".");
        if (nums.length !== 4) return "Neither";
        for (let x of nums) {
            if (x.length === 0 || x.length > 3) return "Neither";
            if (x[0] === '0' && x.length !== 1) return "Neither";
            if (!/^\d+$/.test(x)) return "Neither";
            if (parseInt(x) > 255) return "Neither";
        }
        return "IPv4";
    }

    validateIPv6(IP) {
        const nums = IP.split(":");
        const hexdigits = "0123456789abcdefABCDEF";
        if (nums.length !== 8) return "Neither";
        for (let x of nums) {
            if (x.length === 0 || x.length > 4) return "Neither";
            for (let ch of x) {
                if (!hexdigits.includes(ch)) return "Neither";
            }
        }
        return "IPv6";
    }

    validIPAddress(IP) {
        if (IP.split(".").length === 4) {
            return this.validateIPv4(IP);
        } else if (IP.split(":").length === 8) {
            return this.validateIPv6(IP);
        } else {
            return "Neither";
        }
    }
}

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

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

Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

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

2⃣Проверка уникальности символов:
Для проверки уникальности символов используем множество (set). Если все символы строки уникальны и не пересекаются с символами текущей комбинации, мы можем добавить строку.

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

😎 Решение:

var maxLength = function(arr) {
    const isUnique = s => new Set(s).size === s.length;

    const backtrack = (index, current) => {
        if (!isUnique(current)) return 0;
        let maxLength = current.length;
        for (let i = index; i < arr.length; i++) {
            maxLength = Math.max(maxLength, backtrack(i + 1, current + arr[i]));
        }
        return maxLength;
    };

    return backtrack(0, "");
};

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

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

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.
Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

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

1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1.

3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask.

😎 Решение:

class Solution {
    findComplement(num) {
        let bitmask = num;
        bitmask |= (bitmask >> 1);
        bitmask |= (bitmask >> 2);
        bitmask |= (bitmask >> 4);
        bitmask |= (bitmask >> 8);
        bitmask |= (bitmask >> 16);
        return bitmask ^ num;
    }
}

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

Задача: 148. Sort List
Сложность: medium

Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.

Пример:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

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

1️⃣Разделение списка (Фаза разделения):
Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка.

2️⃣Сортировка подсписков и их объединение (Фаза слияния):
Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.

3️⃣Иллюстрация процесса сортировки:
Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.

😎 Решение:

var sortList = function (head) {
    if (!head || !head.next) return head;

    let mid = getMid(head);
    let left = sortList(head);
    let right = sortList(mid);
    return merge(left, right);

    function merge(list1, list2) {
        let dummyHead = new ListNode();
        let tail = dummyHead;
        while (list1 && list2) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = list1 ? list1 : list2;
        return dummyHead.next;
    }

    function getMid(head) {
        let midPrev = null;
        while (head && head.next) {
            midPrev = midPrev === null ? head : midPrev.next;
            head = head.next.next;
        }
        let mid = midPrev.next;
        midPrev.next = null;
        return mid;
    }
};

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

Задача: 421. Maximum XOR of Two Numbers in an Array
Сложность: medium

Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.

Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

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

1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0.

2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0):
Сдвигайте max_xor влево, чтобы освободить следующий бит.
Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы.

3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums:
Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i.
Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите.

😎 Решение:

class Solution {
    findMaximumXOR(nums) {
        let maxNum = nums[0];
        for (const num of nums) {
            if (num > maxNum) {
                maxNum = num;
            }
        }
        const L = maxNum.toString(2).length;

        let maxXor = 0;
        for (let i = L - 1; i >= 0; i--) {
            maxXor <<= 1;
            const currXor = maxXor | 1;
            const prefixes = new Set();
            for (const num of nums) {
                prefixes.add(num >> i);
            }
            for (const p of prefixes) {
                if (prefixes.has(currXor ^ p)) {
                    maxXor = currXor;
                    break;
                }
            }
        }
        return maxXor;
    }
}

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

Задача: 1425. Constrained Subsequence Sum
Сложность: hard

Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.

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

Пример:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

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

1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums.

2⃣Итерируйте i по индексам nums:
Если i минус первый элемент queue больше k, удалите элемент из начала queue.
Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()].
Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue.
Если dp[i] > 0, добавьте i в конец queue.

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

😎 Решение:

class Solution {
    constrainedSubsetSum(nums, k) {
        const queue = [];
        const dp = new Array(nums.length).fill(0);
        let maxSum = Number.MIN_SAFE_INTEGER;
        
        for (let i = 0; i < nums.length; i++) {
            if (queue.length > 0 && i - queue[0] > k) {
                queue.shift();
            }
            
            dp[i] = (queue.length > 0 ? dp[queue[0]] : 0) + nums[i];
            
            while (queue.length > 0 && dp[queue[queue.length - 1]] < dp[i]) {
                queue.pop();
            }
            
            if (dp[i] > 0) {
                queue.push(i);
            }
            
            maxSum = Math.max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

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

Задача: 392. Is Subsequence
Сложность: easy

Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.
Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).

Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов.

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

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

😎 Решение:

function isSubsequence(s, t) {
    let leftBound = s.length, rightBound = t.length;
    let pLeft = 0, pRight = 0;

    while (pLeft < leftBound && pRight < rightBound) {
        if (s[pLeft] === t[pRight]) {
            pLeft += 1;
        }
        pRight += 1;
    }
    return pLeft === leftBound;
}

// Example usage
console.log(isSubsequence("abc", "ahbgdc")); // Output: true
console.log(isSubsequence("axc", "ahbgdc")); // Output: false

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

Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

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

2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.

😎 Решение:

class Solution {
    videoStitching(clips, T) {
        clips.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
        let end = -1, end2 = 0, res = 0;
        
        for (const [start, finish] of clips) {
            if (end2 >= T || start > end2) break;
            if (end < start && start <= end2) {
                res++;
                end = end2;
            }
            end2 = Math.max(end2, finish);
        }
        return end2 >= T ? res : -1;
    }
}

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

Задача: 639. Decode Ways II
Сложность: hard

Сообщение, содержащее буквы от 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". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"
Output: 9

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

1⃣Инициализация
Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

2⃣Обход строки
Используйте цикл для обхода строки и вычисления количества способов декодирования для каждого символа, включая обработку символа '*'.

3⃣Модульное вычисление
Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎 Решение:

var numDecodings = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= n; i++) {
        if (s[i - 1] === '*') {
            dp[i] = 9 * dp[i - 1];
        } else if (s[i - 1] !== '0') {
            dp[i] = dp[i - 1];
        }

        if (i > 1) {
            if (s[i - 2] === '*') {
                if (s[i - 1] === '*') {
                    dp[i] += 15 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '1') {
                if (s[i - 1] === '*') {
                    dp[i] += 9 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '2') {
                if (s[i - 1] === '*') {
                    dp[i] += 6 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += dp[i - 2];
                }
            }
        }

        dp[i] %= MOD;
    }

    return dp[n];
};

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

Задача: 1539. Kth Missing Positive Number
Сложность: easy

Дан массив arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение

class Solution {
    findKthPositive(arr, k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        const n = arr.length;
        for (let i = 0; i < n - 1; i++) {
            const currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
}

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

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

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

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

function minSubsequences(source, target) {
    let subsequencesCount = 0;
    let targetIndex = 0;

    while (targetIndex < target.length) {
        let sourceIndex = 0;
        subsequencesCount++;
        let startIndex = targetIndex;

        while (sourceIndex < source.length && targetIndex < target.length) {
            if (source[sourceIndex] === target[targetIndex]) {
                targetIndex++;
            }
            sourceIndex++;
        }

        if (targetIndex === startIndex) {
            return -1;
        }
    }

    return subsequencesCount;
}

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

Задача: 974. Subarray Sums Divisible by K
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

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

1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1.

2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений.

3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k.

😎 Решение:

var subarraysDivByK = function(nums, k) {
    let prefixMod = 0, result = 0;
    const modGroups = new Array(k).fill(0);
    modGroups[0] = 1;

    for (let num of nums) {
        prefixMod = (prefixMod + num % k + k) % k;
        result += modGroups[prefixMod];
        modGroups[prefixMod]++;
    }

    return result;
};

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

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

Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции.

Верните true, если вы можете достичь последнего индекса, или false в противном случае.

Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

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

1️⃣ Инициализация таблицы памяти:
Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).

2️⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.

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

😎 Решение:

let memo;
const canJumpFromPosition = (position, nums) => {
    if (memo[position] != "UNKNOWN") {
        return memo[position] == "GOOD";
    }
    let furthestJump = Math.min(position + nums[position], nums.length - 1);
    for (
        let nextPosition = position + 1;
        nextPosition <= furthestJump;
        nextPosition++
    ) {
        if (canJumpFromPosition(nextPosition, nums)) {
            memo[position] = "GOOD";
            return true;
        }
    }
    memo[position] = "BAD";
    return false;
};
var canJump = function (nums) {
    memo = new Array(nums.length).fill("UNKNOWN");
    memo[memo.length - 1] = "GOOD";
    return canJumpFromPosition(0, nums);
};

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

Задача: 122. Best Time to Buy and Sell Stock II
Сложность: medium

Вам дан массив целых чисел prices, где prices[i] — это цена данной акции в i-й день.
Каждый день вы можете решить купить и/или продать акцию. Вы можете держать в руках только одну акцию за раз. Однако вы можете купить её и сразу же продать в тот же день.
Найдите и верните максимальную прибыль, которую вы можете получить.

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

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

1️⃣Предположим, что дан массив:
\[ 7, 1, 5, 3, 6, 4 \]
Если мы изобразим числа данного массива на графике, мы получим: *приложенное изображение*

2️⃣Анализируя график, мы замечаем, что точки интереса — это последовательные впадины и пики.
Математически говоря:
Общая прибыль = ∑ (высота(пик i) - высота(впадина i))

3️⃣Ключевой момент заключается в том, что мы должны учитывать каждый пик, следующий сразу за впадиной, чтобы максимизировать прибыль. Если мы пропустим один из пиков (пытаясь получить больше прибыли), мы потеряем прибыль по одной из сделок, что приведет к общей меньшей прибыли.
Например, в вышеуказанном случае, если мы пропустим пик i и впадину j, пытаясь получить больше прибыли, рассматривая точки с большей разницей в высотах, чистая прибыль всегда будет меньше, чем та, которая была бы получена при их учете, поскольку C всегда будет меньше, чем A+B.

😎 Решение:

var maxProfit = function (prices) {
    let i = 0;
    let valley = prices[0];
    let peak = prices[0];
    let maxprofit = 0;
    while (i < prices.length - 1) {
        while (i < prices.length - 1 && prices[i] >= prices[i + 1]) i++;
        valley = prices[i];
        while (i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;
        peak = prices[i];
        maxprofit += peak - valley;
    }
    return maxprofit;
};

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

Задача: 38. Count and Say
Сложность: medium

Последовательность count-and-say — это последовательность строк, определяемая рекурсивно:
countAndSay(1) = "1"
countAndSay(n) — это проговаривание предыдущей строки: сколько подряд идущих одинаковых символов, и какой символ.

Пример:

Input: n = 4  
Output: "1211"

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

1️⃣Если n = 1, вернуть "1" — это базовый случай.

2️⃣Инициализировать строку temp = "1" — с неё всё начинается.

3️⃣Для i от 2 до n:
- Пройти по строке temp, считая подряд одинаковые символы
- Когда символ меняется — добавить в строку ans количество + символ
- В конце каждой итерации: temp = ans, ans = ""

😎 Решение:

class Solution {
  countAndSay(n) {
    if (n === 1) return "1";

    let temp = "1";
    let ans = "";

    for (let i = 2; i <= n; i++) {
      let cnt = 1;
      let prev = temp[0];

      for (let j = 1; j < temp.length; j++) {
        const char = temp[j];
        if (char === prev) {
          cnt++;
        } else {
          ans += cnt.toString() + prev;
          prev = char;
          cnt = 1;
        }
      }

      ans += cnt.toString() + prev;
      temp = ans;
      ans = "";
    }

    return temp;
  }
}

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

Задача: 969. Pancake Sorting
Сложность: medium

Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов.

При одном перевороте блина мы выполняем следующие шаги:

Выбираем целое число k, где 1 <= k <= arr.length.
Переворачиваем подмассив arr[0...k-1] (индексация с 0).
Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3.

Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным.

Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

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

1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0
] (в Python).

2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего.

3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте.

😎 Решение:

var pancakeSort = function(A) {
    const ans = [];

    for (let valueToSort = A.length; valueToSort > 0; valueToSort--) {
        const index = find(A, valueToSort);
        if (index === valueToSort - 1) continue;
        if (index !== 0) {
            ans.push(index + 1);
            flip(A, index + 1);
        }
        ans.push(valueToSort);
        flip(A, valueToSort);
    }

    return ans;
};

function flip(sublist, k) {
    let i = 0;
    while (i < k / 2) {
        [sublist[i], sublist[k - i - 1]] = [sublist[k - i - 1], sublist[i]];
        i++;
    }
}

function find(a, target) {
    for (let i = 0; i < a.length; i++) {
        if (a[i] === target) {
            return i;
        }
    }
    return -1;
}

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