C/C++ | LeetCode

Бесплатный курс по дизайну: веб, графический и UX/UI Получи востребованные навыки: - создание дизайна сайтов и приложений - создание инфографики и карточек для маркетплейсов - работа в графическом редакторе Figma и др. Студенты курса в среднем зарабатывают от 68 000 ₽ уже во время обучения💰 Зарегистрироваться #реклама 16+ ydaev.ru О рекламодателе

Задача: 526. Beautiful Arrangement Сложность: medium Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий: perm[i] делится на i. i делится на perm[i]. Дано целое число n, верните количество красивых перестановок, которые вы можете создать. Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

class Solution {
public:
    int count = 0;
    
    int countArrangement(int N) {
        vector<int> nums(N);
        iota(nums.begin(), nums.end(), 1);
        permute(nums, 0);
        return count;
    }
    
    void permute(vector<int>& nums, int l) {
        if (l == nums.size()) {
            count++;
        }
        for (int i = l; i < nums.size(); ++i) {
            swap(nums[i], nums[l]);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                permute(nums, l + 1);
            }
            swap(nums[i], nums[l]);
        }
    }
};

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

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 113. Path Sum II Сложность: medium Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листов, сумма значений узлов в которых равна targetSum. Каждый путь должен быть представлен списком значений узлов. Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]]

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

class Solution {
public:
    void recurseTree(TreeNode* node, int remainingSum, vector<int>& pathNodes,
                     vector<vector<int>>& pathsList) {
        if (node == NULL) {
            return;
        }

        pathNodes.push_back(node->val);

        if (remainingSum == node->val && node->left == NULL && node->right == NULL) {
            pathsList.push_back(vector<int>(pathNodes));
        } else {
            this->recurseTree(node->left, remainingSum - node->val, pathNodes, pathsList);
            this->recurseTree(node->right, remainingSum - node->val, pathNodes, pathsList);
        }

        pathNodes.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> pathsList;
        vector<int> pathNodes;
        this->recurseTree(root, sum, pathNodes, pathsList);
        return pathsList;
    }
};

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

Задача: 344. Reverse String Сложность: easy Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s. Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти. Пример:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

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

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

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

⚡️ Айтишник из «VISION» скупил топовые айти-курсы и выложил гигабайты материалов к себе Каждый найдет что-то по душе: 903 ГБ — Python 812 ГБ — Frontend 978 ГБ — C, C++ 804 ГБ — Java 432 ГБ — C#, GameDev 411 ГБ — SQL & БД 309 ГБ — DevOps 998 ГБ — ИБ & Хакинг 773 ГБ — Kotlin, Swift 189 ГБ — PHP 201 ГБ — GoLang 170 ГБ — Rust 167 ГБ — QA-Тестирование 310 ГБ — 1C + Лицензии 495 ГБ — Машинное обучение 704 ГБ — Аналитика Данных 991 ГБ — Дизайн Материалы в закрепе, постоянно пополняются👆🏻

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

Задача: 535. Encode and Decode TinyURL Сложность: medium Спроектируйте класс для кодирования URL и декодирования короткого URL. Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL. Реализуйте класс Solution: Solution() Инициализирует объект системы. String encode(String longUrl) Возвращает короткий URL для данного longUrl. String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом. Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

class Codec {
public:
    string alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    unordered_map<string, string> map;
    random_device rd;
    mt19937 gen;
    
    Codec() : gen(rd()) {}
    
    string getRand() {
        string res;
        for (int i = 0; i < 6; ++i) {
            res += alphabet[gen() % 62];
        }
        return res;
    }
    
    string encode(string longUrl) {
        string key = getRand();
        while (map.find(key) != map.end()) {
            key = getRand();
        }
        map[key] = longUrl;
        return "http://tinyurl.com/" + key;
    }

    string decode(string shortUrl) {
        string key = shortUrl.substr(19);
        return map[key];
    }
};

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

Задача: 1235. Maximum Profit in Job Scheduling Сложность: hard У нас есть n заданий, где каждое задание планируется выполнить от startTime[i] до endTime[i], получив прибыль profit[i]. Вам даны массивы startTime, endTime и profit, верните максимальную прибыль, которую вы можете получить, так чтобы в подмножестве не было двух заданий с перекрывающимся временным диапазоном. Если вы выберете задание, которое заканчивается в момент времени X, вы сможете начать другое задание, которое начинается в момент времени X. Пример:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120

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

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        vector<tuple<int, int, int>> jobs;
        for (int i = 0; i < startTime.size(); ++i) {
            jobs.emplace_back(endTime[i], startTime[i], profit[i]);
        }
        sort(jobs.begin(), jobs.end());

        vector<pair<int, int>> dp = {{0, 0}};

        for (auto& [e, s, p] : jobs) {
            auto it = upper_bound(dp.begin(), dp.end(), make_pair(s, INT_MAX));
            int new_profit = prev(it)->second + p;
            if (new_profit > dp.back().second) {
                dp.emplace_back(e, new_profit);
            }
        }

        return dp.back().second;
    }
};

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

