C/C++ | LeetCode

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама 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;
    }
};

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

Задача: 1155. Number of Dice Rolls With Target Sum Сложность: medium У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k. Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

👨‍💻 Алгоритм: 1⃣Начните с: Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент. Сумма чисел на предыдущих кубиках currSum равна 0. Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию. 2⃣Базовые случаи: Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target. 3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum. 😎 Решение:

class Solution {
public:
    const int MOD = 1e9 + 7;

    int waysToTarget(vector<vector<int>>& memo, int diceIndex, int n, int currSum, int target, int k) {
        if (diceIndex == n) {
            return currSum == target;
        }
        if (memo[diceIndex][currSum] != -1) {
            return memo[diceIndex][currSum];
        }

        int ways = 0;
        for (int i = 1; i <= min(k, target - currSum); i++) {
            ways = (ways + waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD;
        }
        return memo[diceIndex][currSum] = ways;
    }

    int numRollsToTarget(int n, int k, int target) {
        vector<vector<int>> memo(n + 1, vector<int>(target + 1, -1));
        return waysToTarget(memo, 0, n, 0, target, k);
    }
};

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

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

Задача: 1020. Number of Enclaves Сложность: medium Вам дана двоичная матричная сетка m x n, где 0 обозначает морскую ячейку, а 1 - сухопутную. Ход состоит из перехода от одной сухопутной ячейки к другой соседней (в 4-х направлениях) или выхода за границу сетки. Верните количество сухопутных ячеек в сетке, для которых мы не можем выйти за границу сетки за любое количество ходов. Пример:

Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3

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

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != 1)
            return;
        grid[x][y] = 0;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
    
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 1)
                dfs(grid, i, 0);
            if (grid[i][n - 1] == 1)
                dfs(grid, i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            if (grid[0][j] == 1)
                dfs(grid, 0, j);
            if (grid[m - 1][j] == 1)
                dfs(grid, m - 1, j);
        }
        
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1)
                    ++count;
            }
        }
        return count;
    }
};

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

Задача: 36. Valid Sudoku Сложность: medium Определите, является ли 9×9 судоку валидным. Проверке подлежат только заполненные ячейки. Каждое число от 1 до 9 должно встречаться один раз в каждой строке, столбце и каждом из девяти 3×3 подблоков. Пример:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: true

👨‍💻 Алгоритм: 1⃣Инициализируем по 9 множеств для строк, столбцов и блоков 3×3. 2⃣Проходим по всем ячейкам: — если символ '.' — пропускаем. — если число уже есть в строке/столбце/блоке — возвращаем false. 3⃣Если дубликатов не найдено — возвращаем true. 😎 Решение:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int N = 9;
        unordered_set<char> rows[9];
        unordered_set<char> cols[9];
        unordered_set<char> boxes[9];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                char val = board[r][c];
                if (val == '.') continue;
                if (rows[r].count(val) || cols[c].count(val) || boxes[(r/3)*3 + c/3].count(val))
                    return false;
                rows[r].insert(val);
                cols[c].insert(val);
                boxes[(r/3)*3 + c/3].insert(val);
            }
        }
        return true;
    }
};

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

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing Сложность: hard Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим. В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j]. Если нет способа сделать arr1 строго возрастающим, верните -1. Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

👨‍💻 Алгоритм: 1⃣Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение. 2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]). 3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1. 😎 Решение:

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        int answer = dfs(0, -1, arr1, arr2);
        return answer < 2001 ? answer : -1;
    }
    
private:
    unordered_map<pair<int, int>, int, hash_pair> dp;
    
    int dfs(int i, int prev, vector<int>& arr1, vector<int>& arr2) {
        if (i == arr1.size()) return 0;
        pair<int, int> key = {i, prev};
        if (dp.count(key)) return dp[key];
        
        int cost = 2001;
        if (arr1[i] > prev) {
            cost = dfs(i + 1, arr1[i], arr1, arr2);
        }
        int idx = bisectRight(arr2, prev);
        if (idx < arr2.size()) {
            cost = min(cost, 1 + dfs(i + 1, arr2[idx], arr1, arr2));
        }
        
        dp[key] = cost;
        return cost;
    }
    
    int bisectRight(const vector<int>& arr, int value) {
        int left = 0, right = arr.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    struct hash_pair {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2>& p) const {
            auto hash1 = hash<T1>{}(p.first);
            auto hash2 = hash<T2>{}(p.second);
            return hash1 ^ hash2;
        }
    };
};

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