C/C++ | LeetCode

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 174. Dungeon Game Сложность: hard Демоны захватили принцессу и заточили её в правом нижнем углу подземелья. Подземелье состоит из m x n комнат, расположенных в виде двумерной сетки. Наш отважный рыцарь изначально находится в левом верхнем углу и должен пробиться через подземелье, чтобы спасти принцессу. У рыцаря есть начальное количество очков здоровья, представленное положительным целым числом. Если в какой-то момент его очки здоровья упадут до 0 или ниже, он немедленно умрёт. Некоторые комнаты охраняются демонами (представлены отрицательными числами), поэтому рыцарь теряет здоровье, заходя в эти комнаты; другие комнаты либо пусты (представлены как 0), либо содержат магические шары, увеличивающие здоровье рыцаря (представлены положительными числами). Чтобы как можно быстрее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге. Верните минимальное начальное количество здоровья рыцаря, чтобы он мог спасти принцессу. Учтите, что любая комната может содержать угрозы или усиления, включая первую комнату, в которую входит рыцарь, и последнюю комнату, где заточена принцесса. Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] Output: 7

👨‍💻 Алгоритм: 1⃣Определяем матрицу dp[row][col], где элемент указывает минимальное количество здоровья, необходимое рыцарю с этой позиции до конца пути. 2⃣Заполняем матрицу снизу-вверх и справа-налево, начиная с конечной ячейки, сравнивая варианты движения вправо и вниз. 3⃣Для каждой клетки берем минимальное здоровье, необходимое для движения дальше, и корректируем с учетом текущего значения подземелья. 😎 Решение:

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int rows = dungeon.size(), cols = dungeon[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, INT_MAX));

        auto get_min_health = [&](int currCell, int nextRow, int nextCol) -> int {
            if (nextRow >= rows || nextCol >= cols) {
                return INT_MAX;
            }
            int nextCell = dp[nextRow][nextCol];
            return max(1, nextCell - currCell);
        };

        for (int row = rows - 1; row >= 0; --row) {
            for (int col = cols - 1; col >= 0; --col) {
                int currCell = dungeon[row][col];

                int right_health = get_min_health(currCell, row, col + 1);
                int down_health = get_min_health(currCell, row + 1, col);
                int next_health = min(right_health, down_health);

                int min_health;
                if (next_health != INT_MAX) {
                    min_health = next_health;
                } else {
                    min_health = currCell >= 0 ? 1 : 1 - currCell;
                }

                dp[row][col] = min_health;
            }
        }

        return dp[0][0];
    }
};

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

Задача: 114. Flatten Binary Tree to Linked List Сложность: medium Преобразуйте бинарное дерево в "связный список", используя тот же класс TreeNode, где right указывает на следующий элемент, а left всегда равен null. Порядок обхода должен соответствовать прямому (preorder) обходу дерева. Пример:

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

👨‍💻 Алгоритм: 1⃣Рекурсивно преобразуем левое и правое поддеревья, сохраняя хвостовые узлы leftTail и rightTail. 2⃣Если у текущего узла есть левое поддерево: leftTail->right = node->right — соединяем хвост левого поддерева с началом правого. node->right = node->left — правый указатель указывает на левое поддерево. node->left = nullptr — левый указатель обнуляется. 3⃣Возвращаем в качестве хвоста либо rightTail, либо leftTail, если правого нет. 😎 Решение:

class Solution {
public:
    TreeNode* flattenTree(TreeNode* node) {
        if (node == NULL) {
            return NULL;
        }

        if (node->left == NULL && node->right == NULL) {
            return node;
        }

        TreeNode* leftTail = this->flattenTree(node->left);
        TreeNode* rightTail = this->flattenTree(node->right);

        if (leftTail != NULL) {
            leftTail->right = node->right;
            node->right = node->left;
            node->left = NULL;
        }

        return rightTail == NULL ? leftTail : rightTail;
    }

    void flatten(TreeNode* root) {
        this->flattenTree(root);
    }
};

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать

Задача: 752. Open the Lock Сложность: medium Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно. Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        queue<pair<string, int>> queue;
        queue.push({"0000", 0});
        unordered_set<string> visited;
        visited.insert("0000");
        
        while (!queue.empty()) {
            auto [node, steps] = queue.front();
            queue.pop();
            if (node == target) {
                return steps;
            }
            if (dead.count(node)) {
                continue;
            }
            for (auto neighbor : neighbors(node)) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    queue.push({neighbor, steps + 1});
                }
            }
        }
        
        return -1;
    }

private:
    vector<string> neighbors(const string& node) {
        vector<string> res;
        for (int i = 0; i < 4; i++) {
            string up = node;
            up[i] = (node[i] - '0' + 1) % 10 + '0';
            res.push_back(up);
            string down = node;
            down[i] = (node[i] - '0' - 1 + 10) % 10 + '0';
            res.push_back(down);
        }
        return res;
    }
};

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

