C/C++ | LeetCode

Дизайн в FIGMA с нуля. Бесплатный курс + портфолио ✅ Личный наставник ✅ Подойдет новичкам ✅ Разбор всех ваших Д/З ✅ 4+ работы себе в портфолио Попробуй себя в дизайне это бесплатно! Узнать больше #реклама 16+ yudaevschool.com О рекламодателе

Задача: 1062. Longest Repeating Substring Сложность: medium Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0. Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

class Solution {
public:
    int search(int L, int n, string S) {
        unordered_set<string> seen;
        for (int start = 0; start <= n - L; ++start) {
            string tmp = S.substr(start, L);
            if (seen.count(tmp)) return start;
            seen.insert(tmp);
        }
        return -1;
    }

    int longestRepeatingSubstring(string S) {
        int n = S.length();
        int left = 1, right = n;
        while (left <= right) {
            int L = left + (right - left) / 2;
            if (search(L, n, S) != -1) {
                left = L + 1;
            } else {
                right = L - 1;
            }
        }
        return left - 1;
    }
};

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

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

Задача: 43. Multiply Strings Сложность: hard Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните их произведение, также в виде строки. Нельзя использовать встроенные BigInteger или преобразование строк в числа напрямую. Пример:

Input: num1 = "2", num2 = "3" Output: "6"

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

class Solution {
private:
    string sumResults(vector<vector<int>>& results) {
        vector<int> answer = results.back();
        results.pop_back();
        vector<int> newAnswer;
        int carry = 0;

        for (vector<int>& result : results) {
            newAnswer.clear();
            int maxLen = max(answer.size(), result.size());
            for (int i = 0; i < maxLen || carry; ++i) {
                int sum = carry + (i < result.size() ? result[i] : 0) + (i < answer.size() ? answer[i] : 0);
                newAnswer.push_back(sum % 10);
                carry = sum / 10;
            }
            answer = move(newAnswer);
        }
        string finalAnswer;
        for (int digit : answer) finalAnswer.push_back(digit + '0');
        return finalAnswer;
    }

    vector<int> multiplyOneDigit(string& firstNumber, char secondNumberDigit, int numZeros) {
        vector<int> currentResult(numZeros, 0);
        int carry = 0;

        for (char firstNumberDigit : firstNumber) {
            int multiplication = (secondNumberDigit - '0') * (firstNumberDigit - '0') + carry;
            currentResult.push_back(multiplication % 10);
            carry = multiplication / 10;
        }

        if (carry) currentResult.push_back(carry);
        return currentResult;
    }

public:
    string multiply(string firstNumber, string secondNumber) {
        if (firstNumber == "0" || secondNumber == "0") return "0";

        reverse(firstNumber.begin(), firstNumber.end());
        reverse(secondNumber.begin(), secondNumber.end());

        vector<vector<int>> results;
        for (int i = 0; i < secondNumber.size(); ++i) {
            results.push_back(multiplyOneDigit(firstNumber, secondNumber[i], i));
        }
        string answer = sumResults(results);
        reverse(answer.begin(), answer.end());
        return answer;
    }
};

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

Ведем набор учеников 3-10 классов на новый учебный год! Московская школа программистов - это не курсы, а школа с государственной лицензией, которая обучает детей IT с 2001 года. Мы сотрудничаем с МФТИ, НИУ ВШЭ, Яндекс и Физтехпарк Что получит ребенок, в результате обучения: - Участие и победы в олимпиадах всероссийского и международного уровня - Поступление в престижные технические вузы России и работу в известных IT-компаниях: Apple, Google, Yandex, Nvidia и других - Практику на реальных IT-проектах - Усидчивость, целеустремленность и умение работать в команде - Сдача ЕГЭ/ОГЭ на высокие баллы Сейчас идет набор в виртуальный класс. В этом формате, дети в небольших группах обучаются с преподавателем онлайн в реальном времени. Эффективно как очно. Позаботьтесь о том, чтобы ребенок стал востребованным IT-специалистом! Зарегистрироваться #реклама 16+ vc.informatics.ru О рекламодателе

