Задача: 841. Keys and Rooms
Сложность: medium

Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

var canVisitAllRooms = function(rooms) {
    let seen = new Array(rooms.length).fill(false);
    seen[0] = true;
    let stack = [0];

    while (stack.length > 0) {
        let node = stack.pop();
        for (let nei of rooms[node]) {
            if (!seen[nei]) {
                seen[nei] = true;
                stack.push(nei);
            }
        }
    }

    return seen.every(Boolean);
};

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1️⃣ Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2️⃣ Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

3️⃣ Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания.

😎 Решение:

class Solution {
    constructor() {
        this.WHITE = 1;
        this.GRAY = 2;
        this.BLACK = 3;
        this.isPossible = true;
        this.color = new Map();
        this.adjList = new Map();
        this.topologicalOrder = [];
    }

    findOrder(numCourses, prerequisites) {
        for (let i = 0; i < numCourses; i++) {
            this.color.set(i, this.WHITE);
        }

        for (let [dest, src] of prerequisites) {
            if (!this.adjList.has(src)) {
                this.adjList.set(src, []);
            }
            this.adjList.get(src).push(dest);
        }

        for (let i = 0; i < numCourses && this.isPossible; i++) {
            if (this.color.get(i) === this.WHITE) {
                this.dfs(i);
            }
        }

        if (this.isPossible) {
            const order = new Array(numCourses);
            for (let i = 0; i < numCourses; i++) {
                order[i] = this.topologicalOrder[numCourses - i - 1];
            }
            return order;
        } else {
            return [];
        }
    }

    dfs(node) {
        if (!this.isPossible) return;
        this.color.set(node, this.GRAY);

        if (this.adjList.has(node)) {
            for (let neighbor of this.adjList.get(node)) {
                if (this.color.get(neighbor) === this.WHITE) {
                    this.dfs(neighbor);
                } else if (this.color.get(neighbor) === this.GRAY) {
                    this.isPossible = false;
                }
            }
        }

        this.color.set(node, this.BLACK);
        this.topologicalOrder.push(node);
    }
}

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

Задача: 424. Longest Repeating Character Replacement
Сложность: medium

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

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

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

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

😎 Решение:

class Solution {
    characterReplacement(s, k) {
        let lo = 1, hi = s.length + 1;

        while (lo + 1 < hi) {
            let mid = lo + Math.floor((hi - lo) / 2);
            if (this.canMakeValidSubstring(s, mid, k)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    canMakeValidSubstring(s, substringLength, k) {
        let freqMap = new Array(26).fill(0);
        let maxFrequency = 0;
        let start = 0;

        for (let end = 0; end < s.length; end++) {
            freqMap[s.charCodeAt(end) - 65]++;

            if (end + 1 - start > substringLength) {
                freqMap[s.charCodeAt(start) - 65]--;
                start++;
            }

            maxFrequency = Math.max(maxFrequency, freqMap[s.charCodeAt(end) - 65]);
            if (substringLength - maxFrequency <= k) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 203. Remove Linked List Elements
Сложность: easy

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

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

1️⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2️⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3️⃣Верните sentinel.next.

😎 Решение:

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function deleteNode(head, value) {
    let sentinel = new ListNode(0);
    sentinel.next = head;
    let prev = sentinel, curr = head;

    while (curr !== null) {
        if (curr.val === value) {
            prev.next = curr.next;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
    return sentinel.next;
}

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

Задача: 53. Maximum Subarray
Сложность: hard

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

Пример:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

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

1️⃣Инициализируйте переменную maxSubarray значением минус бесконечность, чтобы отслеживать лучший подмассив. Необходимо использовать отрицательную бесконечность, а не 0, поскольку в массиве могут быть только отрицательные числа.

2️⃣Используйте цикл for, который рассматривает каждый индекс массива в качестве начальной точки. Для каждой начальной точки создайте переменную currentSubarray с начальным значением 0. Затем пройдитесь по массиву, начиная с указанного индекса, прибавляя каждый элемент к currentSubarray. При каждом добавлении элемента получается возможный подмассив, поэтому непрерывно обновляйте maxSubarray, чтобы он содержал максимум из currentSubarray и самого себя.

3️⃣Верните значение maxSubarray.

😎 Решение:

var maxSubArray = function (nums) {
    let max_subarray = Number.NEGATIVE_INFINITY;
    for (let i = 0; i < nums.length; i++) {
        let current_subarray = 0;
        for (let j = i; j < nums.length; j++) {
            current_subarray += nums[j];
            max_subarray = Math.max(max_subarray, current_subarray);
        }
    }
    return max_subarray;
};

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

Задача: 527. Word Abbreviation
Сложность: hard

Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.
Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

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

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

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

😎 Решение:

var wordsAbbreviation = function(words) {
    const n = words.length;
    const ans = new Array(n).fill("");
    const prefix = new Array(n).fill(0);

    for (let i = 0; i < n; ++i) {
        ans[i] = abbrev(words[i], 0);
    }

    for (let i = 0; i < n; ++i) {
        while (true) {
            const dupes = new Set();
            for (let j = i + 1; j < n; ++j) {
                if (ans[i] === ans[j]) {
                    dupes.add(j);
                }
            }

            if (dupes.size === 0) break;
            dupes.add(i);
            for (const k of dupes) {
                ans[k] = abbrev(words[k], ++prefix[k]);
            }
        }
    }

    return ans;
};

function abbrev(word, i) {
    const n = word.length;
    if (n - i <= 3) return word;
    return word.slice(0, i + 1) + (n - i - 2) + word.slice(-1);
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

var deleteTreeNodes = function(nodes, parent, value) {
    let tree = new Map();
    for (let i = 0; i < nodes; i++) {
        if (!tree.has(parent[i])) tree.set(parent[i], []);
        tree.get(parent[i]).push(i);
    }

    function dfs(node) {
        let totalSum = value[node];
        let totalCount = 1;
        if (tree.has(node)) {
            for (let child of tree.get(node)) {
                let [childSum, childCount] = dfs(child);
                totalSum += childSum;
                totalCount += childCount;
            }
        }
        return totalSum === 0 ? [0, 0] : [totalSum, totalCount];
    }

    return dfs(0)[1];
};

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в следующую игру Nim со своим другом:
Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution {
    canWinNim(n) {
        return n % 4 !== 0;
    }
}

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

Задача: 165. Compare Version Numbers
Сложность: medium

Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.
Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.
Верните следующее:
- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.

Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

1️⃣Разделение строк: Разделите обе строки по символу точки на два массива.

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

3️⃣Определение результатов сравнения:
Если два сегмента не равны, верните 1 или -1 в зависимости от того, какой сегмент больше.
Если все сегменты равны после завершения цикла, версии считаются равными. Верните 0

😎 Решение:

var compareVersion = function (version1, version2) {
    let nums1 = version1.split(".");
    let nums2 = version2.split(".");
    let n1 = nums1.length,
        n2 = nums2.length;

    for (let i = 0; i < Math.max(n1, n2); ++i) {
        let i1 = i < n1 ? parseInt(nums1[i]) : 0;
        let i2 = i < n2 ? parseInt(nums2[i]) : 0;
        if (i1 != i2) {
            return i1 > i2 ? 1 : -1;
        }
    }
    return 0;
};

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

Задача: 52. N-Queens II
Сложность: hard

Задача "n-ферзей" заключается в размещении n ферзей на шахматной доске размером n x n таким образом, чтобы ни одна пара ферзей не атаковала друг друга.
Дано целое число n, верните количество различных решений задачи "n-ферзей".

Пример:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

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

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

2️⃣Введение локальной переменной solutions = 0, представляющей все возможные решения, которые могут быть получены из текущего состояния доски. Итерация по столбцам текущей строки, попытка разместить ферзя в каждом квадрате (row, col), учитывая текущую строку через аргументы функции.

3️⃣Расчёт принадлежности квадрата к диагонали и антидиагонали. Если в столбце, диагонали или антидиагонали ещё не размещен ферзь, то ферзь можно разместить в этом столбце текущей строки. Если ферзя разместить нельзя, переходим к следующему столбцу. Если ферзь успешно размещён, обновляем три набора (cols, diagonals, и antiDiagonals) и вызываем функцию снова, но с row + 1. После завершения исследования этого пути происходит откат, путём удаления ферзя из квадрата — это означает удаление значений, добавленных в наши наборы.

😎 Решение:

var totalNQueens = function (n) {
    function backtrack(row, diagonals, anti_diagonals, cols) {
        if (row == n) {
            return 1;
        }
        let solutions = 0;
        for (let col = 0; col < n; col++) {
            let curr_diagonal = row - col;
            let curr_anti_diagonal = row + col;
            if (
                cols.has(col) ||
                diagonals.has(curr_diagonal) ||
                anti_diagonals.has(curr_anti_diagonal)
            ) {
                continue;
            }
            cols.add(col);
            diagonals.add(curr_diagonal);
            anti_diagonals.add(curr_anti_diagonal);
            solutions += backtrack(row + 1, diagonals, anti_diagonals, cols);
            cols.delete(col);
            diagonals.delete(curr_diagonal);
            anti_diagonals.delete(curr_anti_diagonal);
        }
        return solutions;
    }
    return backtrack(0, new Set(), new Set(), new Set());
};

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

Задача: 108. Convert Sorted Array to Binary Search Tree
Сложность: easy

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

Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

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

1️⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right.
Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None.

2️⃣Выбор корня и разделение массива:
Выберите элемент в середине для корня: p = (left + right) // 2.
Инициализируйте корень: root = TreeNode(nums[p]).

3️⃣Рекурсивное построение поддеревьев:
Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1).
Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right).
В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева.

😎 Решение:

var sortedArrayToBST = function (nums) {
    return helper(nums, 0, nums.length - 1);
};
var helper = function (nums, left, right) {
    if (left > right) {
        return null;
    }
    var p = Math.floor((left + right) / 2);
    var root = new TreeNode(nums[p], null, null);
    root.left = helper(nums, left, p - 1);
    root.right = helper(nums, p + 1, right);
    return root;
};

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

Задача: 849. Maximize Distance to Closest Person
Сложность: medium

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

Верните это максимальное расстояние до ближайшего человека.

Пример:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

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

1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

3⃣Найдите и верните максимальное расстояние до ближайшего занятого места.

😎 Решение:

var maxDistToClosest = function(seats) {
    let n = seats.length;
    let prev = -1, future = 0;
    let ans = 0;

    for (let i = 0; i < n; ++i) {
        if (seats[i] === 1) {
            prev = i;
        } else {
            while (future < n && (seats[future] === 0 || future < i)) {
                future++;
            }
            let left = prev === -1 ? n : i - prev;
            let right = future === n ? n : future - i;
            ans = Math.max(ans, Math.min(left, right));
        }
    }

    return ans;
};

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

Задача: 345. Reverse Vowels of a String
Сложность: easy

Дана строка s, переверните только все гласные в строке и верните её.

Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры.

Пример:

Input: s = "hello"
Output: "holle"

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

1⃣Инициализация указателей и гласных:
Создайте набор гласных для быстрой проверки.
Установите два указателя: один на начало строки (left), другой на конец строки (right).

2⃣Перестановка гласных:
Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные.
Обменивайте найденные гласные и продолжайте сдвигать указатели.

3⃣Завершение работы:
Когда указатели пересекутся, остановите процесс и верните строку.

😎 Решение:

var reverseVowels = function(s) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
    let chars = s.split('');
    let left = 0, right = chars.length - 1;
    
    while (left < right) {
        if (!vowels.has(chars[left])) {
            left++;
        } else if (!vowels.has(chars[right])) {
            right--;
        } else {
            [chars[left], chars[right]] = [chars[right], chars[left]];
            left++;
            right--;
        }
    }
    
    return chars.join('');
};

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

Задача: 474. Ones and Zeroes
Сложность: medium

Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.

Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

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

1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.

2⃣Считаем количество нулей и единиц в каждом подмножестве.

3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.

😎 Решение:

class Solution {
    findMaxForm(strs, m, n) {
        let maxlen = 0;
        for (let i = 0; i < (1 << strs.length); i++) {
            let zeroes = 0, ones = 0, length = 0;
            for (let j = 0; j < 32; j++) {
                if ((i & (1 << j)) !== 0) {
                    const count = this.countZeroesOnes(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n) break;
                    length++;
                }
            }
            if (zeroes <= m && ones <= n) {
                maxlen = Math.max(maxlen, length);
            }
        }
        return maxlen;
    }

    countZeroesOnes(s) {
        const count = [0, 0];
        for (const char of s) {
            count[char - '0']++;
        }
        return count;
    }
}

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

Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

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

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎 Решение:

class Solution {
    valid(str1, str2, k) {
        let len1 = str1.length, len2 = str2.length;
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            let base = str1.slice(0, k);
            let n1 = Math.floor(len1 / k), n2 = Math.floor(len2 / k);
            return str1 === this.joinWords(base, n1) && str2 === this.joinWords(base, n2);
        }
    }
    
    joinWords(str, k) {
        let ans = '';
        for (let i = 0; i < k; ++i) {
            ans += str;
        }
        return ans;
    }

    gcdOfStrings(str1, str2) {
        let len1 = str1.length, len2 = str2.length;
        for (let i = Math.min(len1, len2); i >= 1; --i) {
            if (this.valid(str1, str2, i)) {
                return str1.slice(0, i);
            }
        }
        return "";
    }
}

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

Задача: 836. Rectangle Overlap
Сложность: easy

Прямоугольник, выровненный по осям, представляется в виде списка [x1, y1, x2, y2], где (x1, y1) — координата его нижнего левого угла, а (x2, y2) — координата его верхнего правого угла. Его верхняя и нижняя грани параллельны оси X, а левая и правая грани параллельны оси Y.

Два прямоугольника перекрываются, если площадь их пересечения положительна. Для ясности, два прямоугольника, которые касаются только в углу или по краям, не перекрываются.

Даны два выровненных по осям прямоугольника rec1 и rec2, вернуть true, если они перекрываются, в противном случае вернуть false.

Пример:
Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

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

1⃣Рассчитайте ширину пересечения: пересечение по оси x положительно, если min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]).

2⃣Рассчитайте высоту пересечения: пересечение по оси y положительно, если min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]).

3⃣Если и ширина, и высота пересечения положительны, прямоугольники перекрываются.

😎 Решение:

var isRectangleOverlap = function(rec1, rec2) {
    return Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]) &&
           Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]);
};

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

