Задача: 1267. Count Servers that Communicate
Сложность: medium

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:

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

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

1⃣Подсчитайте количество серверов в каждой строке и каждом столбце.

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

3⃣Подсчитайте и верните количество взаимодействующих серверов.

😎 Решение:

var countServers = function(grid) {
    let rows = new Array(grid.length).fill(0);
    let cols = new Array(grid[0].length).fill(0);

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 1) {
                rows[i]++;
                cols[j]++;
            }
        }
    }

    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 1 && (rows[i] > 1 || cols[j] > 1)) {
                count++;
            }
        }
    }

    return count;
};

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

Задача: 96. Unique Binary Search Trees
Сложность: medium

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

Пример:

Input: n = 3
Output: 5

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

1️⃣Рассчитать количество уникальных BST (бинарных деревьев поиска).

2️⃣Позднее мы увидим, что G(n) можно вывести из F(i, n), которая, в свою очередь, рекурсивно относится к G(n).
Следуя идее из раздела "Интуиция", мы видим, что общее количество уникальных BST G(n) равно сумме BST F(i, n) с перечислением каждого числа i (1 ≤ i ≤ n) в качестве корня. Таким образом, G(n) = ∑ F(i, n) для i от 1 до n.

3️⃣Дана последовательность от 1 до n, мы выбираем число i из последовательности в качестве корня, тогда количество уникальных BST с указанным корнем, определенным как F(i, n), является декартовым произведением количества BST для его левого и правого поддеревьев.

😎 Решение:

var numTrees = function (n) {
    let G = new Array(n + 1).fill(0);
    G[0] = 1;
    G[1] = 1;
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            G[i] += G[j - 1] * G[i - j];
        }
    }
    return G[n];
};

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

Задача: 161. One Edit Distance
Сложность: medium

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

Пример:

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

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

1️⃣Проверка длины строк:
Убедитесь, что строка s короче строки t. Если это не так, поменяйте их местами и повторите проверку.
Если разница в длине между s и t больше 1, то строки невозможно привести к равенству одной операцией редактирования, верните false.

2️⃣Сравнение строк посимвольно:
Проходите по строке s и сравнивайте каждый символ с соответствующим символом в строке t.
Если находите различающийся символ:
Если длины строк равны (ns == nt), проверьте, равны ли подстроки после текущего символа для обеих строк (s.substr(i + 1) == t.substr(i + 1)). Если равны, возвращайте true, иначе false.
Если длины строк различаются, проверьте, равна ли подстрока s начиная с текущего символа подстроке t начиная с следующего символа (s.substr(i) == t.substr(i + 1)). Если равны, возвращайте true, иначе false

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

😎 Решение:

var isOneEditDistance = function (s, t) {
    let ns = s.length;
    let nt = t.length;
    if (ns > nt) return isOneEditDistance(t, s);
    if (nt - ns > 1) return false;

    for (let i = 0; i < ns; i++)
        if (s[i] != t[i])
            if (ns == nt)
                return s.slice(i + 1) === t.slice(i + 1);
            else return s.slice(i) === t.slice(i + 1);
    return ns + 1 === nt;
};

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

Задача: 1023. Camelcase Matching
Сложность: medium

Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.

Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

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

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

2⃣Проверка каждого запроса:
Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.
Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.

3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.

😎 Решение:

class Solution {
    camelMatch(queries, pattern) {
        const matches = (query, pattern) => {
            let i = 0, j = 0;
            while (i < query.length) {
                if (j < pattern.length && query[i] === pattern[j]) {
                    j++;
                } else if (query[i] >= 'A' && query[i] <= 'Z') {
                    return false;
                }
                i++;
            }
            return j === pattern.length;
        };
        
        return queries.map(query => matches(query, pattern));
    }
}

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

Задача: 973. K Closest Points to Origin
Сложность: medium

Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).

Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).

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

Пример:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

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

1⃣Отсортируйте массив с помощью функции компаратора.

2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.

3⃣Верните первые k элементов массива.

😎 Решение:

class Solution {
    kClosest(points, k) {
        points.sort((a, b) => this.squaredDistance(a) - this.squaredDistance(b))
        return points.slice(0, k)
    }

    squaredDistance(point) {
        return point[0] * point[0] + point[1] * point[1]
    }
}

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

Задача: 1265. Print Immutable Linked List in Reverse
Сложность: medium

Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API.

Пример:

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

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

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

2⃣На обратном пути рекурсии распечатайте значение каждого узла.

