Задача: 366. Find Leaves of Binary Tree
Сложность: medium

Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.

Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

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

1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

3⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

#include <vector>
#include <algorithm>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    vector<pair<int, int>> pairs;

    int getHeight(TreeNode* node) {
        if (!node) return -1;
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        int currHeight = max(leftHeight, rightHeight) + 1;
        pairs.push_back({currHeight, node->val});
        return currHeight;
    }

public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        getHeight(root);
        sort(pairs.begin(), pairs.end());
        vector<vector<int>> solution;
        int currentHeight = -1;
        for (const auto& p : pairs) {
            if (p.first != currentHeight) {
                solution.push_back(vector<int>());
                currentHeight = p.first;
            }
            solution.back().push_back(p.second);
        }
        return solution;
    }
};

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

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One
Сложность: medium

Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.

Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

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

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

2⃣Повторяйте операции, пока длина строки s больше 1: Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит. В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию.

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

😎 Решение:

class Solution {
public:
    int numSteps(string s) {
        int operations = 0;
        while (s.size() > 1) {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int i = s.size() - 1;
                while (i >= 0 && s[i] == '1') {
                    s[i] = '0';
                    i--;
                }
                if (i < 0) {
                    s.insert(s.begin(), '1');
                } else {
                    s[i] = '1';
                }
            }
            operations++;
        }
        return operations;
    }
};

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

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

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Solution {
public:
    int treeDiameter(vector<vector<int>>& edges) {
        if (edges.empty()) return 0;

        unordered_map<int, vector<int>> graph;
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        int farthest_node = 0;
        auto dfs = [&](int node, int parent) {
            int max_depth = 0;
            for (int neighbor : graph[node]) {
                if (neighbor != parent) {
                    int depth = dfs(neighbor, node);
                    if (depth + 1 > max_depth) {
                        max_depth = depth + 1;
                        farthest_node = neighbor;
                    }
                }
            }
            return max_depth;
        };

        dfs(0, -1);
        int start_node = farthest_node;

        dfs(start_node, -1);
        return dfs(farthest_node, -1);
    }
};

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

Вам дан массив цен, где prices[i] — цена акции в i-й день. Можно совершить не более двух транзакций. Найдите максимальную прибыль.

Пример:

Input: prices = [3,3,5,0,0,3,1,4] Output: 6

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

1⃣Проходим массив слева направо и сохраняем в leftProfits[i] максимальную прибыль от одной транзакции от начала до дня i.

2⃣Проходим массив справа налево и сохраняем в rightProfits[i] максимальную прибыль от одной транзакции от дня i до конца.

3⃣Для каждой точки разбиения i считаем сумму leftProfits[i] + rightProfits[i+1], и выбираем максимум из всех таких сумм.

😎 Решение:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length = prices.size();
        if (length <= 1) return 0;

        int leftMin = prices[0];
        int rightMax = prices[length - 1];

        vector<int> leftProfits(length, 0);
        vector<int> rightProfits(length + 1, 0);

        for (int l = 1; l < length; ++l) {
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = min(leftMin, prices[l]);

            int r = length - 1 - l;
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r]);
            rightMax = max(rightMax, prices[r]);
        }

        int maxProfit = 0;
        for (int i = 0; i < length; ++i) {
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1]);
        }

        return maxProfit;
    }
};

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

Задача: 304. Range Sum Query 2D - Immutable
Сложность: medium

Дана двумерная матрица matrix. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Реализуйте класс NumMatrix:
- NumMatrix(int[][] matrix) Инициализирует объект целочисленной матрицей matrix.- int sumRegion(int row1, int col1, int row2, int col2) Возвращает сумму элементов матрицы внутри прямоугольника, определенного его верхним левым углом (row1, col1) и нижним правым углом (row2, col2).
Необходимо разработать алгоритм, где метод sumRegion работает за O(1) по времени.

Пример:

Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

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

1⃣Инициализация:
Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями.

2⃣Предварительное вычисление сумм:
Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени.

😎 Решение:

class NumMatrix {
private:
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        int m = matrix.size(), n = matrix[0].size();
        dp = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
};

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60
Сложность: medium

Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0.

Пример:

Input: time = [30,20,150,100,40]
Output: 3

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

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

2⃣Подсчет пар:
Пройдитесь по каждой песне в списке и для каждого элемента:
Вычислите остаток от деления времени песни на 60.
Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0).
Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0).
Обновите массив остатков, увеличивая количество песен с текущим остатком на 1.

3⃣Возврат результата:
Верните общее количество пар.

😎 Решение:

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        vector<int> remainders(60, 0);
        int count = 0;
        
        for (int t : time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
};

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

Задача: 372. Super Pow
Сложность: medium

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

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

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        const int MOD = 1337;

        auto powmod = [](int x, int y, int mod) -> int {
            int result = 1;
            x = x % mod;
            while (y > 0) {
                if (y % 2 == 1) {
                    result = (result * x) % mod;
                }
                y = y / 2;
                x = (x * x) % mod;
            }
            return result;
        };

        function<int(int, vector<int>&, int)> superPowHelper = [&](int a, vector<int>& b, int mod) -> int {
            if (b.empty()) {
                return 1;
            }
            int last_digit = b.back();
            b.pop_back();
            int part1 = powmod(a, last_digit, mod);
            int part2 = powmod(superPowHelper(a, b, mod), 10, mod);
            return (part1 * part2) % mod;
        };

        return superPowHelper(a, b, MOD);
    }
};

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

Задача: 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.

😎 Решение:

vector<int> getModifiedArray(int length, vector<vector<int> > updates)
{
    vector<int> result(length, 0);

    for (auto& tuple : updates) {
        int start = tuple[0], end = tuple[1], val = tuple[2];

        for (int i = start; i <= end; i++) {
            result[i] += val;
        }
    }

    return result;
}

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

Задача: 980. Unique Paths III
Сложность: hard

Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть:

1, представляющая начальную клетку. Существует ровно одна начальная клетка.
2, представляющая конечную клетку. Существует ровно одна конечная клетка.
0, представляющая пустые клетки, по которым можно ходить.
-1, представляющая препятствия, по которым нельзя ходить.
Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз.

Пример:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

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

1⃣Как видно, метод обратного отслеживания (backtracking) является методологией для решения определенного типа задач.

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

3⃣Здесь мы просто покажем один пример реализации, следуя псевдокоду, показанному в разделе интуиции.

😎 Решение:

class Solution {
public:
    int rows, cols;
    vector<vector<int>> grid;
    int path_count;

    void backtrack(int row, int col, int remain) {
        if (grid[row][col] == 2 && remain == 1) {
            path_count += 1;
            return;
        }

        int temp = grid[row][col];
        grid[row][col] = -4;
        remain -= 1;

        int row_offsets[4] = {0, 0, 1, -1};
        int col_offsets[4] = {1, -1, 0, 0};
        for (int i = 0; i < 4; ++i) {
            int next_row = row + row_offsets[i];
            int next_col = col + col_offsets[i];

            if (0 > next_row || next_row >= rows || 0 > next_col || next_col >= cols)
                continue;

            if (grid[next_row][next_col] < 0)
                continue;

            backtrack(next_row, next_col, remain);
        }

        grid[row][col] = temp;
    }

    int uniquePathsIII(vector<vector<int>>& grid) {
        int non_obstacles = 0, start_row = 0, start_col = 0;

        rows = grid.size();
        cols = grid[0].size();
        this->grid = grid;

        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col) {
                int cell = grid[row][col];
                if (cell >= 0)
                    non_obstacles += 1;
                if (cell == 1) {
                    start_row = row;
                    start_col = col;
                }
            }

        path_count = 0;

        backtrack(start_row, start_col, non_obstacles);

        return path_count;
    }
};

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

Задача: 286. Walls and Gates
Сложность: medium

Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями:
-1: Стена или препятствие.
0: Ворота.
INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647.
Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF.

Пример:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

1⃣Обход всех комнат:
Пройдите через каждую клетку сетки, инициализируя очередь для BFS. Если клетка содержит ворота (0), добавьте её в очередь.

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

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

😎 Решение:

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty()) return;

        int m = rooms.size();
        int n = rooms[0].size();
        queue<pair<int, int>> q;
        const int INF = 2147483647;
        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto& [dx, dy] : directions) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
                    rooms[nx][ny] = rooms[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
};

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

Задача: 98. Validate Binary Search Tree
Сложность: medium

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

Пример:

Input: root = [2,1,3]
Output: true

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

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

2⃣При проходе вниз:
левый потомок должен быть в диапазоне [min, node.val)
правый потомок должен быть в диапазоне (node.val, max]

3⃣Если в процессе обхода найден узел, нарушающий ограничения диапазона —
дерево не является BST, возвращаем false.

😎 Решение:

class Solution {
private:
    stack<TreeNode*> stk, lower_limits, upper_limits;

public:
    void update(TreeNode* node, TreeNode* low, TreeNode* high) {
        stk.push(node);
        lower_limits.push(low);
        upper_limits.push(high);
    }

    bool isValidBST(TreeNode* root) {
        TreeNode* low = nullptr;
        TreeNode* high = nullptr;
        update(root, low, high);

        while (!stk.empty()) {
            root = stk.top(); stk.pop();
            low = lower_limits.top(); lower_limits.pop();
            high = upper_limits.top(); upper_limits.pop();

            if (root == nullptr) continue;

            if ((low && root->val <= low->val) || (high && root->val >= high->val))
                return false;

            update(root->right, root, high);
            update(root->left, low, root);
        }

        return true;
    }
};

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

Задача: 978. Longest Turbulent Subarray
Сложность: medium

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

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

Более формально, подмассив [arr[i], arr[i + 1], ..., arr[j]] массива arr считается турбулентным тогда и только тогда, когда:

Для всех i <= k < j:
arr[k] > arr[k + 1], когда k нечетное, и
arr[k] < arr[k + 1], когда k четное.
Или, для всех i <= k < j:
arr[k] > arr[k + 1], когда k четное, и
arr[k] < arr[k + 1], когда k нечетное.

Пример:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

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

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

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

3⃣Повторяйте шаг 2 до конца массива и верните максимальную длину турбулентного подмассива.

😎 Решение:

class Solution {
public:
    int maxTurbulenceSize(vector<int>& A) {
        int N = A.size();
        int ans = 1;
        int anchor = 0;

        for (int i = 1; i < N; ++i) {
            int c = (A[i - 1] > A[i]) - (A[i - 1] < A[i]);
            if (c == 0) {
                anchor = i;
            } else if (i == N - 1 || c * ((A[i] > A[i + 1]) - (A[i] < A[i + 1])) != -1) {
                ans = max(ans, i - anchor + 1);
                anchor = i;
            }
        }

        return ans;
    }
};

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

Ура, друзья! Изиоффер переходит в публичное бета-тестирование!

🎉 Что нового:
🟢Анализ IT собеседований на основе 4500+ реальных интервью
🟢Вопросы из собеседований с вероятностью встречи
🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов
🟢Пример лучшего ответа
🟢Задачи из собеседований
🟢Тестовые задания
🟢Примеры собеседований
🟢Фильтрация всего контента по грейдам, компаниям
🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек
🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро)
🟢Автоотклики на HeadHunter
🟢Закрытое сообщество easyoffer


💎 Акция в честь открытия для первых 500 покупателей:
🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽)

🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 1030. Matrix Cells in Distance Order
Сложность: easy

Вам даны четыре целых числа row, cols, rCenter и cCenter. Имеется матрица rows x cols, и вы находитесь на ячейке с координатами (rCenter, cCenter). Верните координаты всех ячеек в матрице, отсортированные по их расстоянию от (rCenter, cCenter) от наименьшего расстояния до наибольшего. Вы можете вернуть ответ в любом порядке, удовлетворяющем этому условию. Расстояние между двумя ячейками (r1, c1) и (r2, c2) равно |r1 - r2| + |c1 - c2|.

Пример:

Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]

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

1⃣Инициализация и вычисление расстояний:
Создайте список для хранения всех координат ячеек в матрице.
Вычислите расстояние Манхэттена от каждой ячейки до центра и добавьте пару (расстояние, координаты) в список.

2⃣Сортировка списка:
Отсортируйте список по расстоянию в порядке возрастания.

3⃣Извлечение координат:
Извлеките координаты из отсортированного списка и верните их.

😎 Решение:

vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
    vector<vector<int>> cells;
    
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) {
            cells.push_back({abs(r - rCenter) + abs(c - cCenter), r, c});
        }
    }
    
    sort(cells.begin(), cells.end());
    
    vector<vector<int>> result;
    for (const auto& cell : cells) {
        result.push_back({cell[1], cell[2]});
    }
    
    return result;
}

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

Задача: 823. Binary Trees With Factors
Сложность: medium

Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1.

Мы создаем бинарное дерево, используя эти числа, и каждое число может быть использовано любое количество раз. Значение каждого не листового узла должно быть равно произведению значений его дочерних узлов.

Верните количество бинарных деревьев, которые мы можем создать. Ответ может быть слишком большим, поэтому верните ответ по модулю 10^9 + 7.

Пример:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

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

1⃣Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование.

2⃣Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k.

3⃣После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением.

😎 Решение:

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& A) {
        const int MOD = 1'000'000'007;
        sort(A.begin(), A.end());
        vector<long> dp(A.size(), 1);
        unordered_map<int, int> index;
        
        for (int i = 0; i < A.size(); ++i) {
            index[A[i]] = i;
        }
        
        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (A[i] % A[j] == 0) {
                    int right = A[i] / A[j];
                    if (index.find(right) != index.end()) {
                        dp[i] = (dp[i] + dp[j] * dp[index[right]]) % MOD;
                    }
                }
            }
        }
        
        long result = 0;
        for (long x : dp) {
            result = (result + x) % MOD;
        }
        return result;
    }
};

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

Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

1⃣Создайте функцию для вычисления оценки слова.

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

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

😎 Решение:

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        int maxScore = 0;
        unordered_map<char, int> letterCount;
        for (char ch : letters) {
            letterCount[ch]++;
        }

        int n = words.size();
        for (int i = 1; i < (1 << n); i++) {
            int currScore = 0;
            unordered_map<char, int> usedLetters;
            bool valid = true;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    for (char ch : words[j]) {
                        usedLetters[ch]++;
                        if (usedLetters[ch] > letterCount[ch]) {
                            valid = false;
                            break;
                        }
                        currScore += score[ch - 'a'];
                    }
                }
                if (!valid) break;
            }
            if (valid) {
                maxScore = max(maxScore, currScore);
            }
        }

        return maxScore;
    }
};

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

Задача: 438. Find All Anagrams in a String
Сложность: medium

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

Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

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

1⃣Построить эталонный счетчик pCount для строки p.

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

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int ns = s.length(), np = p.length();
        if (ns < np) return {};

        unordered_map<char, int> pCount, sCount;

        for (char ch : p) {
            pCount[ch]++;
        }

        vector<int> output;

        for (int i = 0; i < ns; ++i) {
            char ch = s[i];
            sCount[ch]++;

            if (i >= np) {
                char leftChar = s[i - np];
                if (sCount[leftChar] == 1) {
                    sCount.erase(leftChar);
                } else {
                    sCount[leftChar]--;
                }
            }

            if (pCount == sCount) {
                output.push_back(i - np + 1);
            }
        }
        return output;
    }
};

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

Задача: 735. Asteroid Collision
Сложность: medium

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

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

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

2⃣Пройдите по массиву астероидов: Если астероид движется вправо, добавьте его в стек. Если астероид движется влево, сравните его с последним астероидом в стеке (если он есть и движется вправо): Если движущийся вправо астероид больше, текущий взорвется. Если движущийся влево астероид больше, последний астероид в стеке взорвется, и продолжите сравнение. Если они одинакового размера, оба взорвутся.

3⃣Добавьте оставшиеся астероиды из стека и текущий астероид в результат.

😎 Решение:

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> stack;
        
        for (int asteroid : asteroids) {
            bool alive = true;
            while (alive && asteroid < 0 && !stack.empty() && stack.back() > 0) {
                int last = stack.back();
                stack.pop_back();
                if (last == -asteroid) {
                    alive = false;
                } else if (last > -asteroid) {
                    stack.push_back(last);
                    alive = false;
                }
            }
            if (alive) {
                stack.push_back(asteroid);
            }
        }
        
        return stack;
    }
};

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

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

Вам дана строка currentState, содержащая только символы '+' и '-'. Нужно вернуть все возможные состояния строки после одного допустимого хода, где один ход — это замена двух последовательных '++' на '--'.

Пример:

Input: currentState = "++++"
Output: ["--++", "+--+", "++--"]

👨‍💻 Алгоритм

1⃣Создайте пустой список nextPossibleStates, в который будем добавлять новые состояния строки после одного хода.

2⃣Пройдитесь по строке от index = 0 до length - 2
На каждом шаге проверьте, есть ли пара ++ на позиции index и index + 1
Если да — создайте новую строку, заменив эту пару на -- и добавьте результат в список.

3⃣После завершения цикла верните список nextPossibleStates.

😎 Решение

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> generatePossibleNextMoves(string currentState) {
        vector<string> nextPossibleStates;

        for (int index = 0; index < currentState.length() - 1; ++index) {
            if (currentState[index] == '+' && currentState[index + 1] == '+') {
                string nextState = currentState.substr(0, index) + "--" + currentState.substr(index + 2);
                nextPossibleStates.push_back(nextState);
            }
        }

        return nextPossibleStates;
    }
};

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

Задача: 1472. Design Browser History
Сложность: medium

У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории.

Реализуйте класс BrowserHistory:
BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера.
void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд.
string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов.
string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов.

Пример:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

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

1⃣Инициализация:
Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей.

2⃣Посещение URL:
Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future.

3⃣Навигация назад и вперед:
Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым.
Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым.

😎 Решение:

#include <stack>
#include <string>
using namespace std;

class BrowserHistory {
private:
    stack<string> history;
    stack<string> future;
    string current;

public:
    BrowserHistory(string homepage) {
        current = homepage;
    }
    
    void visit(string url) {
        history.push(current);
        current = url;
        while (!future.empty()) {
            future.pop();
        }
    }
    
    string back(int steps) {
        while (steps > 0 && !history.empty()) {
            future.push(current);
            current = history.top();
            history.pop();
            steps--;
        }
        return current;
    }
    
    string forward(int steps) {
        while (steps > 0 && !future.empty()) {
            history.push(current);
            current = future.top();
            future.pop();
            steps--;
        }
        return current;
    }
};

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