Задача: 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);
    }
}

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

Задача: 1219. Path with Maximum Gold
Сложность: medium

В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста.

Верните максимальное количество золота, которое вы можете собрать при следующих условиях:
- Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки.
- Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз.
- Вы не можете посещать одну и ту же ячейку более одного раза.
- Никогда не посещайте ячейку с 0 золотом.
- Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото.

Пример:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

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

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

2⃣Функция DFS и обратный трек:
Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека.
Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота.
Пометьте текущую ячейку как посещённую и сохраните её значение.
Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь.
Сбросьте текущую ячейку до её исходного значения для дальнейших исследований.

3⃣Поиск максимального золота:
Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack.
Обновите maxGold при нахождении лучшего пути.
Верните maxGold.

😎 Решение:

var getMaximumGold = function(grid) {
    const directions = [0, 1, 0, -1, 0];
    const rows = grid.length;
    const cols = grid[0].length;
    let maxGold = 0;

    function dfsBacktrack(grid, rows, cols, row, col) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] === 0) {
            return 0;
        }
        const originalVal = grid[row][col];
        grid[row][col] = 0;
        let maxGold = 0;

        for (let i = 0; i < 4; i++) {
            maxGold = Math.max(maxGold, dfsBacktrack(grid, rows, cols, row + directions[i], col + directions[i + 1]));
        }

        grid[row][col] = originalVal;
        return maxGold + originalVal;
    }

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            maxGold = Math.max(maxGold, dfsBacktrack(grid, rows, cols, row, col));
        }
    }

    return maxGold;
};

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

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

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

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

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

😎 Решение:

var maxSubarraySumCircular = function(nums) {
    const kadane = (arr) => {
        let currentSum = arr[0], maxSum = arr[0];
        for (let i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    };

    const maxKadane = kadane(nums);
    const totalSum = nums.reduce((a, b) => a + b, 0);
    const minKadane = kadane(nums.map(num => -num));

    return Math.max(maxKadane, totalSum + minKadane === 0 ? maxKadane : totalSum + minKadane);
};

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

Задача: 531. Lonely Pixel I
Сложность: medium

Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей.
Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей.

Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

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

1⃣ Подсчёт количества чёрных пикселей в строках и столбцах:
Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1.

2⃣ Поиск одиночных чёрных пикселей:
Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1.

3⃣ Возврат результата:
Верните answer.

😎 Решение:

var findLonelyPixel = function(picture) {
    let n = picture.length;
    let m = picture[0].length;
    
    let rowCount = new Array(n).fill(0);
    let columnCount = new Array(m).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (picture[i][j] === 'B') {
                rowCount[i]++;
                columnCount[j]++;
            }
        }
    }
    
    let answer = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (picture[i][j] === 'B' && rowCount[i] === 1 && columnCount[j] === 1) {
                answer++;
            }
        }
    }
    
    return answer;
};

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

Задача: 191. Number of 1 Bits
Сложность: easy

Напишите функцию, которая принимает бинарное представление положительного целого числа и возвращает количество установленных битов (также известных как вес Хэмминга).

Пример:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

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

1️⃣Решение простое: проверяем каждый из 32 битов числа. Если бит равен 1, увеличиваем количество 1-битов на единицу.

2️⃣Для проверки i-го бита числа используем битовую маску. Начинаем с маски m=1, так как двоичное представление 1 это 0000 0000 0000 0000 0000 0000 0000 0001. Логическое И между любым числом и маской 1 дает нам младший бит этого числа.

3️⃣Для проверки следующего бита сдвигаем маску влево на один:
0000 0000 0000 0000 0000 0000 0000 0010 и так далее.

😎 Решение:

function hammingWeight(n) {
    let bits = 0;
    let mask = 1;
    for (let i = 0; i < 32; i++) {
        if ((n & mask) !== 0) {
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

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

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

var colorBorder = function(grid, row, col, color) {
    const m = grid.length, n = grid[0].length;
    const originalColor = grid[row][col];
    const visited = new Array(m).fill(null).map(() => new Array(n).fill(false));
    const borders = [];

    const dfs = (r, c) => {
        visited[r][c] = true;
        let isBorder = false;
        for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                if (!visited[nr][nc]) {
                    if (grid[nr][nc] === originalColor) {
                        dfs(nr, nc);
                    } else {
                        isBorder = true;
                    }
                }
            } else {
                isBorder = true;
            }
        }
        if (isBorder || r === 0 || r === m - 1 || c === 0 || c === n - 1) {
            borders.push([r, c]);
        }
    };

    dfs(row, col);
    for (const [r, c] of borders) {
        grid[r][c] = color;
    }

    return grid;
};

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

Задача: 204. Count Primes
Сложность: medium

Дано целое число n, верните количество простых чисел, которые строго меньше n.

Пример:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

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

1️⃣Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу.

2️⃣Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само число p должно быть простым). Найдите наименьшее число в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2.

3️⃣Когда алгоритм завершится, все оставшиеся числа, которые не отмечены, являются простыми.

😎 Решение:

class Solution {
    countPrimes(n) {
        if (n <= 2) {
            return 0;
        }

        let numbers = new Array(n).fill(true);
        for (let p = 2; p <= Math.sqrt(n); ++p) {
            if (numbers[p]) {
                for (let j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }

        let numberOfPrimes = 0;
        for (let i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }

        return numberOfPrimes;
    }
}

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

Задача: 245. Shortest Word Distance II
Сложность: medium

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.
Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

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

1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3️⃣Верните значение переменной shortestDistance.

😎 Решение:

class Solution {
    shortestWordDistance(wordsDict, word1, word2) {
        const indices1 = [];
        const indices2 = [];
        wordsDict.forEach((word, i) => {
            if (word === word1) {
                indices1.push(i);
            }
            if (word === word2) {
                indices2.push(i);
            }
        });

        let shortestDistance = Infinity;
        indices1.forEach(index => {
            const x = indices2.findIndex(i => i > index);
            if (x !== -1) {
                shortestDistance = Math.min(shortestDistance, indices2[x] - index);
            }
            if (x > 0 && indices2[x - 1] !== index) {
                shortestDistance = Math.min(shortestDistance, index - indices2[x - 1]);
            }
        });
        return shortestDistance;
    }
}

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

Задача: 300. Longest Increasing Subsequence
Сложность: medium

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

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

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

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


2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).


3⃣Верните максимальное значение из dp.

😎 Решение:

function lengthOfLIS(nums) {
  if (nums.length === 0) {
    return 0;
  }

  const dp = Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

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

Задача: 1207. Unique Number of Occurrences
Сложность: easy

Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

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

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

var uniqueOccurrences = function(arr) {
    let freq = new Map();
    for (let num of arr) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    let freqSet = new Set(freq.values());
    return freq.size === freqSet.size;
};

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

var flipLights = function(n, m) {
    let seen = new Set();
    n = Math.min(n, 6);
    let shift = Math.max(0, 6 - n);
    for (let cand = 0; cand < 16; ++cand) {
        let bcount = cand.toString(2).split('1').length - 1;
        if (bcount % 2 == m % 2 && bcount <= m) {
            let lights = 0;
            if ((cand >> 0) & 1) lights ^= 0b111111 >> shift;
            if ((cand >> 1) & 1) lights ^= 0b010101 >> shift;
            if ((cand >> 2) & 1) lights ^= 0b101010 >> shift;
            if ((cand >> 3) & 1) lights ^= 0b100100 >> shift;
            seen.add(lights);
        }
    }
    return seen.size;
}

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