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

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

Задача: 1058. Minimize Rounding Error to Meet Target
Сложность: medium

Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби.

Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

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

1⃣Округли каждую цену вниз и вычисли текущую сумму округленных цен.
Найди разницу между целевой суммой и текущей суммой.

2⃣Определи количество округлений вверх, необходимых для достижения целевой суммы.
Если разница отрицательная или больше количества элементов в массиве, верни "-1".

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

😎 Решение:

string minimizeRoundingError(vector<string>& prices, int target) {
    vector<int> floors;
    vector<double> floatPrices;
    double totalFloor = 0;

    for (const string& price : prices) {
        double p = stod(price);
        floatPrices.push_back(p);
        int floorVal = floor(p);
        floors.push_back(floorVal);
        totalFloor += floorVal;
    }
    
    int difference = target - totalFloor;
    if (difference < 0 || difference > prices.size()) {
        return "-1";
    }
    
    vector<pair<double, double>> roundingErrors;
    for (int i = 0; i < prices.size(); ++i) {
        roundingErrors.push_back({ceil(floatPrices[i]) - floors[i], floatPrices[i] - floors[i]});
    }
    
    sort(roundingErrors.begin(), roundingErrors.end(), [](const pair<double, double>& a, const pair<double, double>& b) {
        return a.second < b.second;
    });
    
    double roundingErrorSum = 0;
    for (int i = 0; i < floors.size(); ++i) {
        roundingErrorSum += (floatPrices[i] - floors[i]);
    }
    
    for (int i = 0; i < difference; ++i) {
        roundingErrorSum += roundingErrors[i].second;
    }
    
    stringstream ss;
    ss << fixed << setprecision(3) << roundingErrorSum;
    return ss.str();
}

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

Задача: 1001. Grid Illumination
Сложность: hard

Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный массив позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный массив queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. Верните массив целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.

Пример:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]

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

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

2⃣Обработка запросов:
Для каждого запроса проверьте, освещена ли ячейка, используя словари строк, столбцов, диагоналей и обратных диагоналей.
После ответа на запрос выключите лампу в указанной ячейке и 8 соседних ячейках, обновив множества и словари.

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

😎 Решение:

class Solution {
public:
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        unordered_set<long long> lamps_on;
        unordered_map<int, int> rows, cols, diag1, diag2;

        for (auto& lamp : lamps) {
            int r = lamp[0], c = lamp[1];
            long long key = (long long)r * n + c;
            if (lamps_on.count(key)) continue;
            lamps_on.insert(key);
            rows[r]++;
            cols[c]++;
            diag1[r - c]++;
            diag2[r + c]++;
        }

        vector<int> result;
        vector<pair<int, int>> directions = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

        for (auto& query : queries) {
            int r = query[0], c = query[1];
            if (rows[r] > 0 || cols[c] > 0 || diag1[r - c] > 0 || diag2[r + c] > 0) {
                result.push_back(1);
            } else {
                result.push_back(0);
            }

            for (auto& dir : directions) {
                int nr = r + dir.first, nc = c + dir.second;
                long long key = (long long)nr * n + nc;
                if (lamps_on.count(key)) {
                    lamps_on.erase(key);
                    rows[nr]--;
                    cols[nc]--;
                    diag1[nr - nc]--;
                    diag2[nr + nc]--;
                }
            }
        }

        return result;
    }
};

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, обозначающие диапазон [left, right].
Нужно вернуть результат побитового AND всех чисел в этом диапазоне (включительно).

Пример:

Input: left = 5, right = 7 Output: 4

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

1⃣Пока left < right, сдвигаем оба числа вправо (>>= 1), пока они не станут равны. Это находит общий префикс битов.

2⃣Подсчитываем количество сдвигов — это количество младших битов, которые могут изменяться в диапазоне, и обнуляются при AND.

3⃣После этого сдвигаем результат left обратно влево (<< shift) — возвращаем биты на место.

😎 Решение:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
};

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

Задача: 733. Flood Fill
Сложность: easy

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

1⃣Получите цвет начального пикселя.

2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.

3⃣Обновите изображение и верните его.

😎 Решение:

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        
        dfs(image, sr, sc, originalColor, color);
        return image;
    }
    
private:
    void dfs(vector<vector<int>>& image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        dfs(image, x + 1, y, originalColor, newColor);
        dfs(image, x - 1, y, originalColor, newColor);
        dfs(image, x, y + 1, originalColor, newColor);
        dfs(image, x, y - 1, originalColor, newColor);
    }
};

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

Задача: 107. Binary Tree Level Order Traversal II
Сложность: medium

Дан корень бинарного дерева. Верните обход значений узлов снизу вверх по уровням (то есть слева направо, уровень за уровнем, от листа к корню).

Пример:

Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]

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

