JavaScript | LeetCode

Встречай смартфон Honor — с выгодой для себя! ✅ Стильный дизайн ✅ Заряд надолго ✅ Качественные фото ✅ Быстрая и плавная работа Выбирай свой Honor по привлекательной цене! Купить #реклама market.yandex.ru О рекламодателе

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

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

5 офферов получили наши ребята на прошлой неделе Оффер на 4,2k долларов Оффер на 5k евро Оффер 260k рублей Оффер на 210k рублей Оффер на 220k рублей И еще 19 за сентябрь... а за лето более 50... и у тебя получится!

👋 Меня зовут Тихон, я действующий Frontend-разработчик и ментор. За руку довожу до оффера в Big Tech и не бросаю на испытательном сроке. Вокруг меня собралось целое комьюнити из почти 300 фронтендеров.

Я веду канал, в котором уже 15 тыс разработчиков. Регулярно публикую полезные материалы по подготовке к собесам. А еще каждый четверг у нас проходят полезные стримы с решениями задач и разборами резюме) Забирайте в закрепленном сообщении Полные разборы реальных собеседований: Сбер, VK, OZON, M-Video, Evrone, еще раз OZON, IT One, Trading View, МТС, Лантан, ДОМ.РФ Сборники вопросов по темам: Кибербезопасность на собеседовании Все вопросы по React на собеседовании Все вопросы по TypeScript на собеседовании Как решать задачи двумя указателями Вопросы с Vue собеседований Вопросы по сетям и методологиям с 200 собесов Вопросы по JS с 200 собесов Какие задачи спрашивают на livecoding чаще Полезные посты: Job-борды для поиска работы Запись нашего самого кринжового собеса Новый HTTP метод QUERY 🏆Статистика по рынку: Июль, Июнь, Май, Апрель, Март Подписывайся 👇 frontend_punks Реклама, erid: 2W5zFJ4g4au ИП Галактионов Тихон Витальевич, ИНН 771618975809

Задача: 1510. Stone Game IV Сложность: hard Алиса и Боб поочередно играют в игру, причем Алиса начинает первой. Изначально в куче n камней. В ходе каждого хода игрок удаляет любое ненулевое количество камней, являющееся квадратом целого числа. Кроме того, если игрок не может сделать ход, он/она проигрывает игру. Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально. Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

👨‍💻 Алгоритм: 1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях. 2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs. 3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True. 😎 Решение:

var winnerSquareGame = function(n) {
    const cache = new Map();
    cache.set(0, false);

    const dfs = (remain) => {
        if (cache.has(remain)) {
            return cache.get(remain);
        }
        const sqrtRoot = Math.floor(Math.sqrt(remain));
        for (let i = 1; i <= sqrtRoot; i++) {
            if (!dfs(remain - i * i)) {
                cache.set(remain, true);
                return true;
            }
        }
        cache.set(remain, false);
        return false;
    };

    return dfs(n);
};

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

«Москвич» приглашает на Дни открытых дверей! 10–11 и 17–18 октября дилерские центры «Москвич» устроят для вас настоящий автомобильный праздник. Гостей ждут презентации Москвич M70 и Москвич M90, мастер-классы и розыгрыши призов. Хотите испытать новинки в деле — запишитесь на тест-драйв и получите эксклюзивные предложения на покупку. Время совершать открытия вместе! Узнать больше #реклама 16+ moskvich-m.ru О рекламодателе

Задача: 1086. High Five Сложность: easy Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента. Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания. Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления. Пример:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

👨‍💻 Алгоритм: 1⃣Создайте словарь для хранения оценок каждого студента, где ключом будет ID студента, а значением — список его оценок. Переберите элементы в массиве items и добавьте каждую оценку в соответствующий список в словаре, используя ID студента как ключ. 2⃣Создайте список для хранения результата result. Переберите словарь и для каждого студента отсортируйте его оценки в порядке убывания, возьмите пять лучших оценок, вычислите их среднее значение (с целочисленным делением на 5) и добавьте пару [ID, topFiveAverage] в результат. 3⃣Отсортируйте список result по возрастанию ID студента и верните его. 😎 Решение:

var highFive = function(items) {
    const K = 5;
    items.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return b[1] - a[1];
    });

    const solution = [];
    let i = 0;
    while (i < items.length) {
        const id = items[i][0];
        let sum = 0;
        for (let k = i; k < i + K; k++) {
            sum += items[k][1];
        }
        while (i < items.length && items[i][0] === id) {
            i++;
        }
        solution.push([id, Math.floor(sum / K)]);
    }
    return solution;
};

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

Задача: 1058. Minimize Rounding Error to Meet Target Сложность: medium Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби. Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

