Задача: 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];
    }
};

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

Задача: 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];
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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;
    }
};

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

Задача: 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);
    }
};

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

Задача: 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;
    }
};

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

Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. 
Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. 
In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

👨‍💻 Алгоритм:

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

2⃣ Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния.
Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат.
Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат.

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        vector<vector<vector<int>>> dp(2, vector<vector<int>>(piles.size() + 1, vector<int>(piles.size() + 1, -1)));
        
        function<int(int, int, int)> f = [&](int p, int i, int m) {
            if (i == piles.size()) return 0;
            if (dp[p][i][m] != -1) return dp[p][i][m];
            int res = p == 1 ? 1000000 : -1, s = 0;
            for (int x = 1; x <= min(2 * m, (int)piles.size() - i); x++) {
                s += piles[i + x - 1];
                if (p == 0) {
                    res = max(res, s + f(1, i + x, max(m, x)));
                } else {
                    res = min(res, f(0, i + x, max(m, x)));
                }
            }
            return dp[p][i][m] = res;
        };
        
        return f(0, 0, 1);
    }
};

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

Задача: 1236. Web Crawler
Сложность: medium

Учитывая url startUrl и интерфейс HtmlParser, реализуйте веб-краулер для просмотра всех ссылок, которые находятся под тем же именем хоста, что и startUrl.Верните все ссылки, полученные вашим краулером, в любом порядке. Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все ссылки с веб-страницы с заданным url. Не просматривайте одну и ту же ссылку дважды. Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl. Как показано в примере url выше, имя хоста - example.org. Для простоты можно считать, что все урлы используют протокол http без указания порта. Например, урлы https://leetcode.com/problems и https://leetcode.com/contest находятся под одним и тем же именем хоста, а урлы https://example.org/test и https://example.com/abc не находятся под одним и тем же именем хоста.

Пример:

Input:
urls = [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.google.com",
  "https://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "https://news.yahoo.com/news/topics/"
Output: [
  "https://news.yahoo.com",
  "https://news.yahoo.com/news",
  "https://news.yahoo.com/news/topics/",
  "https://news.yahoo.com/us"
]

👨‍💻 Алгоритм:

1⃣Извлечение имени хоста:
Сначала извлекаем имя хоста из начального URL для проверки всех последующих ссылок.

2⃣Использование очереди для BFS:
Начинаем с начального URL и помещаем его в очередь.
Пока очередь не пуста, извлекаем текущий URL, получаем все ссылки с этой страницы, и для каждой ссылки проверяем, принадлежит ли она тому же имени хоста.

3⃣Если да, и если мы еще не посещали эту ссылку, добавляем ее в очередь и отмечаем как посещенную.

😎 Решение:

class HtmlParser {
public:
    vector<string> getUrls(string url);
};

string extractHostname(string url) {
    regex rgx(R"(https://([^/]+))");
    smatch match;
    regex_search(url, match, rgx);
    return match[1];
}

vector<string> crawl(string startUrl, HtmlParser htmlParser) {
    string hostname = extractHostname(startUrl);
    unordered_set<string> visited;
    queue<string> q;
    q.push(startUrl);
    visited.insert(startUrl);
    
    while (!q.empty()) {
        string url = q.front();
        q.pop();
        
        for (string nextUrl : htmlParser.getUrls(url)) {
            if (visited.find(nextUrl) == visited.end() && extractHostname(nextUrl) == hostname) {
                visited.insert(nextUrl);
                q.push(nextUrl);
            }
        }
    }
    
    return vector<string>(visited.begin(), visited.end());
}

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

Задача: 532. K-diff Pairs in an Array
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве.
Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Обратите внимание, что |val| обозначает абсолютное значение val.

Пример:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

👨‍💻 Алгоритм:

1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums.

2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям:
Если k > 0, проверьте, существует ли ключ, равный x + k.
Если k == 0, проверьте, есть ли более одного вхождения x.

3⃣ Увеличьте счётчик результатов, если условие выполняется.

😎 Решение:

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_map<int, int> counter;
        for (int num : nums) {
            counter[num]++;
        }
        
        int result = 0;
        for (const auto& entry : counter) {
            int x = entry.first;
            int val = entry.second;
            if (k > 0 && counter.count(x + k)) {
                result++;
            } else if (k == 0 && val > 1) {
                result++;
            }
        }
        
        return result;
    }
};

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

Задача: 649. Dota2 Senate
Сложность: medium

В мире Dota2 есть две партии: Radiant и Dire. Сенат Dota2 состоит из сенаторов, представляющих две партии. Теперь сенат хочет принять решение об изменении игры Dota2. Голосование за это изменение проходит в несколько раундов. В каждом раунде каждый сенатор может воспользоваться одним из двух прав: Запретить право одного сенатора: Сенатор может заставить другого сенатора потерять все свои права в этом и всех последующих раундах. Объявить о победе: Если этот сенатор обнаружил, что все сенаторы, у которых еще есть право голоса, принадлежат к одной партии, он может объявить о победе и принять решение об изменении игры. Дана строка senate, представляющая партийную принадлежность каждого сенатора. Символы "R" и "D" обозначают партию Лучезарных и партию Ужасных. Если сенаторов n, то размер данной строки будет равен n. Процедура голосования по кругу начинается от первого сенатора к последнему в заданном порядке. Эта процедура длится до конца голосования. Все сенаторы, потерявшие свои права, будут пропущены во время процедуры. Предположим, что каждый сенатор достаточно умен и будет играть по лучшей стратегии для своей партии. Предскажите, какая партия в итоге объявит о победе и изменит игру в Dota2. На выходе должно получиться "Radiant" или "Dire".