Задача: 927. Three Equal Parts Сложность: hard Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с i + 1 < j, такой что: arr[0], arr[1], ..., arr[i] - это первая часть, arr[i + 1], arr[i + 2], ...., arr[j - 1] - вторая часть, и arr[j], arr[j + 1], ..., arr[arr.length - 1] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение. Пример:

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

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

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int ones = 0;
        for (int num : arr) {
            ones += num;
        }
        if (ones % 3 != 0) return {-1, -1};
        if (ones == 0) return {0, (int)arr.size() - 1};

        int partOnes = ones / 3;
        int first = 0, second = 0, third = 0, cnt = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] == 1) {
                if (cnt == 0) first = i;
                else if (cnt == partOnes) second = i;
                else if (cnt == 2 * partOnes) third = i;
                cnt++;
            }
        }

        while (third < arr.size() && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++;
            second++;
            third++;
        }

        if (third == arr.size()) return {first - 1, second};
        return {-1, -1};
    }
};

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Открытые школы — это возможность за месяц прокачать свои навыки и получить оффер в ИТ-холдинг Т1. С тебя — год опыта работы в ИТ, с нас — бесплатный онлайн-интенсив и топовые преподаватели. Что ты получишь? ✅ Уникальный рыночный опыт. Наши проекты ежегодно получают награды на ИТ-конкурсах: Global CIO, Национальной банковской премии и др. ✅ Быстрый рост в ИТ при экспертной поддержке. ✅ Материалы от HR, которые помогут прокачать резюме и подготовиться к интервью в Т1. ✅ Поддержка опытных преподавателей и уникальный карьерный фаст-трек до мидла в Т1 для выпускников интенсива. ✅ Реальный шанс получить оффер в Т1. Подавай заявку до 11 апреля и приходи учиться! Старт ИТ-интенсива уже 14 апреля. Подать заявку #реклама 16+ t1.ru О рекламодателе

Задача: 820. Short Encoding of Words Сложность: medium Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что: words.length == indices.length Опорная строка s заканчивается символом '#'. Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i]. Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов. Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

👨‍💻 Алгоритм: 1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством. 2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'. 3⃣В конце вернем длину полученной опорной строки. 😎 Решение:

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> good(words.begin(), words.end());
        for (const string& word : words) {
            for (int k = 1; k < word.length(); ++k) {
                good.erase(word.substr(k));
            }
        }
        int length = 0;
        for (const string& word : good) {
            length += word.length() + 1;
        }
        return length;
    }
};

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

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

Задача: 1120. Maximum Average Subtree Сложность: medium Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты. Поддерево дерева — это любой узел этого дерева плюс все его потомки. Среднее значение дерева — это сумма его значений, деленная на количество узлов. Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

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

class Solution {
public:
    struct State {
        int nodeCount;
        int valueSum;
        double maxAverage;

        State(int nodes, int sum, double maxAvg)
            : nodeCount(nodes), valueSum(sum), maxAverage(maxAvg) {}
    };

    double maximumAverageSubtree(TreeNode* root) {
        return maxAverage(root).maxAverage;
    }

private:
    State maxAverage(TreeNode* root) {
        if (root == nullptr) {
            return State(0, 0, 0);
        }

        State left = maxAverage(root->left);
        State right = maxAverage(root->right);

        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root->val;
        double currentAverage = static_cast<double>(sum) / nodeCount;
        double maxAverage = std::max(currentAverage, std::max(left.maxAverage, right.maxAverage));

        return State(nodeCount, sum, maxAverage);
    }
};

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

Качаем скиллы PostgreSQL на PG BootCamp Russia 2025! Регистрируйся на бесплатную конференцию по PostgreSQL — 10.04.2025.📅 ✅ Бесплатное участие ✅ Опытные спикеры ✅ Тематические доклады ✅ Рабочие кейсы Каждый участник получает именной Сертификат участника мероприятия. Одни из немногих спикеров конференции: — Андрей Бородин PostgreSQL contributor, руководитель подразделения разработки РСУБД с открытым исходным кодом Yandex Cloud — Александр Никитин Ведущий администратор БД DBA.Team — Максим Милютин PostgreSQL Contributor, openGauss Contributor ... и многие другие. Регистрируйся, будет интересно! И бесплатно! Зарегистрироваться #реклама pgbootcamp.ru О рекламодателе

Задача: 1015. Smallest Integer Divisible by K Сложность: medium Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число. Пример:

Input: k = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Использование остатка для нахождения числа с цифрами 1: Создайте переменную num и установите ее равной 1. Создайте переменную length и установите ее равной 1 для отслеживания длины числа. 2⃣Итеративное нахождение числа: Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k. Увеличивайте length на 1 в каждой итерации. Если в какой-то итерации num % k == 0, верните length. 3⃣Проверка бесконечного цикла: Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует. 😎 Решение:

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        unordered_set<int> seen;
        
        while (num % k != 0) {
            if (seen.count(num % k)) {
                return -1;
            }
            seen.insert(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
};

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

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

Задача: 1372. Longest ZigZag Path in a Binary Tree Сложность: medium Вам дан корень бинарного дерева. Зигзагообразный путь для бинарного дерева определяется следующим образом: Выберите любой узел в бинарном дереве и направление (вправо или влево). Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу. Измените направление с вправо на влево или с влево на вправо. Повторяйте второй и третий шаги, пока не сможете двигаться по дереву. Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0). Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве. Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

#include <algorithm>

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

class Solution {
public:
    int maxLength = 0;

    int longestZigZag(TreeNode* root) {
        dfs(root, true, 0);
        dfs(root, false, 0);
        return maxLength;
    }

    void dfs(TreeNode* node, bool isLeft, int length) {
        if (!node) return;
        maxLength = std::max(maxLength, length);
        if (isLeft) {
            dfs(node->left, false, length + 1);
            dfs(node->right, true, 1);
        } else {
            dfs(node->right, true, length + 1);
            dfs(node->left, false, 1);
        }
    }
};

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

Задача: 684. Redundant Connection Сложность: medium В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов. Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе. Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных. Пример:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

#include <vector>
#include <unordered_set>
#include <array>

class Solution {
public:
    std::unordered_set<int> seen;
    static const int MAX_EDGE_VAL = 1000;

    std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) {
        std::array<std::vector<int>, MAX_EDGE_VAL + 1> graph;
        for (auto& edge : edges) {
            seen.clear();
            if (!graph[edge[0]].empty() && !graph[edge[1]].empty() && dfs(graph, edge[0], edge[1])) {
                return edge;
            }
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        throw std::runtime_error("No redundant connection found");
    }

    bool dfs(const std::array<std::vector<int>, MAX_EDGE_VAL + 1>& graph, int source, int target) {
        if (!seen.count(source)) {
            seen.insert(source);
            if (source == target) return true;
            for (int nei : graph[source]) {
                if (dfs(graph, nei, target)) return true;
            }
        }
        return false;
    }
};

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

Большая онлайн-конференция UserGate OpenConf ⚡ ИТ-конференция про защиту в открытую. Диалог между заказчиками, партнерами, экспертами и специалистами в сфере продуктов, технологий и услуг информационной безопасности. Зарегистрироваться #реклама 16+ openconf.usergate.com О рекламодателе

Задача: 1247. Minimum Swaps to Make Strings Equal Сложность: hard Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать. Пример:

Input: arr = [1,2]
Output: 2

👨‍💻 Алгоритм: 1⃣Подсчет несоответствующих пар: Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'. 2⃣Проверка четности: Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1. 3⃣Вычисление минимального количества замен: Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2. Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2. 😎 Решение:

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1[i] == 'x' && s2[i] == 'y') {
                ++xy;
            } else if (s1[i] == 'y' && s2[i] == 'x') {
                ++yx;
            }
        }
        if ((xy + yx) % 2 != 0) {
            return -1;
        }
        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
};

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

Бесплатное льготное обучение: 3 месяца Мы ищем людей, которые хотят работать в IT-сфере из дома 💰 Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку: Узнать больше #реклама technolium.ru О рекламодателе

Задача: 999. Available Captures for Rook Сложность: easy Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья. Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        auto count_pawns = [&](int x, int y, int dx, int dy) {
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'B') break;
                if (board[x][y] == 'p') return 1;
                x += dx;
                y += dy;
            }
            return 0;
        };

        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    return count_pawns(i, j, -1, 0) + count_pawns(i, j, 1, 0) +
                           count_pawns(i, j, 0, -1) + count_pawns(i, j, 0, 1);
                }
            }
        }
        return 0;
    }
};

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

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