Задача: 870. Advantage Shuffle
Сложность: medium

Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i].

Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2.

Пример:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

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

1⃣Отсортируйте nums1 и nums2. Для каждой карты a из отсортированного nums1 определите, может ли она побить текущую наименьшую карту b из отсортированного nums2. Если да, добавьте a в assigned[b], если нет, добавьте a в remaining.

2⃣После распределения всех карт из nums1, используйте assigned и remaining для построения итогового результата. Для каждой карты b из nums2, если assigned[b] не пуст, добавьте в результат последнюю карту из assigned[b], иначе добавьте последнюю карту из remaining.

3⃣Верните итоговый результат.

😎 Решение:

var advantageCount = function(A, B) {
    let sortedA = A.slice().sort((a, b) => a - b);
    let sortedB = B.map((val, idx) => [val, idx]).sort((a, b) => a[0] - b[0]);
    let assigned = {}, remaining = [], j = 0;

    B.forEach(b => assigned[b] = []);

    sortedA.forEach(a => {
        if (a > sortedB[j][0]) {
            assigned[sortedB[j][0]].push(a);
            j++;
        } else {
            remaining.push(a);
        }
    });

    return B.map(b => assigned[b].length ? assigned[b].pop() : remaining.pop());
};

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

Задача: 954. Array of Doubled Pairs
Сложность: medium

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:
Input: arr = [3,1,3,6]
Output: false

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

1⃣Подсчитать частоту каждого элемента в массиве.
Отсортировать массив по абсолютным значениям элементов.

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

var canReorderDoubled = function(arr) {
    let count = new Map();
    for (let num of arr) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    arr.sort((a, b) => Math.abs(a) - Math.abs(b));
    for (let num of arr) {
        if (count.get(num) === 0) continue;
        if (count.get(num * 2) === 0) return false;
        count.set(num, count.get(num) - 1);
        count.set(num * 2, count.get(num * 2) - 1);
    }
    return true;
};

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

1⃣Создать множество для хранения уникальных результатов побитового ИЛИ.

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

3⃣Вернуть размер множества.

😎 Решение:

var subarrayBitwiseORs = function(arr) {
    let result = new Set();
    let current = new Set();
    for (let num of arr) {
        let next = new Set();
        for (let x of current) {
            next.add(x | num);
        }
        next.add(num);
        current = next;
        for (let x of current) {
            result.add(x);
        }
    }
    return result.size;
};

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

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

😎 Решение:

var minCostPath = function(coins, maxJump) {
    const n = coins.length;
    if (coins[0] === -1) return [];
    
    const dp = new Array(n).fill(Infinity);
    dp[0] = coins[0];
    const path = Array.from({ length: n }, () => []);
    path[0] = [1];
    
    const heap = [[coins[0], 0]];
    
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]);
        const [current_cost, i] = heap.shift();
        if (current_cost > dp[i]) continue;
        for (let k = 1; k <= maxJump; k++) {
            if (i + k < n && coins[i + k] !== -1) {
                const new_cost = current_cost + coins[i + k];
                if (new_cost < dp[i + k] || (new_cost === dp[i + k] && path[i].concat(i + k + 1) < path[i + k])) {
                    dp[i + k] = new_cost;
                    path[i + k] = path[i].concat(i + k + 1);
                    heap.push([new_cost, i + k]);
                }
            }
        }
    }
    
    return dp[n - 1] === Infinity ? [] : path[n - 1];
};

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

1⃣Инициализация. Создайте пустой список inorder для хранения значений узлов после обхода в порядке возрастания.

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

var balanceBST = function(root) {
    if (!root) return null;

    const vineHead = new TreeNode(0);
    vineHead.right = root;
    let current = vineHead;

    while (current.right) {
        if (current.right.left) {
            rightRotate(current, current.right);
        } else {
            current = current.right;
        }
    }

    let nodeCount = 0;
    current = vineHead.right;
    while (current) {
        nodeCount++;
        current = current.right;
    }

    let m = 2 ** Math.floor(Math.log2(nodeCount + 1)) - 1;
    makeRotations(vineHead, nodeCount - m);
    while (m > 1) {
        m = Math.floor(m / 2);
        makeRotations(vineHead, m);
    }

    return vineHead.right;
};

