C/C++ | LeetCode

Задача: 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 О рекламодателе

Ура, друзья! Изиоффер переходит в публичное бета-тестирование! 🎉 Что нового: 🟢Анализ IT собеседований на основе 4500+ реальных интервью 🟢Вопросы из собеседований с вероятностью встречи 🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов 🟢Пример лучшего ответа 🟢Задачи из собеседований 🟢Тестовые задания 🟢Примеры собеседований 🟢Фильтрация всего контента по грейдам, компаниям 🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек 🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро) 🟢Автоотклики на HeadHunter 🟢Закрытое сообщество easyoffer 💎 Акция в честь открытия для первых 500 покупателей: 🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽) 🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 978. Longest Turbulent Subarray Сложность: medium Дан целочисленный массив arr, верните длину максимального турбулентного подмассива массива arr. Подмассив считается турбулентным, если знак сравнения меняется между каждой парой смежных элементов в подмассиве. Более формально, подмассив [arr[i], arr[i + 1], ..., arr[j]] массива arr считается турбулентным тогда и только тогда, когда: Для всех i <= k < j: arr[k] > arr[k + 1], когда k нечетное, и arr[k] < arr[k + 1], когда k четное. Или, для всех i <= k < j: arr[k] > arr[k + 1], когда k четное, и arr[k] < arr[k + 1], когда k нечетное. Пример:

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

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

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

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

        return ans;
    }
};

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

Задача: 98. Validate Binary Search Tree Сложность: medium Дано бинарное дерево. Нужно определить, является ли оно допустимым деревом поиска (BST), в котором для каждого узла: все значения в левом поддереве строго меньше все значения в правом поддереве строго больше поддеревья также являются BST Пример:

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

👨‍💻 Алгоритм: 1⃣Используем итеративный обход в глубину через стек: для каждого узла храним допустимый диапазон значений — (min, max), который ограничивает допустимые значения для текущего узла. 2⃣При проходе вниз: левый потомок должен быть в диапазоне [min, node.val) правый потомок должен быть в диапазоне (node.val, max] 3⃣Если в процессе обхода найден узел, нарушающий ограничения диапазона — дерево не является BST, возвращаем false. 😎 Решение:

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

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

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

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

            if (root == nullptr) continue;

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

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

        return true;
    }
};

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

Стань частью команды поддержки Т-Банка. Выбери вакансию В ваши летние планы входит обновление карьеры? Можно работать с клиентами Т-Банка: есть вакансии на удаленке, с гибким графиком и обучением. Посмотрите на сайте! Узнать больше #реклама tbank.ru О рекламодателе

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

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

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

#include <vector>
#include <queue>

using namespace std;

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

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

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

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

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

Все серии шпионского детектива «Разящий луч» уже на Иви! ❤️Повёлся на женскую провокацию и сдал себя с потрохами! 🏃‍♂️Молодой и влюблённый Ульрих делает роковую ошибку, раскрывая своё местонахождение. Ведь за ним и его матерью гонятся сотрудники ЦРУ. Парень должен стать разменной монетой в борьбе советской и американской разведок. На кону — секретный проект новейшего лазерного оружия. ⚡Включайте «Разящий луч» и узнайте, чем закончится гонка вооружений США и СССР в разгар холодной войны. Создатели сериала вдохновлялись реальными советскими учёными и разработками, что, однако, не помешало им лихо закрутить сюжет! Смотреть #реклама 16+ ivi.ru О рекламодателе

Задача: 980. Unique Paths III Сложность: hard Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть: 1, представляющая начальную клетку. Существует ровно одна начальная клетка. 2, представляющая конечную клетку. Существует ровно одна конечная клетка. 0, представляющая пустые клетки, по которым можно ходить. -1, представляющая препятствия, по которым нельзя ходить. Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз. Пример:

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

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

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

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

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

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

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

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

            backtrack(next_row, next_col, remain);
        }

        grid[row][col] = temp;
    }

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

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

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

        path_count = 0;

        backtrack(start_row, start_col, non_obstacles);

        return path_count;
    }
};

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