Задача: 57. Insert Interval Сложность: medium Дан отсортированный массив непересекающихся интервалов intervals, и новый интервал newInterval. Вставьте newInterval, объединив перекрывающиеся интервалы, и сохраните сортировку по возрастанию. Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

👨‍💻 Алгоритм: 1⃣Пройти все интервалы, которые не перекрываются с newInterval (т.е. заканчиваются раньше) — добавить их в результат 2⃣Все перекрывающиеся с newInterval интервалы объединить, обновив начало и конец 3⃣Добавить объединённый интервал в результат и приклеить оставшиеся интервалы, идущие после него 😎 Решение:

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        vector<vector<int>> res;

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval);

        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};

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

Задача: 1166. Design File System Сложность: medium Вам нужно разработать файловую систему, которая позволяет создавать новые пути и связывать их с различными значениями. Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы. Реализуйте класс FileSystem: - bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует. - int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует. Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

👨‍💻 Алгоритм: 1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции. 2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем. 3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение. 😎 Решение:

class FileSystem {
public:
    unordered_map<string, int> paths;

    FileSystem() {
        paths = unordered_map<string, int>();
    }

    bool createPath(string path, int value) {
        if (path.empty() || (path.length() == 1 && path == "/") || paths.count(path)) {
            return false;
        }

        int delimIndex = path.rfind("/");
        string parent = path.substr(0, delimIndex);

        if (parent.length() > 1 && !paths.count(parent)) {
            return false;
        }

        paths[path] = value;
        return true;
    }

    int get(string path) {
        return paths.count(path) ? paths[path] : -1;
    }
};

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

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

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

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

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

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

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

Tanks Blitz — в RuStore, ты — на Финале Лиги Блиц Поинт! Проведи киберспортивные выходные с саундтреком от «ХЛЕБа», Oligarkh'а и FANKIN’а — скачай Tanks Blitz в RuStore, чтобы узнать больше о Финальном турнире Лиги Блиц Поинт, Часть 3 в Москве! ⚡ Узнать больше #реклама 16+ apps.rustore.ru О рекламодателе

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

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

Мы ищем людей, которые хотят работать турагентом из дома 💰Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — зарегистрироваться на сайте — пройти трехдневный курс На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку. ⚡ Набор заканчивается в понедельник! Зарегистрироваться #реклама интревел.рф О рекламодателе

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

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

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

Внимание ученики 1-9 класса и их родители! С 1 июня стартует бесплатная 3-х месячная программа по углубленному изучению школьных предметов с 1 по 4 класс, с 5 по 8 класс и с 9 по 11 класс от резидента Сколково. Программа предлагает подтянуть знания по основным предметам: — Математика: 83% учеников повышают оценку до 4 или 5 за 2 месяца — Подготовиться к контрольным и ВПР — Подготовка к ОГЭ и ЕГЭ без стресса — Русский язык: средний балл ВПР 87 при общешкольном показателе 65 — Английский: 72% учащихся переходят на уровень выше за 4 месяца Для участия достаточно заполнить заявку. Жмите "Записаться" Записаться #реклама 16+ mrqz.me О рекламодателе

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

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

Как повысить эффективность вебинаров? Организация продающего вебинара - не простая задача, ведь необходимо предусмотреть множество деталей: удобную дату, вовлекающий контент, методы продвижения и взаимодействия с участниками. Вебинары от МТС Линк помогают привлекать новых клиентов и увеличивать конверсию из участника в лид. В сервисе доступен анализ поведения пользователей во время вебинара, синхронный перевод, автовебинары и интерактивные инструменты для вовлечения участников. Делимся методичкой с кейсами, чек-листами и инструкциями для маркетологов, PR и event-менеджеров, чтобы сделать вебинары эффективным инструментом для лидогенерации. Получите методичку бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

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

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

Старт продаж офисов класса «А». Рост цены от 40% Бизнес-центр KOBZON CITY (K-CITY) Офисы для инвестиций от 21,6 млн руб. Рассрочка 0% до 3 лет. Минимальный первоначальный взнос от 20% Лоты от 36 до 716 м² с возможностью объединения до 10 тыс. м². 200 м до ТТК и 500 до м. Бауманская. Уникальная архитектура от международного бюро NIKKEN. Собственная инфраструктура: сanteen, магазины, арт-хаб, фитнес. Двухуровневый подземный паркинг. Сдача – 4 квартал 2028 года. Узнать больше Проектная декларация на сайте https://наш.дом.рф/. Финансовые услуги оказывает: АО "Банк ДОМ.РФ". #реклама kobzon.city О рекламодателе