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

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

Задача: 71. Simplify Path
Сложность: medium

Дан абсолютный путь для файловой системы в стиле Unix, который начинается с символа '/'. Преобразуйте этот путь в его упрощенный канонический путь.
В контексте файловой системы Unix-style одинарная точка '.' обозначает текущий каталог, двойная точка '..' означает переход на один уровень каталога вверх, а несколько слэшей, таких как '//', интерпретируются как один слэш. В этой задаче последовательности точек, не охваченные предыдущими правилами (например, '...'), следует рассматривать как допустимые имена для файлов или каталогов.
Упрощенный канонический путь должен соответствовать следующим правилам:
Он должен начинаться с одного слэша '/'.
Каталоги в пути должны быть разделены только одним слэшем '/'.
Он не должен заканчиваться слэшем '/', если только это не корневой каталог.
Он должен исключать любые одинарные или двойные точки, используемые для обозначения текущих или родительских каталогов.
Верните новый путь.

Пример:

Input: path = "/home/"

Output: "/home"

Explanation:

The trailing slash should be removed.

👨‍💻 Алгоритм:

1️⃣Инициализируем стек S, который будет использоваться в нашей реализации. Разделяем входную строку, используя символ '/' в качестве разделителя. Этот шаг очень важен, поскольку входные данные всегда являются допустимым путем, и наша задача — лишь его сократить. Таким образом, все, что находится между двумя символами '/', является либо именем каталога, либо специальным символом, и мы должны соответственно обработать их.

2️⃣Как только входной путь разделен, мы обрабатываем каждый компонент по отдельности. Если текущий компонент — это точка '.' или пустая строка, мы ничего не делаем и просто продолжаем. Если вспомнить, массив строк, полученный при разделении строки '/a//b', будет [a, , b], где между a и b находится пустая строка, что в контексте общего пути не имеет значения. Если мы сталкиваемся с двойной точкой '..', это означает, что нужно подняться на один уровень выше в текущем пути каталога. Поэтому мы удаляем запись из нашего стека, если он не пуст.

3️⃣Наконец, если обрабатываемый нами в данный момент компонент не является одним из специальных символов, мы просто добавляем его в наш стек, так как это законное имя каталога. Как только все компоненты обработаны, нам просто нужно соединить все имена каталогов в нашем стеке, используя '/' в качестве разделителя, и мы получим самый короткий путь, который приведет нас в тот же каталог, что и предоставленный на входе.

😎 Решение:

var simplifyPath = function (path) {
    let stack = [];
    for (let portion of path.split("/")) {
        if (portion === "..") {
            if (stack.length) {
                stack.pop();
            }
        } else if (portion !== "." && portion) {
            stack.push(portion);
        }
    }
    return "/" + stack.join("/");
};

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

Задача: 58. Length of Last Word
Сложность: easy

Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке.
Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами.

Пример:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

👨‍💻 Алгоритм:

1️⃣Поиск последнего слова:
Сначала мы пытаемся найти последнее слово, начиная с конца строки. Итерируем строку в обратном порядке, пропуская пробелы. Когда мы встречаем первый непробельный символ, мы знаем, что нашли последний символ последнего слова.

2️⃣Определение длины последнего слова:
После того как последнее слово найдено, мы подсчитываем его длину, начиная с его последнего символа. Здесь также можно использовать цикл.

3️⃣Итог:
Используя обратную итерацию и пропуск пробелов, определяется начало и конец последнего слова в строке для вычисления его длины.

😎 Решение:

var lengthOfLastWord = function (s) {
    let p = s.length - 1;
    while (p >= 0 && s[p] === " ") {
        p--;
    }
    let length = 0;
    while (p >= 0 && s[p] !== " ") {
        p--;
        length++;
    }
    return length;
};

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

👨‍💻 Алгоритм:

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

2⃣Используйте множество для отслеживания слов, которые можно построить.

3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.

😎 Решение:

var longestWord = function(words) {
    words.sort();
    let validWords = new Set([""]);
    let longest = "";
    for (let word of words) {
        if (validWords.has(word.slice(0, -1))) {
            validWords.add(word);
            if (word.length > longest.length) {
                longest = word;
            }
        }
    }
    return longest;
};

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

Задача: 976. Largest Perimeter Triangle
Сложность: easy

Дан целочисленный массив nums. Верните наибольший периметр треугольника с ненулевой площадью, образованный из трех этих длин. Если невозможно образовать треугольник с ненулевой площадью, верните 0.

