Задача: 496. Next Greater Element I
Сложность: easy

Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве.

Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2.
Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1.

Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше.

Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

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

1⃣Инициализация и поиск совпадений
Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2.

2⃣Поиск следующего большего элемента
После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res.

3⃣Заполнение результата
Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res.

😎 Решение:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size(), -1);
        
        for (int i = 0; i < nums1.size(); i++) {
            bool found = false;
            for (int j = 0; j < nums2.size(); j++) {
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        
        return res;
    }
};

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

Задача: 811. Subdomain Visit Count
Сложность: medium

Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com".

Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен.

Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз.
Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке.

Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

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

1⃣Следуем указаниям из условия задачи.

2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y.

3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split.

😎 Решение:

#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>

using namespace std;

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> ans;
        for (const string& domain : cpdomains) {
            istringstream iss(domain);
            int count;
            string domain;
            iss >> count >> domain;
            vector<string> frags;
            istringstream fragStream(domain);
            string frag;
            while (getline(fragStream, frag, '.')) {
                frags.push_back(frag);
            }
            for (size_t i = 0; i < frags.size(); ++i) {
                string subdomain;
                for (size_t j = i; j < frags.size(); ++j) {
                    if (j > i) subdomain += ".";
                    subdomain += frags[j];
                }
                ans[subdomain] += count;
            }
        }
        vector<string> res;
        for (const auto& p : ans) {
            res.push_back(to_string(p.second) + " " + p.first);
        }
        return res;
    }
};

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

Задача: 1423. Maximum Points You Can Obtain from Cards
Сложность: medium

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

Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить.

Пример:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

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

1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве.

2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт.

3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости.

😎 Решение:

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        vector<int> frontSetOfCards(k + 1, 0);
        vector<int> rearSetOfCards(k + 1, 0);
        
        for (int i = 0; i < k; ++i) {
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i];
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i];
        }
        
        int maxScore = 0;
        for (int i = 0; i <= k; ++i) {
            int currentScore = frontSetOfCards[i] + rearSetOfCards[k - i];
            maxScore = max(maxScore, currentScore);
        }
        
        return maxScore;
    }
};

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

Задача: 537. Complex Number Multiplication
Сложность: medium

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        auto x = split(a);
        auto y = split(b);
        int a_real = stoi(x[0]);
        int a_img = stoi(x[1]);
        int b_real = stoi(y[0]);
        int b_img = stoi(y[1]);
        int realPart = a_real * b_real - a_img * b_img;
        int imaginaryPart = a_real * b_img + a_img * b_real;
        return to_string(realPart) + "+" + to_string(imaginaryPart) + "i";
    }

private:
    vector<string> split(const string &s) {
        size_t plus = s.find('+');
        size_t i = s.find('i');
        return {s.substr(0, plus), s.substr(plus + 1, i - plus - 1)};
    }
};

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

Задача: 1228. Missing Number In Arithmetic Progression
Сложность: easy

В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1.

Из массива arr было удалено значение, которое не было первым или последним значением в массиве.

Дан массив arr, вернуть удаленное значение.

Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

1⃣Рассчитать разность difference между элементами арифметической прогрессии.

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

3⃣Вернуть первое ожидаемое значение, которое не совпадает с текущим значением в массиве.

😎 Решение:

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int difference = (arr[n - 1] - arr[0]) / n;
        int expected = arr[0];

        for (int val : arr) {
            if (val != expected) {
                return expected;
            }
            expected += difference;
        }
        return expected;
    }
};

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

Задача: 1095. Find in Mountain Array
Сложность: hard

Массив arr является горным массивом тогда и только тогда, когда:

Длина массива arr >= 3.
Существует некоторое i с 0 < i < arr.length - 1 такое, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1.

Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray:

MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0).
MountainArray.length() возвращает длину массива.
Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы.

Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

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

1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика.

2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем.

3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1.

😎 Решение:

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int length = mountainArr.length();

        int low = 1, high = length - 2;
        while (low != high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int peak = low;

        low = 0, high = peak;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        low = peak + 1, high = length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) > target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        return -1;
    }
};

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

Задача: 333. Largest BST Subtree
Сложность: medium

Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов.
Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства:
Значения в левом поддереве меньше значения их родительского (корневого) узла.
Значения в правом поддереве больше значения их родительского (корневого) узла.
Примечание: Поддерево должно включать всех своих потомков.

Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

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

