JavaScript | LeetCode

Задача: 1054. Distant Barcodes
Сложность: medium

На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.

Пример:

Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

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

1⃣Подсчитай частоту каждого штрих-кода.
Помести все штрих-коды в максимальную кучу на основе их частоты.

2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми.

3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.

😎 Решение:

function rearrangeBarcodes(barcodes) {
    const count = new Map();
    for (const barcode of barcodes) {
        count.set(barcode, (count.get(barcode) || 0) + 1);
    }

    const maxHeap = [];
    for (const [barcode, freq] of count) {
        maxHeap.push([-freq, barcode]);
    }
    maxHeap.sort((a, b) => a[0] - b[0]);

    const result = [];
    let prevFreq = 0;
    let prevBarcode = null;

    while (maxHeap.length) {
        const [freq, barcode] = maxHeap.pop();
        result.push(barcode);
        if (prevFreq < 0) {
            maxHeap.push([prevFreq, prevBarcode]);
            maxHeap.sort((a, b) => a[0] - b[0]);
        }
        prevFreq = freq + 1;
        prevBarcode = barcode;
    }

    return result;
}

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

Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium

Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.

Пример:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]

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

1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y).

2⃣Перемещение указателей:
Если 𝑓(𝑥,𝑦)=𝑧
f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x.

3⃣Повторяем шаги до тех пор, пока
𝑥≤1000 x≤1000 и 𝑦≥1y≥1.

😎 Решение:

class CustomFunction {
    f(x, y) {}
}

var findSolution = function(customfunction, z) {
    let result = [];
    let x = 1;
    let y = 1000;
    
    while (x <= 1000 && y >= 1) {
        let value = customfunction.f(x, y);
        if (value === z) {
            result.push([x, y]);
            x++;
        } else if (value < z) {
            x++;
        } else {
            y--;
        }
    }
    
    return result;
};

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

Задача: №19. Remove Nth Node From End of List
Сложность: medium

Дан связанный список и число n.
Нужно удалить n-й узел с конца и вернуть голову изменённого списка.

Пример:

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

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

1️⃣ Создаем фиктивный узел dummy, указывающий на head. Инициализируем два указателя — fast и slow на dummy.

2️⃣ Сдвигаем fast на n шагов вперёд.
Затем двигаем fast и slow одновременно, пока fast не дойдёт до конца списка.

3️⃣ В этот момент slow.next указывает на узел, который нужно удалить.
Обновляем slow.next, чтобы пропустить этот узел. Возвращаем dummy.next как новую голову.

😎 Решение:

var removeNthFromEnd = function (head, n) {
    const dummy = new ListNode(0, head);
    let fast = dummy, slow = dummy;

    while (n--) {
        fast = fast.next;
    }

    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
    }

    slow.next = slow.next.next;
    return dummy.next;
};

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

