C/C++ | LeetCode

Сделайте шаг в новую профессию. Найдите свое место в IT! Пройдите тест, узнайте, какая роль в IT вам подходит, и получите доступ к мини-курсу. 📱5 уроков в Telegram-боте — легко, увлекательно и бесплатно. ✨Подарки в конце пути ✅Пройдите тест и откройте курс Начать #реклама 16+ free.skillfactory.ru О рекламодателе

#medium Задача: 510. Inorder Successor in BST II Дан узел в двоичном дереве поиска, верните его последующего (in-order successor) в этом дереве. Если у узла нет последующего, верните null. Последующий узла — это узел с наименьшим ключом, большим, чем node.val. Вы будете иметь прямой доступ к узлу, но не к корню дерева. Каждый узел будет иметь ссылку на своего родителя. Ниже приведено определение для Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

Пример:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

👨‍💻 Алгоритм: 1⃣Проверка правого поддерева Если у узла есть правый потомок, перейдите к правому узлу, затем спускайтесь влево до самого нижнего узла. Этот узел будет следующим узлом в порядке in-order. 2⃣Поиск предка Если у узла нет правого потомка, поднимайтесь по дереву до тех пор, пока узел не станет левым потомком своего родителя. Родитель этого узла будет следующим узлом в порядке in-order. 3⃣Возвращение результата Верните найденный узел или null, если следующий узел не найден. 😎 Решение:

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};

class Solution {
public:
    Node* inorderSuccessor(Node* x) {
        if (x->right) {
            x = x->right;
            while (x->left) {
                x = x->left;
            }
            return x;
        }

        while (x->parent && x == x->parent->right) {
            x = x->parent;
        }
        return x->parent;
    }
};

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

Битрикс24 💻Один онлайн-сервис для совместной работы. 📱10+ инструментов. ✅0 денег. Счастливые сотрудники. Прибыльный бизнес. Регистрируйтесь и забирайте себе Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

#medium Задача: 340. Longest Substring with At Most K Distinct Characters Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов. Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0, right = 0;
        unordered_map<char, int> charCount;
        int maxLength = 0;
        
        while (right < s.length()) {
            charCount[s[right]]++;
            while (charCount.size() > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.erase(s[left]);
                }
                left++;
            }
            maxLength = max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
};

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

Инвестируй. Живи. Отдыхай. Анапа ждет тебя! ❤️Представьте: каждое утро вы просыпаетесь под мелодию волн Черного моря, открываете окно и вдыхаете свежий морской бриз 🏠«Sun Garden» — это современная архитектура, продуманная инфраструктура и комфорт, созданные для тех, кто ценит качество жизни на курорте Комплекс расположен в шаговой доступности от пляжа, что позволяет наслаждаться морем в любое время На территории предусмотрены детские и спортивные площадки, зоны для отдыха и прогулок, обеспечивая комфорт для всей семьи А еще: - 5 минут до моря -собственный пляж -бассейн XXL протяженностью 50 метров -SPA 365 дней в году Оставьте заявку, получите каталог объектов и сделайте свою мечту явью! 📅Получите цены и планировки Получить предложение #реклама mrqz.me О рекламодателе

#easy Задача: 724. Find Pivot Index Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1. Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

int pivotIndex(vector<int>& nums) {
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }
    int leftSum = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (leftSum == totalSum - leftSum - nums[i]) {
            return i;
        }
        leftSum += nums[i];
    }
    return -1;
}

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

#medium Задача: 723. Candy Crush Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску. Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

vector<vector<int>> candyCrush(vector<vector<int>>& board) {
    int m = board.size();
    int n = board[0].size();
    bool stable = false;

    while (!stable) {
        stable = true;
        vector<vector<bool>> crush(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                int v = abs(board[i][j]);
                if (v != 0 && v == abs(board[i][j + 1]) && v == abs(board[i][j + 2])) {
                    stable = false;
                    crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = true;
                }
            }
        }

        for (int i = 0; i < m - 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int v = abs(board[i][j]);
                if (v != 0 && v == abs(board[i + 1][j]) && v == abs(board[i + 2][j])) {
                    stable = false;
                    crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = true;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (crush[i][j]) {
                    board[i][j] = 0;
                }
            }
        }

        for (int j = 0; j < n; ++j) {
            int idx = m - 1;
            for (int i = m - 1; i >= 0; --i) {
                if (board[i][j] != 0) {
                    board[idx][j] = board[i][j];
                    idx--;
                }
            }
            for (int i = idx; i >= 0; --i) {
                board[i][j] = 0;
            }
        }
    }

    return board;
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка для вас и 3-х ваших близких 30 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте сейчас❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

#easy Задача: 509. Fibonacci Number Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть, F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), для n > 1. Дано n, вычислите F(n). Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

👨‍💻 Алгоритм: 1⃣Проверка начального условия Если N <= 1, вернуть N. 2⃣Инициализация переменных Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения. 3⃣Итерация и вычисление Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации. 😎 Решение:

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int current = 0, prev1 = 1, prev2 = 0;
        for (int i = 2; i <= N; ++i) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
};

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