function rightRotate(parent, node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    parent.right = tmp;
}

function leftRotate(parent, node) {
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    parent.right = tmp;
}

function makeRotations(vineHead, count) {
    let current = vineHead;
    for (let i = 0; i < count; i++) {
        const tmp = current.right;
        leftRotate(current, tmp);
        current = current.right;
    }
}

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

Задача: 967. Numbers With Same Consecutive Differences
Сложность: medium

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

Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются.

Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

1⃣Если n равно 1, верните массив от 0 до 9, так как все однозначные числа являются допустимыми.

2⃣Инициализируйте список очередей начальными цифрами от 1 до 9.

3⃣Для каждого уровня (от 1 до n-1) создайте новый список очередей, добавляя к каждому числу в текущей очереди допустимые цифры, которые удовлетворяют условию разницы k.

😎 Решение:

var numsSameConsecDiff = function(N, K) {
    if (N === 1) return [...Array(10).keys()];

    let queue = [...Array(9).keys()].map(i => i + 1);
    for (let level = 1; level < N; ++level) {
        let nextQueue = [];
        for (let num of queue) {
            let tailDigit = num % 10;
            let nextDigits = [tailDigit + K, tailDigit - K];
            for (let nextDigit of nextDigits) {
                if (nextDigit >= 0 && nextDigit < 10) {
                    nextQueue.push(num * 10 + nextDigit);
                }
            }
        }
        queue = nextQueue;
    }

    return queue;
};

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

Задача: 1662. Check If Two String Arrays are Equivalent
Сложность: easy

Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае.

Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку.

Пример:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

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

1⃣Построение списка символов для word2:
Создайте список list2 для хранения всех символов из массива строк word2.

2⃣Итерация по word1 и проверка соответствующих символов:
Итеративно пройдите по строкам в word1 и сравнивайте каждый символ с соответствующим символом из list2.

3⃣Возврат результата:
Верните true, если все символы совпадают, и false, если найдены несовпадения или длины строк не совпадают.

😎 Решение:

var arrayStringsAreEqual = function(word1, word2) {
    const list2 = word2.join('');
    let index = 0;
    const n = list2.length;

    for (const word of word1) {
        for (const char of word) {
            if (index >= n || char !== list2[index]) {
                return false;
            }
            index++;
        }
    }

    return index === n;
};

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

Задача: 820. Short Encoding of Words
Сложность: medium

Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:

words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.

Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

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

1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.

2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.

3⃣В конце вернем длину полученной опорной строки.

😎 Решение:

var minimumLengthEncoding = function(words) {
    let good = new Set(words);
    for (let word of words) {
        for (let k = 1; k < word.length; k++) {
            good.delete(word.substring(k));
        }
    }
    let length = 0;
    for (let word of good) {
        length += word.length + 1;
    }
    return length;

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

Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

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

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

var atMostNGivenDigitSet = function(digits, n) {
    let s = n.toString();
    let K = s.length;
    let dp = new Array(K + 1).fill(0);
    dp[K] = 1;

    for (let i = K - 1; i >= 0; --i) {
        for (let d of digits) {
            if (d < s[i]) {
                dp[i] += Math.pow(digits.length, K - i - 1);
            } else if (d == s[i]) {
                dp[i] += dp[i + 1];
            }
        }
    }

    for (let i = 1; i < K; ++i) {
        dp[0] += Math.pow(digits.length, i);
    }

    return dp[0];
};

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

Задача: 434. Number of Segments in a String
Сложность: easy

Дана строка s, верните количество сегментов в строке.
Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.

Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

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

1⃣Инициализируйте счетчик сегментов segment_count равным 0.

2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count.

3⃣Верните segment_count.

😎 Решение:

var countSegments = function(s) {
    let segmentCount = 0;

    for (let i = 0; i < s.length; i++) {
        if ((i === 0 || s[i - 1] === ' ') && s[i] !== ' ') {
            segmentCount++;
        }
    }

    return segmentCount;
};

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

Задача: 169. Majority Element
Сложность: easy

Дан массив nums размера n, верните элемент большинства.
Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.

Пример:

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

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

1️⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.

2️⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.

3️⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋

😎 Решение:

var majorityElement = function (nums) {
    let counts = {};
    for (let num of nums) {
        if (!counts[num]) {
            counts[num] = 1;
        } else {
            counts[num]++;
        }
    }

    for (let num in counts) {
        if (counts[num] > nums.length / 2) return Number(num);
    }
    return 0;
};

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

Задача: 149. Max Points on a Line
Сложность: hard

Дан массив точек, где points[i] = [xi, yi] представляет точку на плоскости XY. Верните максимальное количество точек, которые лежат на одной прямой.

Пример:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

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

1️⃣Итерация по всем точкам:
Проходим по всем точкам массива. Пусть текущая точка будет points[i]. Создаём хеш-таблицу cnt для подсчёта углов.

2️⃣Расчёт углов и подсчёт:
Для каждой точки j, не равной i, рассчитываем арктангенс вектора points[j] - points[i] и добавляем это значение в хеш-таблицу

3️⃣Обновление ответа:
Пусть k будет максимальным количеством вхождений какого-либо значения угла в хеш-таблице. Обновляем ответ значением k + 1 (прибавляем 1, потому что точка points[i] также лежит на этой линии, и её нужно включить в ответ).

😎 Решение:

var maxPoints = function (points) {
    let n = points.length;
    if (n == 1) {
        return 1;
    }
    let result = 2;
    for (let i = 0; i < n; i++) {
        let cnt = {};
        for (let j = 0; j < n; j++) {
            if (j != i) {
                let key = Math.atan2(
                    points[j][1] - points[i][1],
                    points[j][0] - points[i][0],
                );
                cnt[key] = cnt[key] ? cnt[key] + 1 : 1;
            }
        }
        result = Math.max(result, Math.max(...Object.values(cnt)) + 1);
    }
    return result;
};

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

Задача: 311. Sparse Matrix Multiplication
Сложность: medium

Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно.

Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

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

1⃣Инициализация результирующей матрицы
Создайте результирующую матрицу result размером m x n, заполненную нулями.

2⃣Хранение ненулевых элементов
Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map.

3⃣Вычисление произведения
Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j].

😎 Решение:

var multiply = function(mat1, mat2) {
    let n = mat1.length;
    let k = mat1[0].length;
    let m = mat2[0].length;
    
    let ans = Array.from({ length: n }, () => Array(m).fill(0));
    
    for (let rowIndex = 0; rowIndex < n; rowIndex++) {
        for (let elementIndex = 0; elementIndex < k; elementIndex++) {
            if (mat1[rowIndex][elementIndex] !== 0) {
                for (let colIndex = 0; colIndex < m; colIndex++) {
                    ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                }
            }
        }
    }
    
    return ans;
};

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

Задача: 651. 4 Keys Keyboard
Сложность: medium

Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.

Пример:

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

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

1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.

2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста.

3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.

😎 Решение:

var maxA = function(n) {
    let dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        for (let j = 2; j < i; j++) {
            dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
        }
    }
    return dp[n];
};

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

Задача: 147. Insertion Sort List
Сложность: medium

Дана голова односвязного списка. Отсортируйте список, используя сортировку вставками, и верните голову отсортированного списка.
Шаги алгоритма сортировки вставками:
1. Сортировка вставками итеративно работает, потребляя один входной элемент за каждую итерацию и формируя отсортированный выходной список.
2. На каждой итерации сортировка вставками удаляет один элемент из входных данных, находит место, куда он принадлежит в отсортированном списке, и вставляет его туда.
3. Процесс повторяется до тех пор, пока не закончатся входные элементы.

Пример:

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

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

1️⃣Создание вспомогательного узла (pseudo_head):
В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком.

2️⃣Механизм вставки узла:
В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A.

3️⃣Использование пары указателей для вставки:
Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка.

😎 Решение:

var insertionSortList = function (head) {
    let dummy = new ListNode();
    let curr = head;
    while (curr !== null) {
        let prev = dummy;
        while (prev.next !== null && prev.next.val <= curr.val) {
            prev = prev.next;
        }
        let next = curr.next;
        curr.next = prev.next;
        prev.next = curr;
        curr = next;
    }
    return dummy.next;
};

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

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

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