JavaScript | LeetCode

Задача: 1165. Single-Row Keyboard Сложность: easy Есть специальная клавиатура, на которой все клавиши расположены в один ряд. Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|. Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем. Пример:

    
        Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.{}
    

👨‍💻 Алгоритм: 1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0. 2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c. 3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова. 😎 Решение:

    
        var calculateTime = function(keyboard, word) {
    const keyIndices = new Array(26).fill(-1)
    for (let i = 0; i < keyboard.length; i++) {
        keyIndices[keyboard.charCodeAt(i) - 97] = i
    }
    
    let prev = 0
    let result = 0
    
    for (let c of word) {
        const index = keyIndices[c.charCodeAt(0) - 97]
        result += Math.abs(prev - index)
        prev = index
    }
    
    return result
}{}
    

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

Бесплатное льготное обучение: 3 месяца Мы ищем людей, которые хотят работать в IT-сфере из дома 💰 Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку: Узнать больше #реклама technolium.ru О рекламодателе

Задача: 780. Reaching Points Сложность: hard Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false. Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y). Пример:

    
        Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5){}
    

👨‍💻 Алгоритм: 1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}. 2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно. 3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy. 😎 Решение:

    
        class Solution {
    reachingPoints(sx, sy, tx, ty) {
        while (tx >= sx && ty >= sy) {
            if (sx === tx && sy === ty) return true;
            if (tx > ty) {
                tx -= ty;
            } else {
                ty -= tx;
            }
        }
        return false;
    }
}{}
    

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 1095. Find in Mountain Array Сложность: hard Массив arr является горным массивом тогда и только тогда, когда: Длина массива arr >= 3. Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1. Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray: MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0). MountainArray.length() возвращает длину массива. Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы. Пример:

    
        Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.{}
    

👨‍💻 Алгоритм: 1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика. 2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем. 3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1. 😎 Решение:

    
        var findInMountainArray = function(target, mountainArr) {
    const length = mountainArr.length()

    let low = 1, high = length - 2
    while (low != high) {
        const mid = Math.floor((low + high) / 2)
        if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    const peak = low

    low = 0
    high = peak
    while (low < high) {
        const mid = Math.floor((low + high) / 2)
        if (mountainArr.get(mid) < target) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    if (mountainArr.get(low) == target) {
        return low
    }

    low = peak + 1
    high = length - 1
    while (low < high) {
        const mid = Math.floor((low + high) / 2)
        if (mountainArr.get(mid) > target) {
            low = mid + 1
        } else {
            high = mid
        }
    }
    if (mountainArr.get(low) == target) {
        return low
    }

    return -1
}{}
    

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

6 мастхэв инструментов для совместной работы в Битрикс24 Читайте подробнее в карточках. Регистрируйтесь сейчас, чтобы забрать их все себе бесплатно😊 Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 1056. Confusing Number Сложность: easy Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно. При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае. Пример:

    
        Input: n = 6
Output: true{}
    

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

    
        function isConfusingNumber(n) {
    const rotationMap = {
        '0': '0', '1': '1', '6': '9', '8': '8', '9': '6'
    };
    const nStr = n.toString();
    let rotatedStr = "";

    for (let char of nStr) {
        if (!(char in rotationMap)) {
            return false;
        }
        rotatedStr = rotationMap[char] + rotatedStr;
    }

    return rotatedStr !== nStr;
}{}
    

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

Задача: 1237. Find Positive Integer Solution for a Given Equation Сложность: medium Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы. int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято. Пример:

    
        Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]{}
    

👨‍💻 Алгоритм: 1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y). 2⃣Перемещение указателей: Если 𝑓(𝑥,𝑦)=𝑧 f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x. 3⃣Повторяем шаги до тех пор, пока 𝑥≤1000 x≤1000 и 𝑦≥1y≥1. 😎 Решение:

    
        class CustomFunction {
    f(x, y) {}
}

var findSolution = function(customfunction, z) {
    let result = [];
    let x = 1;
    let y = 1000;
    
    while (x <= 1000 && y >= 1) {
        let value = customfunction.f(x, y);
        if (value === z) {
            result.push([x, y]);
            x++;
        } else if (value < z) {
            x++;
        } else {
            y--;
        }
    }
    
    return result;
};{}
    

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 1011. Capacity To Ship Packages Within D Days Сложность: medium На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней. Пример:

    
        Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15{}
    

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

    
        class Solution {
    shipWithinDays(weights, D) {
        const canShipInDays = (capacity) => {
            let days = 1, total = 0;
            for (let weight of weights) {
                if (total + weight > capacity) {
                    days++;
                    total = 0;
                }
                total += weight;
            }
            return days <= D;
        };
        
        let left = Math.max(...weights);
        let right = weights.reduce((a, b) => a + b, 0);
        
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (canShipInDays(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}{}
    

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