#medium Задача: 508. Most Frequent Subtree Sum Дано корень бинарного дерева, вернуть наиболее часто встречающуюся сумму поддерева. Если есть несколько таких значений, вернуть все значения с наибольшей частотой в любом порядке. Сумма поддерева узла определяется как сумма всех значений узлов, образованных поддеревом, укорененным в этом узле (включая сам узел). Пример:

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

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

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <queue>

using namespace std;

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

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int, int> sumFreq;
        int maxFreq = 0;
        
        function<int(TreeNode*)> subtreeSum = [&](TreeNode* node) {
            if (!node) return 0;
            int leftSum = subtreeSum(node->left);
            int rightSum = subtreeSum(node->right);
            int currSum = node->val + leftSum + rightSum;
            sumFreq[currSum]++;
            maxFreq = max(maxFreq, sumFreq[currSum]);
            return currSum;
        };
        
        subtreeSum(root);
        vector<int> result;
        for (const auto& [sum, freq] : sumFreq) {
            if (freq == maxFreq) {
                result.push_back(sum);
            }
        }
        return result;
    }
};

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

Как бессерверные технологии меняют науку и образование Узнайте о реальных кейсах использования serverless-решений в научных проектах и обучении разработчиков. Примеры от Yandex Cloud, УрФУ и КФУ. Вебинар бесплатный, нужно только зарегистрироваться! Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе Реклама на Яндексе

#easy Задача: 507. Perfect Number Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело. Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false. Пример:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

👨‍💻 Алгоритм: 1⃣Инициализация Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0. 2⃣Поиск делителей и вычисление суммы Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель. 3⃣Проверка на совершенное число Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false. 😎 Решение:

 class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 0) return false;
        int sum = 0;
        for (int i = 1; i * i <= num; ++i) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }
            }
        }
        return sum - num == num;
    }
};

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

#easy Задача: 506. Relative Ranks Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны. Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг: Ранг спортсмена, занявшего 1-е место, — "Gold Medal". Ранг спортсмена, занявшего 2-е место, — "Silver Medal". Ранг спортсмена, занявшего 3-е место, — "Bronze Medal". Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x"). Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена. Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

👨‍💻 Алгоритм: 1⃣Инициализация и нахождение максимального значения Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score. 2⃣Создание вспомогательных структур Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]]. 3⃣Присваивание рангов и формирование ответа Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего. 😎 Решение:

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int N = score.size();
        int maxScore = *max_element(score.begin(), score.end());
        vector<int> scoreToIndex(maxScore + 1, 0);
        
        for (int i = 0; i < N; i++) {
            scoreToIndex[score[i]] = i + 1;
        }
        
        vector<string> rank(N);
        vector<string> MEDALS = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        int place = 1;
        
        for (int i = maxScore; i >= 0; i--) {
            if (scoreToIndex[i] != 0) {
                int originalIndex = scoreToIndex[i] - 1;
                if (place < 4) {
                    rank[originalIndex] = MEDALS[place - 1];
                } else {
                    rank[originalIndex] = to_string(place);
                }
                place++;
            }
        }
        
        return rank;
    }
};

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

🔥 Бэкендеры, этот пост для вас! Хотите прокачать свои навыки и узнать, как создаются по-настоящему крутые и надежные сервисы? Тогда у нас отличные новости! 19 апреля в Москве пройдет Яндекс Dev Day&Night — конференция для опытных бэкенд-разработчиков. Это не просто лекции, а настоящий интенсив с кучей полезной информации и практики! Что вас ждет: ✅ Доклады и воркшопы. Узнаете, как решать сложные задачи асинхронного взаимодействия между сервисами, как устроен поиск и ранжирование товаров в Маркете, как работает геопоиск с R-tree в Еде и как проводят нагрузочные тестирования в Яндекс Go. В общем, куча инсайдов от профи! ✅ Интерактивный трек с играми и кейслабами, где можно будет применить полученные знания на практике и повеселиться. ✅ Ночная программа. Конференция продлится до 2:00! Вас ждут активности, коктейли и, конечно же, нетворкинг. Отличная возможность познакомиться с коллегами по цеху, обменяться опытом и, возможно, найти новые крутые проекты! Регистрация только открылась, так что успевайте подать заявку в числе первых! И не забудьте позвать друзей — вместе учиться и развиваться всегда веселее! Реклама. ООО «Яндекс.Такси». ИНН 7704340310

Хотите пиццу в подарок? Оформляйте подписку Газпром Бонус за 0₽ и получайте 2 пиццы в подарок к заказам в Додо каждый месяц. 👍И это не все: подписка откроет доступ к онлайн-кинотеатрам PREMIER и Wink, скидкам в Ленте, кешбэку до 50% в Пятерочке и Перекрестке, повышенным бонусам на заправках. Подключайтесь по ссылке, пока это бесплатно, и пользуйтесь! Получить предложение #реклама 16+ dodo.gazprombonus.ru О рекламодателе