Пример:

Input: senate = "RD"
Output: "Radiant"

👨‍💻 Алгоритм:

1⃣Инициализируйте две очереди для хранения индексов сенаторов от партий Radiant и Dire.

2⃣Выполните цикл, пока обе очереди не станут пустыми: Сравните индексы первых сенаторов из обеих очередей. Удалите сенатора с меньшим индексом из очереди и добавьте его с индексом, увеличенным на длину строки. Удалите сенатора с большим индексом из очереди.

3⃣Если одна из очередей опустела, объявите победу партии, чья очередь еще содержит сенаторов.

😎 Решение:

string predictPartyVictory(string senate) {
    queue<int> radiant;
    queue<int> dire;
    
    for (int i = 0; i < senate.size(); ++i) {
        if (senate[i] == 'R') {
            radiant.push(i);
        } else {
            dire.push(i);
        }
    }
    
    while (!radiant.empty() && !dire.empty()) {
        int r = radiant.front();
        int d = dire.front();
        radiant.pop();
        dire.pop();
        if (r < d) {
            radiant.push(r + senate.size());
        } else {
            dire.push(d + senate.size());
        }
    }
    
    return radiant.empty() ? "Dire" : "Radiant";
}

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

Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]
Output: 22

👨‍💻 Алгоритм:

1⃣Рекурсивный обход дерева:
Используйте функцию DFS (поиск в глубину) для обхода дерева, начиная от корня. Передавайте текущее значение числа по пути как параметр.

2⃣Анализ текущего узла:
Если узел является листом (не имеет потомков), добавьте текущее значение числа к общей сумме.
Если узел не является листом, рекурсивно вызовите функцию DFS для левого и правого дочерних узлов, обновляя текущее значение числа.

3⃣Возврат результата:
После завершения обхода верните общую сумму чисел, представленных путями от корня к листьям.

😎 Решение:

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

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int current_value) {
        if (!node) return 0;
        current_value = (current_value << 1) | node->val;
        if (!node->left && !node->right) return current_value;
        return dfs(node->left, current_value) + dfs(node->right, current_value);
    }
};

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

Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

👨‍💻 Алгоритм:

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.

😎 Решение:

class Solution {
public:
    int storeFirstOptions(string& s, int startPos, vector<char>& firstOptions) {
        if (s[startPos] != '{') {
            firstOptions.push_back(s[startPos]);
        } else {
            startPos++;
            while (s[startPos] != '}') {
                if (s[startPos] >= 'a' && s[startPos] <= 'z') {
                    firstOptions.push_back(s[startPos]);
                }
                startPos++;
            }
            sort(firstOptions.begin(), firstOptions.end());
        }
        return startPos + 1;
    }

    vector<string> findAllWords(string& s, int startPos) {
        if (startPos == s.size()) {
            return {""};
        }

        vector<char> firstOptions;
        int remStringStartPos = storeFirstOptions(s, startPos, firstOptions);
        vector<string> wordsWithRemString = findAllWords(s, remStringStartPos);

        vector<string> expandedWords;
        for (char c : firstOptions) {
            for (string& word : wordsWithRemString) {
                expandedWords.push_back(c + word);
            }
        }
        return expandedWords;
    }

    vector<string> expand(string s) {
        return findAllWords(s, 0);
    }
};

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

Задача: 900. RLE Iterator
Сложность: medium

Для кодирования последовательности целых чисел мы можем использовать кодирование по длине строки (т. е. RLE). В кодированном по длине пробега массиве четной длины (с индексацией 0) для всех четных i значение encoding[i] говорит нам о том, сколько раз неотрицательное целое значение encoding[i + 1] повторяется в последовательности.

Например, последовательность arr = [8,8,8,5,5] может быть закодирована как encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] и encoding = [2,8,1,8,2,5] также являются допустимыми RLE для arr.
Задав кодированный по длине пробега массив, разработайте итератор для его итерации. Реализуйте класс RLEIterator: RLEIterator(int[] encoded) Инициализирует объект с кодированным массивом encoded. int next(int n) Исчерпывает следующие n элементов и возвращает последний исчерпанный таким образом элемент. Если не осталось элементов для исчерпания, возвращает -1.

Пример:

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

👨‍💻 Алгоритм:

1⃣Инициализировать итератор с закодированным массивом и индексом, указывающим на текущую позицию.

2⃣При вызове метода next(n), уменьшить текущий счетчик на n или перейти к следующему числу, если текущий счетчик равен нулю.

3⃣Возвращать текущий элемент или -1, если все элементы исчерпаны.

😎 Решение:

class RLEIterator {
    vector<int> encoding;
    int index;

public:
    RLEIterator(vector<int>& encoding) : encoding(encoding), index(0) {}

    int next(int n) {
        while (index < encoding.size()) {
            if (n > encoding[index]) {
                n -= encoding[index];
                index += 2;
            } else {
                encoding[index] -= n;
                return encoding[index + 1];
            }
        }
        return -1;
    }
};

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