JavaScript | LeetCode

Задача: 423. Reconstruct Original Digits from English
Сложность: medium

Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания.

Пример:

Input: s = "owoztneoer"
Output: "012"

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

1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа.

2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры.

3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат.

😎 Решение:

class Solution {
    originalDigits(s) {
        const count = new Array(26).fill(0);
        for (const letter of s) {
            count[letter.charCodeAt(0) - 97]++;
        }

        const out = new Array(10).fill(0);
        out[0] = count[25];
        out[2] = count[22];
        out[4] = count[20];
        out[6] = count[23];
        out[8] = count[6];
        out[3] = count[7] - out[8];
        out[5] = count[5] - out[4];
        out[7] = count[18] - out[6];
        out[9] = count[8] - out[5] - out[6] - out[8];
        out[1] = count[13] - out[7] - 2 * out[9];

        const output = [];
        for (let i = 0; i < 10; i++) {
            for (let j = 0; j < out[i]; j++) {
                output.push(i);
            }
        }
        return output.join('');
    }
}

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

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

😎 Решение:

var minMalwareSpread = function(graph, initial) {
    const n = graph.length;
    const visited = new Set();
    const components = [];

    const dfs = (node) => {
        const stack = [node];
        const component = new Set();
        while (stack.length) {
            const u = stack.pop();
            if (!visited.has(u)) {
                visited.add(u);
                component.add(u);
                for (let v = 0; v < n; v++) {
                    if (graph[u][v] === 1 && !visited.has(v)) {
                        stack.push(v);
                    }
                }
            }
        }
        components.push(component);
    };

    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
        }
    }

    const infectedInComponent = new Array(components.length).fill(0);
    const nodeToComponent = new Array(n).fill(-1);

    components.forEach((component, idx) => {
        component.forEach(node => {
            nodeToComponent[node] = idx;
            if (initial.includes(node)) {
                infectedInComponent[idx]++;
            }
        });
    });

    let minInfected = Infinity;
    let resultNode = Math.min(...initial);

    for (const node of initial) {
        const componentIdx = nodeToComponent[node];
        if (infectedInComponent[componentIdx] === 1) {
            const componentSize = components[componentIdx].size;
            if (componentSize < minInfected || (componentSize === minInfected && node < resultNode)) {
                minInfected = componentSize;
                resultNode = node;
            }
        }
    }

    return resultNode;
};

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

Задача: 1049. Last Stone Weight II
Сложность: medium

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

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

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

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

😎 Решение:

function lastStoneWeightII(stones) {
    const totalSum = stones.reduce((a, b) => a + b, 0);
    const halfSum = Math.floor(totalSum / 2);
    const dp = Array(halfSum + 1).fill(0);

    for (let stone of stones) {
        for (let j = halfSum; j >= stone; j--) {
            dp[j] = Math.max(dp[j], dp[j - stone] + stone);
        }
    }

    return totalSum - 2 * dp[halfSum];
}

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

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

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    return Math.max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reverse(), secondLen, firstLen));
};

function maxSumNonOverlap(nums, firstLen, secondLen) {
    const n = nums.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    
    const maxFirst = new Array(n).fill(0);
    for (let i = firstLen - 1; i < n; i++) {
        maxFirst[i] = Math.max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
    }
    
    const maxSecond = new Array(n).fill(0);
    for (let i = secondLen - 1; i < n; i++) {
        maxSecond[i] = Math.max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
    }
    
    let maxSum = 0;
    for (let i = firstLen + secondLen - 1; i < n; i++) {
        maxSum = Math.max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
    }
    
    return maxSum;
}

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

Задача: 1278. Palindrome Partitioning III
Сложность: hard

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

Пример:

Input: s = "abc", k = 2
Output: 1

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

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

2⃣Используйте еще одно динамическое программирование для разбиения строки на k палиндромических подстрок с минимальным количеством изменений.

3⃣Верните минимальное количество изменений, найденное во втором шаге.

😎 Решение:

var minChangesToMakePalindrome = function(s, k) {
    const n = s.length;

    const minChangeToPalindrome = (i, j) => {
        let changes = 0;
        while (i < j) {
            if (s[i] !== s[j]) {
                changes++;
            }
            i++;
            j--;
        }
        return changes;
    };

    const dp1 = Array.from({ length: n }, () => Array(n).fill(0));
    for (let length = 1; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            let j = i + length - 1;
            dp1[i][j] = minChangeToPalindrome(i, j);
        }
    }

    const dp2 = Array.from({ length: n + 1 }, () => Array(k + 1).fill(Infinity));
    dp2[0][0] = 0;

    for (let i = 1; i <= n; i++) {
        for (let kk = 1; kk <= k; kk++) {
            for (let j = 0; j < i; j++) {
                dp2[i][kk] = Math.min(dp2[i][kk], dp2[j][kk - 1] + dp1[j][i - 1]);
            }
        }
    }

    return dp2[n][k];
};

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

