JavaScript | LeetCode

Задача: 74. Search a 2D Matrix Сложность: medium Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами: Каждая строка отсортирована в порядке неубывания. Первое число каждой строки больше последнего числа предыдущей строки. Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае. Вы должны написать решение с временной сложностью O(log(m * n)). Пример:

    
        Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true{}
    

👨‍💻 Алгоритм: 1️⃣Инициализируйте индексы слева и справа: left = 0 и right = m x n - 1. 2️⃣Пока left <= right: Выберите индекс посередине виртуального массива в качестве опорного индекса: pivot_idx = (left + right) / 2. 3️⃣Индекс соответствует row = pivot_idx // n и col = pivot_idx % n в исходной матрице, и, следовательно, можно получить pivot_element. Этот элемент делит виртуальный массив на две части. Сравните pivot_element и target, чтобы определить, в какой части нужно искать target. 😎 Решение:

    
        var searchMatrix = function (matrix, target) {
    let m = matrix.length;
    if (m == 0) return false;
    let n = matrix[0].length;
    let left = 0,
        right = m * n - 1;
    let pivotIdx, pivotElement;
    while (left <= right) {
        pivotIdx = Math.floor((left + right) / 2);
        pivotElement = matrix[Math.floor(pivotIdx / n)][pivotIdx % n];
        if (target == pivotElement) return true;
        else {
            if (target < pivotElement) right = pivotIdx - 1;
            else left = pivotIdx + 1;
        }
    }
    return false;
};{}
    

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

Задача: 1218. Longest Arithmetic Subsequence of Given Difference Сложность: medium Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference. Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов. Пример:

    
        Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1. 2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]: Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference: - если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference]. - в противном случае, установите before_a = 0. Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]). 3⃣Верните answer после завершения итерации. 😎 Решение:

    
        var longestSubsequence = function(arr, difference) {
    let dp = new Map();
    let answer = 1;
    
    for (let a of arr) {
        let beforeA = dp.get(a - difference) || 0;
        dp.set(a, beforeA + 1);
        answer = Math.max(answer, dp.get(a));
    }
    
    return answer;
};{}
    

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

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: №23. Merge k Sorted Lists Сложность: hard Дан массив из k отсортированных связанных списков. Нужно объединить их в один отсортированный связанный список и вернуть его голову. Пример:

    
        Input: lists = [[1,4,5],[1,3,4],[2,6]]  
Output: [1,1,2,3,4,4,5,6]{}
    

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

    
        var mergeKLists = function (lists) {
    const pq = new MinPriorityQueue({ priority: node => node.val });

    for (const head of lists) {
        if (head) pq.enqueue(head);
    }

    const dummy = new ListNode();
    let cur = dummy;

    while (!pq.isEmpty()) {
        const node = pq.dequeue().element;
        cur.next = node;
        cur = cur.next;

        if (node.next) pq.enqueue(node.next);
    }

    return dummy.next;
};{}
    

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

Задача: 150. Evaluate Reverse Polish Notation Сложность: medium Вам дан массив строк под названием tokens, который представляет арифметическое выражение в обратной польской нотации. Вычислите это выражение. Верните целое число, которое представляет значение этого выражения. Обратите внимание на следующие моменты: Допустимые операторы: '+', '-', '*' и '/'. Каждый операнд может быть целым числом или другим выражением. Деление двух целых чисел всегда округляется к нулю. Деление на ноль в выражении отсутствует. Входные данные представляют собой действительное арифметическое выражение в обратной польской нотации. Ответ и все промежуточные вычисления можно представить 32-битным целым числом. Пример:

    
        Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9{}
    

👨‍💻 Алгоритм: 1️⃣Обработка входных массивов: Для языков, таких как Java, где входные данные представлены фиксированным массивом, необходимо определить собственные методы для манипулирования массивом (например, удаление элементов). Это может включать сдвиг элементов для заполнения пробелов после удаления элемента. В качестве альтернативы, копирование массива в ArrayList могло бы упростить удаление, но за счет увеличения сложности по памяти с O(1) до O(n). 2️⃣Обработка типов и деление в Python: Необходимо быть внимательным при обработке типов в Python во время обработки списка, поскольку числа могут быть представлены как строки или целые числа. Кроме того, стандартное деление в Python не округляет к нулю. Вместо этого использование int(a / b) достигает желаемого результата округления, что отличается от деления нацело int(a // b), которое является другим распространенным подходом. 3️⃣Использование лямбда-функций: Лямбда-функции могут упростить реализацию арифметических операций (таких как +, -, *, /). Если вы знакомы с лямбда-функциями, они предлагают элегантное решение для динамической обработки операций. Если лямбда-функции новы или не поддерживаются в используемом языке программирования, можно использовать другие методы, а изучение лямбда-функций можно отложить на потом. 😎 Решение:

    
        const OPERATORS = {
    "+": (a, b) => a + b,
    "-": (a, b) => a - b,
    "/": (a, b) => Math.trunc(a / b),
    "*": (a, b) => a * b,
};

var evalRPN = function (tokens) {
    let currentPosition = 0;

    while (tokens.length > 1) {

        while (!(tokens[currentPosition] in OPERATORS)) {
            currentPosition += 1;
        }

        const operator = tokens[currentPosition];
        const operation = OPERATORS[operator];
        const number1 = Number(tokens[currentPosition - 2]);
        const number2 = Number(tokens[currentPosition - 1]);

        tokens[currentPosition] = operation(number1, number2);

        tokens.splice(currentPosition - 2, 2);
        currentPosition -= 1;
    }

    return tokens[0];
};{}
    

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

Задача: 1276. Number of Burgers with No Waste of Ingredients Сложность: medium Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните []. Пример:

    
        Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]{}
    

