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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

    return index === n;
};

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

    return dp[0];
};

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

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

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

Пример:

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

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

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

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

3⃣Верните segment_count.

😎 Решение:

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

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

    return segmentCount;
};

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

Задача: 841. Keys and Rooms
Сложность: medium

Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

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

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

var canVisitAllRooms = function(rooms) {
    let seen = new Array(rooms.length).fill(false);
    seen[0] = true;
    let stack = [0];

    while (stack.length > 0) {
        let node = stack.pop();
        for (let nei of rooms[node]) {
            if (!seen[nei]) {
                seen[nei] = true;
                stack.push(nei);
            }
        }
    }

    return seen.every(Boolean);
};

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1️⃣ Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

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

3️⃣ Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания.

😎 Решение:

class Solution {
    constructor() {
        this.WHITE = 1;
        this.GRAY = 2;
        this.BLACK = 3;
        this.isPossible = true;
        this.color = new Map();
        this.adjList = new Map();
        this.topologicalOrder = [];
    }

    findOrder(numCourses, prerequisites) {
        for (let i = 0; i < numCourses; i++) {
            this.color.set(i, this.WHITE);
        }

        for (let [dest, src] of prerequisites) {
            if (!this.adjList.has(src)) {
                this.adjList.set(src, []);
            }
            this.adjList.get(src).push(dest);
        }

        for (let i = 0; i < numCourses && this.isPossible; i++) {
            if (this.color.get(i) === this.WHITE) {
                this.dfs(i);
            }
        }

        if (this.isPossible) {
            const order = new Array(numCourses);
            for (let i = 0; i < numCourses; i++) {
                order[i] = this.topologicalOrder[numCourses - i - 1];
            }
            return order;
        } else {
            return [];
        }
    }

    dfs(node) {
        if (!this.isPossible) return;
        this.color.set(node, this.GRAY);

        if (this.adjList.has(node)) {
            for (let neighbor of this.adjList.get(node)) {
                if (this.color.get(neighbor) === this.WHITE) {
                    this.dfs(neighbor);
                } else if (this.color.get(neighbor) === this.GRAY) {
                    this.isPossible = false;
                }
            }
        }

        this.color.set(node, this.BLACK);
        this.topologicalOrder.push(node);
    }
}

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

Задача: 424. Longest Repeating Character Replacement
Сложность: medium

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

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

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

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

😎 Решение:

class Solution {
    characterReplacement(s, k) {
        let lo = 1, hi = s.length + 1;

        while (lo + 1 < hi) {
            let mid = lo + Math.floor((hi - lo) / 2);
            if (this.canMakeValidSubstring(s, mid, k)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    canMakeValidSubstring(s, substringLength, k) {
        let freqMap = new Array(26).fill(0);
        let maxFrequency = 0;
        let start = 0;

        for (let end = 0; end < s.length; end++) {
            freqMap[s.charCodeAt(end) - 65]++;

            if (end + 1 - start > substringLength) {
                freqMap[s.charCodeAt(start) - 65]--;
                start++;
            }

            maxFrequency = Math.max(maxFrequency, freqMap[s.charCodeAt(end) - 65]);
            if (substringLength - maxFrequency <= k) {
                return true;
            }
        }
        return false;
    }
}

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

Задача: 203. Remove Linked List Elements
Сложность: easy

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

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

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

1️⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2️⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3️⃣Верните sentinel.next.

😎 Решение:

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function deleteNode(head, value) {
    let sentinel = new ListNode(0);
    sentinel.next = head;
    let prev = sentinel, curr = head;

    while (curr !== null) {
        if (curr.val === value) {
            prev.next = curr.next;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
    return sentinel.next;
}

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

Задача: 53. Maximum Subarray
Сложность: hard

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

Пример:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

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

1️⃣Инициализируйте переменную maxSubarray значением минус бесконечность, чтобы отслеживать лучший подмассив. Необходимо использовать отрицательную бесконечность, а не 0, поскольку в массиве могут быть только отрицательные числа.

2️⃣Используйте цикл for, который рассматривает каждый индекс массива в качестве начальной точки. Для каждой начальной точки создайте переменную currentSubarray с начальным значением 0. Затем пройдитесь по массиву, начиная с указанного индекса, прибавляя каждый элемент к currentSubarray. При каждом добавлении элемента получается возможный подмассив, поэтому непрерывно обновляйте maxSubarray, чтобы он содержал максимум из currentSubarray и самого себя.

3️⃣Верните значение maxSubarray.

😎 Решение:

var maxSubArray = function (nums) {
    let max_subarray = Number.NEGATIVE_INFINITY;
    for (let i = 0; i < nums.length; i++) {
        let current_subarray = 0;
        for (let j = i; j < nums.length; j++) {
            current_subarray += nums[j];
            max_subarray = Math.max(max_subarray, current_subarray);
        }
    }
    return max_subarray;
};

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

Задача: 527. Word Abbreviation
Сложность: hard

Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.
Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

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

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

3⃣ Возврат результата:
Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.

😎 Решение:

var wordsAbbreviation = function(words) {
    const n = words.length;
    const ans = new Array(n).fill("");
    const prefix = new Array(n).fill(0);

    for (let i = 0; i < n; ++i) {
        ans[i] = abbrev(words[i], 0);
    }

    for (let i = 0; i < n; ++i) {
        while (true) {
            const dupes = new Set();
            for (let j = i + 1; j < n; ++j) {
                if (ans[i] === ans[j]) {
                    dupes.add(j);
                }
            }

            if (dupes.size === 0) break;
            dupes.add(i);
            for (const k of dupes) {
                ans[k] = abbrev(words[k], ++prefix[k]);
            }
        }
    }

    return ans;
};

function abbrev(word, i) {
    const n = word.length;
    if (n - i <= 3) return word;
    return word.slice(0, i + 1) + (n - i - 2) + word.slice(-1);
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

var deleteTreeNodes = function(nodes, parent, value) {
    let tree = new Map();
    for (let i = 0; i < nodes; i++) {
        if (!tree.has(parent[i])) tree.set(parent[i], []);
        tree.get(parent[i]).push(i);
    }

    function dfs(node) {
        let totalSum = value[node];
        let totalCount = 1;
        if (tree.has(node)) {
            for (let child of tree.get(node)) {
                let [childSum, childCount] = dfs(child);
                totalSum += childSum;
                totalCount += childCount;
            }
        }
        return totalSum === 0 ? [0, 0] : [totalSum, totalCount];
    }

    return dfs(0)[1];
};

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в следующую игру Nim со своим другом:
Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution {
    canWinNim(n) {
        return n % 4 !== 0;
    }
}

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

Задача: 165. Compare Version Numbers
Сложность: medium

Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.
Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.
Верните следующее:
- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.

Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

1️⃣Разделение строк: Разделите обе строки по символу точки на два массива.

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

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

😎 Решение:

var compareVersion = function (version1, version2) {
    let nums1 = version1.split(".");
    let nums2 = version2.split(".");
    let n1 = nums1.length,
        n2 = nums2.length;

    for (let i = 0; i < Math.max(n1, n2); ++i) {
        let i1 = i < n1 ? parseInt(nums1[i]) : 0;
        let i2 = i < n2 ? parseInt(nums2[i]) : 0;
        if (i1 != i2) {
            return i1 > i2 ? 1 : -1;
        }
    }
    return 0;
};

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

Задача: 52. N-Queens II
Сложность: hard

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

Пример:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

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

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

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

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

😎 Решение:

var totalNQueens = function (n) {
    function backtrack(row, diagonals, anti_diagonals, cols) {
        if (row == n) {
            return 1;
        }
        let solutions = 0;
        for (let col = 0; col < n; col++) {
            let curr_diagonal = row - col;
            let curr_anti_diagonal = row + col;
            if (
                cols.has(col) ||
                diagonals.has(curr_diagonal) ||
                anti_diagonals.has(curr_anti_diagonal)
            ) {
                continue;
            }
            cols.add(col);
            diagonals.add(curr_diagonal);
            anti_diagonals.add(curr_anti_diagonal);
            solutions += backtrack(row + 1, diagonals, anti_diagonals, cols);
            cols.delete(col);
            diagonals.delete(curr_diagonal);
            anti_diagonals.delete(curr_anti_diagonal);
        }
        return solutions;
    }
    return backtrack(0, new Set(), new Set(), new Set());
};

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

Задача: 108. Convert Sorted Array to Binary Search Tree
Сложность: easy

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

Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

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

1️⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right.
Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None.

2️⃣Выбор корня и разделение массива:
Выберите элемент в середине для корня: p = (left + right) // 2.
Инициализируйте корень: root = TreeNode(nums[p]).

3️⃣Рекурсивное построение поддеревьев:
Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1).
Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right).
В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева.

😎 Решение:

var sortedArrayToBST = function (nums) {
    return helper(nums, 0, nums.length - 1);
};
var helper = function (nums, left, right) {
    if (left > right) {
        return null;
    }
    var p = Math.floor((left + right) / 2);
    var root = new TreeNode(nums[p], null, null);
    root.left = helper(nums, left, p - 1);
    root.right = helper(nums, p + 1, right);
    return root;
};

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

Задача: 849. Maximize Distance to Closest Person
Сложность: medium

Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).
Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.
Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.

Верните это максимальное расстояние до ближайшего человека.

Пример:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

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

1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

3⃣Найдите и верните максимальное расстояние до ближайшего занятого места.

😎 Решение:

var maxDistToClosest = function(seats) {
    let n = seats.length;
    let prev = -1, future = 0;
    let ans = 0;

    for (let i = 0; i < n; ++i) {
        if (seats[i] === 1) {
            prev = i;
        } else {
            while (future < n && (seats[future] === 0 || future < i)) {
                future++;
            }
            let left = prev === -1 ? n : i - prev;
            let right = future === n ? n : future - i;
            ans = Math.max(ans, Math.min(left, right));
        }
    }

    return ans;
};

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