Задача: 901. Online Stock Span
Сложность: medium

Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

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

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

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:

var StockSpanner = function() {
    this.stack = [];
};

StockSpanner.prototype.next = function(price) {
    let span = 1;
    while (this.stack.length && this.stack[this.stack.length - 1][0] <= price) {
        span += this.stack.pop()[1];
    }
    this.stack.push([price, span]);
    return span;
};

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

Задача: 470. Implement Rand10() Using Rand7()
Сложность: medium

Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7]. Напишите функцию rand10(), которая генерирует случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и не должны вызывать другие API. Пожалуйста, не используйте встроенные в язык функции для генерации случайных чисел.

Каждый тестовый случай будет содержать один внутренний аргумент n, который указывает количество вызовов вашей реализованной функции rand10() во время тестирования. Обратите внимание, что это не аргумент, передаваемый в rand10().

Пример:

Input: n = 1
Output: [2]

😎 Решение:

var rand10 = function() {
    let row, col, idx;
    do {
        row = rand7();
        col = rand7();
        idx = col + (row - 1) * 7;
    } while (idx > 40);
    return 1 + (idx - 1) % 10;
};

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

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

😎 Решение:

class DSU {
    constructor(N) {
        this.parent = Array.from({ length: N }, (_, i) => i);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        this.parent[this.find(x)] = this.find(y);
    }
}

var regionsBySlashes = function(grid) {
    const N = grid.length;
    const dsu = new DSU(4 * N * N);

    for (let r = 0; r < N; r++) {
        for (let c = 0; c < N; c++) {
            const root = 4 * (r * N + c);
            const val = grid[r][c];
            
            if (val !== '\\') {
                dsu.union(root + 0, root + 1);
                dsu.union(root + 2, root + 3);
            }
            if (val !== '/') {
                dsu.union(root + 0, root + 2);
                dsu.union(root + 1, root + 3);
            }

            if (r + 1 < N) {
                dsu.union(root + 3, (root + 4 * N) + 0);
            }
            if (r - 1 >= 0) {
                dsu.union(root + 0, (root - 4 * N) + 3);
            }
            if (c + 1 < N) {
                dsu.union(root + 2, (root + 4) + 1);
            }
            if (c - 1 >= 0) {
                dsu.union(root + 1, (root - 4) + 2);
            }
        }
    }

    let ans = 0;
    for (let x = 0; x < 4 * N * N; x++) {
        if (dsu.find(x) === x) {
            ans++;
        }
    }

    return ans;
};

овых

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

Задача: 722. Remove Comments
Сложность: medium

Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными.
Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.

Пример:

Input: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

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

1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.

2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.

3⃣После обработки всех строк добавьте непустые строки из buffer в результат.

😎 Решение:

var removeComments = function(source) {
    let inBlock = false;
    let buffer = [];
    let result = [];
    
    for (let line of source) {
        let i = 0;
        if (!inBlock) buffer = [];
        while (i < line.length) {
            if (!inBlock && i + 1 < line.length && line[i] === '/' && line[i + 1] === '*') {
                inBlock = true;
                i += 1;
            } else if (inBlock && i + 1 < line.length && line[i] === '*' && line[i + 1] === '/') {
                inBlock = false;
                i += 1;
            } else if (!inBlock && i + 1 < line.length && line[i] === '/' && line[i + 1] === '/') {
                break;
            } else if (!inBlock) {
                buffer.push(line[i]);
            }
            i += 1;
        }
        if (buffer.length && !inBlock) {
            result.push(buffer.join(''));
        }
    }
    return result;
};

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

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

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

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

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

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

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

1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

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

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

😎 Решение:

var isPossible = function(nums) {
    let freq = new Map();
    let need = new Map();

    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    for (let num of nums) {
        if (freq.get(num) === 0) {
            continue;
        }

        if (need.get(num) > 0) {
            need.set(num, need.get(num) - 1);
            need.set(num + 1, (need.get(num + 1) || 0) + 1);
        } else if (freq.get(num + 1) > 0 && freq.get(num + 2) > 0) {
            freq.set(num + 1, freq.get(num + 1) - 1);
            freq.set(num + 2, freq.get(num + 2) - 1);
            need.set(num + 3, (need.get(num + 3) || 0) + 1);
        } else {
            return false;
        }
        freq.set(num, freq.get(num) - 1);
    }

    return true;
};

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

