Задача: 332. Reconstruct Itinerary
Сложность: hard

Вам дан список авиабилетов, где tickets[i] = [fromi, toi] представляют собой аэропорты отправления и прибытия одного рейса. Восстановите маршрут в порядке следования и верните его.
Все билеты принадлежат человеку, который вылетает из "JFK", поэтому маршрут должен начинаться с "JFK". Если существует несколько возможных маршрутов, вы должны вернуть маршрут, который имеет наименьший лексикографический порядок при чтении как одна строка.
Например, маршрут ["JFK", "LGA"] имеет меньший лексикографический порядок, чем ["JFK", "LGB"].
Вы можете предположить, что все билеты формируют хотя бы один действительный маршрут. Вы должны использовать все билеты один раз и только один раз.

Пример:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

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

1⃣Построение графа и сортировка:
Создайте граф flightMap, где ключи - это аэропорты отправления, а значения - это списки аэропортов прибытия.
Пройдите по всем билетам и заполните flightMap соответствующими значениями.
Отсортируйте списки аэропортов прибытия в лексикографическом порядке.

2⃣Пост-упорядоченный обход (DFS):
Создайте функцию DFS, которая будет рекурсивно проходить по всем ребрам (рейсам), начиная с аэропорта "JFK".
Во время обхода удаляйте использованные рейсы из графа, чтобы не проходить по ним повторно.

3⃣Формирование маршрута:
По мере завершения обхода добавляйте текущий аэропорт в начало списка результата.
После завершения DFS верните сформированный маршрут.

😎 Решение:

class Solution {
public:
    unordered_map<string, priority_queue<string, vector<string>, greater<string>>> flightMap;
    deque<string> result;

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& ticket : tickets) {
            flightMap[ticket[0]].push(ticket[1]);
        }

        dfs("JFK");
        return vector<string>(result.begin(), result.end());
    }

    void dfs(const string& origin) {
        auto& destList = flightMap[origin];
        while (!destList.empty()) {
            string nextDest = destList.top();
            destList.pop();
            dfs(nextDest);
        }
        result.push_front(origin);
    }
};

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

Задача: 746. Min Cost Climbing Stairs
Сложность: easy

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]
Output: 15

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

1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

3⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp = cost;
        for (int i = 2; i < n; i++) {
            dp[i] += min(dp[i - 1], dp[i - 2]);
        }
        return min(dp[n - 1], dp[n - 2]);
    }
};

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

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

Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.

Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.

Пример:

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⃣Извлечь имя хоста из startUrl.
Использовать многопоточность для обработки URL-адресов.

2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения.

3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц.

😎 Решение:

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

std::string extractHostname(const std::string& url) {
    auto pos = url.find("//");
    pos = (pos == std::string::npos) ? 0 : pos + 2;
    auto end = url.find('/', pos);
    return url.substr(pos, end - pos);
}

class Solution {
public:
    std::vector<std::string> crawl(std::string startUrl, HtmlParser htmlParser) {
        std::string hostname = extractHostname(startUrl);
        std::unordered_set<std::string> visited;
        std::mutex mtx;
        std::condition_variable cv;
        std::queue<std::string> q;
        q.push(startUrl);
        visited.insert(startUrl);
        std::vector<std::future<void>> futures;

        auto worker = [&]() {
            while (true) {
                std::string url;
                {
                    std::unique_lock<std::mutex> lock(mtx);
                    cv.wait(lock, [&]() { return !q.empty(); });
                    url = q.front();
                    q.pop();
                }
                for (const auto& nextUrl : htmlParser.getUrls(url)) {
                    if (extractHostname(nextUrl) == hostname) {
                        std::unique_lock<std::mutex> lock(mtx);
                        if (visited.insert(nextUrl).second) {
                            q.push(nextUrl);
                            cv.notify_all();
                        }
                    }
                }
            }
        };

        for (int i = 0; i < 10; ++i) {
            futures.push_back(std::async(std::launch::async, worker));
        }
        for (auto& future : futures) {
            future.wait();
        }
        return std::vector<std::string>(visited.begin(), visited.end());
    }
};

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣ Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣ Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣ Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ans(num + 1, 0);
        for (int x = 1; x <= num; ++x) {
            ans[x] = ans[x & (x - 1)] + 1;
        }
        return ans;
    }
};

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

Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram
Сложность: medium

Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.

Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s.

Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.

Пример:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

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

1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count.

2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count.

3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s.

😎 Решение:

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> count(26, 0);
        
        for (int i = 0; i < s.size(); i++) {
            count[t[i] - 'a']++;
            count[s[i] - 'a']--;
        }

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += max(0, count[i]);
        }

        return ans;
    }
};

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