1⃣Пост-упорядоченный обход дерева:
Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды.

2⃣Проверка условий BST для каждой ноды:
Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST:
- значение текущей ноды должно быть больше максимального значения в левом поддереве.
- значение текущей ноды должно быть меньше минимального значения в правом поддереве.
Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды).

3⃣Возврат максимального размера BST:
Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева.
В конце рекурсивного обхода верните максимальный размер BST в дереве.

😎 Решение:

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

class NodeValue {
public:
    int minNode, maxNode, maxSize;
    
    NodeValue(int minNode, int maxNode, int maxSize) : 
        minNode(minNode), maxNode(maxNode), maxSize(maxSize) {}
};

class Solution {
public:
    NodeValue largestBSTSubtreeHelper(TreeNode* root) {
        if (root == nullptr) {
            return NodeValue(INT_MAX, INT_MIN, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root->left);
        NodeValue right = largestBSTSubtreeHelper(root->right);
        
        if (left.maxNode < root->val && root->val < right.minNode) {
            return NodeValue(min(root->val, left.minNode), max(root->val, right.maxNode), 
                             left.maxSize + right.maxSize + 1);
        }
        
        return NodeValue(INT_MIN, INT_MAX, max(left.maxSize, right.maxSize));
    }
    
    int largestBSTSubtree(TreeNode* root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
};

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

Задача: 683. K Empty Slots
Сложность: hard

У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены.

Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.

Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1.

Пример:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

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

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

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

3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1.

😎 Решение:

#include <set>
#include <vector>

class Solution {
public:
    int kEmptySlots(std::vector<int>& flowers, int k) {
        std::set<int> active;
        int day = 0;
        
        for (int flower : flowers) {
            day++;
            active.insert(flower);
            auto lower = active.lower_bound(flower);
            auto higher = active.upper_bound(flower);
            
            if (lower != active.begin() && flower - *std::prev(lower) - 1 == k) {
                return day;
            }
            if (higher != active.end() && *higher - flower - 1 == k) {
                return day;
            }
        }
        return -1;
    }
};

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

2⃣Пройти по каждому слову в предложении и найти все возможные синонимы.
Сгенерировать все возможные комбинации предложений.

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        unordered_map<string, set<string>> graph;
        for (const auto& pair : synonyms) {
            graph[pair[0]].insert(pair[1]);
            graph[pair[1]].insert(pair[0]);
        }

        vector<string> words = split(text, ' ');
        vector<vector<string>> synonymGroups;
        for (const string& word : words) {
            synonymGroups.push_back(findSynonyms(graph, word));
        }

        vector<string> sentences;
        string sentence;
        generate(sentences, synonymGroups, sentence, 0);
        sort(sentences.begin(), sentences.end());
        return sentences;
    }

private:
    vector<string> split(const string& str, char delimiter) {
        vector<string> tokens;
        string token;
        istringstream tokenStream(str);
        while (getline(tokenStream, token, delimiter)) {
            tokens.push_back(token);
        }
        return tokens;
    }

    vector<string> findSynonyms(unordered_map<string, set<string>>& graph, const string& word) {
        set<string> synonyms;
        stack<string> stack;
        stack.push(word);
        while (!stack.empty()) {
            string w = stack.top();
            stack.pop();
            if (synonyms.insert(w).second) {
                for (const string& neighbor : graph[w]) {
                    stack.push(neighbor);
                }
            }
        }
        return vector<string>(synonyms.begin(), synonyms.end());
    }

    void generate(vector<string>& sentences, const vector<vector<string>>& groups, string& sentence, int index) {
        if (index == groups.size()) {
            sentences.push_back(sentence.substr(1));
            return;
        }
        for (const string& word : groups[index]) {
            string original = sentence;
            sentence += " " + word;
            generate(sentences, groups, sentence, index + 1);
            sentence = original;
        }
    }
};

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

Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

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

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎 Решение:

class Solution {
public:
    bool valid(string str1, string str2, int k) {
        int len1 = str1.size(), len2 = str2.size();
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            string base = str1.substr(0, k);
            int n1 = len1 / k, n2 = len2 / k;
            return str1 == joinWords(base, n1) && str2 == joinWords(base, n2);
        }
    }
    string joinWords(string str, int k) {
        string ans = "";
        for (int i = 0; i < k; ++i) {
            ans += str;
        }
        return ans;
    }
    string gcdOfStrings(string str1, string str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = min(len1, len2); i >= 1; --i) {
            if (valid(str1, str2, i)) {
                return str1.substr(0, i);
            }
        }
        return "";
    }
};

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

Задача: 681. Next Closest Time
Сложность: medium

Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.

Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.

Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

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

1⃣Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время.

2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60.

3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д.

😎 Решение:

class Solution {
public:
    string nextClosestTime(string time) {
        int cur = 60 * stoi(time.substr(0, 2)) + stoi(time.substr(3));
        unordered_set<int> allowed;
        for (char c : time) if (c != ':') {
            allowed.insert(c - '0');
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            vector<int> digits = {cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10};
            bool valid = true;
            for (int d : digits) {
                if (!allowed.count(d)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return (cur / 60 < 10 ? "0" : "") + to_string(cur / 60) + ":" + (cur % 60 < 10 ? "0" : "") + to_string(cur % 60);
            }
        }
    }
};

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

Задача: 251. Flatten 2D Vector
Сложность: medium

Пример:

Input: vec = [[1, 2], [3], [4]]
Output: 1, 2, 3, true, true, 4, false

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

1⃣Преобразуем двумерный вектор в одномерный
Итерируемся по каждому вложенному вектору и добавляем его элементы в одномерный массив.

2⃣Метод hasNext проверяет наличие следующего элемента
Возвращает true, если текущий индекс position + 1 находится в пределах размера массива.

3⃣Метод next возвращает элемент
Увеличивает индекс position и возвращает текущий элемент массива.

😎 Решение:

#include <vector>
using namespace std;

class Vector2D {
    vector<int> nums;
    int position;

public:
    Vector2D(vector<vector<int>>& v) : position(-1) {
        for (auto& innerList : v) {
            nums.insert(nums.end(), innerList.begin(), innerList.end());
        }
    }

    int next() {
        position++;
        return nums[position];
    }

    bool hasNext() {
        return position + 1 < nums.size();
    }
};

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

Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

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

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

class MaxStack {
public:
    MaxStack() {}

    void push(int x) {
        stack.push(x);
        if (maxStack.empty() || x >= maxStack.top()) {
            maxStack.push(x);
        }
    }

    int pop() {
        int x = stack.top();
        stack.pop();
        if (x == maxStack.top()) {
            maxStack.pop();
        }
        return x;
    }

    int top() {
        return stack.top();
    }

    int peekMax() {
        return maxStack.top();
    }

    int popMax() {
        int maxVal = maxStack.top();
        maxStack.pop();
        stack<int> buffer;
        while (stack.top() != maxVal) {
            buffer.push(stack.top());
            stack.pop();
        }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

private:
    stack<int> stack;
    stack<int> maxStack;
};

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

Задача: 373. Find K Pairs with Smallest Sums
Сложность: medium

Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.
Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.
Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами.

Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

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

1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар.

2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited.

3⃣Повторяйте до получения k пар и пока minHeap не пуст:
Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2].
Добавьте пару (nums1[i], nums2[j]) в ans.
Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap.
Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap.
Верните ans.

😎 Решение:

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();

        vector<vector<int>> ans;
        set<pair<int, int>> visited;

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
                       greater<pair<int, pair<int, int>>>> minHeap;
        minHeap.push({nums1[0] + nums2[0], {0, 0}});
        visited.insert({0, 0});

        while (k-- && !minHeap.empty()) {
            auto top = minHeap.top();
            minHeap.pop();
            int i = top.second.first;
            int j = top.second.second;

            ans.push_back({nums1[i], nums2[j]});

            if (i + 1 < m && visited.find({i + 1, j}) == visited.end()) {
                minHeap.push({nums1[i + 1] + nums2[j], {i + 1, j}});
                visited.insert({i + 1, j});
            }

            if (j + 1 < n && visited.find({i, j + 1}) == visited.end()) {
                minHeap.push({nums1[i] + nums2[j + 1], {i, j + 1}});
                visited.insert({i, j + 1});
            }
        }

        return ans;
    }
};

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero
Сложность: medium

Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.

Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.

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

Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

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