Задача: 1428. Leftmost Column with at Least a One
Сложность: medium

Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.

Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.

Для пользовательского тестирования вводом будет вся бинарная матрица mat. Вы не будете иметь прямого доступа к бинарной матрице.

Пример:

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

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

1⃣Инициализируйте указатели на текущую строку и столбец, начиная с верхнего правого угла матрицы.

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

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

😎 Решение:

var leftMostColumnWithOne = function(binaryMatrix) {
    const [rows, cols] = binaryMatrix.dimensions();
    let currentRow = 0, currentCol = cols - 1;
    
    while (currentRow < rows && currentCol >= 0) {
        if (binaryMatrix.get(currentRow, currentCol) === 0) {
            currentRow++;
        } else {
            currentCol--;
        }
    }
    
    return (currentCol === cols - 1) ? -1 : currentCol + 1;
};

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

Задача: 984. String Without AAA or BBB
Сложность: medium

Даны два целых числа a и b, верните любую строку s, такую что:

s имеет длину a + b и содержит ровно a букв 'a' и ровно b букв 'b'.
Подстрока 'aaa' не встречается в s.
Подстрока 'bbb' не встречается в s.

Пример:

Input: a = 4, b = 1
Output: "aabaa"

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

1⃣Инициализация переменных:
Завести пустую строку s и переменные a_count и b_count для отслеживания оставшихся 'a' и 'b' соответственно.

2⃣Создание строки:
Добавляйте символы в строку s, попеременно добавляя 'a' и 'b', чтобы избегать подстрок 'aaa' и 'bbb'.
Если в строке подряд уже два символа 'a' и осталось ещё 'b', добавьте 'b' и наоборот.
Если оба символа возможны для добавления, выбирайте тот, которого осталось больше.

3⃣Добавление оставшихся символов:
После основной логики добавления символов, добавьте оставшиеся 'a' или 'b' в конец строки, если они остались.

😎 Решение:

var strWithout3a3b = function(a, b) {
    let result = [];
    
    while (a > 0 || b > 0) {
        if (result.length >= 2 && result[result.length - 1] === result[result.length - 2]) {
            if (result[result.length - 1] === 'a') {
                result.push('b');
                b--;
            } else {
                result.push('a');
                a--;
            }
        } else {
            if (a >= b) {
                result.push('a');
                a--;
            } else {
                result.push('b');
                b--;
            }
        }
    }
    
    return result.join('');
};

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

Задача: 246. Strobogrammatic Number
Сложность: easy

Дана строка num, представляющая собой целое число. Верните true, если num является стробограмматическим числом.
Стробограмматическое число — это число, которое выглядит одинаково при повороте на 180 градусов (если посмотреть вверх ногами).

Пример:

Input: num = "69"
Output: true

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

1️⃣Создайте новую строку, перебирая оригинальную строку num в обратном порядке. Для каждого символа проверьте, является ли он допустимым для поворота (0, 1, 6, 8, 9). Если символ недопустим (2, 3, 4, 5, 7), немедленно верните false.

2️⃣Для каждого допустимого символа добавьте его соответствующее значение после поворота (0 ⟶ 0, 1 ⟶ 1, 6 ⟶ 9, 8 ⟶ 8, 9 ⟶ 6) в новую строку.

3️⃣Сравните полученную строку с исходной строкой num. Если они равны, верните true, в противном случае верните false.

😎 Решение:

class Solution {
    isStrobogrammatic(num) {
        let rotated = "";
        for (let i = num.length - 1; i >= 0; i--) {
            const c = num[i];
            if (c === '0' || c === '1' || c === '8') {
                rotated += c;
            } else if (c === '6') {
                rotated += '9';
            } else if (c === '9') {
                rotated += '6';
            } else {
                return false;
            }
        }
        return num === rotated;
    }
}

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

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

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

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
    arraysIntersection(arr1, arr2, arr3) {
        const counter = new Map();
        
        for (const e of arr1) counter.set(e, (counter.get(e) || 0) + 1);
        for (const e of arr2) counter.set(e, (counter.get(e) || 0) + 1);
        for (const e of arr3) counter.set(e, (counter.get(e) || 0) + 1);

        const ans = [];
        for (const [key, value] of counter) {
            if (value === 3) ans.push(key);
        }

        return ans;
    }
}

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

Задача: 729. My Calendar I
Сложность: medium

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

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

