#hard
Задача: 43. Multiply Strings

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

Примечание: Вы не должны использовать встроенную библиотеку BigInteger или прямо преобразовывать входные данные в целые числа.

Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

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

1️⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2️⃣Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.

3️⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.
Добавьте currentResult к ans.
Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.
Переверните ans и верните его.

😎 Решение:

let addStrings = function (num1, num2) {
    let ans = [];
    let carry = 0;

    for (let i = 0; i < num1.length || i < num2.length; ++i) {
        let digit1 = i < num1.length ? num1[i] : 0;
        let digit2 = i < num2.length ? num2[i] : 0;

        let sum = digit1 + digit2 + carry;
        carry = Math.floor(sum / 10);
        ans.push(sum % 10);
    }

    if (carry) {
        ans.push(carry);
    }
    return ans;
};

let multiplyOneDigit = function (firstNumber, secondNumberDigit, numZeros) {
    let currentResult = [];
    for (let i = 0; i < numZeros; ++i) {
        currentResult.push(0);
    }

    let carry = 0;

    for (let i = 0; i < firstNumber.length; ++i) {
        let multiplication = Number(secondNumberDigit) * Number(firstNumber[i]) + carry;
        carry = Math.floor(multiplication / 10);
        currentResult.push(multiplication % 10);
    }

    if (carry) {
        currentResult.push(carry);
    }
    return currentResult;
};

let multiply = function (num1, num2) {
    if (num1 === "0" || num2 === "0") {
        return "0";
    }

    let firstNumber = [...num1];
    let secondNumber = [...num2];

    firstNumber.reverse();
    secondNumber.reverse();

    let N = firstNumber.length + secondNumber.length;
    let ans = new Array(N).fill(0);

    for (let i = 0; i < secondNumber.length; ++i) {
        ans = addStrings(
            multiplyOneDigit(firstNumber, secondNumber[i], i),
            ans,
        );
    }

    if (ans[ans.length - 1] === 0) {
        ans.pop();
    }

    ans.reverse();
    return ans.join("");
};

🪙 1429 вопроса вопроса на Frontend разработчика

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 44. Wildcard Matching

Дана входная строка (s) и шаблон (p), реализуйте сопоставление с шаблоном с поддержкой символов '?' и '*' где:

'?' соответствует любому одиночному символу.
'*' соответствует любой последовательности символов (включая пустую последовательность).
Сопоставление должно покрывать всю входную строку (не частично).

Пример:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

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

1️⃣Очистите входные данные, заменив несколько звездочек подряд одной звездочкой: p = remove_duplicate_stars(p).
Инициируйте хеш-карту для мемоизации dp.
Верните вспомогательную функцию с очищенным входом: helper(s, p).

2️⃣Функция helper(s, p):
Если пара (s, p) уже известна и сохранена в dp, верните значение.
Если строки равны (p == s) или шаблон соответствует любой строке (p == '*'), добавьте dp[(s, p)] = True.
В противном случае, если p пусто или s пусто, добавьте dp[(s, p)] = False.
Если текущие символы совпадают (p[0] == s[0] или p[0] == '?'), то сравните следующие и добавьте dp[(s, p)] = helper(s[1:], p[1:]).

3️⃣Если текущий символ шаблона - звездочка (p[0] == '*'), то возможны две ситуации: звездочка не соответствует никаким символам, и звездочка соответствует одному или нескольким символам: dp[(s, p)] = helper(s, p[1:]) или helper(s[1:], p).
Если p[0] != s[0], тогда добавьте dp[(s, p)] = False.
Когда значение вычислено, верните его: dp[(s, p)].

😎 Решение:

var isMatch = function (s, p) {
    var dp = {};
    var remove_duplicate_stars = function (p) {
        var new_string = "";
        for (var c of p) {
            if (new_string.length == 0 || c != "*") new_string += c;
            else if (new_string[new_string.length - 1] != "*") new_string += c;
        }
        return new_string;
    };
    var helper = function (si, pi) {
        var key = si + "," + pi;
        if (key in dp) return dp[key];
        if (pi == p.length) dp[key] = si == s.length;
        else if (si == s.length) dp[key] = pi + 1 == p.length && p[pi] == "*";
        else if (p[pi] == s[si] || p[pi] == "?")
            dp[key] = helper(si + 1, pi + 1);
        else if (p[pi] == "*")
            dp[key] = helper(si, pi + 1) || helper(si + 1, pi);
        else dp[key] = false;
        return dp[key];
    };
    p = remove_duplicate_stars(p);
    return helper(0, 0);
};

🪙 1429 вопроса вопроса на Frontend разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 45. Jump Game II

Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0].

Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где:

0 <= j <= nums[i] и
i + j < n
Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1].

Пример:

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

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

1️⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0.

2️⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]).

3️⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2.

😎 Решение:

var jump = function (nums) {
    let answer = 0,
        n = nums.length;
    let curEnd = 0,
        curFar = 0;
    for (let i = 0; i < n - 1; ++i) {
        curFar = Math.max(curFar, i + nums[i]);
        if (i === curEnd) {
            ++answer;
            curEnd = curFar;
        }
    }
    return answer;
};

🪙 1429 вопроса вопроса на Frontend разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 46. Permutations

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

Пример:

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

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

1️⃣Если длина curr равна длине nums, добавьте копию curr в ans и вернитесь.

2️⃣Итерируйтесь по nums. Для каждого num, если num не в curr, выполните следующее:
Добавьте num в curr и вызовите backtrack(curr), затем удалите num из curr.

3️⃣Вызовите backtrack с изначально пустым curr.
Верните ans.

😎 Решение:

var permute = function (nums) {
    var ans = [];
    var backtrack = function (curr) {
        if (curr.length === nums.length) {
            ans.push([...curr]);
            return;
        }
        for (var num of nums) {
            if (!curr.includes(num)) {
                curr.push(num);
                backtrack(curr);
                curr.pop();
            }
        }
    };
    backtrack([]);
    return ans;
};

🪙 1429 вопроса вопроса на Frontend разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 47. Permutations II

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

Пример:

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

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

1️⃣Для реализации алгоритма сначала определим функцию под названием backtrack(comb, counter), которая генерирует все перестановки, начиная с текущей комбинации (comb) и оставшихся чисел (counter).

2️⃣После реализации функции достаточно вызвать её с начальной пустой комбинацией и хеш-таблицей, построенной из входного массива, чтобы решить задачу.

3️⃣Это позволяет эффективно и систематически исследовать все возможные уникальные перестановки, учитывая дубликаты в исходном наборе чисел.

😎 Решение:

var permuteUnique = function (nums) {
    let results = [];
    let counter = {};
    for (let num of nums) {
        if (!(num in counter)) counter[num] = 0;
        counter[num]++;
    }
    function backtrack(comb, N) {
        if (comb.length === N) {
            results.push([...comb]);
            return;
        }
        for (let num in counter) {
            if (counter[num] === 0) continue;
            comb.push(parseInt(num));
            counter[num]--;
            backtrack(comb, N);
            counter[num]++;
            comb.pop();
        }
    }
    backtrack([], nums.length);
    return results;
};

🪙 1429 вопроса вопроса на Frontend разработчика

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 48. Rotate Image

Вам дана квадратная матрица размером n x n, представляющая изображение. Поверните изображение на 90 градусов по часовой стрелке.

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

Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

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

1️⃣Самым элегантным решением для поворота матрицы является первоначальное транспонирование матрицы вокруг главной диагонали.

2️⃣После транспонирования следует выполнить отражение матрицы слева направо.

3️⃣Эти операции в линейной алгебре называются транспонированием и отражением.

😎 Решение:

var rotate = function (matrix) {
    const n = matrix.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n / 2; j++) {
            [matrix[i][j], matrix[i][n - 1 - j]] = [
                matrix[i][n - 1 - j],
                matrix[i][j],
            ];
        }
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 49. Group Anagrams

Дан массив строк strs. Сгруппируйте анаграммы вместе. Вы можете вернуть ответ в любом порядке.