Задача: 101. Symmetric Tree
Сложность: easy

Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).

Пример:

Input: root = [1,2,2,3,4,4,3]
Output: true

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

1️⃣Дерево симметрично, если левое поддерево является зеркальным отражением правого поддерева.

2️⃣Следовательно, вопрос заключается в том, когда два дерева являются зеркальным отражением друг друга?

Два дерева являются зеркальным отражением друг друга, если:

- Их корни имеют одинаковое значение.
- Правое поддерево каждого дерева является зеркальным отражением левого поддерева другого дерева.

3️⃣Это похоже на человека, смотрящего в зеркало. Отражение в зеркале имеет ту же голову, но правая рука отражения соответствует левой руке настоящего человека и наоборот.

Вышеописанное объяснение естественным образом превращается в рекурсивную функцию.

😎 Решение:

var isSymmetric = function (root) {
    return isMirror(root, root);
};
var isMirror = function (t1, t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (
        t1.val === t2.val &&
        isMirror(t1.right, t2.left) &&
        isMirror(t1.left, t2.right)
    );
};

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

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

Дано целое число num. Вы можете поменять местами две цифры не более одного раза, чтобы получить число с наибольшим значением.
Верните число с наибольшим значением, которое можно получить.

Пример:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

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

1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно.

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

3⃣Возвращаем максимальное значение из всех кандидатов.