1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий.

2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.

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

😎 Решение:

class MyCalendar {
    constructor() {
        this.events = [];
    }

    book(start, end) {
        for (let [s, e] of this.events) {
            if (start < e && end > s) {
                return false;
            }
        }
        this.events.push([start, end]);
        return true;
    }
}

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

Задача: 167. Two Sum II - Input Array Is Sorted
Сложность: medium

Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length.
Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2].
Тесты генерируются таким образом, что существует ровно одно решение. Нельзя использовать один и тот же элемент дважды.
Ваше решение должно использовать только константное дополнительное пространство.

Пример:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

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

1️⃣Инициализация указателей:
Используйте два указателя: один (left) начинается с начала массива, а другой (right) - с конца.

2️⃣Поиск решения:
Сравните сумму элементов, на которые указывают left и right, с целевым значением target.
Если сумма равна target, верните индексы этих элементов как решение.
Если сумма меньше target, увеличьте left (так как массив отсортирован и увеличение left увеличивает сумму).
Если сумма больше target, уменьшите right (чтобы уменьшить сумму).

3️⃣Продолжение до нахождения решения:
Перемещайте указатели left и right, повторяя сравнение, пока не будет найдено решение.
Учитывая, что задача гарантирует существование ровно одного решения, этот метод всегда найдет ответ.

😎 Решение:

var twoSum = function (numbers, target) {
    let low = 0;
    let high = numbers.length - 1;
    while (low < high) {
        let sum = numbers[low] + numbers[high];

        if (sum == target) {
            return [low + 1, high + 1];
        } else if (sum < target) {
            low++;
        } else {
            high--;
        }
    }
    return [-1, -1];
};

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

Задача: 1028. Recover a Tree From Preorder Traversal
Сложность: hard

Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

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

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

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

😎 Решение:

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

class Solution {
    recoverFromPreorder(S) {
        const stack = [];
        let i = 0;
        
        while (i < S.length) {
            let level = 0;
            while (i < S.length && S[i] === '-') {
                level++;
                i++;
            }
            
            let value = 0;
            while (i < S.length && !isNaN(S[i])) {
                value = value * 10 + parseInt(S[i], 10);
                i++;
            }
            
            const node = new TreeNode(value);
            if (level === stack.length) {
                if (stack.length > 0) {
                    stack[stack.length - 1].left = node;
                }
            } else {
                while (level !== stack.length) {
                    stack.pop();
                }
                stack[stack.length - 1].right = node;
            }
            stack.push(node);
        }
        
        while (stack.length > 1) {
            stack.pop();
        }
        
        return stack[0];
    }
}

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

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, 
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

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

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

class Solution {
    maxProduct(nums) {
        let biggest = 0;
        let secondBiggest = 0;
        for (let num of nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else if (num > secondBiggest) {
                secondBiggest = num;
            }
        }
        return (biggest - 1) * (secondBiggest - 1);
    }
}

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

Задача: 1496. Path Crossing
Сложность: easy

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных:
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями.
Инициализировать множество visited с начальной точкой (0, 0). Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path: Для каждого символа c в path получить значения (dx, dy) из moves[c]. Обновить координаты: добавить dx к x и dy к y. Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true. Добавить текущую точку (x, y) в visited.

3⃣Возврат результата:
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

var isPathCrossing = function(path) {
    const moves = {
        'N': [0, 1], 'S': [0, -1],
        'E': [1, 0], 'W': [-1, 0]
    };
    const visited = new Set(['0,0']);
    let x = 0, y = 0;

    for (const c of path) {
        const [dx, dy] = moves[c];
        x += dx;
        y += dy;
        const point = `${x},${y}`;
        if (visited.has(point)) {
            return true;
        }
        visited.add(point);
    }

    return false;
};

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

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

😎 Решение:

var flipLights = function(n, m) {
    let seen = new Set();
    n = Math.min(n, 6);
    let shift = Math.max(0, 6 - n);
    for (let cand = 0; cand < 16; ++cand) {
        let bcount = cand.toString(2).split('1').length - 1;
        if (bcount % 2 == m % 2 && bcount <= m) {
            let lights = 0;
            if ((cand >> 0) & 1) lights ^= 0b111111 >> shift;
            if ((cand >> 1) & 1) lights ^= 0b010101 >> shift;
            if ((cand >> 2) & 1) lights ^= 0b101010 >> shift;
            if ((cand >> 3) & 1) lights ^= 0b100100 >> shift;
            seen.add(lights);
        }
    }
    return seen.size;
}

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