3⃣Обратный порядок достигается благодаря природе рекурсии (стек вызовов).

😎 Решение:

var printLinkedListInReverse = function(head) {
    function helper(node) {
        if (node.getNext() !== null) {
            helper(node.getNext());
        }
        node.printValue();
    }
    helper(head);
};

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

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

Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5.
Дано целое число n, верните true, если n является уродливым числом.

Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

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

1️⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым.

2️⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5.

3️⃣Если после всех делений n равно 1, верните true, иначе верните false.

😎 Решение:

class Solution {
    isUgly(n) {
        if (n <= 0) {
            return false
        }
        for (const factor of [2, 3, 5]) {
            n = this.keepDividingWhenDivisible(n, factor)
        }
        return n === 1
    }

    keepDividingWhenDivisible(dividend, divisor) {
        while (dividend % divisor === 0) {
            dividend /= divisor
        }
        return dividend
    }
}

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов
Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

3⃣Обновление времени выполнения
Когда функция завершает выполнение, обновите ее эксклюзивное время и также учитывайте время выполнения вложенных функций.

😎 Решение:

var exclusiveTime = function(n, logs) {
    let stack = [];
    let times = new Array(n).fill(0);
    let prevTime = 0;
    
    for (let log of logs) {
        let [fid, type, time] = log.split(':');
        fid = parseInt(fid);
        time = parseInt(time);
        
        if (type === 'start') {
            if (stack.length) {
                times[stack[stack.length - 1]] += time - prevTime;
            }
            stack.push(fid);
            prevTime = time;
        } else {
            times[stack.pop()] += time - prevTime + 1;
            prevTime = time + 1;
        }
    }
    
    return times;
};

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

Задача: 134. Gas Station
Сложность: medium

Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].
У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.
Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.

Пример:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

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

1️⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0.

2️⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i].
Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2.

3️⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer.

😎 Решение:

var canCompleteCircuit = function (gas, cost) {
    let currGain = 0,
        totalGain = 0,
        answer = 0;
    for (let i = 0; i < gas.length; ++i) {
        totalGain += gas[i] - cost[i];
        currGain += gas[i] - cost[i];
        if (currGain < 0) {
            answer = i + 1;
            currGain = 0;
        }
    }
    return totalGain >= 0 ? answer : -1;
};

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

Задача: 538. Convert BST to Greater Tree
Сложность: medium

Дано корень бинарного дерева поиска (BST), преобразуйте его в дерево, в котором каждый ключ исходного BST изменен на исходный ключ плюс сумму всех ключей, больших исходного ключа в BST.
Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям:
Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла.
Правое поддерево узла содержит только узлы с ключами, большими ключа узла.
И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

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

2⃣Посещаем текущий узел, обновляем его значение и общую сумму.

3⃣Рекурсивно обрабатываем левое поддерево.

😎 Решение:

class Solution {
    constructor() {
        this.sum = 0;
    }

    convertBST(root) {
        if (root !== null) {
            this.convertBST(root.right);
            this.sum += root.val;
            root.val = this.sum;
            this.convertBST(root.left);
        }
        return root;
    }
}

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

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

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: num = 23
Output: "1000"

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

1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n)

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

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

😎 Решение:

function encode(num) {
    if (num === 0) return "";
    return (num - 1).toString(2);
}

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

Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

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

1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы.

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение:

var shortestDistanceColor = function(colors, queries) {
    let queryResults = [];
    let hashmap = new Map();

    for (let i = 0; i < colors.length; i++) {
        if (!hashmap.has(colors[i])) {
            hashmap.set(colors[i], []);
        }
        hashmap.get(colors[i]).push(i);
    }

    for (let [target, color] of queries) {
        if (!hashmap.has(color)) {
            queryResults.push(-1);
            continue;
        }

        let indexList = hashmap.get(color);
        let insert = binarySearch(indexList, target);

        if (insert < 0) {
            insert = -insert - 1;
        }

        if (insert === 0) {
            queryResults.push(indexList[insert] - target);
        } else if (insert === indexList.length) {
            queryResults.push(target - indexList[insert - 1]);
        } else {
            let leftNearest = target - indexList[insert - 1];
            let rightNearest = indexList[insert] - target;
            queryResults.push(Math.min(leftNearest, rightNearest));
        }
    }

    return queryResults;
};

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -left - 1;
}

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

Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard

Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.

Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.

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

Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.

Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

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

1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.

2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.

3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.

😎 Решение:

class Solution {
  constructor() {
    this.MOD = 1000000007;
    this.memo = [];
    this.done = 0;
    this.n = 0;
    this.hatsToPeople = new Map();
  }

  numberWays(hats) {
    this.n = hats.length;
    this.hatsToPeople.clear();
    hats.forEach((personHats, i) => {
      personHats.forEach(hat => {
        if (!this.hatsToPeople.has(hat)) {
          this.hatsToPeople.set(hat, []);
        }
        this.hatsToPeople.get(hat).push(i);
      });
    });

    this.done = (1 << this.n) - 1;
    this.memo = Array.from({ length: 41 }, () => Array(this.done).fill(-1));

    return this.dp(1, 0);
  }

  dp(hat, mask) {
    if (mask === this.done) {
      return 1;
    }

    if (hat > 40) {
      return 0;
    }

    if (this.memo[hat][mask] !== -1) {
      return this.memo[hat][mask];
    }

    let ans = this.dp(hat + 1, mask);

    if (this.hatsToPeople.has(hat)) {
      for (const person of this.hatsToPeople.get(hat)) {
        if ((mask & (1 << person)) === 0) {
          ans = (ans + this.dp(hat + 1, mask | (1 << person))) % this.MOD;
        }
      }
    }

    this.memo[hat][mask] = ans;
    return ans;
  }
}

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

Задача: 383. Ransom Note
Сложность: easy

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

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления".

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

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

😎 Решение:

function canConstruct(ransomNote, magazine) {
  for (let char of ransomNote) {
    let index = magazine.indexOf(char);
    if (index === -1) {
      return false;
    }
    magazine = magazine.slice(0, index) + magazine.slice(index + 1);
  }
  return true;
}

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

Задача: 279. Perfect Squares
Сложность: medium

Дано целое число n, верните наименьшее количество чисел, являющихся совершенными квадратами, сумма которых равна n.
Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

var numSquares = function(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    const maxSquareIndex = Math.floor(Math.sqrt(n)) + 1;
    const squareNums = new Array(maxSquareIndex).fill(0).map((_, i) => i * i);
    
    for (let i = 1; i <= n; i++) {
        for (let s = 1; s < maxSquareIndex; s++) {
            if (i < squareNums[s]) break;
            dp[i] = Math.min(dp[i], dp[i - squareNums[s]] + 1);
        }
    }
    
    return dp[n];
};

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

Задача: 606. Construct String from Binary Tree
Сложность: medium

Дано корневой узел бинарного дерева, ваша задача — создать строковое представление дерева, следуя определенным правилам форматирования. Представление должно быть основано на прямом обходе бинарного дерева и должно соответствовать следующим требованиям:
Представление узлов: Каждый узел в дереве должен быть представлен его целочисленным значением.
Скобки для дочерних узлов: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:
- Если у узла есть левый дочерний узел, значение левого дочернего узла должно быть заключено в скобки сразу после значения узла.
- Если у узла есть правый дочерний узел, значение правого дочернего узла также должно быть заключено в скобки. Скобки для правого дочернего узла должны следовать за скобками для левого дочернего узла.
Пропуск пустых скобок: Любые пустые пары скобок (т.е. ()) должны быть опущены в окончательном строковом представлении дерева, за одним исключением: когда у узла есть правый дочерний узел, но нет левого дочернего узла. В таких случаях вы должны включить пустую пару скобок, чтобы указать на отсутствие левого дочернего узла. Это гарантирует, что однозначное соответствие между строковым представлением и исходной структурой бинарного дерева сохраняется.
В итоге, пустые пары скобок должны быть опущены, когда у узла есть только левый дочерний узел или нет дочерних узлов. Однако, когда у узла есть правый дочерний узел, но нет левого дочернего узла, пустая пара скобок должна предшествовать представлению правого дочернего узла, чтобы точно отразить структуру дерева.

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

var tree2str = function(t) {
    const dfs = (t) => {
        if (!t) return "";
        let res = `${t.val}`;
        if (!t.left && !t.right) return res;
        res += `(${dfs(t.left)})`;
        if (t.right) {
            res += `(${dfs(t.right)})`;
        }
        return res;
    }
    return dfs(t);
};

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

Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

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

Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

