JavaScript | LeetCode

Приглашаем на пикник для ИТ-специалистов Отвлекитесь от экрана — оторвитесь на ИТ-пикнике 17 августа. У фестиваля больше 17-ти ИТ-партнеров. Вас ждут воркшопы, лекции от спикеров известных компаний, нетворкинг, выступления топовых музыкантов и даже детская зона. Ждем опытных ИТ-специалистов. Зарегистрироваться #реклама 16+ it-picnic.ru О рекламодателе

#medium Задача: 82. Remove Duplicates from Sorted List II Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список. Пример:

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

👨‍💻 Алгоритм: 1️⃣Инициализация "стража" и предшественника: Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены. Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж. 2️⃣Проход по списку с проверкой на дубликаты: Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val. Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов. 3️⃣Переход к следующему узлу и возврат результата: Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел. Двигаем указатель head на следующий узел в списке. После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов. 😎 Решение:

var deleteDuplicates = function (head) {
    let sentinel = new ListNode(0, head);
    let pred = sentinel;
    while (head !== null) {
        if (head.next !== null && head.val === head.next.val) {
            while (head.next !== null && head.val === head.next.val) {
                head = head.next;
            }
            pred.next = head.next;
        } else {
            pred = pred.next;
        }
        head = head.next;
    }
    return sentinel.next;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Бакалавриат и специалитет Президентской академии! ✅ Важное для абитуриентов! 🎓 🎓Хотите стать студентом одного из лучших университетов страны? Тогда не упустите шанс поступить на программы бакалавриата и специалитета в Президентскую академию (РАНХиГС). На выбор более 100 программ обучения, стажировки и практики в органах государственной власти и крупных коммерческих компаниях, участие в реальных проектах во время обучения, стипендии и общежития. Создавайте будущее страны вместе с РАНХиГС. Подробности о поступлении и об Академии вы найдете на нашем сайте. Успейте подать заявку! Узнать больше #реклама ranepa.ru О рекламодателе

#medium Задача: 81. Search in Rotated Sorted Array II В массиве целых чисел nums, отсортированном в неубывающем порядке (не обязательно содержащем уникальные значения), произведена ротация в неизвестном индексе поворота k (0 <= k < nums.length). В результате массив принимает вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (нумерация с 0). Например, массив [0,1,2,4,4,4,5,6,6,7] может быть повернут в индексе 5 и превратиться в [4,5,6,6,7,0,1,2,4,4]. Для данного массива nums после ротации и целого числа target необходимо вернуть true, если target присутствует в nums, и false в противном случае. Необходимо сократить количество операций поиска настолько, насколько это возможно. Пример:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

👨‍💻 Алгоритм: 1️⃣Вспомним стандартный бинарный поиск, где мы используем два указателя (start и end), чтобы отслеживать область поиска в массиве arr. Затем мы делим пространство поиска на три части: [start, mid), [mid, mid], (mid, end]. Далее мы продолжаем искать наш целевой элемент в одной из этих зон поиска. 2️⃣Определяя положение arr[mid] и target в двух частях массива F и S, мы можем сократить область поиска так же, как в стандартном бинарном поиске: Случай 1: arr[mid] находится в F, target в S: так как S начинается после окончания F, мы знаем, что элемент находится здесь: (mid, end]. Случай 2: arr[mid] находится в S, target в F: аналогично, мы знаем, что элемент находится здесь: [start, mid). Случай 3: Оба arr[mid] и target находятся в F: поскольку оба они находятся в той же отсортированной части массива, мы можем сравнить arr[mid] и target, чтобы решить, как сократить область поиска. Случай 4: Оба arr[mid] и target находятся в S: так как оба они в той же отсортированной части массива, мы также можем сравнить их для решения о сокращении области поиска. 3️⃣Однако, если arr[mid] равен arr[start], то мы знаем, что arr[mid] может принадлежать и F, и S, и поэтому мы не можем определить относительное положение target относительно mid. В этом случае у нас нет другого выбора, кроме как перейти к следующей области поиска итеративно. Таким образом, существуют области поиска, которые позволяют использовать бинарный поиск, и области, где это невозможно. 😎 Решение:

var search = function (nums, target) {
    let n = nums.length;
    if (n == 0) return false;
    let end = n - 1;
    let start = 0;
    while (start <= end) {
        let mid = start + Math.floor((end - start) / 2);
        if (nums[mid] == target) {
            return true;
        }
        if (!isBinarySearchHelpful(nums, start, nums[mid])) {
            start++;
            continue;
        }
        let pivotArray = existsInFirst(nums, start, nums[mid]);
        let targetArray = existsInFirst(nums, start, target);
        if (pivotArray ^ targetArray) {
            if (pivotArray) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        } else {
            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return false;
};

function isBinarySearchHelpful(nums, start, element) {
    return nums[start] != element;
}

function existsInFirst(nums, start, element) {
    return nums[start] <= element;
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

ТОП-4 Курса по UX/UI-дизайну по версии Tutortop Tutortop — маркетплейс курсов №1 по количеству школ-партнеров, курсов и реальных отзывов студентов. Освойте востребованную профессию с нуля за 4-5 месяцев. Соберите портфолио из 10+ проектов. Выйдите на заработок 100 000₽+ и работайте удаленно в гибком графике. Выбрать #реклама 16+ tutortop.ru О рекламодателе

#medium Задача: 80. Remove Duplicates from Sorted Array II Дан массив целых чисел nums, отсортированный в неубывающем порядке. Удалите из него некоторые дубликаты на месте так, чтобы каждый уникальный элемент встречался не более двух раз. Относительный порядок элементов должен быть сохранён. Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов. Верните k после размещения итогового результата в первые k слотов массива nums. Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1). Пример:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

👨‍💻 Алгоритм: 1️⃣Инициализация переменных: Используйте две переменные: i, которая указывает на текущий индекс в массиве, и count, которая отслеживает количество каждого элемента. Начните обработку массива с первого элемента (индекс 1), предполагая, что первый элемент всегда имеет count равный 1. 2️⃣Обработка элементов массива: Для каждого элемента в массиве: 3️⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count. Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент. Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1. Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи. 😎 Решение:

var removeDuplicates = function (nums) {
    let j = 0;
    for (let i = 0; i < nums.length; i++) {
        if (j < 2 || nums[i] > nums[j - 2]) {
            nums[j++] = nums[i];
        }
    }
    return j;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Используете серверы для высокочастотной торговли? Поставляем HFT-серверы с кастомной жидкостной системой охлаждения и доработанной прошивкой BIOS. - Платформы 1U на Intel и AMD. - Более высокий hit rate и меньшая задержка tick-to-order. - Есть демо-фонд для тестирования. - Гарантия от 1 года. Факты о компании «Work System»: Международный статус. Имеем зарегистрированные компании в Китае, России и Казахстане. В Китае мы официальные партнеры HPE, Lenovo, Dell, Huawei. Поставка "под ключ". Полный цикл проекта — от анализа задачи до поставки и внедрения. Подтвержденный опыт. Среди наших клиентов Ростех, Rutube, МКБ, ВТБ и другие компании, благодарственные письма и отзывы на сайте Отправьте запрос нашему менеджеру, возьмите оборудование в тест и повысьте эффективность транзакций до 20%! Получить предложение #реклама work-systems.ru О рекламодателе

#medium Задача: 79. Word Search Дана сетка символов размером m на n, называемая board, и строка word. Верните true, если слово word существует в сетке. Слово можно составить из букв последовательно смежных ячеек, где смежные ячейки находятся рядом по горизонтали или вертикали. Одна и та же ячейка с буквой не может быть использована более одного раза. Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

👨‍💻 Алгоритм: 1️⃣Общий подход к алгоритмам обратной трассировки: В каждом алгоритме обратной трассировки существует определенный шаблон кода. Например, один из таких шаблонов можно найти в нашем разделе "Рекурсия II". Скелет алгоритма представляет собой цикл, который проходит через каждую ячейку в сетке. Для каждой ячейки вызывается функция обратной трассировки (backtrack()), чтобы проверить, можно ли найти решение, начиная с этой ячейки. 2️⃣Функция обратной трассировки: Эта функция, реализуемая как алгоритм поиска в глубину (DFS), часто представляет собой рекурсивную функцию. Первым делом проверяется, достигнут ли базовый случай рекурсии, когда слово для сопоставления пусто, то есть для каждого префикса слова уже найдено совпадение. Затем проверяется, не является ли текущее состояние недопустимым: либо позиция ячейки выходит за границы доски, либо буква в текущей ячейке не совпадает с первой буквой слова. 3️⃣Исследование и завершение: Если текущий шаг допустим, начинается исследование с использованием стратегии DFS. Сначала текущая ячейка помечается как посещенная, например, любой неалфавитный символ подойдет. Затем осуществляется итерация через четыре возможных направления: вверх, вправо, вниз и влево. Порядок направлений может быть изменен по предпочтениям пользователя. В конце исследования ячейка возвращается к своему исходному состоянию, и возвращается результат исследования. 😎 Решение:

var exist = function (board, word) {
    const ROWS = board.length;
    const COLS = board[0].length;
    const backtrack = function (row, col, suffix) {
        if (suffix.length == 0) return true;
        if (
            row < 0 ||
            row == ROWS ||
            col < 0 ||
            col == COLS ||
            board[row][col] != suffix.charAt(0)
        )
            return false;
        let ret = false;
        board[row][col] = "#";
        const directions = [
            [0, 1],
            [1, 0],
            [0, -1],
            [-1, 0],
        ];
        for (let [rowOffset, colOffset] of directions) {
            ret = backtrack(row + rowOffset, col + colOffset, suffix.slice(1));
            if (ret) break;
        }
        board[row][col] = suffix.charAt(0);
        return ret;
    };

    for (let row = 0; row < ROWS; ++row) {
        for (let col = 0; col < COLS; ++col) {
            if (backtrack(row, col, word)) return true;
        }
    }
    return false;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Виртуальный сервер в аренду в России и Турции. Отказоустойчивый виртуальный облачный сервер / дата центр IaaS на базе виртуализаций VMWARE, РУСТЭК по модели подписки. Аналог Elastic Cloud EC2. - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Резервное копирование на удаленную площадку (ок. 10 км) - Размещение персональных данных и ГИС по ФЗ-152 - Лицензированные решения Microsoft - Почасовой биллинг и постоплата - Оплата в рублях, турецких лирах, Euro - 30 дней бесплатное тестирование для юр. лиц Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе

#medium Задача: 78. Subsets Дан массив целых чисел 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;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых