Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 903. Valid Permutations for DI Sequence
Сложность: hard

Вам дана строка s длины n, где s[i] либо: 'D' означает убывание, либо 'I' означает возрастание. Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] называется допустимой, если для всех допустимых i: если s[i] == 'D', то perm[i] > perm[i + 1], а если s[i] == 'I', то perm[i] < perm[i + 1]. Верните количество допустимых перестановок perm. Поскольку ответ может быть большим, верните его по модулю 109 + 7.

Пример:

Input: s = "DID"
Output: 5

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

1⃣Создать двумерный массив dp, где dp[i][j] представляет количество допустимых перестановок длины i, оканчивающихся на j.

2⃣Заполнить массив dp, учитывая условия возрастания и убывания из строки s.

3⃣Вернуть сумму dp[n][j] для всех j, что даст количество допустимых перестановок длины n + 1.

😎 Решение:

var numPermsDISequence = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
    dp[0][0] = 1;

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= i; j++) {
            if (s[i - 1] === 'D') {
                dp[i][j] = dp[i - 1].slice(j, i).reduce((sum, x) => (sum + x) % MOD, 0);
            } else {
                dp[i][j] = dp[i - 1].slice(0, j).reduce((sum, x) => (sum + x) % MOD, 0);
            }
        }
    }

    return dp[n].reduce((sum, x) => (sum + x) % MOD, 0);
};

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

var fib = function(N) {
    if (N <= 1) return N;
    let current = 0, prev1 = 1, prev2 = 0;
    for (let i = 2; i <= N; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
};

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

Задача: 1232. Check If It Is a Straight Line
Сложность: easy

Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY.

Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

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

1⃣Определение наклона:
Вычисляем наклон между первыми двумя точками и используем его как эталон.

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

3⃣Если все наклоны совпадают, то все точки лежат на одной прямой.

😎 Решение:

var checkStraightLine = function(coordinates) {
    const [x0, y0] = coordinates[0];
    const [x1, y1] = coordinates[1];
    
    for (const [x, y] of coordinates) {
        if ((x1 - x0) * (y - y0) !== (y1 - y0) * (x - x0)) {
            return false;
        }
    }
    return true;
};

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

Задача: 139. Word Break
Сложность: medium

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

Пример:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

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

1️⃣Инициализация структур данных:
Преобразуйте wordDict в множество words для быстрой проверки вхождения.
Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов.

2️⃣Обход в ширину (BFS):
Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start.
Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря.
Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже.

3️⃣Проверка подстроки и обновление структур:
Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый.
Если BFS завершается и конечный узел не достигнут, возвращайте false.

😎 Решение:

var wordBreak = function (s, wordDict) {
    let words = new Set(wordDict);
    let queue = [0];
    let seen = new Set();
    while (queue.length != 0) {
        let start = queue.shift();
        if (start == s.length) return true;
        for (let end = start + 1; end <= s.length; end++) {
            if (seen.has(end)) continue;
            if (words.has(s.substring(start, end))) {
                queue.push(end);
                seen.add(end);
            }
        }
    }
    return false;
};

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

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

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

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

2⃣Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.

3⃣Вернуть count.

😎 Решение:

var minDeletionSize = function(strs) {
    let count = 0;
    for (let col = 0; col < strs[0].length; col++) {
        for (let row = 1; row < strs.length; row++) {
            if (strs[row][col] < strs[row - 1][col]) {
                count++;
                break;
            }
        }
    }
    return count;
};

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

Задача: 502. IPO
Сложность: hard

LeetCode планирует IPO и хочет увеличить капитал, выполняя проекты. У компании ограниченные ресурсы, поэтому она может завершить до k проектов. Помогите LeetCode максимизировать капитал после завершения этих проектов.
У вас есть n проектов с чистой прибылью profits[i] и минимальным капиталом capital[i] для начала.
Изначально у вас есть капитал w. Завершив проект, вы получаете его прибыль, которая добавляется к вашему капиталу.
Выберите до k проектов, чтобы максимально увеличить капитал, и верните его окончательное значение. Ответ гарантированно поместится в 32-битное целое число.

Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

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

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

2⃣Выбор проектов
Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм.

3⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.

😎 Решение:

class MaxHeap {
    constructor(compare) {
        this.heap = [];
        this.compare = compare;
    }

    insert(value) {
        this.heap.push(value);
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.compare(this.heap[index], this.heap[parentIndex]) <= 0) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    extract() {
        const max = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            let index = 0;
            const length = this.heap.length;
            while (true) {
                let left = 2 * index + 1;
                let right = 2 * index + 2;
                let largest = index;

                if (left < length && this.compare(this.heap[left], this.heap[largest]) > 0) largest = left;
                if (right < length && this.compare(this.heap[right], this.heap[largest]) > 0) largest = right;
                if (largest === index) break;
                [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
                index = largest;
            }
        }
        return max;
    }

    get size() {
        return this.heap.length;
    }
}

const findMaximizedCapital = (k, w, profits, capital) => {
    const projects = capital.map((cap, i) => [cap, profits[i]]).sort((a, b) => a[0] - b[0]);
    const maxHeap = new MaxHeap((a, b) => b - a);
    let ptr = 0;

    for (let i = 0; i < k; i++) {
        while (ptr < projects.length && projects[ptr][0] <= w) {
            maxHeap.insert(projects[ptr][1]);
            ptr++;
        }
        if (maxHeap.size === 0) break;
        w += maxHeap.extract();
    }

    return w;
};

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

Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: nums = [4,6,15,35]
Output: 4

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

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

2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.

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

😎 Решение:

var largestComponentSize = function(nums) {
    const parent = {};
    const rank = {};
    
    nums.forEach(num => {
        parent[num] = num;
        rank[num] = 0;
    });
    
    const find = (x) => {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    };
    
    const union = (x, y) => {
        const rootX = find(x);
        const rootY = find(y);
        if (rootX !== rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    };
    
    const primeFactors = (n) => {
        const factors = new Set();
        let d = 2;
        while (d * d <= n) {
            while (n % d === 0) {
                factors.add(d);
                n = Math.floor(n / d);
            }
            d++;
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    };
    
    const primeToIndex = {};
    nums.forEach(num => {
        const primes = primeFactors(num);
        primes.forEach(prime => {
            if (!primeToIndex[prime]) {
                primeToIndex[prime] = [];
            }
            primeToIndex[prime].push(num);
        });
    });
    
    for (const primes of Object.values(primeToIndex)) {
        for (let i = 1; i < primes.length; i++) {
            union(primes[0], primes[i]);
        }
    }
    
    const size = {};
    nums.forEach(num => {
        const root = find(num);
        if (!size[root]) {
            size[root] = 0;
        }
        size[root]++;
    });
    
    return Math.max(...Object.values(size));
};

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

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

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

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

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

😎 Решение:

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    let dp = matrix[0].slice();
    
    for (let i = 1; i < n; i++) {
        const newDp = new Array(n).fill(0);
        for (let j = 0; j < n; j++) {
            newDp[j] = matrix[i][j] + Math.min(dp[j], dp[j-1] !== undefined ? dp[j-1] : Infinity, dp[j+1] !== undefined ? dp[j+1] : Infinity);
        }
        dp = newDp;
    }
    
    return Math.min(...dp);
};

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

Задача: 1001. Grid Illumination
Сложность: hard

Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный массив позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный массив queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. Верните массив целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.

Пример:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]

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

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

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

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

😎 Решение:

class Solution {
    gridIllumination(n, lamps, queries) {
        const lamps_on = new Set();
        const rows = new Map();
        const cols = new Map();
        const diag1 = new Map();
        const diag2 = new Map();

        for (const [r, c] of lamps) {
            const key = r * n + c;
            if (lamps_on.has(key)) continue;
            lamps_on.add(key);
            rows.set(r, (rows.get(r) || 0) + 1);
            cols.set(c, (cols.get(c) || 0) + 1);
            diag1.set(r - c, (diag1.get(r - c) || 0) + 1);
            diag2.set(r + c, (diag2.get(r + c) || 0) + 1);
        }

        const directions = [[0, 0], [0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]];
        const result = [];

        for (const [r, c] of queries) {
            if ((rows.get(r) || 0) > 0 || (cols.get(c) || 0) > 0 || (diag1.get(r - c) || 0) > 0 || (diag2.get(r + c) || 0) > 0) {
                result.push(1);
            } else {
                result.push(0);
            }

            for (const [dr, dc] of directions) {
                const nr = r + dr, nc = c + dc;
                const key = nr * n + nc;
                if (lamps_on.has(key)) {
                    lamps_on.delete(key);
                    rows.set(nr, rows.get(nr) - 1);
                    cols.set(nc, cols.get(nc) - 1);
                    diag1.set(nr - nc, diag1.get(nr - nc) - 1);
                    diag2.set(nr + nc, diag2.get(nr + nc) - 1);
                }
            }
        }

        return result;
    }
}

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

Задача: 690. Employee Importance
Сложность: medium

У вас есть структура данных с информацией о сотрудниках, включая уникальный идентификатор сотрудника, значение его важности и идентификаторы его прямых подчиненных.

Вам дан массив сотрудников employees, где:

employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.

Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

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

1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.

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

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

😎 Решение:

class Employee {
    constructor(id, importance, subordinates) {
        this.id = id;
        this.importance = importance;
        this.subordinates = subordinates;
    }
}

class Solution {
    getImportance(employees, queryid) {
        this.emap = new Map();
        for (const e of employees) {
            this.emap.set(e.id, e);
        }
        return this.dfs(queryid);
    }
    
    dfs(eid) {
        const employee = this.emap.get(eid);
        let ans = employee.importance;
        for (const subid of employee.subordinates) {
            ans += this.dfs(subid);
        }
        return ans;
    }
}

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

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

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter {
    constructor(words) {
        this.prefixSuffixMap = new Map();
        for (let index = 0; index < words.length; index++) {
            const word = words[index];
            const length = word.length;
            for (let prefixLength = 1; prefixLength <= length; prefixLength++) {
                for (let suffixLength = 1; suffixLength <= length; suffixLength++) {
                    const prefix = word.substring(0, prefixLength);
                    const suffix = word.substring(length - suffixLength);
                    const key = prefix + '#' + suffix;
                    this.prefixSuffixMap.set(key, index);
                }
            }
        }
    }
    
    f(pref, suff) {
        const key = pref + '#' + suff;
        return this.prefixSuffixMap.has(key) ? this.prefixSuffixMap.get(key) : -1;
    }
}

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

Задача: 657. Robot Return to Origin
Сложность: easy

На плоскости с координатами (0, 0) находится робот. Дана последовательность его движений, определите, возвращается ли робот в исходную точку (0, 0) после завершения всех своих движений.

Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).

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

Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.

Пример:

Input: moves = "UD"
Output: true

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

1⃣Инициализация координат:
Начните с координат (0, 0).

2⃣Обработка движений:
Пройдите по строке moves и обновляйте координаты в зависимости от движения:
'R' увеличивает координату x на 1.
'L' уменьшает координату x на 1.
'U' увеличивает координату y на 1.
'D' уменьшает координату y на 1.

3⃣Проверка конечных координат:
Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false.

😎 Решение:

var judgeCircle = function(moves) {
    let x = 0, y = 0;
    for (let move of moves) {
        switch (move) {
            case 'R': x++; break;
            case 'L': x--; break;
            case 'U': y++; break;
            case 'D': y--; break;
        }
    }
    return x === 0 && y === 0;
};

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

Задача: 949. Largest Time for Given Digits
Сложность: medium

Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.

Пример:

Input: arr = [1,2,3,4]
Output: "23:41"

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

1⃣Перебрать все возможные перестановки массива arr.

2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.

3⃣Алгоритм
Перебрать все возможные перестановки массива arr.
Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время.
Найти самое позднее допустимое время среди всех перестановок.
Вернуть найденное время в формате "HH
". Если допустимое время не найдено, вернуть пустую строку.

😎 Решение:

var largestTimeFromDigits = function(arr) {
    let maxTime = -1;

    const permute = (arr, start = 0) => {
        if (start === arr.length) {
            const hours = arr[0] * 10 + arr[1];
            const minutes = arr[2] * 10 + arr[3];
            if (hours < 24 && minutes < 60) {
                maxTime = Math.max(maxTime, hours * 60 + minutes);
            }
            return;
        }
        for (let i = start; i < arr.length; i++) {
            [arr[start], arr[i]] = [arr[i], arr[start]];
            permute(arr, start + 1);
            [arr[start], arr[i]] = [arr[i], arr[start]];
        }
    };

    permute(arr);

    if (maxTime === -1) {
        return "";
    }

    const hours = Math.floor(maxTime / 60);
    const minutes = maxTime % 60;
    return `${hours.toString().padStart(2, '0')}:${minutes.toString().padStart(2, '0')}`;
};

edium
Задача: 954. Array of Doubled Pairs

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:

Input: arr = [3,1,3,6]
Output: false

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

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

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

var canReorderDoubled = function(arr) {
    let count = new Map();
    for (let num of arr) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    arr.sort((a, b) => Math.abs(a) - Math.abs(b));
    for (let num of arr) {
        if (count.get(num) === 0) continue;
        if (count.get(num * 2) === 0) return false;
        count.set(num, count.get(num) - 1);
        count.set(num * 2, count.get(num * 2) - 1);
    }
    return true;
};

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

Задача: 256. Paint House
Сложность: medium

Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет.
Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3.
Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее...
Верните минимальную стоимость покраски всех домов.

Пример:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

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

1️⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2].

2️⃣Для каждого дома i от 1 до n-1 обновите значения массива dp:
dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

3️⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]).

😎 Решение:

class Solution {
    minCost(costs) {
        const n = costs.length;
        const dp = Array.from({ length: n }, () => Array(3).fill(0));
        dp[0] = costs[0].slice();
        
        for (let i = 1; i < n; i++) {
            dp[i][0] = costs[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = costs[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = costs[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
        }
        
        return Math.min(dp[n-1][0], dp[n-1][1], dp[n-1][2]);
    }
}

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

Задача: 662. Maximum Width of Binary Tree
Сложность: medium

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

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

1⃣Инициализация:
Создайте очередь для хранения узлов и их позиций на уровне.
Начните с корневого узла и его позиции 0.

2⃣Обработка каждого уровня:
Для каждого уровня дерева получите его узлы и их позиции.
Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один.

3⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

var widthOfBinaryTree = function(root) {
    if (!root) return 0;

    let maxWidth = 0;
    const queue = [{ node: root, pos: 0 }];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const firstPos = queue[0].pos;
        for (let i = 0; i < levelSize; i++) {
            const { node, pos } = queue.shift();
            if (node.left) queue.push({ node: node.left, pos: 2 * pos });
            if (node.right) queue.push({ node: node.right, pos: 2 * pos + 1 });
        }
        const lastPos = queue[queue.length - 1]?.pos || firstPos;
        maxWidth = Math.max(maxWidth, lastPos - firstPos + 1);
    }

    return maxWidth;
};

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

Задача: 560. Subarray Sum Equals K
Сложность: easy

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.
Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

Input: nums = [1,1,1], k = 2
Output: 2

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k.

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

😎 Решение:

class Solution {
    subarraySum(nums, k) {
        let count = 0;
        for (let start = 0; start < nums.length; start++) {
            for (let end = start + 1; end <= nums.length; end++) {
                let sum = 0;
                for (let i = start; i < end; i++) {
                    sum += nums[i];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

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

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

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

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение:

var getLastMoment = function(n, left, right) {
    let ans = 0
    for (let num of left) {
        ans = Math.max(ans, num)
    }
    for (let num of right) {
        ans = Math.max(ans, n - num)
    }
    return ans
}

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

Задача: 654. Maximum Binary Tree
Сложность: medium

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

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

1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

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

😎 Решение:

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var constructMaximumBinaryTree = function(nums) {
    if (!nums.length) return null;
    let maxIndex = nums.indexOf(Math.max(...nums));
    let root = new TreeNode(nums[maxIndex]);
    root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
    root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
    return root;
};

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

Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy

Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.

2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.

3⃣Проверка остатка изменений:
Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму.

😎 Решение:

class Solution {
    largestSumAfterKNegations(nums, k) {
        nums.sort((a, b) => a - b);
        
        for (let i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 === 1) {
            nums.sort((a, b) => a - b);
            nums[0] = -nums[0];
        }
        
        return nums.reduce((a, b) => a + b, 0);
    }
}

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