C/C++ | LeetCode

Задача: 784. Letter Case Permutation Сложность: medium Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве. Пример:

Input: s = "a1b2"
Output: ["a1b2","a1B2","A1b2","A1B2"]

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

class Solution {
public:
    vector<string> letterCasePermutation(string S) {
        vector<vector<char>> ans(1);

        for (char c : S) {
            int n = ans.size();
            if (isalpha(c)) {
                for (int i = 0; i < n; ++i) {
                    ans.push_back(ans[i]);
                    ans[i].push_back(tolower(c));
                    ans[n + i].push_back(toupper(c));
                }
            } else {
                for (int i = 0; i < n; ++i) {
                    ans[i].push_back(c);
                }
            }
        }

        vector<string> result;
        for (const auto& list : ans) {
            result.push_back(string(list.begin(), list.end()));
        }
        return result;
    }
};

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

Задача: 247. Strobogrammatic Number II Сложность: medium Пример:

Input: n = 2
Output: ["11","69","88","96"]

👨‍💻 Алгоритм: 1⃣Построить рекурсивную функцию, которая генерирует все стробограмматические числа длины n, начиная с базовых случаев: [""] при n == 0 и ["0", "1", "8"] при n == 1. 2⃣На каждом уровне добавить к уже существующим подстрокам пары: ("0", "0"), ("1", "1"), ("6", "9"), ("8", "8"), ("9", "6"), соблюдая правило: нельзя добавлять "0" на внешний уровень, если n == finalLength. 3⃣Вернуть итоговый список чисел после завершения построения. 😎 Решение:

#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<vector<char>> reversiblePairs = {
        {'0', '0'}, {'1', '1'}, 
        {'6', '9'}, {'8', '8'}, {'9', '6'}
    };
    
    vector<string> generateStroboNumbers(int n, int finalLength) {
        if (n == 0) return { "" };
        if (n == 1) return { "0", "1", "8" };
        
        vector<string> prev = generateStroboNumbers(n - 2, finalLength);
        vector<string> result;
        
        for (string& s : prev) {
            for (vector<char>& p : reversiblePairs) {
                if (p[0] != '0' || n != finalLength) {
                    result.push_back(p[0] + s + p[1]);
                }
            }
        }
        return result;
    }
    
    vector<string> findStrobogrammatic(int n) {
        return generateStroboNumbers(n, n);
    }
};

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

Как IT-компании увеличить продажи с помощью вебинаров? Делимся гайдом для маркетологов IT-компаний с рекомендациями ведущих российских разработчиков и экспертов МТС Линк. Вы узнаете: - Как правильно использовать онлайн-мероприятия для продвижения; - Как собрать 10 000 потенциальных клиентов из любой точки мира в одном месте; - Как увеличить узнаваемость бренда и создать комьюнити вокруг него; - Как оценить вклад онлайн-мероприятия в продвижение компании и правильно обработать лиды; Бонус: кейс IT-компании с доходимостью до вебинаров 70% Получите методичку бесплатно на сайте! Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 93. Restore IP Addresses Сложность: medium Дана строка s, содержащая только цифры. Нужно вставить три точки, чтобы получить все возможные валидные IP-адреса, где каждый сегмент (целое число) находится в диапазоне от 0 до 255, и не содержит ведущих нулей (например, 01, 001 — недопустимы). Пример:

Input: s = "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

👨‍💻 Алгоритм: 1⃣Запускаем рекурсивную функцию, которая на каждом шаге пытается взять 1, 2 или 3 цифры в очередной сегмент. Следим, чтобы оставшейся длины строки хватало на оставшиеся сегменты (не более 3 символов на сегмент). 2⃣Как только добавлено три точки (т.е. выбрано 3 сегмента), проверяем, является ли оставшаяся часть строки допустимым сегментом. Если да — собираем итоговую строку и добавляем в результат. 3⃣Для каждого возможного разбиения (1–3 цифры), проверяем: значение от 0 до 255 отсутствие ведущих нулей (если длина > 1 и начинается с '0' — недопустимо) 😎 Решение:

class Solution {
public:
    bool isValidSegment(const string& s) {
        if (s.empty() || (s.size() > 1 && s[0] == '0') || stoi(s) > 255)
            return false;
        return true;
    }

    void helper(const string& s, int start, vector<int>& dots, vector<string>& ans) {
        int remainingLength = s.size() - start;
        int remainingIntegers = 4 - dots.size();

        if (remainingLength < remainingIntegers || remainingLength > 3 * remainingIntegers)
            return;

        if (remainingIntegers == 1) {
            string lastSegment = s.substr(start);
            if (isValidSegment(lastSegment)) {
                string ip;
                int last = 0;
                for (int len : dots) {
                    ip += s.substr(last, len) + ".";
                    last += len;
                }
                ip += lastSegment;
                ans.push_back(ip);
            }
            return;
        }

        for (int len = 1; len <= 3 && len <= remainingLength; ++len) {
            string part = s.substr(start, len);
            if (isValidSegment(part)) {
                dots.push_back(len);
                helper(s, start + len, dots, ans);
                dots.pop_back();
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        vector<int> dots;
        helper(s, 0, dots, ans);
        return ans;
    }
};

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

Задача: 969. Pancake Sorting Сложность: medium Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов. При одном перевороте блина мы выполняем следующие шаги: Выбираем целое число k, где 1 <= k <= arr.length. Переворачиваем подмассив arr[0...k-1] (индексация с 0). Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3. Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным. Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

👨‍💻 Алгоритм: 1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0 ] (в Python). 2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего. 3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте. 😎 Решение:

class Solution {
public:
    vector<int> pancakeSort(vector<int>& A) {
        vector<int> ans;

        for (int valueToSort = A.size(); valueToSort > 0; valueToSort--) {
            int index = find(A, valueToSort);
            if (index == valueToSort - 1) continue;
            if (index != 0) {
                ans.push_back(index + 1);
                flip(A, index + 1);
            }
            ans.push_back(valueToSort);
            flip(A, valueToSort);
        }

        return ans;
    }

private:
    void flip(vector<int>& sublist, int k) {
        int i = 0;
        while (i < k / 2) {
            swap(sublist[i], sublist[k - i - 1]);
            i++;
        }
    }

    int find(vector<int>& a, int target) {
        for (int i = 0; i < a.size(); i++) {
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }
};

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

Задача: 1490. Clone N-ary Tree Сложность: medium Дан корень N-арного дерева, верните глубокую копию (клон) дерева. Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей.

class Node {
    public int val;
    public List<Node> children;
}

Сериализация входных данных N-арного дерева представлена в порядке обхода по уровням, каждая группа детей разделена значением null (см. примеры). Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

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

class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    Node* cloneTree(Node* root) {
        if (!root) return nullptr;

        Node* nodeCopy = new Node(root->val);
        for (Node* child : root->children) {
            nodeCopy->children.push_back(cloneTree(child));
        }
        return nodeCopy;
    }
};

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

Задача: 654. Maximum Binary Tree Сложность: medium Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums. Пример:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

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

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

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size());
    }

private:
    TreeNode* build(const vector<int>& nums, int l, int r) {
        if (l == r) return nullptr;
        int maxIndex = max_element(nums.begin() + l, nums.begin() + r) - nums.begin();
        TreeNode* root = new TreeNode(nums[maxIndex]);
        root.left = build(nums, l, maxIndex);
        root.right = build(nums, maxIndex + 1, r);
        return root;
    }
};

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

👩‍💻 Ищем C# разработчиков. Релокейт, удалёнка, платим много! Специально для Вас, собираем лучшие вакансии, только с прямыми контактами в Telegram! 👩‍💻 C# 👩‍💻 Java 👩‍💻 DevOps 👩‍💻 Python 👣 Go 👩‍💻 Node.js 🖼️ PHP 🤖 ML & DS 🖥 SQL 🔎 QA 👩‍💻 UX/UI 👩‍💻 Frontend 👩‍💻 Mobile 📋 Analyst 💼 1C 👩‍💻 IT HR Подпишись чтобы не упустить свой шанс получить лучший оффер!

Чего хотят ваши сотрудники ⚡Мы перепробовали всё: — KPI — не работает. — Премии — ждут как зарплату, эффекта ноль. — Тимбилдинг — стало только хуже. В итоге мотивация у всех держится на одном: "не бесить начальство". Это не потому что "люди не те" — просто вы ещё не знаете, чтО на самом деле мотивирует команду. Сегодня открыт бесплатный доступ к курсу "Ежедневная мотивация" от Школы Генерального директора. Он о том, как работает мотивация в реальности: — Почему большинство систем мотивации не просто бесполезны, а вредны — Как узнать, чего на самом деле хотят ваши люди и почему они сами не могут это сформулировать — Как создать условия, при которых сотрудник работает не из страха и не за надбавку, а потому что сам этого хочет Оставьте заявку, куратор перезвонит и откроет полный доступ на 2 дня. Подать заявку #реклама 16+ gd.ru О рекламодателе

Задача: 1282. Group the People Given the Group Size They Belong To Сложность: medium Есть n человек, которые разделены на неизвестное количество групп. Каждый человек имеет уникальный ID от 0 до n - 1. Вам дан целочисленный массив groupSizes, где groupSizes[i] - это размер группы, в которой находится человек i. Например, если groupSizes[1] = 3, то человек 1 должен быть в группе размером 3. Верните список групп таким образом, чтобы каждый человек i находился в группе размером groupSizes[i]. Каждый человек должен быть ровно в одной группе, и каждый человек должен быть в группе. Если существует несколько ответов, верните любой из них. Гарантируется, что для данного ввода существует хотя бы одно правильное решение. Пример:

Input: groupSizes = [3,3,3,3,3,1,3]
Output: [[5],[0,1,2],[3,4,6]]
Explanation: 
The first group is [5]. The size is 1, and groupSizes[5] = 1.
The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

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

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> ans;
        vector<int> szToGroup[groupSizes.size() + 1];
        
        for (int i = 0; i < groupSizes.size(); i++) {
            szToGroup[groupSizes[i]].push_back(i);
            
            if (szToGroup[groupSizes[i]].size() == groupSizes[i]) {
                ans.push_back(szToGroup[groupSizes[i]]);
                szToGroup[groupSizes[i]].clear();
            }
        }
        
        return ans;
    }
};

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

Внимание ученики 1-9 класса и их родители! Стартует бесплатная 3-х месячная программа по углубленному изучению школьных предметов с 1 по 4 класс, с 5 по 8 класс и с 9 по 11 класс от резидента Сколково. Программа предлагает подтянуть знания по основным предметам: — Математика: 83% учеников повышают оценку до 4 или 5 за 2 месяца — Подготовиться к контрольным и ВПР — Подготовка к ОГЭ и ЕГЭ без стресса — Русский язык: средний балл ВПР 87 при общешкольном показателе 65 — Английский: 72% учащихся переходят на уровень выше за 4 месяца Для участия достаточно заполнить заявку. Жмите "Записаться" Записаться #реклама 16+ mrqz.me О рекламодателе

Задача: 443. String Compression Сложность: medium Дан массив символов chars, сжать его, используя следующий алгоритм: Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars: Если длина группы равна 1, добавьте символ к строке s. В противном случае добавьте символ, а за ним длину группы. Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars. После того как вы закончите модификацию входного массива, верните новую длину массива. Вы должны написать алгоритм, который использует только постоянное дополнительное пространство. Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

👨‍💻 Алгоритм: 1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0. 2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе. 3⃣Верните res. 😎 Решение:

class Solution {
public:
    int compress(vector<char>& chars) {
        int i = 0, res = 0;
        while (i < chars.size()) {
            int groupLength = 1;
            while (i + groupLength < chars.size() && chars[i + groupLength] == chars[i]) {
                groupLength++;
            }
            chars[res++] = chars[i];
            if (groupLength > 1) {
                for (char ch : to_string(groupLength)) {
                    chars[res++] = ch;
                }
            }
            i += groupLength;
        }
        return res;
    }
};

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

Быстрый старт в кибербез: с нуля до первой работы Ищешь перспективную профессию с быстрым ростом зарплаты? Кибербезопасность — востребованная сфера с острой нехваткой специалистов. Здесь реально выйти на доход от 70 000 уже за полгода. Даже без опыта и образования в ИТ. С чего начать и как построить карьеру, расскажут эксперты Солара на вебинаре 11 сентября в 19:00: ✅Какие профессии доступны новичкам без опыта и как быстро их освоить. ✅Как найти свою первую работу. ✅Какие ошибки допускают новички в начале пути. 👌Всем участникам подарим пошаговый план по саморазвитию и быстрому старту в кибербезопасность. Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

Задача: 766. Toeplitz Matrix Сложность: easy Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false. Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы. Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

👨‍💻 Алгоритм: 1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м 2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой. 3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true. 😎 Решение:

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        unordered_map<int, int> groups;
        for (int r = 0; r < matrix.size(); ++r) {
            for (int c = 0; c < matrix[0].size(); ++c) {
                if (!groups.count(r - c))
                    groups[r - c] = matrix[r][c];
                else if (groups[r - c] != matrix[r][c])
                    return false;
            }
        }
        return true;
    }
};

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

Конференция для блогеров ПОСТ РОСТ 12 сентября В самом начале сентября Яндекс собирает авторов контента на первую конференцию для блогеров! Что вас ждёт: — Выступления топ-экспертов о том, как блогеру расти и развивать свой контент — Спонтанный нетворкинг — Классные активности — Консультации специалистов по монетизации контента Участие бесплатное Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 919. Complete Binary Tree Inserter Сложность: medium Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки. Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева. Пример:

Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]

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

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

class CBTInserter {
public:
    CBTInserter(TreeNode* root) {
        this->root = root;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (!node->left || !node->right) {
                deque.push(node);
            }
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }

    int insert(int v) {
        TreeNode* node = deque.front();
        TreeNode* newNode = new TreeNode(v);
        if (!node->left) {
            node->left = newNode;
        } else {
            node->right = newNode;
            deque.pop();
        }
        deque.push(newNode);
        return node->val;
    }

    TreeNode* get_root() {
        return root;
    }

private:
    TreeNode* root;
    queue<TreeNode*> deque;
};

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

Открой мощь новых MSI с GeForce RTX 50 Серия NVIDIA GeForce RTX 50 в ноутбуках MSI — это квантовый скачок в мире мощности. Игры на максималках, 3D-рендер без ожиданий, монтаж видео в реальном времени и искусственный интеллект, работающий с небывалой скоростью. Эта техника создана не просто для задач — она их уничтожает. Будь в центре производительности нового поколения. MSI с RTX 50 — когда ты не хочешь ждать, а действуешь. Узнать больше #реклама msi.gm О рекламодателе

Задача: 1332. Remove Palindromic Subsequences Сложность: easy Вам дана строка s, состоящая только из букв 'a' и 'b'. За один шаг вы можете удалить одну палиндромную подпоследовательность из s. Верните минимальное количество шагов, чтобы сделать данную строку пустой. Строка является подпоследовательностью данной строки, если она создается путем удаления некоторых символов из данной строки без изменения их порядка. Обратите внимание, что подпоследовательность не обязательно должна быть непрерывной. Строка называется палиндромом, если она читается одинаково как вперед, так и назад. Пример:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

👨‍💻 Алгоритм: 1⃣Если строка s уже является палиндромом, верните 1, так как можно удалить всю строку за один шаг. 2⃣Если строка s не является палиндромом, верните 2. В этом случае можно удалить все символы 'a' за один шаг, а затем все символы 'b' за второй шаг (или наоборот). 3⃣Таким образом, минимум шагов для опустошения строки всегда будет либо 1, либо 2, в зависимости от того, является ли строка палиндромом. 😎 Решение:

class Solution {
public:
    int removePalindromeSub(string s) {
        if (s.empty()) {
            return 0;
        }
        string reversedString = s;
        reverse(reversedString.begin(), reversedString.end());
        if (reversedString == s) {
            return 1;
        }
        return 2;
    }
};

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

Задача: 343. Integer Break Сложность: medium Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false. Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x. Пример:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

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

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 1) return 0;
        
        vector<int> dp(n + 1, 0);
        
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i / 2; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        
        return dp[n];
    }
};

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

За границу за наш счет Представьте: отдыхаете в отеле за рубежом, а вам потом стоимость проживания возвращают. Такое провернули в Яндекс Путешествиях. Для отдохнувших с 22 августа по 31 октября устраивают розыгрыш. Раз в месяц 10 счастливчикам возвращают до 100 000 рублей каждому. А промокод SECRET5 скинет 5000 рублей от стоимости отеля при бронировании от 60 000 рублей. Забронировать #реклама special.travel.yandex.ru О рекламодателе