function assignBikes(workers, bikes) {
    const pairs = [];
    
    for (let i = 0; i < workers.length; i++) {
        for (let j = 0; j < bikes.length; j++) {
            const distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
            pairs.push([distance, i, j]);
        }
    }
    
    pairs.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[1] !== b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });
    
    const result = Array(workers.length).fill(-1);
    const bikeTaken = Array(bikes.length).fill(false);
    const workerAssigned = Array(workers.length).fill(false);
    
    for (const [distance, workerIdx, bikeIdx] of pairs) {
        if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
            result[workerIdx

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

🔥 Скрытые вакансии с удаленной работой для Frontend разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.

🔹 Frontend Jobs | Вакансии
🔹 Node.js Jobs | Вакансии

🔸 Все каналы с вакансиями

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

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

Пример:

Input: arr = ["un","iq","ue"]
Output: 4

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

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

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

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

😎 Решение:

var maxLength = function(arr) {
    const isUnique = s => new Set(s).size === s.length;

    const backtrack = (index, current) => {
        if (!isUnique(current)) return 0;
        let maxLength = current.length;
        for (let i = index; i < arr.length; i++) {
            maxLength = Math.max(maxLength, backtrack(i + 1, current + arr[i]));
        }
        return maxLength;
    };

    return backtrack(0, "");
};

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

Задача: 1510. Stone Game IV
Сложность: hard

Алиса и Боб поочередно играют в игру, причем Алиса начинает первой.

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

Кроме того, если игрок не может сделать ход, он/она проигрывает игру.

Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

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

1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях.

2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs.

3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True.

😎 Решение:

var winnerSquareGame = function(n) {
    const cache = new Map();
    cache.set(0, false);

    const dfs = (remain) => {
        if (cache.has(remain)) {
            return cache.get(remain);
        }
        const sqrtRoot = Math.floor(Math.sqrt(remain));
        for (let i = 1; i <= sqrtRoot; i++) {
            if (!dfs(remain - i * i)) {
                cache.set(remain, true);
                return true;
            }
        }
        cache.set(remain, false);
        return false;
    };

    return dfs(n);
};

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

Задача: 1086. High Five
Сложность: easy

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

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

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

2⃣Создайте список для хранения результата result. Переберите словарь и для каждого студента отсортируйте его оценки в порядке убывания, возьмите пять лучших оценок, вычислите их среднее значение (с целочисленным делением на 5) и добавьте пару [ID, topFiveAverage] в результат.

3⃣Отсортируйте список result по возрастанию ID студента и верните его.

😎 Решение:

var highFive = function(items) {
    const K = 5;
    items.sort((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return b[1] - a[1];
    });

    const solution = [];
    let i = 0;
    while (i < items.length) {
        const id = items[i][0];
        let sum = 0;
        for (let k = i; k < i + K; k++) {
            sum += items[k][1];
        }
        while (i < items.length && items[i][0] === id) {
            i++;
        }
        solution.push([id, Math.floor(sum / K)]);
    }
    return solution;
};

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

Задача: 1058. Minimize Rounding Error to Meet Target
Сложность: medium

Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби.

Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

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

1⃣Округли каждую цену вниз и вычисли текущую сумму округленных цен.
Найди разницу между целевой суммой и текущей суммой.

2⃣Определи количество округлений вверх, необходимых для достижения целевой суммы.
Если разница отрицательная или больше количества элементов в массиве, верни "-1".

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

😎 Решение:

function minimizeRoundingError(prices, target) {
    let floors = prices.map(p => Math.floor(parseFloat(p)));
    let totalFloor = floors.reduce((a, b) => a + b, 0);
    
    let difference = target - totalFloor;
    if (difference < 0 || difference > prices.length) {
        return "-1";
    }
    
    let roundingErrors = prices.map((p, i) => [Math.ceil(parseFloat(p)) - floors[i], parseFloat(p) - floors[i]]);
    roundingErrors.sort((a, b) => a[1] - b[1]);
    
    let roundingErrorSum = floors.reduce((sum, floor, i) => sum + (floor - parseFloat(prices[i])), 0);
    
    for (let i = 0; i < difference; i++) {
        roundingErrorSum += roundingErrors[i][1];
    }
    
    return roundingErrorSum.toFixed(3);
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

var crackSafe = function(n, k) {
    const seen = new Set();
    const result = [];

    const dfs = (node) => {
        for (let x = 0; x < k; x++) {
            const neighbor = node + x;
            if (!seen.has(neighbor)) {
                seen.add(neighbor);
                dfs(neighbor.slice(1));
                result.push(x);
            }
        }
    };

    const startNode = '0'.repeat(n - 1);
    dfs(startNode);
    return startNode + result.join('');
};

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

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium

Вам дан массив целых чисел nums.

За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.

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

Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

1⃣Инициализация: определите размер массива nums, если размер меньше или равен 4, верните 0. Отсортируйте массив nums и инициализируйте переменную minDiff очень большим числом.

2⃣Итерация по первым четырем элементам отсортированного массива: для каждого индекса left от 0 до 3 вычислите соответствующий правый индекс, разницу между элементами на этих индексах и обновите minDiff с минимальным значением.

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

😎 Решение:

var minDifference = function(nums) {
    const numsSize = nums.length
    
    if (numsSize <= 4) return 0
    
    nums.sort((a, b) => a - b)
    
    let minDiff = Infinity
    
    for (let left = 0; left < 4; left++) {
        const right = numsSize - 4 + left
        minDiff = Math.min(minDiff, nums[right] - nums[left])
    }
    
    return minDiff
}

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

Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium

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

Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

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

1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.

2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.

3⃣Вернуть первые j символов строки.

😎 Решение:

class Solution {
    removeDuplicates(s, k) {
        let counts = [];
        let sa = s.split('');
        let j = 0;
        
        for (let i = 0; i < sa.length; ++i, ++j) {
            sa[j] = sa[i];
            if (j === 0 || sa[j] !== sa[j - 1]) {
                counts.push(1);
            } else {
                let incremented = counts.pop() + 1;
                if (incremented === k) {
                    j -= k;
                } else {
                    counts.push(incremented);
                }
            }
        }
        return sa.slice(0, j).join('');
    }
}

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

Задача: 179. Largest Number
Сложность: medium

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

Пример:

Input: nums = [10,2]
Output: "210"

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

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

2️⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3️⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    largestNumber(nums) {
        const strNums = nums.map(String);
        strNums.sort((a, b) => (b + a).localeCompare(a + b));
        if (strNums[0] === "0") {
            return "0";
        }
        return strNums.join('');
    }
}

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

Задача: 1673. Find the Most Competitive Subsequence
Сложность: medium

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

Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива.

Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.

Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

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

1⃣Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность.

2⃣Переберите массив nums, выбирая наиболее конкурентоспособные элементы и добавляя их в очередь. Сравнивайте последний элемент в очереди с текущим элементом, удаляя из очереди более крупные элементы, если можно удалить больше элементов, чем необходимо для достижения размера k.

3⃣ В конце получите первые k элементов из очереди и создайте результирующий массив.

😎 Решение:

var mostCompetitive = function(nums, k) {
    let queue = [];
    let additionalCount = nums.length - k;
    
    for (let num of nums) {
        while (queue.length > 0 && queue[queue.length - 1] > num && additionalCount > 0) {
            queue.pop();
            additionalCount--;
        }
        queue.push(num);
    }
    
    return queue.slice(0, k);
};

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

Задача: 602. Friend Requests II: Who Has the Most Friends
Сложность: medium

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

Пример:

Input: 
RequestAccepted table:
+--------------+-------------+-------------+
| requester_id | accepter_id | accept_date |
+--------------+-------------+-------------+
| 1            | 2           | 2016/06/03  |
| 1            | 3           | 2016/06/08  |
| 2            | 3           | 2016/06/08  |
| 3            | 4           | 2016/06/09  |
+--------------+-------------+-------------+
Output: 
+----+-----+
| id | num |
+----+-----+
| 3  | 3   |
+----+-----+
Explanation: 
The person with id 3 is a friend of people 1, 2, and 4, so he has three friends in total, which is the most number than any others.

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

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

2⃣Используем UNION ALL для сохранения всех дублирующихся значений и переименовываем столбцы в id.

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

😎 Решение:

WITH Combined AS (
    SELECT requester_id AS id
    FROM friendships
    UNION ALL
    SELECT accepter_id AS id
    FROM friendships
),
FriendCounts AS (
    SELECT id, COUNT(*) AS friend_count
    FROM Combined
    GROUP BY id
    ORDER BY friend_count DESC
)
SELECT id, friend_count
FROM FriendCounts
LIMIT 1;

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

Задача: 318. Maximum Product of Word Lengths
Сложность: medium

Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.

Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

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

1⃣Предварительная обработка масок и длин
Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens.

2⃣Сравнение слов и проверка общих букв
Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd.

3⃣Возврат результата
Верните максимальное значение произведения maxProd.

😎 Решение:

var maxProduct = function(words) {
    const n = words.length;
    const masks = new Array(n).fill(0);
    const lens = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        let bitmask = 0;
        for (const ch of words[i]) {
            bitmask |= 1 << (ch.charCodeAt(0) - 'a'.charCodeAt(0));
        }
        masks[i] = bitmask;
        lens[i] = words[i].length;
    }
    
    let maxVal = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if ((masks[i] & masks[j]) === 0) {
                maxVal = Math.max(maxVal, lens[i] * lens[j]);
            }
        }
    }
    return maxVal;
};

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

Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

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

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

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

