JavaScript | LeetCode

REKONFA Live 6 ноября приглашаем рекламодателей, агентства и рекламные площадки обсудить технологии, маркетинговые инструменты и актуальные новинки. Ключевые участники рынка поделятся опытом и расскажут: — О ситуации на рынке рекламы — Как продвигать и продавать в интернете в 2025 году — Как бизнесу адаптироваться к меняющимся условиям Вас ждут доклады на актуальные темы, классный нетворкинг, вдохновляющая атмосфера для творчества и креатива. Встречаемся 6 ноября в Москве. Для тех, кто не сможет приехать, организуем интерактивное digital-шоу. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 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{}
    

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

Задача: 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;
    }
}{}
    

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

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 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;
    }
}{}
    

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 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;
    }
};{}
    

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

Задача: 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;
    }
}{}
    

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

Задача: 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" и "192.168@1.1" являются недопустимыми 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";
        }
    }
}{}
    

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

Задача: 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";
};{}
    

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