Переезжай на Юг! Скидка 2% клиентам из других регионов ЖК "Песчаный" Анапа – Выгода до 642 000 ₽ за наличный расчет; – Ремонт в подарок на 2-к квартиры; – Паркинг на 226 мест; – Дизайнерский ремонт "под ключ"; – 5 минут до моря; – Закрытая территория; – ФЗ-214. Не является публичной офертой. Перейти на сайт Проектная декларация на сайте https://наш.дом.рф/. #реклама ssk-peschaniy.ru О рекламодателе

Задача: 967. Numbers With Same Consecutive Differences Сложность: medium Даны два целых числа n и k, верните массив всех целых чисел длины n, где разница между каждыми двумя последовательными цифрами равна k. Вы можете вернуть ответ в любом порядке. Учтите, что целые числа не должны начинаться с нулей. Целые числа, такие как 02 и 043, не допускаются. Пример:

Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

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

class Solution {
public:
    vector<int> numsSameConsecDiff(int N, int K) {
        if (N == 1) return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        vector<int> queue = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        for (int level = 1; level < N; ++level) {
            vector<int> nextQueue;
            for (int num : queue) {
                int tailDigit = num % 10;
                vector<int> nextDigits = {tailDigit + K, tailDigit - K};
                
                for (int nextDigit : nextDigits) {
                    if (nextDigit >= 0 && nextDigit < 10) {
                        nextQueue.push_back(num * 10 + nextDigit);
                    }
                }
            }
            queue = nextQueue;
        }
        
        return queue;
    }
};

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

Задача: 739. Daily Temperatures Сложность: medium Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0. Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> answer(n, 0);
        stack<int> stack;
        
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && T[i] > T[stack.top()]) {
                int j = stack.top();
                stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        return answer;
    }
};

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

Задача: 40. Combination Sum II Сложность: medium Дан массив candidates и число target. Найдите все уникальные комбинации, где сумма элементов равна target. Каждое число можно использовать только один раз. Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

👨‍💻 Алгоритм: 1⃣Отсортировать и подсчитать количество каждого уникального элемента, чтобы избежать дубликатов. 2⃣Запустить рекурсивный backtrack, на каждом шаге выбирая доступный элемент, уменьшая его частоту и остаток target. 3⃣Если remain == 0 — сохранить комбинацию; иначе — откатить шаг (уменьшение глубины, восстановление частоты и удаление элемента из комбинации). 😎 Решение:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> comb;
        map<int, int> counter;
        for (int candidate : candidates) {
            counter[candidate]++;
        }
        vector<pair<int, int>> counterList(counter.begin(), counter.end());
        backtrack(comb, target, 0, counterList, results);
        return results;
    }

private:
    void backtrack(vector<int>& comb, int remain, int curr,
                   vector<pair<int, int>>& counter,
                   vector<vector<int>>& results) {
        if (remain == 0) {
            results.push_back(comb);
            return;
        } else if (remain < 0) {
            return;
        }

        for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
            auto& [candidate, freq] = counter[nextCurr];
            if (freq == 0) continue;

            comb.push_back(candidate);
            --freq;

            backtrack(comb, remain - candidate, nextCurr, counter, results);

            ++freq;
            comb.pop_back();
        }
    }
};

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

Задача: 258. Add Digits Сложность: easy Дано целое число num. Необходимо многократно складывать его цифры, пока не получится однозначное число, и вернуть его. Пример:

Input: num = 38
Output: 2
Объяснение: 3 + 8 = 11 → 1 + 1 = 2

👨‍💻 Алгоритм: 1⃣Используем переменную digital_root, в которую будем поэтапно добавлять цифры num. 2⃣В цикле: Добавляем num % 10 к digital_root Делим num на 10 (удаляем последнюю цифру) Если num == 0 и digital_root > 9, значит, число всё ещё не однозначное — присваиваем digital_root в num и обнуляем digital_root, продолжая цикл. 3⃣Как только число становится однозначным, возвращаем его. 😎 Решение:

class Solution {
public:
    int addDigits(int num) {
        int digital_root = 0;
        while (num > 0) {
            digital_root += num % 10;
            num /= 10;
            if (num == 0 && digital_root > 9) {
                num = digital_root;
                digital_root = 0;
            }
        }
        return digital_root;
    }
};

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

Задача: 1530. Number of Good Leaf Nodes Pairs Сложность: medium Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance. Верните количество хороших пар листовых узлов в дереве. Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

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

class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        unordered_map<TreeNode*, vector<TreeNode*>> graph;
        unordered_set<TreeNode*> leafNodes;
        traverseTree(root, nullptr, graph, leafNodes);
        int ans = 0;
        for (auto leaf : leafNodes) {
            queue<TreeNode*> bfsQueue;
            unordered_set<TreeNode*> seen;
            bfsQueue.push(leaf);
            seen.insert(leaf);
            for (int i = 0; i <= distance; ++i) {
                int size = bfsQueue.size();
                for (int j = 0; j < size; ++j) {
                    TreeNode* currNode = bfsQueue.front();
                    bfsQueue.pop();
                    if (leafNodes.count(currNode) && currNode != leaf) {
                        ++ans;
                    }
                    for (auto neighbor : graph[currNode]) {
                        if (!seen.count(neighbor)) {
                            bfsQueue.push(neighbor);
                            seen.insert(neighbor);
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

private:
    void traverseTree(TreeNode* currNode, TreeNode* prevNode,
                      unordered_map<TreeNode*, vector<TreeNode*>>& graph, unordered_set<TreeNode*>& leafNodes) {
        if (!currNode) {
            return;
        }
        if (!currNode->left && !currNode->right) {
            leafNodes.insert(currNode);
        }
        if (prevNode) {
            graph[prevNode].push_back(currNode);
            graph[currNode].push_back(prevNode);
        }
        traverseTree(currNode->left, currNode, graph, leafNodes);
        traverseTree(currNode->right, currNode, graph, leafNodes);
    }
};

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

REKONFA Live 6 ноября приглашаем всех, кто имеет отношение к маркетингу и рекламным технологиям, обсудить рынок, тренды, вызовы и их решения. С докладами на актуальные темы выступят лидеры индустрии и медийные спикеры. Принять участие можно офлайн и онлайн. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 1539. Kth Missing Positive Number Сложность: easy Дан массив arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k. Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве. Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

👨‍💻 Алгоритм: 1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1. 2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте. 3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k. 😎 Решение:

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        int n = arr.size();
        for (int i = 0; i < n - 1; ++i) {
            int currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
};

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

Как получить максимальный доход от недвижимости? Инвестиционные квартиры в Лимасоле 📅 Вебинар: 2 октября 19:00 по Мск Вебинар точно для вас, если: ✅ Вы хотите инвестировать в недвижимость с прогнозируемым потенциалом. ✅ Получить стабильный и высокий доход в евро. ✅ Рассматриваете Кипр для инвестиций, ПМЖ, релокации семьи или спокойной жизни у моря. ✅Цените эксклюзивные предложения, которых нет в открытом доступе. Ждем вас на вебинаре! Зарегистрироваться #реклама 16+ webinar.tranio.ru О рекламодателе

Задача: 531. Lonely Pixel I Сложность: medium Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей. Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей. Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

👨‍💻 Алгоритм: 1⃣ Подсчёт количества чёрных пикселей в строках и столбцах: Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1. 2⃣ Поиск одиночных чёрных пикселей: Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1. 3⃣ Возврат результата: Верните answer. 😎 Решение:

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int n = picture.size();
        int m = picture[0].size();
        
        vector<int> rowCount(n, 0);
        vector<int> columnCount(m, 0);
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    columnCount[j]++;
                }
            }
        }
        
        int answer = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && columnCount[j] == 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
};

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

Задача: 1376. Time Needed to Inform All Employees Сложность: medium В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID. У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру. Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости. i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость). Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости. Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

👨‍💻 Алгоритм: 1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i. 2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1. 3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime. 😎 Решение:

class Solution {
public:
    int maxTime = INT_MIN;
    
    void DFS(vector<int> adjList[], vector<int>& informTime, int curr, int time) {
        maxTime = max(maxTime, time);
        for (int adjacent : adjList[curr]) { 
            DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<int> adjList[n];
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adjList[manager[i]].push_back(i);
            }
        }
        DFS(adjList, informTime, headID, 0);
        return maxTime;
    }
};

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