Задача: 530. Minimum Absolute Difference in BST
Сложность: easy

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

Пример:

Input: root = [4,2,6,1,3]
Output: 1

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

1⃣ Обход дерева в порядке возрастания (инфиксный обход):
Создайте список inorderNodes для хранения значений узлов.
Выполните инфиксный обход дерева, добавляя значения узлов в список.

2⃣ Нахождение минимальной разницы:
Создайте переменную minDifference и инициализируйте её бесконечностью.
Пройдите по списку inorderNodes, начиная с индекса 1, и найдите минимальную абсолютную разницу между последовательными элементами.

3⃣ Возврат результата:
Верните minDifference.

😎 Решение:

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> inorderNodes;
        inorderTraversal(root, inorderNodes);
        int minDifference = INT_MAX;
        for (int i = 1; i < inorderNodes.size(); ++i) {
            minDifference = min(minDifference, inorderNodes[i] - inorderNodes[i - 1]);
        }
        return minDifference;
    }

private:
    void inorderTraversal(TreeNode* node, vector<int>& inorderNodes) {
        if (node == nullptr) return;
        inorderTraversal(node->left, inorderNodes);
        inorderNodes.push_back(node->val);
        inorderTraversal(node->right, inorderNodes);
    }
};

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

Задача: 761. Special Binary String
Сложность: hard

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"
Output: "11100100"

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

1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.

2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎 Решение:

class Solution {
public:
    string makeLargestSpecial(string s) {
        int count = 0, i = 0;
        vector<string> substrs;
        for (int j = 0; j < s.size(); j++) {
            count += s[j] == '1' ? 1 : -1;
            if (count == 0) {
                substrs.push_back("1" + makeLargestSpecial(s.substr(i + 1, j - i - 1)) + "0");
                i = j + 1;
            }
        }
        sort(substrs.begin(), substrs.end(), greater<string>());
        string result;
        for (const string& substr : substrs) {
            result += substr;
        }
        return result;
    }
};

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

Задача: 1189. Maximum Number of Balloons
Сложность: easy

Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon".

Каждый символ строки text можно использовать не более одного раза. Верните максимальное количество экземпляров, которые можно сформировать.

Пример:

Input: text = "nlaebolko"
Output: 1

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

1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text.

2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений.

3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение.

😎 Решение:

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        int bCount = 0, aCount = 0, lCount = 0, oCount = 0, nCount = 0;

        for (char c : text) {
            if (c == 'b') {
                bCount++;
            } else if (c == 'a') {
                aCount++;
            } else if (c == 'l') {
                lCount++;
            } else if (c == 'o') {
                oCount++;
            } else if (c == 'n') {
                nCount++;
            }
        }

        lCount = lCount / 2;
        oCount = oCount / 2;

        return min({bCount, aCount, lCount, oCount, nCount});
    }
};

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

Задача: 725. Split Linked List in Parts
Сложность: medium

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

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

1⃣Определите общую длину связного списка.

2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее.

3⃣Разделите список на части, присваивая каждую часть в массив результатов.

😎 Решение:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

vector<ListNode*> splitListToParts(ListNode* root, int k) {
    int length = 0;
    ListNode* node = root;
    while (node != nullptr) {
        length++;
        node = node->next;
    }

    int partLength = length / k;
    int extraParts = length % k;

    vector<ListNode*> parts(k, nullptr);
    node = root;
    for (int i = 0; i < k; i++) {
        ListNode* partHead = node;
        int partSize = partLength + (i < extraParts ? 1 : 0);
        for (int j = 0; j < partSize - 1; j++) {
            if (node != nullptr) node = node->next;
        }
        if (node != nullptr) {
            ListNode* nextPart = node->next;
            node->next = nullptr;
            node = nextPart;
        }
        parts[i] = partHead;
    }

    return parts;
}

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

Задача: 239. Sliding Window Maximum
Сложность: hard

Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните максимальные значения скользящего окна.

Пример:

Input: nums = [1], k = 1
Output: [1]

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

1⃣Инициализация и заполнение первой части окна:
Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов.
Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента:
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]].

2⃣Сканирование оставшейся части массива:
Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента:
Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна.
Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i].
Добавьте текущий индекс i в конец dq.
Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]].

3⃣Возвращение результата:
Верните список res, содержащий максимальные элементы для каждого скользящего окна.

😎 Решение:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k){
        deque<int> dq;
        vector<int> res;
        for (int i = 0; i < k; i++) {
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        res.push_back(nums[dq.front()]);

        for (int i = k; i < nums.size(); i++) {
            if(dq.front() == i - k) {
                dq.pop_front();
            }
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);
            res.push_back(nums[dq.front()]);
        }
        
        return res;
    }
};

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