😎 Решение:

var maximumSwap = function(num) {
    let A = num.toString().split('');
    let ans = [...A];
    for (let i = 0; i < A.length; i++) {
        for (let j = i + 1; j < A.length; j++) {
            [A[i], A[j]] = [A[j], A[i]];
            for (let k = 0; k < A.length; k++) {
                if (A[k] !== ans[k]) {
                    if (A[k] > ans[k]) {
                        ans = [...A];
                    }
                    break;
                }
            }
            [A[i], A[j]] = [A[j], A[i]];
        }
    }
    return parseInt(ans.join(''));
}

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

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

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

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

var isPossible = function(target) {
    let pq = new MaxPriorityQueue({ priority: x => x });
    let total = target.reduce((acc, num) => acc + num, 0);
    target.forEach(num => pq.enqueue(num));
    
    while (pq.front().element > 1) {
        let maxVal = pq.dequeue().element;
        total -= maxVal;
        if (maxVal < total || total === 0 || maxVal % total === 0) return false;
        pq.enqueue(maxVal % total);
        total += pq.front().element;
    }
    return true;
};

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

Задача: 68. Text Justification
Сложность: hard

Дан массив строк words и ширина maxWidth. Необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов и была полностью (слева и справа) выровнена.
Слова следует упаковывать жадным способом; то есть стараться поместить как можно больше слов в каждую строку. Дополнительные пробелы ' ' следует добавлять по мере необходимости, чтобы каждая строка имела ровно maxWidth символов.
Дополнительные пробелы между словами должны распределяться как можно более равномерно. Если количество пробелов в строке не делится поровну между словами, то пустые места слева будут содержать больше пробелов, чем места справа.
Для последней строки текста выравнивание должно быть по левому краю, и между словами не добавляются дополнительные пробелы.

