C/C++ | LeetCode

Задача: 755. Pour Water Сложность: medium Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке. Пример:

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

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

class Solution {
public:
    vector<int> pourWater(vector<int>& heights, int volume, int k) {
        for (int v = 0; v < volume; v++) {
            int dropIndex = k;
            for (int d : {-1, 1}) {
                int i = k;
                while (i + d >= 0 && i + d < heights.size() && heights[i + d] <= heights[i]) {
                    if (heights[i + d] < heights[i]) {
                        dropIndex = i + d;
                    }
                    i += d;
                }
                if (dropIndex != k) {
                    break;
                }
            }
            heights[dropIndex]++;
        }
        return heights;
    }
};

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

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

Задача: 128. Longest Consecutive Sequence Сложность: medium Найти длину самой длинной последовательности последовательных чисел в неотсортированном массиве. Время работы — O(n). Пример:

Input: [100,4,200,1,3,2] → Output: 4

👨‍💻 Алгоритм: 1⃣Помещаем все числа в unordered_set, чтобы можно было быстро проверять наличие элемента (O(1) время доступа). 2⃣Проходим по каждому числу, и если num - 1 не существует в сете — это начало новой последовательности. Затем увеличиваем currentNum, пока currentNum + 1 есть в сете, считая длину последовательности. 3⃣После проверки каждого числа обновляем longestStreak, если текущая последовательность длиннее. 😎 Решение:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.count(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};

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

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

Задача: 1470. Shuffle the Array Сложность: easy Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn]. Верните массив в форме [x1, y1, x2, y2, ..., xn, yn]. Пример:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

👨‍💻 Алгоритм: 1⃣Создайте массив result размером 2 * n. 2⃣Итеративно пройдите по массиву nums от 0 до n - 1: Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result. Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result. 3⃣Верните массив result. 😎 Решение:

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> result(2 * n);
        for (int i = 0; i < n; ++i) {
            result[2 * i] = nums[i];
            result[2 * i + 1] = nums[n + i];
        }
        return result;
    }
};

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

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

Задача: 1026. Maximum Difference Between Node and Ancestor Сложность: medium Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b. Пример:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7

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

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

class Solution {
public:
    int maxAncestorDiff(TreeNode* root) {
        return dfs(root, root->val, root->val);
    }
    
private:
    int dfs(TreeNode* node, int min_val, int max_val) {
        if (!node) return max_val - min_val;
        min_val = min(min_val, node->val);
        max_val = max(max_val, node->val);
        int left = dfs(node->left, min_val, max_val);
        int right = dfs(node->right, min_val, max_val);
        return max(left, right);
    }
};

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

Гайд МТС Линк для CEO по эффективным онлайн-встречам Как CEO сохранять фокус на стратегии и развивающих задачах и не терять договоренности с руководителями и топ-командой? Гайд МТС Линк — чек-листы, кейсы и подходы для оптимизации совещаний с помощью онлайн-встреч и ИИ. ✅ В гайде: - Как доносить цели, культуру и стратегию компании до каждого сотрудника; - Как снижать затраты на корпоративное обучение без потери качества и вовлечения; - Как сократить расходы на организацию имиджевых событий с помощью одного решения; - Как не устроить хаос в коммуникациях между командами при расширении компании. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 834. Sum of Distances in Tree Сложность: hard Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами. Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве. Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами. Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

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

class Solution {
public:
    vector<int> ans, count;
    vector<unordered_set<int>> graph;
    int N;

    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
        this->N = N;
        graph.resize(N);
        ans.resize(N);
        count.resize(N, 1);

        for (auto& edge : edges) {
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }

        dfs(0, -1);
        dfs2(0, -1);
        return ans;
    }

    void dfs(int node, int parent) {
        for (int child : graph[node]) {
            if (child != parent) {
                dfs(child, node);
                count[node] += count[child];
                ans[node] += ans[child] + count[child];
            }
        }
    }

    void dfs2(int node, int parent) {
        for (int child : graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child];
                dfs2(child, node);
            }
        }
    }
};

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

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