👨‍💻 Алгоритм: 1⃣Округли каждую цену вниз и вычисли текущую сумму округленных цен. Найди разницу между целевой суммой и текущей суммой. 2⃣Определи количество округлений вверх, необходимых для достижения целевой суммы. Если разница отрицательная или больше количества элементов в массиве, верни "-1". 3⃣Вычисли ошибки округления для всех элементов и отсортируй их по возрастанию. Выбери необходимые округления вверх и вычисли общую ошибку округления. 😎 Решение:

function minimizeRoundingError(prices, target) {
    let floors = prices.map(p => Math.floor(parseFloat(p)));
    let totalFloor = floors.reduce((a, b) => a + b, 0);
    
    let difference = target - totalFloor;
    if (difference < 0 || difference > prices.length) {
        return "-1";
    }
    
    let roundingErrors = prices.map((p, i) => [Math.ceil(parseFloat(p)) - floors[i], parseFloat(p) - floors[i]]);
    roundingErrors.sort((a, b) => a[1] - b[1]);
    
    let roundingErrorSum = floors.reduce((sum, floor, i) => sum + (floor - parseFloat(prices[i])), 0);
    
    for (let i = 0; i < difference; i++) {
        roundingErrorSum += roundingErrors[i][1];
    }
    
    return roundingErrorSum.toFixed(3);
}

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

Открытый урок: бизнес-логика в микросервисах Разработка в микросервисах — это не только разбиение на сервисы, но и грамотное распределение логики. 22 октября в 19:00 мск — открытый урок для разработчиков и архитекторов. Узнаете, где должна жить бизнес-логика. Запишитесь! Зарегистрироваться #реклама 16+ otus.ru О рекламодателе

Задача: 753. Cracking the Safe Сложность: medium Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно. После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода. Пример:

Input: n = 1, k = 2
Output: "10"

👨‍💻 Алгоритм: 1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1]. 2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз. 3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры. 😎 Решение:

var crackSafe = function(n, k) {
    const seen = new Set();
    const result = [];

    const dfs = (node) => {
        for (let x = 0; x < k; x++) {
            const neighbor = node + x;
            if (!seen.has(neighbor)) {
                seen.add(neighbor);
                dfs(neighbor.slice(1));
                result.push(x);
            }
        }
    };

    const startNode = '0'.repeat(n - 1);
    dfs(startNode);
    return startNode + result.join('');
};

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

Услуги дата-центра в Москве Размещение и аренда серверного оборудования в дата-центре. 👍 4 современных дата-центра в Москве. 👍 Лицензированный оператор связи. 👍 Индивидуальные конфигурации выделенных серверов под задачи клиента. 👍 Круглосуточная техническая поддержка в Телеграм, без ботов. Узнать цену #реклама 16+ itsoft.ru О рекламодателе

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves Сложность: medium Вам дан массив целых чисел nums. За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение. Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов. Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

👨‍💻 Алгоритм: 1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом. 2⃣Итерация по первым четырем элементам отсортированного массива: для каждого индекса left от 0 до 3 вычислите соответствующий правый индекс, разницу между элементами на этих индексах и обновите minDiff с минимальным значением. 3⃣Верните minDiff, которое хранит минимальную разницу между наибольшими и наименьшими значениями после удаления до трех элементов. 😎 Решение:

var minDifference = function(nums) {
    const numsSize = nums.length
    
    if (numsSize <= 4) return 0
    
    nums.sort((a, b) => a - b)
    
    let minDiff = Infinity
    
    for (let left = 0; left < 4; left++) {
        const right = numsSize - 4 + left
        minDiff = Math.min(minDiff, nums[right] - nums[left])
    }
    
    return minDiff
}

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

Программируешь? Участвуй в олимпиаде Высшая проба Сделай шаг в IT вместе с Яндексом и ВШЭ — прими участие в олимпиаде по промышленному программированию! Победителям — БВИ или 100 баллов по профильному предмету в лучших вузах России. Регистрируйся до 20 октября! Узнать больше #реклама olymp.hse.ru О рекламодателе

Задача: 1209. Remove All Adjacent Duplicates in String II Сложность: medium Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе. Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать. Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален. Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

👨‍💻 Алгоритм: 1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов. 2⃣Перемещать быстрый указатель i по строке s: Копировать s[i] в s[j]. Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека. Иначе добавить 1 в стек. Если количество символов равно k, уменьшить j на k и извлечь из стека. 3⃣Вернуть первые j символов строки. 😎 Решение:

class Solution {
    removeDuplicates(s, k) {
        let counts = [];
        let sa = s.split('');
        let j = 0;
        
        for (let i = 0; i < sa.length; ++i, ++j) {
            sa[j] = sa[i];
            if (j === 0 || sa[j] !== sa[j - 1]) {
                counts.push(1);
            } else {
                let incremented = counts.pop() + 1;
                if (incremented === k) {
                    j -= k;
                } else {
                    counts.push(incremented);
                }
            }
        }
        return sa.slice(0, j).join('');
    }
}

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

REKONFA: что интересного вас ждёт 15 октября 15 октября встречаемся на REKONFA — большой конференции Яндекс Рекламы. На сцене: — Глеб Доброрадных — о рекламном рынке и эффективности в сложных условиях — Алексей Штоколов — о новых продуктах и технологиях — Лиза Смирнова — о 360°-форматах и новых точках контакта — Александр Пушной — о человеке и ИИ — Александр Умаров — о персональном подходе, который помогает влюблять клиентов в бренд — Яна Чурикова — об актуальных задачах предпринимателей — Татьяна Мужицкая — о целях и энергии — Антон Беляев — об индивидуальности и проектах, которые любят зрители Вне сцены — зона продуктов Яндекс Рекламы, три игры, викторина, зоны Яндекс Ярда и eLama и нетворкинг. 15 октября, Москва, ВТБ Арена и онлайн. Участие бесплатное. Зарегистрироваться #реклама 16+ ya.rekonfa.ru О рекламодателе

Задача: 179. Largest Number Сложность: medium Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его. Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа. Пример:

Input: nums = [10,2]
Output: "210"

👨‍💻 Алгоритм: 1️⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎. 2️⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули. 3️⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки. 😎 Решение:

class Solution {
    largestNumber(nums) {
        const strNums = nums.map(String);
        strNums.sort((a, b) => (b + a).localeCompare(a + b));
        if (strNums[0] === "0") {
            return "0";
        }
        return strNums.join('');
    }
}

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

Бесплатный курс по дизайну в FIGMA от Yudaev School Онлайн-программа с наставником и чатом. Внимание! 80% практики. ✅По результату обучения у вас будет портфолио из нескольких работ. ✅Сертификат о прохождении курса. ✅Возможность пройти полное обучение и получить карьерное сопровождение! Учитесь дизайну у профессионалов в Yudaev Shool. Переходи по кнопки: "Подробнее" и начинай свое обучение. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

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

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

Бесплатный 14-дневный онлайн-курс по дизайну интерьеров Давно хочешь работать в творческой сфере и иметь доход от 100 тыс/мес? Тебе не нужно уметь рисовать или прямо сейчас принимать решение. Просто приходи и попробуй! Вдруг понравится создавать уютные интерьеры и ты найдешь в этом себя. Регистрируйся на практический курс по дизайну интерьера с личным наставником. Осталось 7 мест!⚡ Зарегистрироваться

Задача: 602. Friend Requests II: Who Has the Most Friends Сложность: medium Напишите решение для нахождения людей, у которых больше всего друзей, и количества их друзей. Тестовые случаи сгенерированы так, что только у одного человека больше всего друзей. Формат результата приведён в следующем примере. Пример:

Input: 
RequestAccepted table:
+--------------+-------------+-------------+
| requester_id | accepter_id | accept_date |
+--------------+-------------+-------------+
| 1            | 2           | 2016/06/03  |
| 1            | 3           | 2016/06/08  |
| 2            | 3           | 2016/06/08  |
| 3            | 4           | 2016/06/09  |
+--------------+-------------+-------------+
Output: 
+----+-----+
| id | num |
+----+-----+
| 3  | 3   |
+----+-----+
Explanation: 
The person with id 3 is a friend of people 1, 2, and 4, so he has three friends in total, which is the most number than any others.

👨‍💻 Алгоритм: 1⃣Поскольку человек может подружиться, отправив или приняв запрос дружбы, для подсчета количества друзей у каждого человека объединяем столбцы requester_id и accepter_id в один. 2⃣Используем UNION ALL для сохранения всех дублирующихся значений и переименовываем столбцы в id. 3⃣Подсчитываем, сколько раз каждый id появляется, группируем по id, сортируем по убыванию и берем первую запись для определения человека с максимальным количеством друзей. 😎 Решение:

WITH Combined AS (
    SELECT requester_id AS id
    FROM friendships
    UNION ALL
    SELECT accepter_id AS id
    FROM friendships
),
FriendCounts AS (
    SELECT id, COUNT(*) AS friend_count
    FROM Combined
    GROUP BY id
    ORDER BY friend_count DESC
)
SELECT id, friend_count
FROM FriendCounts
LIMIT 1;

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

Solar JSOC - Флагманский SOC с гарантией Гарантии крупнейшего коммерческого SOCа России теперь доступны вам. Узнать больше #реклама 16+ rt-solar.ru О рекламодателе