JavaScript | LeetCode

Задача: 925. Long Pressed Name Сложность: easy Ваш друг набирает на клавиатуре свое имя. Иногда, при наборе символа c, клавиша может быть долго нажата, и символ будет набран 1 или более раз. Вы исследуете набранные символы клавиатуры. Верните True, если возможно, что это было имя вашего друга, при этом некоторые символы (возможно, ни один) не были долго нажаты. Пример:

    
        Input: name = "alex", typed = "aaleex"
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Инициализировать два указателя i и j для строки имени и набранной строки соответственно. 2⃣Пройти по набранной строке: Если символы имени и набранной строки совпадают, сдвинуть оба указателя. Если символы не совпадают, проверить, является ли текущий символ набранной строки повторением предыдущего символа. Если да, сдвинуть указатель набранной строки. Если символ не совпадает и не является повторением предыдущего символа, вернуть False. После завершения цикла проверить, что все символы имени были обработаны. 3⃣Вернуть True, если все символы имени были обработаны, иначе False. 😎 Решение:

    
        var isLongPressedName = function(name, typed) {
    let i = 0, j = 0;
    while (j < typed.length) {
        if (i < name.length && name[i] === typed[j]) {
            i++;
        } else if (j === 0 || typed[j] !== typed[j - 1]) {
            return false;
        }
        j++;
    }
    return i === name.length;
};{}
    

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

Задача: 1039. Minimum Score Triangulation of Polygon Сложность: medium У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника. Пример:

    
        Input: values = [1,2,3]
Output: 6{}
    

👨‍💻 Алгоритм: 1⃣Инициализация: Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j. 2⃣Основное заполнение dp: Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n). Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника. Заполнение dp для каждого подмногоугольника: Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j. 3⃣Возврат результата: Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника. 😎 Решение:

    
        var minScoreTriangulation = function(values) {
    const n = values.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    for (let length = 2; length < n; length++) {
        for (let i = 0; i < n - length; i++) {
            const j = i + length;
            dp[i][j] = Infinity;
            for (let k = i + 1; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
            }
        }
    }
    
    return dp[0][n - 1];
};{}
    

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

Задача: 259. 3Sum Smaller Сложность: medium Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target. Пример:

    
        Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]{}
    

👨‍💻 Алгоритм: 1️⃣Отсортируйте массив nums. 2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения. 3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар. 😎 Решение:

    
        class Solution {
    threeSumSmaller(nums, target) {
        nums.sort((a, b) => a - b)
        let sum = 0
        for (let i = 0; i < nums.length - 2; i++) {
            sum += this.twoSumSmaller(nums, i + 1, target - nums[i])
        }
        return sum
    }

    twoSumSmaller(nums, startIndex, target) {
        let sum = 0
        for (let i = startIndex;{}
    

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

Задача: 215. Kth Largest Element in an Array Сложность: medium Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве. Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент. Пример:

    
        Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4{}
    

👨‍💻 Алгоритм: 1️⃣ Отсортируйте массив в порядке убывания: Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее. 2️⃣ Найдите k-й по величине элемент: После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0). 3️⃣ Верните результат: Возвратите найденное значение как результат. 😎 Решение:

    
        class Solution {
    shortestPalindrome(s) {
        const n = s.length;
        const rev = s.split('').reverse().join('');
        for (let i = 0; i < n; i++) {
            if (s.substring(0, n - i) === rev.substring(i)) {
                return rev.substring(0, i) + s;
            }
        }
        return "";
    }
}{}
    

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

Задача: 341. Flatten Nested List Iterator Сложность: medium Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки. Реализуйте класс NestedIterator: NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList. int next() Возвращает следующий целый элемент вложенного списка. boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае. Пример:

    
        Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].{}
    

👨‍💻 Алгоритм: 1⃣Инициализация Сохраняйте исходный вложенный список в стеке или очереди. Используйте стек для сохранения состояния итерации по вложенным спискам. 2⃣Метод next() Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек. 3⃣Метод hasNext() Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент. 😎 Решение:

    
        var NestedIterator = function(nestedList) {
    this.stack = [];
    this.flatten(nestedList);
};

NestedIterator.prototype.flatten = function(nestedList) {
    for (let i = nestedList.length - 1; i >= 0; i--) {
        this.stack.push(nestedList[i]);
    }
};

NestedIterator.prototype.next = function() {
    return this.stack.pop().getInteger();
};

NestedIterator.prototype.hasNext = function() {
    while (this.stack.length > 0 && !this.stack[this.stack.length - 1].isInteger()) {
        this.flatten(this.stack.pop().getList());
    }
    return this.stack.length > 0;
};{}
    

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

Задача: 1101. The Earliest Moment When Everyone Become Friends Сложность: medium В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi. Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b. Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1. Пример:

    
        Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
Output: 3
Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.{}
    

👨‍💻 Алгоритм: 1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они. 2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск": Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b). Каждое объединение добавляет новые связи между участниками. 3⃣Следите за количеством групп: Изначально каждый участник рассматривается как отдельная группа. Количество групп уменьшается с каждым полезным объединением. Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени. Если такого момента не существует, верните -1. 😎 Решение:

    
        class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i)
        this.rank = Array(n).fill(1)
    }

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

    union(x, y) {
        const rootX = this.find(x)
        const rootY = this.find(y)
        
        if (rootX !== rootY) {
            if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX
            } else if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY
            } else {
                this.parent[rootY] = rootX
                this.rank[rootX]++
            }
            return true
        }
        return false
    }
}

var earliestAcq = function(logs, n) {
    logs.sort((a, b) => a[0] - b[0])
    const uf = new UnionFind(n)
    let groupCount = n
    
    for (const [timestamp, friendA, friendB] of logs) {
        if (uf.union(friendA, friendB)) {
            groupCount--
        }
        if (groupCount === 1) {
            return timestamp
        }
    }
    
    return -1
}{}
    

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

Задача: 1353. Maximum Number of Events That Can Be Attended Сложность: medium Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi. Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d. Верните максимальное количество событий, которые вы можете посетить. Пример:

    
        Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4{}
    

👨‍💻 Алгоритм: 1⃣Сортировка событий по времени завершения: Сначала отсортируйте массив событий по времени окончания каждого события в порядке возрастания. Это позволит сначала рассматривать события, которые заканчиваются раньше. 2⃣Использование множества для отслеживания посещенных дней: Создайте множество для хранения дней, в которые уже были посещены события. Это позволит легко проверять, был ли день уже использован для посещения другого события. 3⃣Посещение событий в доступные дни: Пройдитесь по отсортированному массиву событий. Для каждого события проверьте каждый день от начала события до его окончания и найдите первый доступный день, который еще не был использован. Если такой день найден, добавьте его в множество и увеличьте счетчик посещенных событий. 😎 Решение:

    
        var maxEvents = function(events) {
    events.sort((a, b) => a[1] - b[1]);
    let visitedDays = new Set();
    let count = 0;
    
    for (let [start, end] of events) {
        for (let day = start; day <= end; day++) {
            if (!visitedDays.has(day)) {
                visitedDays.add(day);
                count++;
                break;
            }
        }
    }
    
    return count;
};{}
    

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

Сложность: medium Задача: 556. Next Greater Element III Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм: Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1. Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1. Пример:

    
        Input: n = 12
Output: 21{}
    

👨‍💻 Алгоритм: 1⃣Нахождение и перестановка цифр Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j. 2⃣Обратный порядок оставшихся цифр Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной. 3⃣Проверка результата и преобразование обратно в число Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число. 😎 Решение:

    
        class Solution {
    swap(s, i0, i1) {
        if (i0 === i1) return s;
        let chars = s.split('');
        [chars[i0], chars[i1]] = [chars[i1], chars[i0]];
        return chars.join('');
    }

    constructor() {
        this.list = [];
    }

    permute(a, l, r) {
        if (l === r) {
            this.list.push(a);
        } else {
            for (let i = l; i <= r; i++) {
                a = this.swap(a, l, i);
                this.permute(a, l + 1, r);
                a = this.swap(a, l, i);
            }
        }
    }

    nextGreaterElement(n) {
        let s = '' + n;
        this.permute(s, 0, s.length - 1);
        this.list.sort();
        let index = this.list.indexOf(s);
        if (index !== -1 && index < this.list.length - 1) {
            let result = parseInt(this.list[index + 1]);
            if (result <= 2147483647) {
                return result;
            }
        }
        return -1;
    }
}{}
    

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

Задача: 207. Course Schedule Сложность: medium Всего у вас есть numCourses курсов, которые нужно пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai. Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1. Верните true, если вы можете завершить все курсы. В противном случае верните false. Пример:

    
        Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.{}
    

👨‍💻 Алгоритм: 1️⃣Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1. 2️⃣Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов. 3️⃣Пока очередь не пуста: Извлеките первый узел из очереди. Увеличьте nodesVisited на 1. Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor. Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь. Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses. 😎 Решение:

    
        class Solution {
    canFinish(numCourses, prerequisites) {
        const indegree = new Array(numCourses).fill(0);
        const adj = Array.from({ length: numCourses }, () => []);

        for (const [a, b] of prerequisites) {
            adj[b].push(a);
            indegree[a]++;
        }

        const q = [];
        for (let i = 0; i < numCourses; i++) {
            if (indegree[i] === 0) {
                q.push(i);
            }
        }

        let nodesVisited = 0;
        while (q.length > 0) {
            const node = q.shift();
            nodesVisited++;

            for (const neighbor of adj[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] === 0) {
                    q.push(neighbor);
                }
            }
        }

        return nodesVisited === numCourses;
    }
}{}
    

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

Задача: 437. Path Sum III Сложность: medium Дан корень бинарного дерева и целое число targetSum, вернуть количество путей, где сумма значений вдоль пути равна targetSum. Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним). Пример:

    
        Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.{}
    

👨‍💻 Алгоритм: 1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0). 2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target]. 3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его. 😎 Решение:

    
        var pathSum = function(root, sum) {
    let count = 0
    const k = sum
    const h = new Map()
    const preorder = (node, curr_sum) => {
        if (!node) return
        curr_sum += node.val
        if (curr_sum === k) {
            count++
        }
        count += (h.get(curr_sum - k) || 0)
        h.set(curr_sum, (h.get(curr_sum) || 0) + 1)
        preorder(node.left, curr_sum)
        preorder(node.right, curr_sum)
        h.set(curr_sum, h.get(curr_sum) - 1)
    }
    preorder(root, 0)
    return count
}{}
    

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