C/C++ | LeetCode

Задача: 1271. Hexspeak Сложность: easy Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR". Пример:

Input: num = "257"
Output: "IOI"

👨‍💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение:

class Solution {
public:
    string toHexString(string num) {
        stringstream ss;
        ss << hex << uppercase << stol(num);
        string hexStr = ss.str();
        for (char& c : hexStr) {
            if (c == '0') c = 'O';
            else if (c == '1') c = 'I';
            else if (string("ABCDEFIO").find(c) == string::npos) return "ERROR";
        }
        return hexStr;
    }
};

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

Задача: 422. Valid Word Square Сложность: easy Дан массив строк words, верните true, если он образует правильный квадрат слов. Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns). Пример:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

👨‍💻 Алгоритм: 1⃣Инициализируйте переменные: cols для максимальной длины слов в массиве, rows для количества строк в массиве words, и пустой массив newWords для хранения новых слов, представленных каждым столбцом. 2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false. 3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false. 😎 Решение:

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

class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        int cols = 0;
        int rows = words.size();
        vector<string> newWords;
        
        for (auto& word : words) {
            cols = max(cols, (int)word.size
        }

        if (cols != words[0].size() || rows != cols) {
            return false;
        }

        for (int col = 0; col < cols; ++col) {
            string newWord;
            for (int row = 0; row < rows; ++row) {
                if (col < words[row].size()) {
                    newWord += words[row][col];
                }
            }
            newWords.push_back(newWord);
        }

        return words == newWords;
    }
};

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

Задача: 245. Shortest Word Distance III Сложность: medium Пример:

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

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

class Solution {
public:
    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
        int idx1 = -1, idx2 = -1, minDist = INT_MAX;
        bool same = (word1 == word2);

        for (int i = 0; i < wordsDict.size(); ++i) {
            string word = wordsDict[i];

            if (word == word1) {
                if (same) {
                    if (idx1 != -1) {
                        minDist = min(minDist, i - idx1);
                    }
                    idx1 = i;
                } else {
                    idx1 = i;
                }
            } else if (word == word2) {
                idx2 = i;
            }

            if (idx1 != -1 && idx2 != -1 && !same) {
                minDist = min(minDist, abs(idx1 - idx2));
            }
        }

        return minDist;
    }
};

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

Задача: 505. The Maze II Сложность: medium В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление. Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, верните -1. Расстояние — это количество пройденных пустых пространств мячиком от начальной позиции (исключительно) до пункта назначения (включительно). Предположим, что границы лабиринта — это стены. В примере ниже они не указаны. Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

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

#include <vector>
#include <queue>
#include <array>

using namespace std;

class Solution {
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<int>> distance(m, vector<int>(n, INT_MAX));
        distance[start[0]][start[1]] = 0;
        array<array<int, 2>, 4> directions = {{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}};
        queue<array<int, 2>> q;
        q.push({start[0], start[1]});
        
        while (!q.empty()) {
            auto s = q.front(); q.pop();
            for (auto& dir : directions) {
                int x = s[0] + dir[0], y = s[1] + dir[1], count = 0;
                while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                    count++;
                }
                x -= dir[0];
                y -= dir[1];
                if (distance[s[0]][s[1]] + count < distance[x][y]) {
                    distance[x][y] = distance[s[0]][s[1]] + count;
                    q.push({x, y});
                }
            }
        }
        
        return distance[destination[0]][destination[1]] == INT_MAX ? -1 : distance[destination[0]][destination[1]];
    }
};

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

Задача: 1129. Shortest Path with Alternating Colors Сложность: medium Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра. Вам даны два массива redEdges и blueEdges, где: redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj. Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует. Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

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

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        unordered_map<int, vector<pair<int, int>>> adj;
        for (const auto& edge : redEdges) {
            adj[edge[0]].emplace_back(edge[1], 0);
        }
        for (const auto& edge : blueEdges) {
            adj[edge[0]].emplace_back(edge[1], 1);
        }

        vector<int> answer(n, -1);
        vector<vector<bool>> visit(n, vector<bool>(2, false));
        queue<tuple<int, int, int>> q;
        q.emplace(0, 0, -1);
        answer[0] = 0;
        visit[0][0] = visit[0][1] = true;

        while (!q.empty()) {
            auto [node, steps, prevColor] = q.front();
            q.pop();

            for (const auto& [neighbor, color] : adj[node]) {
                if (!visit[neighbor][color] && color != prevColor) {
                    if (answer[neighbor] == -1) {
                        answer[neighbor] = steps + 1;
                    }
                    visit[neighbor][color] = true;
                    q.emplace(neighbor, steps + 1, color);
                }
            }
        }
        return answer;
    }
};

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

Задача: 589. N-ary Tree Preorder Traversal Сложность: easy Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода. Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры). Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> output;
        if (root == nullptr) return output;
        
        stack<Node*> stack;
        stack.push(root);
        
        while (!stack.empty()) {
            Node* node = stack.top();
            stack.pop();
            output.push_back(node->val);
            for (auto it = node->children.rbegin(); it != node->children.rend(); ++it) {
                stack.push(*it);
            }
        }
        
        return output;
    }
};

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

Задача: 1051. Height Checker Сложность: easy Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i]. Пример:

Input: heights = [1,1,4,2,1,3]
Output: 3

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

class Solution {
public:
    int heightChecker(vector<int>& heights) {
        vector<int> expected = heights;
        sort(expected.begin(), expected.end());
        int count = 0;
        for (int i = 0; i < heights.size(); i++) {
            if (heights[i] != expected[i]) {
                count++;
            }
        }
        return count;
    }
};

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

Задача: 337. House Robber III Сложность: medium Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем. Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь. Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию. Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

👨‍💻 Алгоритм: 1⃣Инициализация и базовый случай: Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел. Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0]. 2⃣Рекурсивное исследование дерева: В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла. Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся. Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка. 3⃣Возврат результата: В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper. 😎 Решение:

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

class Solution {
public:
    int rob(TreeNode* root) {
        auto answer = helper(root);
        return max(answer[0], answer[1]);
    }

private:
    vector<int> helper(TreeNode* node) {
        if (node == nullptr) return {0, 0};

        auto left = helper(node->left);
        auto right = helper(node->right);

        int rob = node->val + left[1] + right[1];
        int notRob = max(left[0], left[1]) + max(right[0], right[1]);

        return {rob, notRob};
    }
};

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent Сложность: medium Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0. A grandparent of a node is the parent of its parent if it exists. Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

👨‍💻 Алгоритм: 1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму. 2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу. 3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла. 😎 Решение:

class Solution {
public:
    int solve(TreeNode* root, int parent, int gParent) {
        if (!root) {
            return 0;
        }
        return solve(root->left, root->val, parent) + solve(root->right, root->val, parent) + (gParent % 2 == 0 ? root->val : 0);
    }

    int sumEvenGrandparent(TreeNode* root) {
        return solve(root, -1, -1);
    }
};

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

Задача: 688. Knight Probability in Chessboard Сложность: medium На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1). Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении. Каждый раз, когда конь делает ход, он случайным образом выбирает один из восьми возможных ходов (даже если этот ход выведет его за пределы шахматной доски) и перемещается туда. Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски. Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы. Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

👨‍💻 Алгоритм: 1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня. 2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j]. 3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность. 😎 Решение:

class Solution {
public:
    double knightProbability(int n, int k, int row, int column) {
        vector<pair<int, int>> directions = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
                                             {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
        vector dp(k + 1, vector(n, vector<double>(n, 0.0)));
        dp[0][row][column] = 1;

        for (int moves = 1; moves <= k; moves++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (const auto& direction : directions) {
                        int prevI = i - direction.first;
                        int prevJ = j - direction.second;
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
                        }
                    }
                }
            }
        }

        double totalProbability = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalProbability += dp[k][i][j];
            }
        }

        return totalProbability;
    }
};

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

Задача: 658. Find K Closest Elements Сложность: easy Дан отсортированный массив целых чисел arr, два целых числа k и x. Верните k ближайших к x целых чисел в массиве. Результат также должен быть отсортирован в порядке возрастания. Целое число a ближе к x, чем целое число b, если: |a - x| < |b - x|, или |a - x| == |b - x| и a < b. Пример:

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

👨‍💻 Алгоритм: 1⃣Бинарный поиск: Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска. 2⃣Два указателя: Используйте два указателя, чтобы расширять окно, которое содержит k ближайших к x элементов. Начните с ближайших элементов и расширяйте окно, сравнивая элементы слева и справа от текущего окна. 3⃣Сортировка: Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован). 😎 Решение:

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size() - k;

        while (left < right) {
            int mid = (left + right) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return vector<int>(arr.begin() + left, arr.begin() + left + k);
    }
};

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

Задача: 915. Partition Array into Disjoint Intervals Сложность: medium Задав целочисленный массив nums, разбейте его на два (смежных) подмассива left и right так, чтобы: каждый элемент left был меньше или равен каждому элементу right. left и right были непустыми. left имел наименьший возможный размер. Верните длину left после такого разбиения. Тестовые примеры генерируются такие, что разбиение существует. Пример:

Input: nums = [5,0,3,8,6]
Output: 3

👨‍💻 Алгоритм: 1⃣Создать массив max_left и min_right. 2⃣Заполнить max_left максимальными значениями от начала массива до текущего индекса. Заполнить min_right минимальными значениями от текущего индекса до конца массива. 3⃣Найти индекс, где max_left[i] меньше или равен min_right[i + 1]. Вернуть длину левого подмассива. 😎 Решение:

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        vector<int> maxLeft(n), minRight(n);
        
        maxLeft[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            maxLeft[i] = max(maxLeft[i - 1], nums[i]);
        }
        
        minRight[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            minRight[i] = min(minRight[i + 1], nums[i]);
        }
        
        for (int i = 0; i < n - 1; ++i) {
            if (maxLeft[i] <= minRight[i + 1]) {
                return i + 1;
            }
        }
        return n;
    }
};

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

Задача: 242. Valid Anagram Сложность: easy Даны две строки s и t, вернуть true, если t — анаграмма s Пример:

Input: s = "anagram", t = "nagaram" Output: true

👨‍💻 Алгоритм: 1⃣Создаем массив из 26 элементов, представляющих счетчики для каждой буквы латинского алфавита 2⃣Увеличиваем счетчик для каждой буквы строки s и уменьшаем для строки t 3⃣Проверяем, что в финале все счетчики равны нулю — значит, строки состоят из одинаковых букв с одинаковыми частотами 😎 Решение:

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    int count[26] = {0};
    for (int i = 0; i < s.size(); ++i) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }
    for (int i : count) {
        if (i != 0) return false;
    }
    return true;
}

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

Задача: 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts Сложность: medium Дан прямоугольный торт размером h x w и два массива целых чисел horizontalCuts и verticalCuts, где: horizontalCuts[i] — это расстояние от верхнего края прямоугольного торта до i-го горизонтального разреза, verticalCuts[j] — это расстояние от левого края прямоугольного торта до j-го вертикального разреза. Верните максимальную площадь кусочка торта после разрезания в каждом горизонтальном и вертикальном положении, указанном в массивах horizontalCuts и verticalCuts. Так как ответ может быть очень большим числом, верните его по модулю 10^9 + 7. Пример:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts.
 After you cut the cake, the green piece of cake has the maximum area.

👨‍💻 Алгоритм: 1⃣Отсортируйте массивы horizontalCuts и verticalCuts в порядке возрастания. Найдите максимальную высоту, учитывая верхний и нижний края торта, и пройдитесь по массиву horizontalCuts, чтобы найти максимальное расстояние между соседними разрезами. 2⃣Найдите максимальную ширину, учитывая левый и правый края торта, и пройдитесь по массиву verticalCuts, чтобы найти максимальное расстояние между соседними разрезами. 3⃣Верните произведение максимальной высоты и максимальной ширины, взятое по модулю 10^9+7. 😎 Решение:

class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        
        long long maxHeight = max(horizontalCuts[0], h - horizontalCuts.back());
        for (int i = 1; i < horizontalCuts.size(); ++i) {
            maxHeight = max(maxHeight, (long long)horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        
        long long maxWidth = max(verticalCuts[0], w - verticalCuts.back());
        for (int i = 1; i < verticalCuts.size(); ++i) {
            maxWidth = max(maxWidth, (long long)verticalCuts[i] - verticalCuts[i - 1]);
        }
        
        return (maxHeight * maxWidth) % 1000000007;
    }
};

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

Задача: 1009. Complement of Base 10 Integer Сложность: easy Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение. Пример:

Input: n = 5
Output: 2

👨‍💻 Алгоритм: 1⃣Определение длины двоичного представления: Найдите длину двоичного представления числа n. 2⃣Создание маски: Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n. 3⃣Вычисление дополнения: Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа. 😎 Решение:

class Solution {
public:
    int findComplement(int num) {
        int length = sizeof(num) * 8 - __builtin_clz(num);
        int mask = (1 << length) - 1;
        return num ^ mask;
    }
};

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

Задача: 865. Smallest Subtree with all the Deepest Nodes Сложность: medium Дан корень бинарного дерева, глубина каждого узла — это кратчайшее расстояние до корня. Верните наименьшее поддерево, которое содержит все самые глубокие узлы в исходном дереве. Узел называется самым глубоким, если у него наибольшая возможная глубина среди всех узлов в дереве. Поддерево узла — это дерево, состоящее из этого узла и всех его потомков. Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.

👨‍💻 Алгоритм: 1⃣В первой фазе используем поиск в глубину (DFS), чтобы аннотировать узлы. Каждый узел будет хранить информацию о своей глубине и о самой большой глубине среди его потомков. 2⃣Во второй фазе также используем DFS для функции answer(node), которая возвращает наименьшее поддерево, содержащее все самые глубокие узлы. Функция сравнивает глубины левых и правых поддеревьев узла для определения наименьшего поддерева. 3⃣Функция answer(node) возвращает поддерево, которое содержит все самые глубокие узлы всего дерева, а не только рассматриваемого поддерева. 😎 Решение:

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        unordered_map<TreeNode*, int> depth = {{nullptr, -1}};
        dfs(root, nullptr, depth);
        int maxDepth = max_element(depth.begin(), depth.end(), [](const auto& a, const auto& b) {
            return a.second < b.second;
        })->second;
        return answer(root, depth, maxDepth);
    }