Пример:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

👨‍💻 Алгоритм:

1⃣Отсортируйте массив nums в порядке возрастания.

2⃣Для каждого элемента c в массиве, начиная с конца: Выберите два наибольших возможных значения a и b, которые находятся перед c в отсортированном массиве (т.е. значения, смежные с c). Проверьте, образуют ли a, b и c треугольник (условие треугольника: a + b > c). Если образуют, верните их сумму как периметр треугольника.

3⃣Если не удалось найти такие значения, верните 0.

😎 Решение:

var largestPerimeter = function(A) {
    A.sort((a, b) => a - b);
    for (let i = A.length - 3; i >= 0; --i)
        if (A[i] + A[i + 1] > A[i + 2])
            return A[i] + A[i + 1] + A[i + 2];
    return 0;
};

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

Задача: 985. Sum of Even Numbers After Queries
Сложность: medium

Дан целочисленный массив nums и массив queries, где queries[i] = [vali, indexi].

Для каждого запроса i, сначала примените nums[indexi] = nums[indexi] + vali, затем выведите сумму четных значений nums.

Верните целочисленный массив answer, где answer[i] - это ответ на i-й запрос.

Пример:

Input: nums = [1], queries = [[4,0]]
Output: [0]

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Завести переменную evenSum для хранения суммы всех четных чисел в массиве nums.
Пройти по массиву nums и вычислить начальное значение evenSum, сложив все четные числа в nums.

2⃣Обработка запросов:
Создать пустой массив result для хранения ответов на каждый запрос.
Для каждого запроса [val, index] из массива queries выполнить следующие действия:
Если значение nums[index] четное, вычесть его из evenSum.
Обновить nums[index] добавлением val.
Если новое значение nums[index] четное, добавить его к evenSum.
Добавить текущее значение evenSum в массив result.

3⃣Возврат результата:
Вернуть массив result, содержащий ответы на все запросы.

😎 Решение:

var sumEvenAfterQueries = function(nums, queries) {
    let evenSum = nums.reduce((acc, num) => num % 2 === 0 ? acc + num : acc, 0);
    const result = [];
    
    for (const [val, index] of queries) {
        if (nums[index] % 2 === 0) {
            evenSum -= nums[index];
        }
        nums[index] += val;
        if (nums[index] % 2 === 0) {
            evenSum += nums[index];
        }
        result.push(evenSum);
    }
    
    return result;
};

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

Задача: 988. Smallest String Starting From Leaf
Сложность: medium

Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.

Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.

Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.

Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.

Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка:
Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк).
Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы.

2⃣Обход дерева:
Если текущий узел пуст (null), просто вернитесь из функции.
Добавьте текущий символ (соответствующий значению узла) в начало строки пути.
Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше.
Рекурсивно вызовите dfs для левого и правого потомков текущего узла.

3⃣Возврат результата:
Вызовите функцию dfs с корневым узлом и пустым путем.
Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня.

😎 Решение:

var smallestFromLeaf = function(root) {
    let ans = "~";
    
    const dfs = (node, path) => {
        if (!node) return;
        path = String.fromCharCode(node.val + 'a'.charCodeAt(0)) + path;
        if (!node.left && !node.right) {
            if (path < ans) {
                ans = path;
            }
        }
        dfs(node.left, path);
        dfs(node.right, path);
    };
    
    dfs(root, "");
    return ans;
};

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

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy

Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.

Дерево cloned является копией оригинального дерева.

Верните ссылку на тот же узел в дереве cloned.

Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.

Пример:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

👨‍💻 Алгоритм:

1⃣Добавьте корень в очередь.

2⃣Пока очередь не пуста, извлекайте узел из очереди. Если узел является целевым, завершите выполнение. Добавьте сначала левый, затем правый дочерний узел в очередь.

3⃣Верните ссылку на найденный целевой узел.

😎 Решение:

var getTargetCopy = function(original, cloned, target) {
    const queue_o = [original];
    const queue_c = [cloned];
    
    while (queue_o.length) {
        const node_o = queue_o.shift();
        const node_c = queue_c.shift();
        
        if (node_o === target) {
            return node_c;
        }
        
        if (node_o.left !== null) {
            queue_o.push(node_o.left);
            queue_c.push(node_c.left);
        }
        if (node_o.right !== null) {
            queue_o.push(node_o.right);
            queue_c.push(node_c.right);
        }
    }
    return null;
};

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

