C/C++ | LeetCode

#hard Задача: 730. Count Different Palindromic Subsequences Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi. Пример:

Input: s = "bccb"
Output: 6

👨‍💻 Алгоритм: 1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей. 2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j. 3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок. 😎 Решение:

class Solution {
public:
    int countPalindromicSubsequences(string s) {
        const int MOD = 1000000007;
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = 0; i < n; ++i) {
            dp[i][i] = 1;
        }

        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                if (s[i] == s[j]) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s[l] != s[i]) l++;
                    while (l <= r && s[r] != s[j]) r--;
                    if (l > r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
                    }
                } else {
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        }

        return dp[0][n - 1];
    }
};

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

#medium Задача: 729. My Calendar I Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь. Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

👨‍💻 Алгоритм: 1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий. 2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями. 3⃣Если новое событие не пересекается с существующими событиями, добавьте его в список событий и верните true. В противном случае верните false. 😎 Решение:

class MyCalendar {
public:
    MyCalendar() {}

    bool book(int start, int end) {
        for (const auto& event : events) {
            if (start < event[1] && end > event[0]) {
                return false;
            }
        }
        events.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> events;
};

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

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

#hard Задача: 728. Self Dividing Numbers Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right]. Пример:

Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]

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

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> result;
        for (int num = left; num <= right; num++) {
            if (isSelfDividing(num)) {
                result.push_back(num);
            }
        }
        return result;
    }

private:
    bool isSelfDividing(int num) {
        int n = num;
        while (n > 0) {
            int digit = n % 10;
            if (digit == 0 || num % digit != 0) {
                return false;
            }
            n /= 10;
        }
        return true;
    }
};

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

🚀Открыта вакансия C++ Software Engineer в YADRO: получите оффер за 3 дня Если вы давно хотели работать в технологической компании с амбициозными задачами, то скорее подавайте заявку на сайте. YADRO запускает SPRINT OFFER для инженеров-разработчиков C++, готовых прокачаться в команде Telecom Platform. Здесь вы будете: ✔️ Разрабатывать платформенные решения для мобильных сетей LTE/GSM ✔️ Разрабатывать компоненты телеком-платформы в технологическом стеке С++/Linux ✔️ Участвовать в проектировании и развитии архитектуры телеком-платформы Как попасть в команду? 1️⃣ Оставить заявку до 9 марта 2️⃣ Пройти скрининг и техническое интервью 3️⃣ Получить оффер всего за 3 дня 📍 Формат работы: офис, гибрид или удалёнка (Москва, СПб, Нижний Новгород, Екатеринбург, Минск). 💡 В команде — инженеры с опытом 10–25 лет, у которых есть чему научиться! Готовы к карьерному рывку? Подавайте заявку сейчас — по ссылке.

Крупнейший университет искусственного интеллекта Временные ряды — это данные, упорядоченные во времени, например, трафик на дорогах, изменения температуры или спрос на товары. С помощью AI можно предсказывать тренды, выявлять аномалии и оптимизировать процессы. Получите полный доступ к курсу по временным рядам на сайте. Это абсолютно бесплатно. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя среди наших студентов! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

#hard Задача: 727. Minimum Window Subsequence Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом. Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

class Solution {
public:
    string minWindow(string s1, string s2) {
        if (s1.empty() || s2.empty()) {
            return "";
        }

        unordered_map<char, int> dictT;
        for (char c : s2) {
            dictT[c]++;
        }

        int required = dictT.size();
        int l = 0, r = 0, formed = 0;
        unordered_map<char, int> windowCounts;
        int ans[3] = {INT_MAX, 0, 0};

        while (r < s1.size()) {
            char c = s1[r];
            windowCounts[c]++;

            if (dictT.count(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s1[l];

                if (r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts[c]--;
                if (dictT.count(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == INT_MAX ? "" : s1.substr(ans[1], ans[0]);
    }
};

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

#hard Задача: 726. Number of Atoms Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой. Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами. Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число. Пример:

Input: formula = "H2O"
Output: "H2O"

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

class Solution {
public:
    string countOfAtoms(string formula) {
        stack<map<string, int>> stack;
        stack.push(map<string, int>());
        int n = formula.size();
        int i = 0;

        while (i < n) {
            if (formula[i] == '(') {
                stack.push(map<string, int>());
                i++;
            } else if (formula[i] == ')') {
                map<string, int> top = stack.top();
                stack.pop();
                i++;
                int start = i;
                while (i < n && isdigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? stoi(formula.substr(start, i - start)) : 1;
                for (const auto& [name, count] : top) {
                    stack.top()[name] += count * multiplicity;
                }
            } else {
                int start = i;
                i++;
                while (i < n && islower(formula[i])) {
                    i++;
                }
                string name = formula.substr(start, i - start);
                start = i;
                while (i < n && isdigit(formula[i])) {
                    i++;
                }
                int multiplicity = i > start ? stoi(formula.substr(start, i - start)) : 1;
                stack.top()[name] += multiplicity;
            }
        }

        map<string, int> countMap = stack.top();
        string result;
        for (const auto& [name, count] : countMap) {
            result += name;
            if (count > 1) {
                result += to_string(count);
            }
        }
        return result;
    }
};

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

#medium Задача: 341. Flatten Nested List Iterator Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки. Реализуйте класс NestedIterator: NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList. int next() Возвращает следующий целый элемент вложенного списка. boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае. Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

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

class NestedIterator {
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        flatten(nestedList);
    }
    
    int next() {
        return stack.back().getInteger();
    }
    
    bool hasNext() {
        while (!stack.empty() && !stack.back().isInteger()) {
            auto ni = stack.back();
            stack.pop_back();
            flatten(ni.getList());
        }
        return !stack.empty();
    }
    
private:
    void flatten(const vector<NestedInteger> &nestedList) {
        for (auto it = nestedList.rbegin(); it != nestedList.rend(); ++it) {
            stack.push_back(*it);
        }
    }
    
    vector<NestedInteger> stack;
};

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

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

#medium Задача: 725. Split Linked List in Parts Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей. Пример:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

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

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

vector<ListNode*> splitListToParts(ListNode* root, int k) {
    int length = 0;
    ListNode* node = root;
    while (node != nullptr) {
        length++;
        node = node->next;
    }

    int partLength = length / k;
    int extraParts = length % k;

    vector<ListNode*> parts(k, nullptr);
    node = root;
    for (int i = 0; i < k; i++) {
        ListNode* partHead = node;
        int partSize = partLength + (i < extraParts ? 1 : 0);
        for (int j = 0; j < partSize - 1; j++) {
            if (node != nullptr) node = node->next;
        }
        if (node != nullptr) {
            ListNode* nextPart = node->next;
            node->next = nullptr;
            node = nextPart;
        }
        parts[i] = partHead;
    }

    return parts;
}

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

Сделайте шаг в новую профессию. Найдите свое место в 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;
    }
};

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