#medium Задача: 505. The Maze II В лабиринте есть мячик с пустыми пространствами (обозначенными как 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]];
    }
};

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

#medium Задача: 503. Next Greater Element II Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums. Следующее большее число для числа x — это первое большее число, следующее за ним в порядке обхода массива, что означает, что вы можете искать циклически, чтобы найти следующее большее число. Если оно не существует, верните -1 для этого числа. Пример:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

👨‍💻 Алгоритм: 1⃣Инициализация Создайте массив res той же длины, что и nums, и заполните его значениями -1. 2⃣Поиск следующего большего элемента Для каждого элемента nums[i], используя индекс j, ищите следующий больший элемент среди следующих (циклически) n-1 элементов. Если найден больший элемент, обновите res[i] и прервите внутренний цикл. 3⃣Возврат результата Верните массив res. 😎 Решение:

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (nums[(i + j) % n] > nums[i]) {
                    res[i] = nums[(i + j) % n];
                    break;
                }
            }
        }
        
        return res;
    }
};

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

Живите в Сочи и зарабатывайте от 7 млн. рублей в год! ✨Премиальный гостиничный комплекс в Сочи ❤️Апартаменты в 20 метрах от берега Черного Моря! Обширное живописное пространство с оздоравливающим микроклиматом, наполненное субтропическими растениями и цветами, общей площадью более 8 га ✅Уникальная локация: - Приватное пространство размером с 8 футбольных полей -4 бассейна и лаунж-зоны -частный пляж - тропический бар -просторный детский центр 1000м2 И еще много плюсов: кинотеатр, ультрасовременный фитнес-центр и многое другое 😊Идеален для инвестиций: здесь можно отдыхать самому, а еще сдавать в аренду другим гостям, зарабатывая от 7 000 000 рублей в год 📅Получите цены и планировки Узнать больше #реклама mrqz.me О рекламодателе

#hard Задача: 502. IPO Предположим, что LeetCode скоро начнет свое IPO. Чтобы продать свои акции по хорошей цене венчурным капиталистам, LeetCode хочет выполнить несколько проектов для увеличения своего капитала перед IPO. Поскольку у компании ограниченные ресурсы, она может завершить не более k различных проектов до IPO. Помогите LeetCode разработать лучший способ максимизации общего капитала после завершения не более k различных проектов. Вам дано n проектов, где i-й проект имеет чистую прибыль profits[i] и требует минимального капитала capital[i] для его начала. Изначально у вас есть капитал w. Когда вы завершаете проект, вы получаете его чистую прибыль, и эта прибыль добавляется к вашему общему капиталу. Выберите список из не более чем k различных проектов из данных, чтобы максимально увеличить ваш конечный капитал, и верните окончательно максимизированный капитал. Ответ гарантированно поместится в 32-битное целое число со знаком. Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

👨‍💻 Алгоритм: 1⃣Сортировка и инициализация Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста. 2⃣Выбор проектов Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм. 3⃣Увеличение капитала Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован. 😎 Решение:

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        vector<pair<int, int>> projects;
        for (int i = 0; i < profits.size(); ++i) {
            projects.emplace_back(capital[i], profits[i]);
        }
        sort(projects.begin(), projects.end());
        
        priority_queue<int> maxHeap;
        int ptr = 0;
        
        for (int i = 0; i < k; ++i) {
            while (ptr < projects.size() && projects[ptr].first <= w) {
                maxHeap.push(projects[ptr].second);
                ptr++;
            }
            if (maxHeap.empty()) break;
            w += maxHeap.top();
            maxHeap.pop();
        }
        
        return w;
    }
};

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

#easy Задача: 501. Find Mode in Binary Search Tree Дано корень бинарного дерева поиска (BST) с дубликатами. Необходимо вернуть все моды (т.е. самые часто встречающиеся элементы) в этом дереве. Если в дереве более одной моды, верните их в любом порядке. Предположим, что BST определяется следующим образом: Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла. Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла. Оба поддерева также должны быть бинарными деревьями поиска. Пример:

Input: root = [1,null,2,2]
Output: [2]

👨‍💻 Алгоритм: 1⃣Обход дерева Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values. 2⃣Поиск мод Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans. 3⃣Возврат результата Верните список ans. 😎 Решение:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> values;
        dfs(root, values);
        
        int maxStreak = 0, currStreak = 0, currNum = 0;
        vector<int> ans;
        
        for (int num : values) {
            if (num == currNum) {
                currStreak++;
            } else {
                currStreak = 1;
                currNum = num;
            }
            
            if (currStreak > maxStreak) {
                ans = {num};
                maxStreak = currStreak;
            } else if (currStreak == maxStreak) {
                ans.push_back(num);
            }
        }
        
        return ans;
    }
    
private:
    void dfs(TreeNode* node, vector<int>& values) {
        if (!node) return;
        dfs(node->left, values);
        values.push_back(node->val);
        dfs(node->right, values);
    }
};

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