Задача: 661. Image Smoother
Сложность: easy

Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.

Пример:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

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

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

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

3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.

😎 Решение:

var imageSmoother = function(img) {
    let m = img.length, n = img[0].length;
    let result = Array.from({ length: m }, () => Array(n).fill(0));
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let count = 0, total = 0;
            for (let ni = Math.max(0, i - 1); ni <= Math.min(m - 1, i + 1); ni++) {
                for (let nj = Math.max(0, j - 1); nj <= Math.min(n - 1, j + 1); nj++) {
                    total += img[ni][nj];
                    count++;
                }
            }
            result[i][j] = Math.floor(total / count);
        }
    }
    
    return result;
};

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

Задача: 772. Basic Calculator III
Сложность: medium

Реализуйте базовый калькулятор для вычисления простого строкового выражения.
Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.
Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval().

Пример:

Input: s = "1+1"
Output: 2

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

1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@".

2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+".

3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке.

😎 Решение:

class Solution {
    evaluate(operator, first, second) {
        const x = parseInt(first)
        const y = parseInt(second)
        let res = 0

        if (operator === '+') {
            res = x
        } else if (operator === '-') {
            res = -x
        } else if (operator === '*') {
            res = x * y
        } else {
            res = Math.trunc(x / y)
        }

        return res.toString()
    }

    calculate(s) {
        const stack = []
        let curr = ""
        let previousOperator = '+'
        s += "@"
        const operators = new Set(["+", "-", "*", "/"])

        for (const c of s) {
            if (/\d/.test(c)) {
                curr += c
            } else if (c === '(') {
                stack.push(previousOperator)
                previousOperator = '+'
            } else {
                if (previousOperator === '*' || previousOperator === '/') {
                    stack.push(this.evaluate(previousOperator, stack.pop(), curr))
                } else {
                    stack.push(this.evaluate(previousOperator, curr, "0"))
                }

                curr = ""
                previousOperator = c
                if (c === ')') {
                    let currentTerm = 0
                    while (!operators.has(stack[stack.length - 1])) {
                        currentTerm += parseInt(stack.pop())
                    }

                    curr = currentTerm.toString()
                    previousOperator = stack.pop()
                }
            }
        }

        let ans = 0
        for (const num of stack) {
            ans += parseInt(num)
        }

        return ans
    }
}

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

Задача: 977. Squares of a Sorted Array
Сложность: easy

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

Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

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

1⃣Создайте массив квадратов каждого элемента.

2⃣Отсортируйте массив квадратов.

3⃣Верните отсортированный массив квадратов.

😎 Решение:

class Solution {
    sortedSquares(nums) {
        const ans = nums.map(num => num * num)
        ans.sort((a, b) => a - b)
        return ans
    }
}

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

Сложность: medium
Задача: 378. Kth Smallest Element in a Sorted Matrix

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

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

😎 Решение:

class Solution {
    dfs(word, length, visited, dictionary) {
        if (length === word.length) {
            return true;
        }
        if (visited[length]) {
            return false;
        }
        visited[length] = true;
        for (let i = word.length - (length === 0 ? 1 : 0); i > length; i--) {
            if (dictionary.has(word.slice(length, i)) && this.dfs(word, i, visited, dictionary)) {
                return true;
            }
        }
        return false;
    }

    findAllConcatenatedWordsInADict(words) {
        const dictionary = new Set(words);
        const answer = [];
        for (const word of words) {
            const visited = Array(word.length).fill(false);
            if (this.dfs(word, 0, visited, dictionary)) {
                answer.push(word);
            }
        }
        return answer;
    }
}

const solution = new Solution();
const words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
console.log(solution.findAllConcatenatedWordsInADict(words));

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

Задача: 895. Maximum Frequency Stack
Сложность: hard

Разработайте структуру данных, похожую на стек, чтобы заталкивать элементы в стек и вытаскивать из него самый частый элемент. Реализуйте класс FreqStack: FreqStack() строит пустой стек частот. void push(int val) заталкивает целое число val на вершину стека. int pop() удаляет и возвращает самый частый элемент в стеке. Если есть равенство в выборе самого частого элемента, то удаляется и возвращается элемент, который ближе всего к вершине стека.

Пример:

Input
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output
[null, null, null, null, null, null, null, 5, 7, 5, 4]

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

1⃣Создать два словаря: freq для хранения частоты каждого элемента и group для хранения стека элементов для каждой частоты.

2⃣При добавлении элемента увеличивать его частоту в freq и добавлять его в стек соответствующей частоты в group.

3⃣При извлечении элемента найти максимальную частоту, удалить элемент из стека соответствующей частоты и уменьшить его частоту в freq. Если стек для данной частоты становится пустым, удалить его.

😎 Решение:

var FreqStack = function() {
    this.freq = new Map();
    this.group = new Map();
    this.maxfreq = 0;
};

FreqStack.prototype.push = function(val) {
    let f = (this.freq.get(val) || 0) + 1;
    this.freq.set(val, f);
    if (f > this.maxfreq) {
        this.maxfreq = f;
        this.group.set(f, []);
    }
    this.group.get(f).push(val);
};

FreqStack.prototype.pop = function() {
    let val = this.group.get(this.maxfreq).pop();
    this.freq.set(val, this.freq.get(val) - 1);
    if (this.group.get(this.maxfreq).length === 0) {
        this.maxfreq--;
    }
    return val;
};

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

Задача: 28. Find the Index of the First Occurrence in a String
Сложность: easy

Даны две строки: haystack и needle. Нужно вернуть индекс первого вхождения строки needle в строку haystack.
Если needle не найдена — вернуть -1.

Пример:

Input: haystack = "sadbutsad", needle = "sad"  
Output: 0

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

1️⃣ Если needle пустая строка — возвращаем 0, так как пустая строка входит в любую строку.

2️⃣ Проходим по haystack от начала до позиции, где ещё может поместиться needle, и на каждой итерации извлекаем подстроку такой же длины.

3️⃣ Если подстрока равна needle, возвращаем текущий индекс. Если не нашли до конца — возвращаем -1.

😎 Решение:

function strStr(haystack, needle) {
  if (needle === "") return 0;

  for (let i = 0; i <= haystack.length - needle.length; i++) {
    let haySlice = haystack.slice(i, i + needle.length);
    if (haySlice === needle) {
      return i;
    }
  }

  return -1;
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

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

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.

😎 Решение:

var shortestPathBinaryMatrix = function(grid) {
    if (grid[0][0] !== 0 || grid[grid.length - 1][grid[0].length - 1] !== 0) {
        return -1;
    }

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

    const queue = [[0, 0]];
    grid[0][0] = 1;

    while (queue.length > 0) {
        const [row, col] = queue.shift();
        const distance = grid[row][col];
        if (row === grid.length - 1 && col === grid[0].length - 1) {
            return distance;
        }
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            if (newRow >= 0 && newCol >= 0 && newRow < grid.length && newCol < grid[0].length && grid[newRow][newCol] === 0) {
                queue.push([newRow, newCol]);
                grid[newRow][newCol] = distance + 1;
            }
        }
    }
    return -1;
};

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

Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard

Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.
Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева.
Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.

Пример:

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

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

1⃣Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".

2⃣Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").

3⃣Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.

😎 Решение:

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Codec {
    rserialize(root, str) {
        if (root === null) {
            str.push("null");
        } else {
            str.push(String(root.val));
            this.rserialize(root.left, str);
            this.rserialize(root.right, str);
        }
    }

    serialize(root) {
        const str = [];
        this.rserialize(root, str);
        return str.join(",");
    }

    rdeserialize(data) {
        if (data[0] === "null") {
            data.shift();
            return null;
        }

        const root = new TreeNode(Number(data.shift()));
        root.left = this.rdeserialize(data);
        root.right = this.rdeserialize(data);
        return root;
    }

    deserialize(data) {
        const dataArray = data.split(",");
        return this.rdeserialize(dataArray);
    }
}

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

Задача: 771. Jewels and Stones
Сложность: medium

Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.
Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".

Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям.

2⃣Инициализируйте счетчик для подсчета количества камней, которые являются драгоценностями. Пройдите по каждому символу в строке stones и проверьте, содержится ли этот символ в множестве jewels.

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

😎 Решение:

class Solution {
    numJewelsInStones(J, S) {
        let ans = 0
        for (const s of S) {
            for (const j of J) {
                if (j === s) {
                    ans++
                    break
                }
            }
        }
        return ans
    }
}

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

Задача: 111. Minimum Depth of Binary Tree
Сложность: easy

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

Минимальная глубина - это количество узлов вдоль самого короткого пути от корневого узла до ближайшего листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 2

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

1️⃣Мы будем использовать метод обхода в глубину (dfs) с корнем в качестве аргумента.
Базовое условие рекурсии: это для узла NULL, в этом случае мы должны вернуть 0.

2️⃣Если левый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для правого ребенка корневого узла, что равно 1 + dfs(root.right).

3️⃣Если правый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для левого ребенка корневого узла, что равно 1 + dfs(root.left). Если оба ребенка не являются NULL, тогда вернуть 1 + min(dfs(root.left), dfs(root.right)).

😎 Решение:

var minDepth = function (root) {
    function dfs(root) {
        if (root === null) {
            return 0;
        }
        if (root.left === null) {
            return 1 + dfs(root.right);
        } else if (root.right === null) {
            return 1 + dfs(root.left);
        }
        return 1 + Math.min(dfs(root.left), dfs(root.right));
    }
    return dfs(root);
};

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

Задача: 851. Loud and Rich
Сложность: medium

Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.

Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).

Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.

Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

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

1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов.

2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person.

3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного.

😎 Решение:

var loudAndRich = function(richer, quiet) {
    let N = quiet.length;
    let graph = Array.from({ length: N }, () => []);
    let answer = Array(N).fill(-1);

    for (let [u, v] of richer) {
        graph[v].push(u);
    }

    let dfs = function(node) {
        if (answer[node] === -1) {
            answer[node] = node;
            for (let child of graph[node]) {
                let cand = dfs(child);
                if (quiet[cand] < quiet[answer[node]]) {
                    answer[node] = cand;
                }
            }
        }
        return answer[node];
    };

    for (let node = 0; node < N; node++) {
        dfs(node);
    }

    return answer;
};

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

Задача: 790. Domino and Tromino Tiling
Сложность: medium

У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.

Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

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

Пример:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

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

1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).

2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас.

3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.

😎 Решение:

const MOD = 1_000_000_007;
const fCache = new Map();
const pCache = new Map();

function p(n) {
    if (pCache.has(n)) {
        return pCache.get(n);
    }
    if (n === 2) {
        return 1;
    }
    const result = (p(n - 1) + f(n - 2)) % MOD;
    pCache.set(n, result);
    return result;
}

function f(n) {
    if (fCache.has(n)) {
        return fCache.get(n);
    }
    if (n <= 2) {
        return n;
    }
    const result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
    fCache.set(n, result);
    return result;
}

function numTilings(n) {
    return f(n);
}

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

Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

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

😎 Решение:

class Solution {
    calcEquation(equations, values, queries) {
        const graph = new Map();

        for (let i = 0; i < equations.length; i++) {
            const [A, B] = equations[i];
            const value = values[i];
            if (!graph.has(A)) graph.set(A, new Map());
            if (!graph.has(B)) graph.set(B, new Map());
            graph.get(A).set(B, value);
            graph.get(B).set(A, 1.0 / value);
        }

        const bfs = (start, end) => {
            if (!graph.has(start) || !graph.has(end)) return -1.0;
            const q = [[start, 1.0]];
            const visited = new Set();
            
            while (q.length) {
                const [current, curProduct] = q.shift();
                if (current === end) return curProduct;
                visited.add(current);
                for (const [neighbor, value] of graph.get(current).entries()) {
                    if (!visited.has(neighbor)) {
                        q.push([neighbor, curProduct * value]);
                    }
                }
            }
            return -1.0;
        };

        return queries.map(([C, D]) => bfs(C, D));
    }
}

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣ Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣ Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣ Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

var countBits = function(num) {
    let ans = new Array(num + 1).fill(0);
    for (let x = 1; x <= num; x++) {
        ans[x] = ans[x & (x - 1)] + 1;
    }
    return ans;
};

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

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

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

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
    arraysIntersection(arr1, arr2, arr3) {
        const counter = new Map();
        
        for (const e of arr1) counter.set(e, (counter.get(e) || 0) + 1);
        for (const e of arr2) counter.set(e, (counter.get(e) || 0) + 1);
        for (const e of arr3) counter.set(e, (counter.get(e) || 0) + 1);

        const ans = [];
        for (const [key, value] of counter) {
            if (value === 3) ans.push(key);
        }

        return ans;
    }
}

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

Задача: 776. Split BST
Сложность: medium

Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.
Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.
Верните массив из двух корней двух поддеревьев в порядке.

Пример:

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

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

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

2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

😎 Решение:

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var splitBST = function(root, target) {
    if (!root) {
        return [null, null];
    }

    if (root.val > target) {
        let left = splitBST(root.left, target);
        root.left = left[1];
        return [left[0], root];
    } else {
        let right = splitBST(root.right, target);
        root.right = right[0];
        return [root, right[1]];
    }
};

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

Задача: 495. Teemo Attacking
Сложность: easy

Наш герой Тимо атакует врага Эшу ядовитыми атаками! Когда Тимо атакует Эшу, она оказывается отравленной на ровно duration секунд. Более формально, атака в секунду t означает, что Эша будет отравлена в течение интервала времени [t, t + duration - 1] включительно. Если Тимо атакует снова до окончания эффекта яда, таймер для него сбрасывается, и эффект яда закончится через duration секунд после новой атаки.
Вам дано неубывающее целое число timeSeries, где timeSeries[i] обозначает, что Тимо атакует Эшу во вторую timeSeries[i], и целое число duration.
Верните общее количество секунд, в течение которых Эша была отравлена.

Пример:

Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

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

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

2⃣Итерация
Пройдите по всем элементам массива timeSeries, кроме последнего. На каждой итерации добавьте к total минимальное значение между длительностью интервала и временем действия яда duration.

3⃣Возврат результата
Верните сумму total и duration, чтобы учесть последнюю атаку.

😎 Решение:

class Solution {
    findPoisonedDuration(timeSeries, duration) {
        const n = timeSeries.length;
        if (n === 0) return 0;

        let total = 0;
        for (let i = 0; i < n - 1; i++) {
            total += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
        }
        return total + duration;
    }
}

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

Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

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

1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

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

😎 Решение:

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

var isCousins = function(root, x, y) {
    let parentX = null, parentY = null;
    let depthX = -1, depthY = -1;
    
    function dfs(node, parent, depth) {
        if (!node) return;
        if (node.val === x) {
            parentX = parent;
            depthX = depth;
        } else if (node.val === y) {
            parentY = parent;
            depthY = depth;
        } else {
            dfs(node.left, node, depth + 1);
            dfs(node.right, node, depth + 1);
        }
    }
    
    dfs(root, null, 0);
    return depthX === depthY && parentX !== parentY;
};

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

Задача: 370. Range Addition
Сложность: medium

Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].
У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.
Верните arr после применения всех обновлений.

Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

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

1⃣Для каждого обновления (start, end, val) выполните две операции:
Увеличьте значение в позиции start на val: arr[start] = arr[start] + val.
Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val.

2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0).

3⃣Верните обновленный массив arr.

😎 Решение:

function getModifiedArray(length, updates) {
    let result = new Array(length).fill(0);

    for (let update of updates) {
        let [start, end, val] = update;
        result[start] += val;
        if (end + 1 < length) {
            result[end + 1] -= val;
        }
    }

    for (let i = 1; i < length; i++) {
        result[i] += result[i - 1];
    }

    return result;
}

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