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

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

Задача: 1424. Diagonal Traverse II
Сложность: medium

Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке.

Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

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

1⃣Инициализируйте очередь с (0, 0) и список ответов ans.

2⃣Пока очередь не пуста:
Извлеките (row, col) из очереди.
Добавьте nums[row][col] в ans.
Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь.
Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь.

3⃣Верните ans.

😎 Решение:

class Solution {
    findDiagonalOrder(nums) {
        const queue = [[0, 0]];
        const ans = [];
        
        while (queue.length > 0) {
            const [row, col] = queue.shift();
            ans.push(nums[row][col]);
            
            if (col === 0 && row + 1 < nums.length) {
                queue.push([row + 1, col]);
            }
            
            if (col + 1 < nums[row].length) {
                queue.push([row, col + 1]);
            }
        }
        
        return ans;
    }
}

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

Задача: 410. Split Array Largest Sum
Сложность: easy

Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива.

Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

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

1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

2⃣Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму.

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

😎 Решение:

function splitArray(nums, k) {
    function canSplit(nums, k, maxSum) {
        let currentSum = 0;
        let subarrays = 1;
        for (const num of nums) {
            if (currentSum + num > maxSum) {
                currentSum = num;
                subarrays++;
                if (subarrays > k) {
                    return false;
                }
            } else {
                currentSum += num;
            }
        }
        return true;
    }
    
    let left = Math.max(...nums);
    let right = nums.reduce((a, b) => a + b, 0);
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canSplit(nums, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

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

Задача: 755. Pour Water
Сложность: medium

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

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

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

function pourWater(heights, volume, k) {
    for (let v = 0; v < volume; v++) {
        let dropIndex = k;
        for (let d of [-1, 1]) {
            let i = k;
            while (i + d >= 0 && i + d < heights.length && heights[i + d] <= heights[i]) {
                if (heights[i + d] < heights[i]) {
                    dropIndex = i + d;
                }
                i += d;
            }
            if (dropIndex != k) {
                break;
            }
        }
        heights[dropIndex]++;
    }
    return heights;
}

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

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

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

Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]
Output: 22

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

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

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

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

😎 Решение:

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    sumRootToLeaf(root) {
        const dfs = (node, currentValue) => {
            if (!node) return 0;
            currentValue = (currentValue << 1) | node.val;
            if (!node.left && !node.right) return currentValue;
            return dfs(node.left, currentValue) + dfs(node.right, currentValue);
        };
        
        return dfs(root, 0);
    }
}

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

Задача: 1356. Sort Integers by The Number of 1 Bits
Сложность: easy

Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию.

Верните массив после сортировки.

Пример:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

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

1⃣Создание функции для подсчета единиц:
Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении.

2⃣Сортировка массива:
Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки.

3⃣Возврат отсортированного массива:
Верните отсортированный массив.

😎 Решение:

var sortByBits = function(arr) {
    return arr.sort((a, b) => {
        const countA = a.toString(2).split('1').length - 1;
        const countB = b.toString(2).split('1').length - 1;
        return countA === countB ? a - b : countA - countB;
    });
};

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

Задача: 164. Maximum Gap
Сложность: medium

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

Пример:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

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

1️⃣Инициализация:
Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве.
Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1).

2️⃣Размещение элементов в ведрах:
Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения.
Игнорируйте пустые ведра при расчете максимального интервала.

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

😎 Решение:

var maximumGap = function (nums) {
    if (nums == null || nums.length < 2)
        return 0;

    nums.sort((a, b) => a - b)

    var maxGap = 0;

    for (var i = 0; i < nums.length - 1; i++)
        maxGap = Math.max(nums[i + 1] - nums[i], maxGap);

    return maxGap;
};

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