private:
    void dfs(TreeNode* node, TreeNode* parent, unordered_map<TreeNode*, int>& depth) {
        if (node) {
            depth[node] = depth[parent] + 1;
            dfs(node->left, node, depth);
            dfs(node->right, node, depth);
        }
    }

    TreeNode* answer(TreeNode* node, unordered_map<TreeNode*, int>& depth, int maxDepth) {
        if (!node || depth[node] == maxDepth) return node;
        TreeNode* L = answer(node->left, depth, maxDepth);
        TreeNode* R = answer(node->right, depth, maxDepth);
        return L && R ? node : L ? L : R;
    }
};

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

Задача: 1240. Tiling a Rectangle with the Fewest Squares Сложность: hard Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник. Пример:

Input: n = 2, m = 3
Output: 3

👨‍💻 Алгоритм: 1⃣Инициализация рекурсивной функции: Функция принимает размеры прямоугольника n x m. 2⃣Базовый случай: Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия. 3⃣Рекурсивный случай: Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m). Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части: Прямоугольник слева от квадрата. Прямоугольник сверху от квадрата. Прямоугольник справа и снизу от квадрата. 😎 Решение:

class Solution {
public:
    int tilingRectangle(int n, int m) {
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        for (int i = 1; i <= min(n, m); ++i) {
            dp[i][i] = 1;
        }
        
        for (int h = 1; h <= n; ++h) {
            for (int w = 1; w <= m; ++w) {
                if (h == w) continue;
                for (int i = 1; i <= h / 2; ++i) {
                    dp[h][w] = min(dp[h][w], dp[i][w] + dp[h - i][w]);
                }
                for (int j = 1; j <= w / 2; ++j) {
                    dp[h][w] = min(dp[h][w], dp[h][j] + dp[h][w - j]);
                }
            }
        }
        return dp[n][m];
    }
};

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

Задача: 1237. Find Positive Integer Solution for a Given Equation Сложность: medium Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы. int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято. Пример:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]

👨‍💻 Алгоритм: 1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y). 2⃣Перемещение указателей: Если 𝑓(𝑥,𝑦)=𝑧 f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x. 3⃣Повторяем шаги до тех пор, пока 𝑥≤1000 x≤1000 и 𝑦≥1y≥1. 😎 Решение:

class CustomFunction {
public:
    int f(int x, int y);
};

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> result;
        int x = 1;
        int y = 1000;
        
        while (x <= 1000 && y >= 1) {
            int value = customfunction.f(x, y);
            if (value == z) {
                result.push_back({x, y});
                x++;
            } else if (value < z) {
                x++;
            } else {
                y--;
            }
        }
        
        return result;
    }
};

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

Задача: 942. DI String Match Сложность: easy Перестановка perm из n + 1 целых чисел всех целых чисел в диапазоне [0, n] может быть представлена в виде строки s длины n, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Получив строку s, восстановите перестановку perm и верните ее. Если существует несколько допустимых перестановок perm, верните любую из них. Пример:

Input: s = "IDID"
Output: [0,4,1,3,2]

👨‍💻 Алгоритм: 1⃣Инициализировать два указателя low и high для отслеживания минимального и максимального числа, которые можно использовать в перестановке. 2⃣Создать массив perm длиной n + 1. Пройти по строке s: Если текущий символ равен 'I', добавить low в текущую позицию perm и увеличить low. Если текущий символ равен 'D', добавить high в текущую позицию perm и уменьшить high. Добавить оставшееся значение (low или high, так как они будут равны) в последнюю позицию perm. 3⃣Вернуть массив perm. 😎 Решение:

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        int low = 0, high = n;
        vector<int> perm(n + 1);
        
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'I') {
                perm[i] = low++;
            } else {
                perm[i] = high--;
            }
        }
        
        perm[n] = low;
        return perm;
    }
};

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

Задача: 988. Smallest String Starting From Leaf Сложность: medium Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'. Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня. Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей. Например, "ab" лексикографически меньше, чем "aba". Лист узла - это узел, у которого нет потомков. Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:

class Solution {
public:
    string ans = "~";

    string smallestFromLeaf(TreeNode* root) {
        dfs(root, "");
        return ans;
    }

    void dfs(TreeNode* node, string path) {
        if (!node) return;
        path += (char)(node->val + 'a');
        if (!node->left && !node->right) {
            reverse(path.begin(), path.end());
            if (path < ans) {
                ans = path;
            }
            reverse(path.begin(), path.end());
        }
        dfs(node->left, path);
        dfs(node->right, path);
    }
};

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