C/C++ | LeetCode

Внимание ученики 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 О рекламодателе

Задача: 920. Number of Music Playlists Сложность: hard В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

class Solution {
public:
    int numMusicPlaylists(int n, int goal, int k) {
        const int MOD = 1'000'000'007;
        vector<vector<long>> dp(goal + 1, vector<long>(n + 1, 0));
        dp[0][0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD;
                if (j > k) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD;
                }
            }
        }

        return dp[goal][n];
    }
};

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

Задача: 1214. Two Sum BSTs Сложность: medium Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target. Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

👨‍💻 Алгоритм: 1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2. 2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2. 3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false. 😎 Решение:

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

class Solution {
    void dfs(TreeNode* node, unordered_set<int>& nodeSet) {
        if (!node) return;
        dfs(node->left, nodeSet);
        nodeSet.insert(node->val);
        dfs(node->right, nodeSet);
    }

public:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        unordered_set<int> nodeSet1, nodeSet2;
        dfs(root1, nodeSet1);
        dfs(root2, nodeSet2);
        
        for (int value1 : nodeSet1) {
            if (nodeSet2.count(target - value1)) {
                return true;
            }
        }
        
        return false;
    }
};

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

Задача: 263. Ugly Number Сложность: easy Уродливое число — это положительное целое число, простые множители которого только 2, 3 и 5. Верните true, если n — уродливое число. Пример:

Input: n = 6 Output: true

👨‍💻 Алгоритм: 1⃣Проверяем, является ли число положительным. Если n <= 0, сразу возвращаем false, так как уродливыми считаются только положительные числа. 2⃣Создаём функцию keepDividingWhenDivisible, которая делит n на factor, пока результат делится без остатка. 3⃣Последовательно делим n на 2, 3 и 5. Если после всех делений n == 1, значит других множителей не было — число уродливое. 😎 Решение:

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        for (auto factor : {2, 3, 5}) {
            n = keepDividingWhenDivisible(n, factor);
        }
        return n == 1;
    }

private:
    int keepDividingWhenDivisible(int dividend, int divisor) {
        while (dividend % divisor == 0) {
            dividend /= divisor;
        }
        return dividend;
    }
};

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

Задача: 815. Bus Routes Сложность: hard Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно. Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно. Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах. Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно. Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

👨‍💻 Алгоритм: 1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis. 2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными. 3⃣Верните -1 после завершения обхода в ширину (BFS). 😎 Решение:

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;

        unordered_map<int, vector<int>> adjList;
        for (int route = 0; route < routes.size(); route++) {
            for (int stop : routes[route]) {
                adjList[stop].push_back(route);
            }
        }

        queue<int> q;
        unordered_set<int> vis;
        for (int route : adjList[source]) {
            q.push(route);
            vis.insert(route);
        }

        int busCount = 1;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int route = q.front();
                q.pop();

                for (int stop : routes[route]) {
                    if (stop == target) return busCount;

                    for (int nextRoute : adjList[stop]) {
                        if (!vis.count(nextRoute)) {
                            vis.insert(nextRoute);
                            q.push(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }
};

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

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

Задача: 1032. Stream of Characters Сложность: hard Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words. Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words. Пример:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

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

class TrieNode {
public:
    TrieNode* children[26] = {};
    bool is_end_of_word = false;
};

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for (const string& word : words) {
            TrieNode* node = root;
            for (int i = word.size() - 1; i >= 0; --i) {
                if (!node->children[word[i] - 'a']) {
                    node->children[word[i] - 'a'] = new TrieNode();
                }
                node = node->children[word[i] - 'a'];
            }
            node->is_end_of_word = true;
        }
    }
    
    bool query(char letter) {
        stream.push_front(letter);
        TrieNode* node = root;
        for (char c : stream) {
            if (!node->children[c - 'a']) return false;
            node = node->children[c - 'a'];
            if (node->is_end_of_word) return true;
        }
        return false;
    }

private:
    TrieNode* root;
    deque<char> stream;
};

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

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе

Задача: 926. Flip String to Monotone Increasing Сложность: medium Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0. Пример:

Input: s = "00110"
Output: 1

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

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        vector<int> left(n + 1, 0);
        vector<int> right(n + 1, 0);
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s[i] == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s[i] == '0' ? 1 : 0);
        }
        
        int result = INT_MAX;
        for (int i = 0; i <= n; i++) {
            result = min(result, left[i] + right[i]);
        }
        return result;
    }
};

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

Бесплатный доступ к MBA Intensive – для руководителей В Школе Генерального Директора сегодня открыт бесплатный доступ на 2 дня к полноценному онлайн-курсу MBA Intensive при переходе из поста. Вы сможете пройти 500+ практических уроков совершенно бесплатно и улучшить управленческие навыки и понимание бизнес-процессов. После сдачи тестов доступен сертификат о прохождении уроков. Вот какие темы вы успеете изучить – выбирайте любую и приступайте прямо сейчас: 1. Лидерство, личная эффективность и эмоциональный интеллект 2. Управление персоналом 3. Финансы и экономика 4. Торговля и сервис 5. Операционная деятельность и принятие решений 6. Project management 7. Управление маркетингом Оставляйте заявку по ссылке >>> Подать заявку #реклама 16+ gd.ru О рекламодателе

Задача: 848. Shifting Letters Сложность: medium Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины. Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a'). Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'. Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз. Верните итоговую строку после применения всех таких сдвигов к s. Пример:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

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

class Solution {
public:
    string shiftingLetters(string S, vector<int>& shifts) {
        string ans;
        int X = 0;
        for (int shift : shifts)
            X = (X + shift) % 26;

        for (int i = 0; i < S.size(); ++i) {
            int index = S[i] - 'a';
            ans += (char) ((index + X) % 26 + 97);
            X = (X - shifts[i] + 26) % 26;
        }

        return ans;
    }
};

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