😎 Решение:

class CombinationIterator {
    constructor(characters, combinationLength) {
        this.combinations = [];
        let n = characters.length;
        let k = combinationLength;
        for (let bitmask = 0; bitmask < (1 << n); bitmask++) {
            if (bitmask.toString(2).split('1').length - 1 === k) {
                let curr = [];
                for (let j = 0; j < n; j++) {
                    if (bitmask & (1 << (n - j - 1))) {
                        curr.push(characters[j]);
                    }
                }
                this.combinations.push(curr.join(''));
            }
        }
    }

    next() {
        return this.combinations.pop();
    }

    hasNext() {
        return this.combinations.length > 0;
    }
}

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

Задача: 917. Reverse Only Letters
Сложность: easy

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

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

1⃣Создать массив для хранения только английских букв из строки s.

2⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3⃣Вернуть результат.

😎 Решение:

var reverseOnlyLetters = function(s) {
    const letters = s.split('').filter(c => /[a-zA-Z]/.test(c));
    letters.reverse();
    let idx = 0;
    return s.split('').map(c => {
        if (/[a-zA-Z]/.test(c)) {
            return letters[idx++];
        } else {
            return c;
        }
    }).join('');
};

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

Задача: 859. Buddy Strings
Сложность: easy

Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.

Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].

Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".

Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

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

1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false.

2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false.

3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена.

😎 Решение:

var buddyStrings = function(s, goal) {
    if (s.length !== goal.length) return false;
    if (s === goal) {
        const freq = new Map();
        for (const ch of s) {
            if (freq.has(ch)) return true;
            freq.set(ch, 1);
        }
        return false;
    }

    let firstIndex = -1, secondIndex = -1;
    for (let i = 0; i < s.length; ++i) {
        if (s[i] !== goal[i]) {
            if (firstIndex === -1) firstIndex = i;
            else if (secondIndex === -1) secondIndex = i;
            else return false;
        }
    }

    return secondIndex !== -1 &&
           s[firstIndex] === goal[secondIndex] &&
           s[secondIndex] === goal[firstIndex];
};

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