Задача: 1673. Find the Most Competitive Subsequence
Сложность: medium

Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k.

Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива.

Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.

Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

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

1⃣Создайте двустороннюю очередь (deque), которая будет хранить выбранную подпоследовательность.

2⃣Переберите массив nums, выбирая наиболее конкурентоспособные элементы и добавляя их в очередь. Сравнивайте последний элемент в очереди с текущим элементом, удаляя из очереди более крупные элементы, если можно удалить больше элементов, чем необходимо для достижения размера k.

3⃣В конце получите первые k элементов из очереди и создайте результирующий массив.

😎 Решение:

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        deque<int> queue;
        int additionalCount = nums.size() - k;
        
        for (int num : nums) {
            while (!queue.empty() && queue.back() > num && additionalCount > 0) {
                queue.pop_back();
                additionalCount--;
            }
            queue.push_back(num);
        }
        
        return vector<int>(queue.begin(), queue.begin() + k);
    }
};

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

Задача: 1274. Number of Ships in a Rectangle
Сложность: hard

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

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

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

2⃣Рекурсивно проверьте наличие кораблей в каждом из четырех подпрямоугольников, используя функцию hasShips

3⃣Суммируйте количество кораблей в подпрямоугольниках для получения общего количества кораблей в текущем прямоугольнике.

😎 Решение:

class Solution {
public:
    int countShips(Sea sea, Point topRight, Point bottomLeft) {
        if (!sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1;
        }
        int midX = (topRight.x + bottomLeft.x) / 2;
        int midY = (topRight.y + bottomLeft.y) / 2;
        return countShips(sea, {midX, midY}, bottomLeft) +
               countShips(sea, topRight, {midX + 1, midY + 1}) +
               countShips(sea, {midX, topRight.y}, {bottomLeft.x, midY + 1}) +
               countShips(sea, {topRight.x, midY}, {midX + 1, bottomLeft.y});
    }
};

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

Задача: 827. Making A Large Island
Сложность: hard

Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1.

Верните размер самого большого острова в grid после выполнения этой операции.

Остров — это группа 1, соединенных в 4 направлениях.

Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

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

1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер.

2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1.

3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1.

😎 Решение:

class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int N = grid.size();
        vector<int> area(N * N + 2);
        int index = 2;
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (grid[r][c] == 1) {
                    area[index] = dfs(grid, r, c, index);
                    ++index;
                }
            }
        }
        
        int ans = *max_element(area.begin(), area.end());
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (grid[r][c] == 0) {
                    unordered_set<int> seen;
                    for (auto [nr, nc] : neighbors(grid, r, c)) {
                        if (grid[nr][nc] > 1) {
                            seen.insert(grid[nr][nc]);
                        }
                    }
                    int bns = 1;
                    for (int i : seen) bns += area[i];
                    ans = max(ans, bns);
                }
            }
        }
        return ans;
    }

private:
    int dfs(vector<vector<int>>& grid, int r, int c, int index) {
        int ans = 1;
        grid[r][c] = index;
        for (auto [nr, nc] : neighbors(grid, r, c)) {
            if (grid[nr][nc] == 1) {
                grid[nr][nc] = index;
                ans += dfs(grid, nr, nc, index);
            }
        }
        return ans;
    }

    vector<pair<int, int>> neighbors(vector<vector<int>>& grid, int r, int c) {
        int N = grid.size();
        vector<pair<int, int>> result;
        vector<int> dr = {-1, 0, 1, 0};
        vector<int> dc = {0, -1, 0, 1};
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
                result.emplace_back(nr, nc);
            }
        }
        return result;
    }
};

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

Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

Верните минимальный размер набора, чтобы было удалено не менее половины целых чисел из массива.

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа.

2⃣Отсортировать список подсчета в порядке убывания.

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

😎 Решение:

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        
        vector<int> counts;
        int currentRun = 1;
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1;
                continue;
            }
            counts.push_back(currentRun);
            currentRun = 1;
        }
        counts.push_back(currentRun);
        
        sort(counts.rbegin(), counts.rend());
        
        int numbersRemovedFromArr = 0;
        int setSize = 0;
        for (int count : counts) {
            numbersRemovedFromArr += count;
            setSize += 1;   
            if (numbersRemovedFromArr >= arr.size() / 2) {
                break;
            }
        }
        
        return setSize;
    }
};

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

Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

class Solution {
public:
    int minSwaps(vector<int>& data) {
        int ones = accumulate(data.begin(), data.end(), 0);
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;

        while (right < data.size()) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = max(max_one, cnt_one);
        }
        return ones - max_one;
    }
};

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

Задача: 407. Trapping Rain Water II
Сложность: hard

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

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

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

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