Задача: 785. Is Graph Bipartite? Сложность: medium Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами: Нет петель (graph[u] не содержит u). Нет параллельных ребер (graph[u] не содержит дублирующихся значений). Если v есть в graph[u], то u есть в graph[v] (граф неориентированный). Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути. Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B. Верните true, если и только если граф является двудольным. Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

👨‍💻 Алгоритм: 1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null). 2⃣Мы должны быть внимательны к рассмотрению несвязных компонентов графа, выполняя поиск для каждого узла. Для каждого неокрашенного узла мы начнем процесс окрашивания, выполняя поиск в глубину (DFS) для этого узла. Каждый соседний узел получает цвет, противоположный цвету текущего узла. Если мы обнаруживаем, что соседний узел окрашен в тот же цвет, что и текущий узел, значит, наше окрашивание невозможно. 3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел. 😎 Решение:

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        unordered_map<int, int> color;
        for (int node = 0; node < graph.size(); ++node) {
            if (!color.count(node)) {
                stack<int> stack;
                stack.push(node);
                color[node] = 0;
                while (!stack.empty()) {
                    int node = stack.top();
                    stack.pop();
                    for (int nei : graph[node]) {
                        if (!color.count(nei)) {
                            stack.push(nei);
                            color[nei] = color[node] ^ 1;
                        } else if (color[nei] == color[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};

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

🔥 Вакансии в команду разработчиков YADRO: Получите оффер этим летом! 🚀 Хотите писать код, который становится основой для продуктов и новых технологических решений? YADRO — лидер российской инженерной индустрии — расширяет команды разработки BIOS/BMC. 📅 У вас будет возможность присоединиться к команде, которая создаёт ПО UEFI (BIOS) и BMC для серверов, систем хранения данных и телеком-оборудования. Мы работаем с проектами открытого исходного кода — EDK2 и OpenBMC — и влияем на развитие всей индустрии. Кого мы ищем? Ведущих и старших разработчиков — разработка встроенного ПО для серверов — от архитектуры BMC до работы с UEFI и OpenBMC: 1️⃣ TeamLead разработки OpenBMC. 2️⃣ Ведущего разработчика интерфейсов встраиваемых систем (Linux/OpenBMC). 3️⃣ Ведущего разработчика C++ (Linux/OpenBMC). 4️⃣ Старшего C разработчика (BIOS/UEFI). QA-инженеров (ручное и автоматизированное тестирование) — тестирование встроенного ПО, автоматизация процессов и улучшение качества наших платформ: 1️⃣ Инженер по верификации и ручному тестированию встроенного ПО (QA) 2️⃣ Инженер по автоматизации тестирования / Automation QA 3️⃣ Старший инженер по автоматизации аппаратного тестирования / Embedded AQA Почему YADRO? ➡️ Распределённая команда — работайте удалённо или в офисах в Москве, СПб, Нижнем Новгороде, Екатеринбурге и Минске. ➡️ Работа с уникальными проектами, влияющими на жизнь миллионов пользователей. ➡️ Реальный карьерный рост: как вертикальный, так и горизонтальный. ➡️ Возможность работать с талантливыми инженерами и напрямую влиять на развитие технологий. 💙 Присоединяйтесь к YADRO и становитесь частью масштабных проектов!

Регистрируйтесь на Yandex Ecom Open Air 8 августа Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

Задача: 756. Pyramid Transition Matrix Сложность: medium Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае. Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

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

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string, vector<char>> allowedDict;

        for (const string& pattern : allowed) {
            string key = pattern.substr(0, 2);
            char value = pattern[2];
            allowedDict[key].push_back(value);
        }

        return canBuild(bottom, allowedDict);
    }

private:
    bool canBuild(string currentLevel, unordered_map<string, vector<char>>& allowedDict) {
        if (currentLevel.size() == 1) return true;

        vector<vector<char>> nextLevelOptions;
        for (size_t i = 0; i < currentLevel.size() - 1; ++i) {
            string key = currentLevel.substr(i, 2);
            if (!allowedDict.count(key)) return false;
            nextLevelOptions.push_back(allowedDict[key]);
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict);
    }

    bool canBuildNextLevel(vector<vector<char>>& options, size_t index, string nextLevel, unordered_map<string, vector<char>>& allowedDict) {
        if (index == options.size()) return canBuild(nextLevel, allowedDict);
        for (char option : options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true;
        }
        return false;
    }
};

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

Задача: 527. Word Abbreviation Сложность: hard Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова. Правила сокращения строки следующие: Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ. Если более одного слова имеют одинаковое сокращение, выполните следующее: Увеличьте префикс (символы в первой части) каждого из их сокращений на 1. Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"]. Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным. В конце, если сокращение не сделало слово короче, оставьте его в исходном виде. Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

class Solution {
public:
    vector<string> wordsAbbreviation(vector<string>& words) {
        int n = words.size();
        vector<string> ans(n);
        vector<int> prefix(n, 0);

        for (int i = 0; i < n; ++i)
            ans[i] = abbrev(words[i], 0);

        for (int i = 0; i < n; ++i) {
            while (true) {
                unordered_set<int> dupes;
                for (int j = i + 1; j < n; ++j) {
                    if (ans[i] == ans[j])
                        dupes.insert(j);
                }

                if (dupes.empty()) break;
                dupes.insert(i);
                for (int k : dupes) {
                    ans[k] = abbrev(words[k], ++prefix[k]);
                }
            }
        }

        return ans;
    }

private:
    string abbrev(const string& word, int i) {
        int n = word.size();
        if (n - i <= 3) return word;
        return word.substr(0, i + 1) + to_string(n - i - 2) + word.back();
    }
};

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

Гайд МТС Линк для CCO по эффективным вебинарам Как коммерческим директорам системно развивать продажи и маркетинг без лишних затрат на перёлеты тренеров, расширения команды и ФОТ? Гайд МТС Линк — чек-листы, кейсы и подходы для управления продажами и маркетингом с помощью вебинаров. ✅ В гайде: - Как правильно использовать онлайн-мероприятия для продвижения продуктов компании; - Как увеличить конверсию из участника мероприятия в лид с помощью данных о поведении зрителей; - Как сократить расходы на организацию внутреннего обучения без потери качества и вовлечения; - Как оценить вклад онлайн-мероприятия в продвижение компании и правильно обработать лиды. Бонус внутри: Чек-лист c инструментами для продвижения вебинара. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 1250. Check If It Is a Good Array Сложность: hard Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False. Пример:

Input: nums = [12,5,7,23]
Output: true

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

class Solution {
public:
    bool isGoodArray(std::vector<int>& nums) {
        int gcd = nums[0];
        for (int num : nums) {
            gcd = std::gcd(gcd, num);
            if (gcd == 1) return true;
        }
        return gcd == 1;
    }
};

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

Задача: 977. Squares of a Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке. Верните массив квадратов каждого числа, отсортированный в неубывающем порядке. Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

👨‍💻 Алгоритм: 1⃣Создайте массив квадратов каждого элемента. 2⃣Отсортируйте массив квадратов. 3⃣Верните отсортированный массив квадратов. 😎 Решение:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        size_t n = nums.size();
        vector<int> ans(n);
        for (size_t i = 0; i < n; i++) {
            ans[i] = nums[i] * nums[i];
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};

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

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

Задача: 1074. Number of Submatrices That Sum to Target Сложность: hard Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению. Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2. Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'. Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

👨‍💻 Алгоритм: 1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений. 2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target. 3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count. 😎 Решение:

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int r = matrix.size(), c = matrix[0].size();
        vector<vector<int>> ps(r + 1, vector<int>(c + 1, 0));
        
        for (int i = 1; i <= r; ++i) {
            for (int j = 1; j <= c; ++j) {
                ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        
        int count = 0;
        
        for (int r1 = 1; r1 <= r; ++r1) {
            for (int r2 = r1; r2 <= r; ++r2) {
                unordered_map<int, int> h;
                h[0] = 1;
                for (int col = 1; col <= c; ++col) {
                    int currSum = ps[r2][col] - ps[r1 - 1][col];
                    count += h[currSum - target];
                    h[currSum]++;
                }
            }
        }
        
        return count;
    }
};

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