👨‍💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:

    
        var numOfBurgers = function(tomatoSlices, cheeseSlices) {
    if (tomatoSlices % 2 !== 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
        return [];
    }
    let total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
    let total_small = cheeseSlices - total_jumbo;
    return [total_jumbo, total_small];
};{}
    

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

Задача: 635. Design Log Storage System Сложность: medium Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения. int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать. Пример:

    
        Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и хранение журналов Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения. 2⃣Формирование диапазона Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity. 3⃣Фильтрация и возврат результатов Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон. 😎 Решение:

    
        class LogSystem {
    constructor() {
        this.logs = [];
        this.granularity = {
            "Year": 4,
            "Month": 7,
            "Day": 10,
            "Hour": 13,
            "Minute": 16,
            "Second": 19
        };
    }

    put(id, timestamp) {
        this.logs.push({ id, timestamp });
    }

    retrieve(start, end, granularity) {
        const length = this.granularity[granularity];
        start = start.slice(0, length);
        end = end.slice(0, length);
        return this.logs.filter(log => {
            const ts = log.timestamp.slice(0, length);
            return start <= ts && ts <= end;
        }).map(log => log.id);
    }
}{}
    

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

Задача: 861. Score After Flipping Matrix Сложность: hard Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1. Подмассив — это непрерывная часть массива. Пример:

    
        Input: nums = [1], k = 1
Output: 1{}
    

👨‍💻 Алгоритм: 1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались. 2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались. 3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека. 😎 Решение:

    
        var shortestSubarray = function(A, K) {
    const N = A.length;
    const P = new Array(N + 1).fill(0);
    for (let i = 0; i < N; ++i) {
        P[i + 1] = P[i] + A[i];
    }

    let ans = N + 1;
    const monoq = [];

    for (let y = 0; y < P.length; ++y) {
        while (monoq.length > 0 && P[y] <= P[monoq[monoq.length - 1]]) {
            monoq.pop();
        }
        while (monoq.length > 0 && P[y] >= P[monoq[0]] + K) {
            ans = Math.min(ans, y - monoq.shift());
        }
        monoq.push(y);
    }

    return ans < N + 1 ? ans : -1;
};{}
    

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

Задача: 116. Populating Next Right Pointers in Each Node Сложность: medium Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение Заполните каждый указатель next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL. Изначально все указатели next установлены в NULL. Пример:

    
        Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.{}
    

👨‍💻 Алгоритм: 1️⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных. 2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве. 3️⃣Подход, который мы будем использовать здесь, будет иметь структуру вложенных циклов, чтобы обойти необходимость указателя NULL. По сути, на каждом шаге мы записываем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и не более. К моменту, когда мы закончим обработку заданного количества элементов, в очереди будут все узлы следующего уровня. Вот псевдокод для этого: 😎 Решение:

    
        var connect = function (root) {
    if (root == null) {
        return root;
    }
    let Q = [];
    Q.push(root);
    while (Q.length > 0) {
        let size = Q.length;
        for (let i = 0; i < size; i++) {
            let node = Q.shift();
            if (i < size - 1) {
                node.next = Q[0];
            }
            if (node.left != null) {
                Q.push(node.left);
            }
            if (node.right != null) {
                Q.push(node.right);
            }
        }
    }
    return root;
};{}
    

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

Задача: 251. Flatten 2D Vector Сложность: medium Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext. Реализуйте класс Vector2D: Vector2D(int[][] vec) инициализирует объект двумерным вектором vec. next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы. hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае. Пример:

    
        Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False{}
    

👨‍💻 Алгоритм: 1️⃣Инициализация: Установите указатель position так, чтобы он указывал на следующий элемент массива, который должен быть возвращен методом next(). Это обеспечивает, что position всегда готов к получению следующего действительного элемента. 2️⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае. 3️⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next(). 😎 Решение:

    
        class Vector2D {
    constructor(v) {
        this.nums = [].concat(...v);
        this.position = -1;
    }

    next() {
        this.position++;
        return this.nums[this.position];
    }

    hasNext() {
        return this.position + 1 < this.nums.length;
    }
}{}
    

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