1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).

2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.

3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.

😎 Решение:

class Solution {
public:
    int count = 0;

    void dfs(int node, int parent, unordered_map<int, vector<pair<int, int>>>& adj) {
        if (adj.find(node) == adj.end()) {
            return;
        }
        for (auto& nei : adj[node]) {
            int neighbor = nei.first;
            int sign = nei.second;
            if (neighbor != parent) {
                count += sign;
                dfs(neighbor, node, adj);
            }
        }
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        unordered_map<int, vector<pair<int, int>>> adj;
        for (auto& connection : connections) {
            adj[connection[0]].emplace_back(connection[1], 1);
            adj[connection[1]].emplace_back(connection[0], 0);
        }
        dfs(0, -1, adj);
        return count;
    }
};

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

class Solution {
public:
    string crackSafe(int n, int k) {
        unordered_set<string> seen;
        string result;

        string startNode(n - 1, '0');
        dfs(startNode, k, seen, result);

        result += startNode;
        return result;
    }

private:
    void dfs(const string& node, int k, unordered_set<string>& seen, string& result) {
        for (int x = 0; x < k; ++x) {
            string neighbor = node + to_string(x);
            if (!seen.count(neighbor)) {
                seen.insert(neighbor);
                dfs(neighbor.substr(1), k, seen, result);
                result += to_string(x);
            }
        }
    }
};

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

Задача: 76. Minimum Window Substring
Сложность: hard

Даны две строки s и t длиной m и n соответственно.
Верните наименьшую подстроку строки s, содержащую все символы строки t (включая дубликаты).
Если такой подстроки не существует, верните пустую строку "".

Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

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

1⃣Используем два указателя left и right, инициализированные на начало строки s.

2⃣Расширяем окно, двигая right, пока окно не будет содержать все символы из t.

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

😎 Решение:

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }
        unordered_map<char, int> dictT;
        for (int i = 0; i < t.length(); i++) {
            dictT[t[i]]++;
        }
        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;
        unordered_map<char, int> windowCounts;
        int ans[3] = {-1, 0, 0};
        while (r < s.length()) {
            char c = s[r];
            windowCounts[c]++;
            if (dictT.find(c) != dictT.end() && windowCounts[c] == dictT[c]) {
                formed++;
            }
            while (l <= r && formed == required) {
                c = s[l];
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowCounts[c]--;
                if (dictT.find(c) != dictT.end() && windowCounts[c] < dictT[c]) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.substr(ans[1], ans[2] - ans[1] + 1);
    }
};

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

Задача: 867. Transpose Matrix
Сложность: easy

Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу.

Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами.

Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

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

1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк.

2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c].

3⃣Верните матрицу ans.

😎 Решение:

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& A) {
        int R = A.size(), C = A[0].size();
        vector<vector<int>> ans(C, vector<int>(R));
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                ans[c][r] = A[r][c];
        return ans;
    }
};

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

Задача: 1046. Last Stone Weight
Сложность: easy

Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.

Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

1⃣Создай максимальную кучу из массива камней.

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

3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0, если камней не осталось.

😎 Решение:

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> maxHeap(stones.begin(), stones.end());
        
        while (maxHeap.size() > 1) {
            int first = maxHeap.top(); maxHeap.pop();
            int second = maxHeap.top(); maxHeap.pop();
            if (first != second) {
                maxHeap.push(first - second);
            }
        }
        
        return maxHeap.empty() ? 0 : maxHeap.top();
    }
};

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

Задача: 790. Domino and Tromino Tiling
Сложность: medium

У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.

Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

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

Пример:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

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

1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).

2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас.

3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.

😎 Решение:

class Solution {
public:
    int numTilings(int n) {
        const int MOD = 1'000'000'007;
        unordered_map<int, int> fCache;
        unordered_map<int, int> pCache;

        function<int(int)> p = [&](int n) -> int {
            if (pCache.count(n)) return pCache[n];
            if (n == 2) return 1;
            return pCache[n] = (p(n - 1) + f(n - 2)) % MOD;
        };

        function<int(int)> f = [&](int n) -> int {
            if (fCache.count(n)) return fCache[n];
            if (n <= 2) return n;
            return fCache[n] = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
        };

        return f(n);
    }
};

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