Задача: 1019. Next Greater Node In Linked List
Сложность: medium

Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.

Пример:

Input: head = [2,1,5]
Output: [5,5,0]

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Пройдитесь по всему списку и сохраните значения узлов в массив.
Инициализируйте стек для хранения индексов узлов, которые нужно обработать.

2⃣Поиск следующего большего элемента:
Итерируйте по массиву значений узлов.
Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека.
Добавьте текущий индекс в стек.

3⃣Заполнение оставшихся значений:
Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента.

😎 Решение:

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    nextLargerNodes(head) {
        const values = [];
        while (head) {
            values.push(head.val);
            head = head.next;
        }
        
        const answer = Array(values.length).fill(0);
        const stack = [];
        
        for (let i = 0; i < values.length; i++) {
            while (stack.length && values[stack[stack.length - 1]] < values[i]) {
                answer[stack.pop()] = values[i];
            }
            stack.push(i);
        }
        
        return answer;
    }
}

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

Задача: 1143. Longest Common Subsequence
Сложность: medium

Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0.

Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов.
Например, "ace" является подпоследовательностью "abcde".
Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк.

Пример:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

👨‍💻 Алгоритм:

1⃣Создайте двумерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте массив значением -1, чтобы указать, что эти ячейки еще не были рассчитаны.

2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями.

3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки.

😎 Решение:

var longestCommonSubsequence = function(text1, text2) {
    const memo = Array.from({ length: text1.length + 1 }, () => Array(text2.length + 1).fill(-1));
    
    const memoSolve = (p1, p2) => {
        if (p1 === text1.length || p2 === text2.length) return 0;
        if (memo[p1][p2] !== -1) return memo[p1][p2];
        let answer;
        if (text1[p1] === text2[p2]) {
            answer = 1 + memoSolve(p1 + 1, p2 + 1);
        } else {
            answer = Math.max(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2));
        }
        memo[p1][p2] = answer;
        return answer;
    };
    
    return memoSolve(0, 0);
};

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

Сложность: medium
Задача: 628. Maximum Product of Three Numbers

Задав целочисленный массив nums, найдите три числа, произведение которых максимально, и верните максимальное произведение.

Пример:

Input: nums = [1,2,3]
Output: 6

👨‍💻 Алгоритм:

1⃣Отсортируйте массив nums.

2⃣Найдите два возможных максимальных произведения: Произведение трех наибольших элементов массива. Произведение двух наименьших (отрицательных) и одного наибольшего элемента массива.

3⃣Верните максимальное из двух найденных произведений.

😎 Решение:

function maximumProduct(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const max1 = nums[n - 1] * nums[n - 2] * nums[n - 3];
    const max2 = nums[0] * nums[1] * nums[n - 1];
    return Math.max(max1, max2);
}

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.

Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций.

Обратите внимание: вы не можете участвовать в нескольких транзакциях одновременно (то есть, вы должны продать акцию, прежде чем снова её купить).

Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

👨‍💻 Алгоритм:

1️⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение.
Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²).

2️⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй,
одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство.

3️⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i].
Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]).
Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5.

😎 Решение:

var maxProfit = function (prices) {
    if (prices.length <= 1) return 0;
    let left_min = prices[0];
    let right_max = prices[prices.length - 1];
    let length = prices.length;
    let left_profits = new Array(length).fill(0);
    let right_profits = new Array(length + 1).fill(0);
    for (let l = 1; l < length; ++l) {
        left_profits[l] = Math.max(left_profits[l - 1], prices[l] - left_min);
        left_min = Math.min(left_min, prices[l]);
        let r = length - 1 - l;
        right_profits[r] = Math.max(
            right_profits[r + 1],
            right_max - prices[r],
        );
        right_max = Math.max(right_max, prices[r]);
    }
    let max_profit = 0;
    for (let i = 0; i < length; ++i) {
        max_profit = Math.max(
            max_profit,
            left_profits[i] + right_profits[i + 1],
        );
    }
    return max_profit;
};

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

Задача: 734. Sentence Similarity
Сложность: easy

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].
Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

👨‍💻 Алгоритм:

1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false.

2⃣Создайте словарь для хранения всех пар похожих слов.

3⃣Проверьте каждую пару слов из предложений sentence1 и sentence2 на схожесть, используя словарь и правило, что слово всегда похоже на само себя.

😎 Решение:

var areSentencesSimilar = function(sentence1, sentence2, similarPairs) {
    if (sentence1.length !== sentence2.length) {
        return false;
    }

    const similar = new Map();
    for (const [x, y] of similarPairs) {
        if (!similar.has(x)) similar.set(x, new Set());
        if (!similar.has(y)) similar.set(y, new Set());
        similar.get(x).add(y);
        similar.get(y).add(x);
    }

    for (let i = 0; i < sentence1.length; i++) {
        const w1 = sentence1[i], w2 = sentence2[i];
        if (w1 !== w2 && (!similar.has(w1) || !similar.get(w1).has(w2))) {
            return false;
        }
    }

    return true;
};

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

Задача: 1522. Diameter of N-Ary Tree
Сложность: medium

Дано корневое дерево N-арности, нужно вычислить длину диаметра дерева.

Диаметр N-арного дерева - это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.

(Входная сериализация N-арного дерева представлена их обходом в порядке уровней, каждая группа дочерних узлов разделена значением null.)

Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

👨‍💻 Алгоритм:

1⃣Определите функцию height(node), которая возвращает высоту узла. Функция может быть реализована рекурсивно, основываясь на вычислении максимальной высоты среди всех дочерних узлов плюс один.

2⃣Внутри функции height(node) выберите две наибольшие высоты среди дочерних узлов. Эти два значения помогут вычислить длину пути, которая будет кандидатом на диаметр всего дерева.

3⃣Существует два подхода для выбора двух наибольших высот:
— Первый способ заключается в хранении высот всех дочерних узлов в массиве, последующей сортировке массива и выборе двух наибольших элементов.
— Второй способ использует две переменные, которые отслеживают текущие два наибольших значения. Во время итерации по всем высотам эти переменные обновляются соответствующим образом.

😎 Решение:

class Solution {
    constructor() {
        this.diameter = 0;
    }

    height(node) {
        if (node.children.length === 0) return 0;

        let maxHeight1 = 0, maxHeight2 = 0;
        for (const child of node.children) {
            const parentHeight = this.height(child) + 1;
            if (parentHeight > maxHeight1) {
                maxHeight2 = maxHeight1;
                maxHeight1 = parentHeight;
            } else if (parentHeight > maxHeight2) {
                maxHeight2 = parentHeight;
            }
            const distance = maxHeight1 + maxHeight2;
            this.diameter = Math.max(this.diameter, distance);
        }

        return maxHeight1;
    }

    diameter(root) {
        this.diameter = 0;
        this.height(root);
        return this.diameter;
    }}

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

Задача: 188. Best Time to Buy and Sell Stock IV

Сложность: hard
Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз.
Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).

Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

👨‍💻 Алгоритм:

1️⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).

2️⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).

3️⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.

😎 Решение:

class Solution {
    maxProfit(k, prices) {
        const n = prices.length;
        if (n === 0 || k === 0) return 0;
        if (k * 2 >= n) {
            let res = 0;
            for (let i = 1; i < n; i++) {
                res += Math.max(0, prices[i] - prices[i - 1]);
            }
            return res;
        }
        const dp = Array.from({ length: n }, () =>
            Array.from({ length: k + 1 }, () => Array(2).fill(Number.MIN_SAFE_INTEGER / 2))
        );
        dp[0][0][0] = 0;
        dp[0][1][1] = -prices[0];

        for (let i = 1; i < n; i++) {
            for (let j = 0; j <= k; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                if (j > 0) {
                    dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                }
            }
        }
        return Math.max(...dp[n - 1].map(x => x[0]));
    }
}

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

Задача: 1044. Longest Duplicate Substring
Сложность: hard

Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".

Пример:

Input: s = "banana"
Output: "ana"

👨‍💻 Алгоритм:

1⃣Использование двоичного поиска для определения длины дублированной подстроки:
Двоичный поиск используется для поиска максимальной длины дублированной подстроки.

2⃣Использование хеширования для проверки наличия дублированной подстроки определенной длины:
Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок.

3⃣Хеширование с помощью функции rolling hash:
Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎 Решение:

function longestDupSubstring(s) {
    function search(len) {
        let seen = new Set();
        for (let i = 0; i <= s.length - len; i++) {
            let sub = s.slice(i, i + len);
            if (seen.has(sub)) {
                return sub;
            }
            seen.add(sub);
        }
        return "";
    }

    let left = 1, right = s.length;
    let result = "";
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let dup = search(mid);
        if (dup) {
            result = dup;
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return result;
}

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