В Битрикс24 теперь можно сделать сайт за 30 секунд Серьёзно. Пишешь, что нужно, и AI сам всё собирает: тексты, картинки, оформление. ✨Никакой магии, просто умный помощник. Попробуйте — закайфуете от скорости! Начать #реклама 16+ sites-24.bitrix24.ru О рекламодателе

Задача: 370. Range Addition Сложность: medium Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci]. У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci. Верните arr после применения всех обновлений. Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

👨‍💻 Алгоритм: 1⃣Для каждого обновления (start, end, val) выполните две операции: Увеличьте значение в позиции start на val: arr[start] = arr[start] + val. Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val. 2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0). 3⃣Верните обновленный массив arr. 😎 Решение:

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

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

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

    return result;
}

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

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

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

👨‍💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:

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

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

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

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

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

Не платите больше. Зафиксируйте цену сегодня Сколько клиентов вы уже упустили? Каждая просроченная заявка – это деньги вашим конкурентам. amoCRM помогает закрывать сделки, пока другие теряют лиды. Мы не делаем универсальных решений для всех. Только то, что работает в продажах. И одно из лучших решений, которое вы можете принять сейчас – это зафиксировать текущую цену. С 01 сентября amoCRM станет дороже. Но если подключитесь до этой даты, мы зафиксируем текущую цену для вас — и сейчас, и при продлении. ✨ Переходите по ссылке и успейте зафиксировать свою выгоду! Узнать больше #реклама 16+ amocrm.ru О рекламодателе

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60 Сложность: medium Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0. Пример:

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

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

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

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

Продажа апартаментов в Красной Поляне ✅ АК «Поляна Пик» — премиум в Красной Поляне! 🏠 Апартаменты с ремонтом и мебелью от застройщика 💻 Под управлением DoubleTree by Hilton 4* ✨ Бассейн 25м, территория 4.5 Га Площади от 47 до 144 м² ФЗ-214 | Ипотека | Рассрочка Онлайн-показ — смотрите из любой точки мира! ⚡ Подробности на сайте! Узнать больше Изучите все условия кредита (займа) на сайте в соответствующем разделе. Оценивайте свои финансовые возможности и риски. Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ ТАВРИДА СТРОЙ. Финансовые услуги оказывает: ООО СЗ ТАВРИДА СТРОЙ, ПАО "Сбербанк". #реклама invest-apartmens.online О рекламодателе

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

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

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте двумерный массив sums размером (m + 1) x (n + 1), где m и n — размеры исходной матрицы matrix. Заполните этот массив нулями. 2⃣Предварительное вычисление сумм: Заполните массив sums, где каждый элемент sums[i][j] будет содержать сумму всех элементов матрицы от начала до позиции (i-1, j-1) включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов внутри прямоугольника, определенного его углами (row1, col1) и (row2, col2), используйте предварительно вычисленный массив sums для получения результата за O(1) времени. 😎 Решение:

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

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

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 124. Binary Tree Maximum Path Sum Сложность: hard Вам дан массив цен, где prices[i] — цена акции в i-й день. Можно совершить не более двух транзакций. Найдите максимальную прибыль. Пример:

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

👨‍💻 Алгоритм: 1⃣Проходим массив слева направо и сохраняем в leftProfits[i] максимальную прибыль от одной транзакции от начала до дня i. 2⃣Проходим массив справа налево и сохраняем в rightProfits[i] максимальную прибыль от одной транзакции от дня i до конца. 3⃣Для каждой точки разбиения i считаем сумму leftProfits[i] + rightProfits[i+1], и выбираем максимум из всех таких сумм. 😎 Решение:

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

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

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

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

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

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

        return maxProfit;
    }
};

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