Пример:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

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

1️⃣Создайте два вспомогательных метода getWords и createLine, описанные выше.

2️⃣Инициализируйте список ответов ans и целочисленную переменную i для итерации по входным данным. Используйте цикл while для перебора входных данных. Каждая итерация в цикле while будет обрабатывать одну строку в ответе.

3️⃣Пока i < words.length, выполните следующие шаги:
Получите слова, которые должны быть в текущей строке, как currentLine = getWords(i).
Увеличьте i на currentLine.length.
Создайте строку, вызвав createLine(line, i), и добавьте её в ans.
Верните ans.

😎 Решение:

var fullJustify = function (words, maxWidth) {
    let ans = [];
    let i = 0;
    while (i < words.length) {
        let currentLine = getWords(i, words, maxWidth);
        i += currentLine.length;
        ans.push(createLine(currentLine, i, words, maxWidth));
    }
    return ans;
    function getWords(i, words, maxWidth) {
        let currentLine = [];
        let currLength = 0;
        while (i < words.length && currLength + words[i].length <= maxWidth) {
            currentLine.push(words[i]);
            currLength += words[i].length + 1;
            i++;
        }
        return currentLine;
    }
    function createLine(line, i, words, maxWidth) {
        let baseLength = -1;
        for (let word of line) {
            baseLength += word.length + 1;
        }
        let extraSpaces = maxWidth - baseLength;
        if (line.length === 1 || i === words.length) {
            return line.join(" ") + " ".repeat(extraSpaces);
        }
        let wordCount = line.length - 1;
        let spacesPerWord = Math.floor(extraSpaces / wordCount);
        let needsExtraSpace = extraSpaces % wordCount;
        for (let j = 0; j < needsExtraSpace; j++) {
            line[j] += " ";
        }
        for (let j = 0; j < wordCount; j++) {
            line[j] += " ".repeat(spacesPerWord);
        }
        return line.join(" ");
    }
};

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

Задача: 905. Sort Array By Parity
Сложность: easy

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

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

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

1⃣Создать два списка: один для четных чисел, другой для нечетных.

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

3⃣Объединить два списка и вернуть результат.

😎 Решение:

var sortArrayByParity = function(nums) {
    let evens = [];
    let odds = [];
    for (let num of nums) {
        if (num % 2 === 0) {
            evens.push(num);
        } else {
            odds.push(num);
        }
    }
    return evens.concat(odds);
};

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