var delNodes = function(root, to_delete) {
    const toDeleteSet = new Set(to_delete);
    const forest = [];

    const processNode = (node) => {
        if (!node) return null;

        node.left = processNode(node.left);
        node.right = processNode(node.right);

        if (toDeleteSet.has(node.val)) {
            if (node.left) forest.push(node.left);
            if (node.right) forest.push(node.right);
            return null;
        }
        return node;
    };

    root = processNode(root);
    if (root) {
        forest.push(root);
    }

    return forest;
};

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

Задача: 257. Binary Tree Paths
Сложность: easy

Дано корневое дерево, верните все пути от корня до листа в любом порядке.
Лист — это узел без детей.

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1️⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.

2️⃣Начните с корневого узла, пустого пути и пустого списка путей.

3️⃣Верните список всех путей от корня до листа.

😎 Решение:

class Solution {
    constructPaths(root, path, paths) {
        if (root !== null) {
            path += root.val
            if (root.left === null && root.right === null) {
                paths.push(path)
            } else {
                path += "->"
                this.constructPaths(root.left, path, paths)
                this.constructPaths(root.right, path, paths)
            }
        }
    }

    binaryTreePaths(root) {
        const paths = []
        this.constructPaths(root, "", paths)
        return paths
    }
}

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

Задача: №17. Letter Combinations of a Phone Number
Сложность: medium

Дана строка digits, содержащая цифры от 2 до 9.
Нужно вернуть все возможные комбинации букв, которые может представлять эта строка по стандартной телефонной клавиатуре.

Пример:

Input: digits = "23"  
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

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

1️⃣ Инициализируем массив ans с пустой строкой [''] и таблицу соответствия цифр буквам d[], где d[0] — это буквы для цифры 2 и т.д.

2️⃣ Для каждой цифры в строке digits, берём соответствующую строку символов s из таблицы d.

3️⃣ Для каждого уже полученного префикса a и каждой буквы b из s формируем новую комбинацию a + b и сохраняем в новом массиве. После полной итерации обновляем ans.

😎 Решение:

var letterCombinations = function (digits) {
    if (digits.length === 0) {
        return [];
    }

    const ans = [''];
    const d = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];

    for (const i of digits) {
        const s = d[parseInt(i) - 2];
        const t = [];

        for (const a of ans) {
            for (const b of s) {
                t.push(a + b);
            }
        }

        ans.splice(0, ans.length, ...t);
    }

    return ans;
};

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

Задача: 956. Tallest Billboard
Сложность: hard

Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0.

Пример:

Input: rods = [1,2,3,6]
Output: 6

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

1⃣Определить количество строк n и длину каждой строки m.
Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов.

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

3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным.
Вернуть количество удаленных столбцов.

😎 Решение:

var minDeletionSize = function(strs) {
    const n = strs.length;
    const m = strs[0].length;
    const deleteCount = new Array(m).fill(false);
    
    const isSorted = () => {
        for (let i = 0; i < n - 1; i++) {
            for (let j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                if (strs[i][j] > strs[i + 1][j]) return false;
                if (strs[i][j] < strs[i + 1][j]) break;
            }
        }
        return true;
    };
    
    while (!isSorted()) {
        for (let j = 0; j < m; j++) {
            if (deleteCount[j]) continue;
            for (let i = 0; i < n - 1; i++) {
                if (strs[i][j] > strs[i + 1][j]) {
                    deleteCount[j] = true;
                    break;
                }
            }
            if (deleteCount[j]) break;
        }
    }
    
    return deleteCount.filter(Boolean).length;
};

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

Задача: 751. IP to CIDR
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

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

1⃣Преобразовать начальный IP-адрес в целое число.

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

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

function ipToInt(ip) {
    const parts = ip.split('.').map(Number);
    return (parts[0] << 24) + (parts[1] << 16) + (parts[2] << 8) + parts[3];
}

function intToIp(num) {
    return `${(num >> 24) & 255}.${(num >> 16) & 255}.${(num >> 8) & 255}.${num & 255}`;
}

function cidr(ip, prefixLength) {
    return `${ip}/${prefixLength}`;
}

function findCidrBlocks(startIp, n) {
    let start = ipToInt(startIp);
    const result = [];
    
    while (n > 0) {
        let maxSize = 1;
        while (maxSize <= start && maxSize <= n) {
            maxSize <<= 1;
        }
        maxSize >>= 1;
        
        while (start % maxSize !== 0) {
            maxSize >>= 1;
        }
        
        result.push(cidr(intToIp(start), 32 - Math.log2(maxSize) | 0 + 1));
        start += maxSize;
        n -= maxSize;
    }
    
    return result;
}

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