1⃣Инициализируйте список levels. Его длина определяет текущий уровень дерева. Если уровень level равен длине levels, нужно добавить новый вложенный список.

2⃣Добавьте значение текущего узла в список соответствующего уровня.

3⃣Рекурсивно вызывайте helper для левого и правого поддеревьев, передавая level + 1.

😎 Решение:

class Solution {
public:
    vector<vector<int>> levels;

    void helper(TreeNode* node, int level) {
        if (levels.size() == level)
            levels.push_back(vector<int>());
        levels[level].push_back(node->val);
        if (node->left != NULL) helper(node->left, level + 1);
        if (node->right != NULL) helper(node->right, level + 1);
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        if (root == NULL) return levels;
        helper(root, 0);
        reverse(levels.begin(), levels.end());
        return levels;
    }
};

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

Задача: 287. Find the Duplicate Number
Сложность: medium

Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.

Пример:

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

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

1⃣Определение дубликата:
Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.
Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.
Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.

2⃣Восстановление массива:
Пройдите по массиву и измените все отрицательные элементы обратно на положительные, чтобы восстановить исходное состояние массива.

3⃣Возврат результата:
Верните найденный дубликат.

😎 Решение:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int duplicate = -1;
        for (int i = 0; i < nums.size(); i++) {
            int cur = abs(nums[i]);
            if (nums[cur] < 0) {
                duplicate = cur;
                break;
            }
            nums[cur] *= -1;
        }
        for (int i = 0; i < nums.size(); i++) {
            nums[i] = abs(nums[i]);
        }
        return duplicate;
    }
};

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

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

Создайте итератор, который поддерживает операцию peek (просмотр следующего элемента) на существующем итераторе, помимо операций hasNext (проверка наличия следующего элемента) и next (получение следующего элемента).

Реализуйте класс PeekingIterator:
PeekingIterator(Iterator<int> nums): Инициализирует объект с заданным итератором целых чисел.
int next(): Возвращает следующий элемент в массиве и перемещает указатель на следующий элемент.
boolean hasNext(): Возвращает true, если в массиве еще есть элементы.
int peek(): Возвращает следующий элемент в массиве без перемещения указателя.

Пример:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

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

1⃣Инициализация итератора:
В конструкторе класса PeekingIterator инициализируйте итератор и проверьте, есть ли следующий элемент. Если есть, установите его как next, иначе установите next в null.

2⃣Операция peek:
Метод peek возвращает значение next, не перемещая указатель итератора.

3⃣Операции next и hasNext:
Метод next возвращает текущее значение next, обновляет next к следующему элементу в итераторе и перемещает указатель итератора. Если нет следующего элемента, бросает исключение NoSuchElementException.
Метод hasNext возвращает true, если next не равно null, и false в противном случае.

😎 Решение:

#include <iterator>
#include <stdexcept>

class PeekingIterator : public std::iterator<std::input_iterator_tag, int> {
private:
    std::vector<int>::iterator iter;
    std::vector<int>::iterator end;
    int nextElem;
    bool hasNextElem;

public:
    PeekingIterator(std::vector<int>::iterator begin, std::vector<int>::iterator end) : iter(begin), end(end) {
        if (iter != end) {
            nextElem = *iter;
            hasNextElem = true;
        } else {
            hasNextElem = false;
        }
    }

    int peek() {
        if (!hasNextElem) {
            throw std::out_of_range("No more elements");
        }
        return nextElem;
    }

    int next() {
        if (!hasNextElem) {
            throw std::out_of_range("No more elements");
        }
        int currentElem = nextElem;
        ++iter;
        if (iter != end) {
            nextElem = *iter;
        } else {
            hasNextElem = false;
        }
        return currentElem;
    }

    bool hasNext() const {
        return hasNextElem;
    }
};

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

Задача: 111. Minimum Depth of Binary Tree
Сложность: easy

Дано бинарное дерево. Найдите его минимальную глубину — количество узлов вдоль кратчайшего пути от корня до ближайшего листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7] Output: 2

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

1⃣Используем рекурсивный обход в глубину (dfs). Базовый случай: если узел null, глубина равна 0.

2⃣Если левый потомок отсутствует, возвращаем 1 + dfs(root->right) — двигаемся по правому поддереву.

3⃣Если правый потомок отсутствует, возвращаем 1 + dfs(root->left) — двигаемся по левому поддереву.
Если оба потомка существуют — возвращаем 1 + min(dfs(left), dfs(right)).

😎 Решение:

class Solution {
public:
    int dfs(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        if (!root->left) {
            return 1 + dfs(root->right);
        } else if (!root->right) {
            return 1 + dfs(root->left);
        }
        return 1 + min(dfs(root->left), dfs(root->right));
    }

    int minDepth(TreeNode* root) {
        return dfs(root);
    }
};

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