2⃣Постепенно извлекайте ячейки из очереди, рассматривая их соседей. Если соседняя ячейка ниже текущей, добавьте разницу в высоте к общему объему воды и обновите её высоту.

3⃣Повторите процесс, пока все ячейки не будут обработаны.

😎 Решение:

using namespace std;

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty() || heightMap[0].empty()) return 0;
        int m = heightMap.size(), n = heightMap[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        auto cmp = [](const vector<int>& a, const vector<int>& b) { return a[0] > b[0]; };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> heap(cmp);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    heap.push({ heightMap[i][j], i, j });
                    visited[i][j] = true;
                }
            }
        }
        
        vector<vector<int>> directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        int water = 0;
        
        while (!heap.empty()) {
            auto curr = heap.top(); heap.pop();
            int h = curr[0], x = curr[1], y = curr[2];
            for (auto& dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    water += max(0, h - heightMap[nx][ny]);
                    heap.push({ max(h, heightMap[nx][ny]), nx, ny });
                }
            }
        }
        
        return water;
    }
};

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после удаления всех неалфавитно-цифровых символов и приведения к нижнему регистру, она читается одинаково слева направо и справа налево.

Пример:

Input: s = "A man, a plan, a canal: Panama" Output: true
Explanation: "amanaplanacanalpanama" — палиндром

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

1⃣Установите два указателя: i в начале строки и j в конце.

2⃣Пропускайте все символы, которые не являются буквами или цифрами (isalnum), с обеих сторон.

3⃣Сравнивайте символы, приведённые к нижнему регистру (tolower). Если они не равны — строка не палиндром. Если равны — двигайтесь к центру.

😎 Решение:

class Solution {
public:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            while (i < j && !isalnum(s[i])) i++;
            while (i < j && !isalnum(s[j])) j--;

            if (tolower(s[i]) != tolower(s[j])) return false;
        }

        return true;
    }
};

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

Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

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

1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы.

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение:

class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        vector<int> queryResults;
        unordered_map<int, vector<int>> hashmap;

        for (int i = 0; i < colors.size(); i++) {
            hashmap[colors[i]].push_back(i);
        }

        for (const auto& query : queries) {
            int target = query[0], color = query[1];
            if (hashmap.find(color) == hashmap.end()) {
                queryResults.push_back(-1);
                continue;
            }

            const auto& indexList = hashmap[color];
            auto insert = lower_bound(indexList.begin(), indexList.end(), target);

            if (insert == indexList.begin()) {
                queryResults.push_back(*insert - target);
            } else if (insert == indexList.end()) {
                queryResults.push_back(target - indexList.back());
            } else {
                int leftNearest = target - *(insert - 1);
                int rightNearest = *insert - target;
                queryResults.push_back(min(leftNearest, rightNearest));
            }
        }
        return queryResults;
    }
};

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

Задача: 851. Loud and Rich
Сложность: medium

Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.

Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).

Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.

Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

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

1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов.

2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person.

3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного.

😎 Решение:

class Solution {
public:
    vector<vector<int>> graph;
    vector<int> answer;
    vector<int> quiet;

    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int N = quiet.size();
        graph.resize(N);
        answer.resize(N, -1);
        this->quiet = quiet;

        for (const auto& edge : richer) {
            graph[edge[1]].push_back(edge[0]);
        }

        for (int node = 0; node < N; ++node) {
            dfs(node);
        }
        return answer;
    }

    int dfs(int node) {
        if (answer[node] == -1) {
            answer[node] = node;
            for (int child : graph[node]) {
                int cand = dfs(child);
                if (quiet[cand] < quiet[answer[node]]) {
                    answer[node] = cand;
                }
            }
        }
        return answer[node];
    }
};

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

Задача: 361. Bomb Enemy
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

2⃣Реализовать функцию killEnemies(row, col), которая считает количество врагов, убитых бомбой, установленных в пустой ячейке (row, col), проверяя все четыре направления (влево, вправо, вверх, вниз) до стены или границы сетки.

3⃣Вернуть максимальное количество врагов, убитых среди всех пустых ячеек.

😎 Решение:

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        int maxCount = 0;

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == '0') {
                    int hits = killEnemies(row, col, grid);
                    maxCount = max(maxCount, hits);
                }
            }
        }

        return maxCount;
    }

private:
    int killEnemies(int row, int col, vector<vector<char>>& grid) {
        int enemyCount = 0;
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (const auto& dir : directions) {
            int r = row + dir.first;
            int c = col + dir.second;
            
            while (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
                if (grid[r][c] == 'W') break;
                if (grid[r][c] == 'E') ++enemyCount;
                r += dir.first;
                c += dir.second;
            }
        }

        return enemyCount;
    }
};

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