C/C++ | LeetCode

Теперь AI сам создает сайты ИИшка в Битрикс24 берёт на себя весь процесс: структура, дизайн, контент — всё создаётся автоматически. Сделайте один запрос AI-помощнику, и через 30 секунд он создаст свой вариант полностью работающего сайта. Узнать больше #реклама sites-24.bitrix24.ru О рекламодателе

Задача: 1012. Numbers With Repeated Digits Сложность: hard Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется. Пример:

Input: n = 20
Output: 1

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

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        return n - countUniqueDigitNumbers(n);
    }

private:
    int countUniqueDigitNumbers(int x) {
        string s = to_string(x);
        int n = s.size();
        int res = 0;
        for (int i = 1; i < n; ++i) {
            res += 9 * permutation(9, i - 1);
        }
        unordered_set<int> used;
        for (int i = 0; i < n; ++i) {
            for (int j = (i == 0 ? 1 : 0); j < s[i] - '0'; ++j) {
                if (used.find(j) == used.end()) {
                    res += permutation(9 - i, n - i - 1);
                }
            }
            if (used.find(s[i] - '0') != used.end()) {
                break;
            }
            used.insert(s[i] - '0');
        }
        if (used.size() == n) {
            res += 1;
        }
        return res;
    }

    int permutation(int m, int n) {
        return n == 0 ? 1 : permutation(m, n - 1) * (m - n + 1);
    }
};

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

5 свободных мест на курс Коммутаторы MES продвинутый Осталось 5 мест на курс Коммутаторы MES (продвинутый) в нашем авторизованном учебном центре от Академии Eltex в Москве Даты: 12-16 мая (5 дней) Другие курсы: Курс Wi-Fi (контроллер SoftWLC) 19 мая - 5 дней - Выдаем официальный сертификат Eltex. - Преподаватель корректирует программу обучения под Ваш уровень знаний. - Преподаватели прошли аттестацию на заводе Eltex. - Уже выпустили 210 сетевых инженеров! Записаться #реклама 16+ eltexcm.ru О рекламодателе

Задача: 1267. Count Servers that Communicate Сложность: medium На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение. Пример:

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

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

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        vector<int> rows(grid.size(), 0);
        vector<int> cols(grid[0].size(), 0);

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    rows[i]++;
                    cols[j]++;
                }
            }
        }

        int count = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
                    count++;
                }
            }
        }

        return count;
    }
};

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

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

Задача: 65. Valid Number Сложность: hard Нужно определить, является ли строка s валидным числом, включая целые, десятичные и числа с экспонентой (e или E). Пример:

Input: s = "0" Output: true

👨‍💻 Алгоритм: 1⃣Объявить флаги: seenDigit — были ли цифры seenDot — была ли точка seenExponent — была ли экспонента 2⃣Пройти по строке посимвольно: Цифра: seenDigit = true Знак (+/-) допустим только в начале строки или сразу после e/E e/E: не должно быть второй экспоненты, и до неё должна быть хотя бы одна цифра .: допустима только один раз и только до e Любой другой символ — false 3⃣В конце вернуть seenDigit, т.к. после e должна быть хотя бы одна цифра 😎 Решение:

class Solution {
public:
    bool isNumber(string s) {
        bool seenDigit = false;
        bool seenExponent = false;
        bool seenDot = false;
        for (int i = 0; i < s.length(); i++) {
            char curr = s[i];
            if (curr >= '0' && curr <= '9') {
                seenDigit = true;
            } else if (curr == '+' || curr == '-') {
                if (i > 0 && s[i - 1] != 'e' && s[i - 1] != 'E') {
                    return false;
                }
            } else if (curr == 'e' || curr == 'E') {
                if (seenExponent || !seenDigit) {
                    return false;
                }
                seenExponent = true;
                seenDigit = false;
            } else if (curr == '.') {
                if (seenDot || seenExponent) {
                    return false;
                }
                seenDot = true;
            } else {
                return false;
            }
        }
        return seenDigit;
    }
};

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

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

Задача: 1265. Print Immutable Linked List in Reverse Сложность: medium Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API. Пример:

Input: head = [1,2,3,4]
Output: [4,3,2,1]

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

class ImmutableListNode {
public:
    void printValue();
    ImmutableListNode* getNext();
};

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        if (head->getNext() != nullptr) {
            printLinkedListInReverse(head->getNext());
        }
        head->printValue();
    }
};

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

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 965. Univalued Binary Tree Сложность: medium Дан список слов, и нам нужно реализовать проверку орфографии, которая преобразует слово запроса в правильное слово. Для данного слова запроса, проверка орфографии обрабатывает две категории ошибок правописания: Заглавные буквы: если запрос совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и в списке слов. Пример: wordlist = ["yellow"], query = "YellOw": correct = "yellow" Пример: wordlist = ["Yellow"], query = "yellow": correct = "Yellow" Пример: wordlist = ["yellow"], query = "yellow": correct = "yellow" Ошибки гласных: если после замены гласных ('a', 'e', 'i', 'o', 'u') в слове запроса на любую гласную по отдельности оно совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и совпадающее слово в списке слов. Пример: wordlist = ["YellOw"], query = "yollow": correct = "YellOw" Пример: wordlist = ["YellOw"], query = "yeellow": correct = "" (нет совпадения) Пример: wordlist = ["YellOw"], query = "yllw": correct = "" (нет совпадения) Кроме того, проверка орфографии работает по следующим правилам приоритета: Когда запрос точно совпадает со словом в списке слов (с учетом регистра), вы должны вернуть это же слово. Когда запрос совпадает со словом за исключением регистра, вы должны вернуть первое такое совпадение в списке слов. Когда запрос совпадает со словом за исключением ошибок гласных, вы должны вернуть первое такое совпадение в списке слов. Если запрос не имеет совпадений в списке слов, вы должны вернуть пустую строку. Дан массив запросов, верните список слов answer, где answer[i] — правильное слово для query = queries[i]. Пример:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

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

class Solution {
public:
    unordered_set<string> words_perfect;
    unordered_map<string, string> words_cap;
    unordered_map<string, string> words_vow;

    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        for (const string& word : wordlist) {
            words_perfect.insert(word);

            string wordlow = toLower(word);
            words_cap.insert({wordlow, word});

            string wordlowDV = devowel(wordlow);
            words_vow.insert({wordlowDV, word});
        }

        vector<string> ans;
        for (const string& query : queries) {
            ans.push_back(solve(query));
        }
        return ans;
    }

    string solve(const string& query) {
        if (words_perfect.count(query)) {
            return query;
        }

        string queryL = toLower(query);
        if (words_cap.count(queryL)) {
            return words_cap[queryL];
        }

        string queryLV = devowel(queryL);
        if (words_vow.count(queryLV)) {
            return words_vow[queryLV];
        }

        return "";
    }

    string toLower(const string& str) {
        string result = str;
        transform(result.begin(), result.end(), result.begin(), ::tolower);
        return result;
    }

    string devowel(const string& word) {
        string result = word;
        for (char& c : result) {
            if (isVowel(c)) {
                c = '*';
            }
        }
        return result;
    }

    bool isVowel(char c) {
        return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
    }
};

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

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

Задача: 936. Stamping The Sequence Сложность: hard Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

👨‍💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение:

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        vector<int> res;
        vector<bool> done(target.size(), false);
        string t = target;
        string s = stamp;
        int m = s.size(), n = t.size();
        
        auto canStamp = [&](int i) {
            for (int j = 0; j < m; j++) {
                if (t[i + j] != '?' && t[i + j] != s[j]) {
                    return false;
                }
            }
            return true;
        };
        
        auto doStamp = [&](int i) {
            for (int j = 0; j < m; j++) {
                t[i + j] = '?';
            }
            res.push_back(i);
            done[i] = true;
        };
        
        bool changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i <= n - m; i++) {
                if (!done[i] && canStamp(i)) {
                    doStamp(i);
                    changed = true;
                }
            }
        }
        
        for (char c : t) {
            if (c != '?') {
                return {};
            }
        }
        
        reverse(res.begin(), res.end());
        return res;
    }
};

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

Стартуй в бизнесе на ИЗЗЗИ вместе со Сбером Открой счёт за 0 рублей и получи: ✅ До 100 000 бонусов СберБизнес Спасибо на полезные сервисы ✅ Избавление от рутины: бесплатная бухгалтерия для бизнеса на 6 месяцев Это твой знак начать своё дело! Узнать больше Финансовые услуги оказывает: ПАО Сбербанк. #реклама sberbank.com О рекламодателе

Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List Сложность: medium Преобразуйте двоичное дерево поиска в отсортированный кольцевой двусвязный список на месте. Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом. Мы хотим выполнить преобразование на месте. После преобразования левый указатель узла дерева должен указывать на его предшественника, а правый указатель должен указывать на его последователя. Вы должны вернуть указатель на самый маленький элемент списка. Пример:

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

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

class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
public:
    Node* first = NULL;
    Node* last = NULL;

    void helper(Node* node) {
        if (node != NULL) {
            helper(node->left);

            if (last != NULL) {
                last->right = node;
                node->left = last;
            } else {
                first = node;
            }
            last = node;

            helper(node->right);
        }
    }

    Node* treeToDoublyList(Node* root) {
        if (root == NULL) return NULL;

        helper(root);

        last->right = first;
        first->left = last;
        return first;
    }
};

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

Освойте профессию Системный аналитик с нуля за 7 месяцев Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством. Excel, BPMN, UML, Python, SQL, API Преимущества обучения в Академии Eduson: 🎓 22 реальных бизнес-кейса 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать доход уже во время обучения! Получить скидку #реклама 16+ mrqz.me О рекламодателе

Задача: 318. Maximum Product of Word Lengths Сложность: medium Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0. Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> masks(n);
        vector<int> lens(n);
        
        for (int i = 0; i < n; i++) {
            int bitmask = 0;
            for (char ch : words[i]) {
                bitmask |= 1 << (ch - 'a');
            }
            masks[i] = bitmask;
            lens[i] = words[i].size();
        }
        
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxVal = max(maxVal, lens[i] * lens[j]);
                }
            }
        }
        return maxVal;
    }
};

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

Задача: 665. Non-decreasing Array Сложность: medium Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента. Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1]. Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Завести переменную count для подсчета числа изменений. Проверить последовательность чисел в массиве nums. 2⃣Проверка условий: Если nums[i] > nums[i + 1], то увеличиваем count. Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо. Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false. 3⃣вВозврат результата: Если количество изменений не превышает 1, вернуть true. 😎 Решение:

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
};

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

Получи грант на обучение в Центральном университете Центральный университет выдает гранты на 4 года обучения в бакалавриате. Грант покрывает до 100% стоимости обучения. Участвуй в отборе, чтобы получить грант. Получи доступ к уникальным активностям для абитуриентов. Для выпускников 10-х, 11-х классов и колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 289. Game of Life Сложность: medium Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году." Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии): Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения. Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения. Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения. Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения. Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние. Пример:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

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

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        vector<int> neighbors = {0, 1, -1};
        int rows = board.size();
        int cols = board[0].size();

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                int liveNeighbors = 0;
                for (int i : neighbors) {
                    for (int j : neighbors) {
                        if (!(i == 0 && j == 0)) {
                            int r = row + i;
                            int c = col + j;
                            if (r >= 0 && r < rows && c >= 0 && c < cols && abs(board[r][c]) == 1) {
                                liveNeighbors++;
                            }
                        }
                    }
                }

                if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = -1;
                }
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 2;
                }
            }
        }

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                board[row][col] = (board[row][col] > 0) ? 1 : 0;
            }
        }
    }
};

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

Data и ML для бизнеса. Большая конференция Яндекса Узнайте, как ускорить создание продуктов, упростить процессы и снизить расходы. Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе Реклама на Яндексе