Анаграмма — это слово или фраза, сформированная путем перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

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

1️⃣Поддерживайте карту ans: {String -> List}, где каждый ключ K — это отсортированная строка, а каждое значение — это список строк из исходного ввода, которые при сортировке равны K.

2️⃣В Java ключ будет храниться как строка, например, code. В Python ключ будет храниться как хешируемый кортеж, например, ('c', 'o', 'd', 'e').

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

😎 Решение:

var groupAnagrams = function (strs) {
    let map = new Map();
    for (let str of strs) {
        let chars = Array.from(str);
        chars.sort();
        let key = chars.join("");
        if (!map.has(key)) map.set(key, []);
        map.get(key).push(str);
    }
    return Array.from(map.values());
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 50. Pow(x, n)

Реализуйте функцию pow(x, n), которая вычисляет x, возведенное в степень n (то есть x^n).

Пример:

Input: x = 2.00000, n = 10
Output: 1024.00000

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

1️⃣Создайте метод binaryExp, который принимает параметры x и n.
Если n равно 0, мы возвращаем 1.
Если n отрицательное, вычисляем результат, как если бы n было положительным, и возвращаем обратное значение, то есть 1 / binaryExp(x, -n). При этом -n может выйти за пределы диапазона целых чисел, поэтому n должно быть 64-битной целочисленной переменной.

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

3️⃣Вызовите метод binaryExp(x, n) и верните результат.

😎 Решение:

function binaryExp(x, n) {
    if (n === 0) {
        return 1;
    }
    if (n < 0) {
        return 1 / binaryExp(x, -1 * n);
    }
    if (n % 2 === 1) {
        return x * binaryExp(x * x, (n - 1) / 2);
    } else {
        return binaryExp(x * x, n / 2);
    }
}

var myPow = function (x, n) {
    return binaryExp(x, n);
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 51. N-Queens

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

Для заданного целого числа n верните все различные решения этой задачи. Ответ можно предоставить в любом порядке.

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

Пример:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

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

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

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

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

😎 Решение:

var solveNQueens = function (n) {
    const solutions = [];
    const emptyBoard = Array.from({ length: n }, () => Array(n).fill("."));
    const createBoard = (state) => {
        const board = [];
        for (let row = 0; row < n; row++) {
            board.push(state[row].join(""));
        }
        return board;
    };
    const backtrack = (row, diagonals, antiDiagonals, cols, state) => {
        if (row === n) {
            solutions.push(createBoard(state));
            return;
        }
        for (let col = 0; col < n; col++) {
            const currDiagonal = row - col;
            const currAntiDiagonal = row + col;
            if (
                cols.has(col) ||
                diagonals.has(currDiagonal) ||
                antiDiagonals.has(currAntiDiagonal)
            ) {
                continue;
            }
            cols.add(col);
            diagonals.add(currDiagonal);
            antiDiagonals.add(currAntiDiagonal);
            state[row][col] = "Q";
            backtrack(row + 1, diagonals, antiDiagonals, cols, state);
            cols.delete(col);
            diagonals.delete(currDiagonal);
            antiDiagonals.delete(currAntiDiagonal);
            state[row][col] = ".";
        }
    };
    backtrack(0, new Set(), new Set(), new Set(), emptyBoard);
    return solutions;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 52. N-Queens II

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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 53. Maximum Subarray

Дан массив целых чисел 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;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 55. Jump Game

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

Верните true, если вы можете достичь последнего индекса, или false в противном случае.

Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

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

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

2️⃣Модификация алгоритма обратного трассирования:
Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда возвращается True/False.

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

😎 Решение:

let memo;
const canJumpFromPosition = (position, nums) => {
    if (memo[position] != "UNKNOWN") {
        return memo[position] == "GOOD";
    }
    let furthestJump = Math.min(position + nums[position], nums.length - 1);
    for (
        let nextPosition = position + 1;
        nextPosition <= furthestJump;
        nextPosition++
    ) {
        if (canJumpFromPosition(nextPosition, nums)) {
            memo[position] = "GOOD";
            return true;
        }
    }
    memo[position] = "BAD";
    return false;
};
var canJump = function (nums) {
    memo = new Array(nums.length).fill("UNKNOWN");
    memo[memo.length - 1] = "GOOD";
    return canJumpFromPosition(0, nums);
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 56. Merge Intervals

Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.

Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

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

3️⃣Объединение интервалов внутри компонент:
Наконец, мы рассматриваем каждую связную компоненту, объединяя все её интервалы, создавая новый интервал с началом, равным минимальному началу среди всех интервалов в компоненте, и концом, равным максимальному концу.

Решение:

var overlap = function (a, b) {
    return a[0] <= b[1] && b[0] <= a[1];
};
var buildGraph = function (intervals) {
    var graph = new Map();
    for (var i = 0; i < intervals.length; i++) {
        for (var j = i + 1; j < intervals.length; j++) {
            if (overlap(intervals[i], intervals[j])) {
                if (graph.has(intervals[i])) {
                    graph.get(intervals[i]).push(intervals[j]);
                } else {
                    graph.set(intervals[i], [intervals[j]]);
                }
                if (graph.has(intervals[j])) {
                    graph.get(intervals[j]).push(intervals[i]);
                } else {
                    graph.set(intervals[j], [intervals[i]]);
                }
            }
        }
    }
    return graph;
};
var mergeNodes = function (nodes) {
    var minStart = Infinity;
    var maxEnd = -Infinity;
    for (var node of nodes) {
        minStart = Math.min(minStart, node[0]);
        maxEnd = Math.max(maxEnd, node[1]);
    }
    return [minStart, maxEnd];
};
var markComponentDFS = function (
    start,
    graph,
    nodesInComp,
    compNumber,
    visited,
) {
    var stack = [start];
    while (stack.length) {
        var node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            if (nodesInComp[compNumber]) {
                nodesInComp[compNumber].push(node);
            } else {
                nodesInComp[compNumber] = [node];
            }
            if (graph.has(node)) {
                for (var child of graph.get(node)) {
                    stack.push(child);
                }
            }
        }
    }
};
var merge = function (intervals) {
    var graph = buildGraph(intervals);
    var nodesInComp = {};
    var visited = new Set();
    var compNumber = 0;
    for (var interval of intervals) {
        if (!visited.has(interval)) {
            markComponentDFS(interval, graph, nodesInComp, compNumber, visited);
            compNumber++;
        }
    }
    var merged = [];
    for (var comp = 0; comp < compNumber; comp++) {
        merged.push(mergeNodes(nodesInComp[comp]));
    }
    return merged;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 57. Insert Interval

Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.

Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).

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

Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

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

1️⃣ Инициализация переменных:
Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата.

2️⃣Обработка случаев без перекрытия и с перекрытием:
В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему.
В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один.

3️⃣Обработка интервалов после вставки:
Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.
Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом.

😎 Решение:

var insert = function (intervals, newInterval) {
    let n = intervals.length,
        i = 0,
        res = [];

    while (i < n && intervals[i][1] < newInterval[0]) {
        res.push(intervals[i]);
        i++;
    }

    while (i < n && newInterval[1] >= intervals[i][0]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.push(newInterval);

    while (i < n) {
        res.push(intervals[i]);
        i++;
    }

    return res;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 58. Length of Last Word

Дана строка 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;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 59. Spiral Matrix II

Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке.

Пример:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

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

1️⃣Определение направлений движения:
Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1).

2️⃣Перемещение по матрице:
Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений.

3️⃣Изменение направления:
Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4.

😎 Решение:

var generateMatrix = function (n) {
    const result = new Array(n).fill(0).map(() => new Array(n).fill(0));
    const dirs = [
        [0, 1],
        [1, 0],
        [0, -1],
        [-1, 0],
    ];
    let d = 0;
    let row = 0;
    let col = 0;
    let cnt = 1;
    while (cnt <= n * n) {
        result[row][col] = cnt++;
        let newRow = (row + (dirs[d][0] % n) + n) % n;
        let newCol = (col + (dirs[d][1] % n) + n) % n;
        if (result[newRow][newCol] != 0) d = (d + 1) % 4;
        row += dirs[d][0];
        col += dirs[d][1];
    }
    return result;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 60. Permutation Sequence

Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок.

Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Дано n и k, верните k-ю перестановку последовательности.

Пример:

Input: n = 3, k = 3
Output: "213"

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

1️⃣Сгенерируйте входной массив nums чисел от 1 до N.

2️⃣Вычислите все факториальные основы от 0 до (N−1)!.

3️⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1).

Используйте коэффициенты факториалов для построения перестановки.

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

😎 Решение:

var getPermutation = function (n, k) {
    let factorials = new Array(n);
    let nums = ["1"];
    factorials[0] = 1;
    for (let i = 1; i < n; ++i) {
        factorials[i] = factorials[i - 1] * i;
        nums.push((i + 1).toString());
    }
    --k;
    let output = "";
    for (let i = n - 1; i > -1; --i) {
        let idx = Math.floor(k / factorials[i]);
        k -= idx * factorials[i];
        output += nums[idx];
        nums.splice(idx, 1);
    }
    return output;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 61. Rotate List

Дан указатель на начало связного списка, поверните список вправо на k позиций.

Пример:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

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

1️⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n.

2️⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n).

3️⃣Разорвите кольцо (new_tail.next = None) и верните new_head.

😎 Решение:

var rotateRight = function (head, k) {
    if (head == null) return null;
    if (head.next == null) return head;

    let old_tail = head;
    let n;
    for (n = 1; old_tail.next != null; n++) old_tail = old_tail.next;
    old_tail.next = head;

    let new_tail = head;
    for (let i = 0; i < n - (k % n) - 1; i++) new_tail = new_tail.next;
    let new_head = new_tail.next;

    new_tail.next = null;
    return new_head;
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 62. Unique Paths

На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

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

Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9.

Пример:

Input: m = 3, n = 7
Output: 28

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

1️⃣Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами.

2️⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1].

3️⃣Вернуть d[m - 1][n - 1].

😎 Решение:

var uniquePaths = function (m, n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 63. Unique Paths II

Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

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

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

Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9.

Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

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

1️⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем.

2️⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца.

3️⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях.

😎 Решение:

var uniquePathsWithObstacles = function (obstacleGrid) {
    let R = obstacleGrid.length;
    let C = obstacleGrid[0].length;
    if (obstacleGrid[0][0] == 1) {
        return 0;
    }
    obstacleGrid[0][0] = 1;
    for (let i = 1; i < R; i++) {
        obstacleGrid[i][0] = obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1 ? 1 : 0;
    }
    for (let i = 1; i < C; i++) {
        obstacleGrid[0][i] = obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1 ? 1 : 0;
    }
    for (let i = 1; i < R; i++) {
        for (let j = 1; j < C; j++) {
            if (obstacleGrid[i][j] == 0) {
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            } else {
                obstacleGrid[i][j] = 0;
            }
        }
    }
    return obstacleGrid[R - 1][C - 1];
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 64. Minimum Path Sum

На сетке размером m на n, заполненной неотрицательными числами, найдите путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути.

Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени.

Пример:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

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

1️⃣Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего элемента. Начинаем с инициализации самого правого нижнего элемента dp как последнего элемента заданной матрицы.

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

3️⃣Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий.

😎 Решение:

var minPathSum = function (grid) {
    let dp = new Array(grid.length)
        .fill()
        .map(() => new Array(grid[0].length).fill(0));
    for (let i = grid.length - 1; i >= 0; i--) {
        for (let j = grid[0].length - 1; j >= 0; j--) {
            if (i === grid.length - 1 && j !== grid[0].length - 1)
                dp[i][j] = grid[i][j] + dp[i][j + 1];
            else if (j === grid[0].length - 1 && i !== grid.length - 1)
                dp[i][j] = grid[i][j] + dp[i + 1][j];
            else if (j !== grid[0].length - 1 && i !== grid.length - 1)
                dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
            else dp[i][j] = grid[i][j];
        }
    }
    return dp[0][0];
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых