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

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

Задача: 1669. Merge In Between Linked Lists
Сложность: medium

Вам даны два связанных списка: list1 и list2 размером n и m соответственно.

Удалите узлы list1 с ath узла по bth узел и вставьте на их место list2.

Синие ребра и узлы на рисунке в вверху поста указывают на результат:

Пример:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

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

1⃣Инициализация и добавление узлов из list1 до узла a в массив:
Инициализировать переменную index равную 0 и current1 равную list1.
Пока index меньше a, добавлять current1.val в массив mergeArray, перемещаться к следующему узлу current1.next и увеличивать index.

2⃣Добавление узлов из list2 в массив:
Инициализировать current2 равную list2.
Пока current2 не равен null, добавлять current2.val в mergeArray и перемещаться к следующему узлу current2.next.

3⃣Добавление узлов из list1 от узла b + 1 до конца в массив и создание нового связанного списка:
Найти узел на позиции b + 1, перемещая current1 и увеличивая index, пока index меньше b + 1.
Добавлять узлы из current1 в массив, пока current1 не станет null.
Создать новый связанный список из значений в mergeArray, добавляя узлы в начало списка и возвращая его.

😎 Решение:

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        vector<int> mergeArray;
        int index = 0;
        ListNode* current1 = list1;
        
        while (index < a) {
            mergeArray.push_back(current1->val);
            current1 = current1->next;
            index++;
        }
        
        ListNode* current2 = list2;
        while (current2 != nullptr) {
            mergeArray.push_back(current2->val);
            current2 = current2->next;
        }
        
        while (index < b + 1) {
            current1 = current1->next;
            index++;
        }
        
        while (current1 != nullptr) {
            mergeArray.push_back(current1->val);
            current1 = current1->next;
        }
        
        ListNode* resultList = nullptr;
        for (int i = mergeArray.size() - 1; i >= 0; i--) {
            resultList = new ListNode(mergeArray[i], resultList);
        }
        
        return resultList;
    }
};

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

Задача: 819. Most Common Word
Сложность: easy

Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным.

Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре.

Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

1⃣Заменяем всю пунктуацию пробелами и одновременно переводим каждую букву в нижний регистр. Это можно сделать и в два этапа, но здесь мы объединяем их в один этап.

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

3⃣Затем итерируемся по словам, чтобы подсчитать количество появлений каждого уникального слова, исключая слова из списка запрещенных. С помощью хеш-таблицы {слово->количество} проходим по всем элементам, чтобы найти слово с наивысшей частотой.

😎 Решение:

class Solution {
public:
    string mostCommonWord(string paragraph, vector<string>& banned) {
        for (char& c : paragraph) {
            c = isalnum(c) ? tolower(c) : ' ';
        }

        istringstream iss(paragraph);
        string word;
        unordered_map<string, int> wordCount;
        unordered_set<string> bannedWords(banned.begin(), banned.end());

        while (iss >> word) {
            if (bannedWords.find(word) == bannedWords.end()) {
                wordCount[word]++;
            }
        }

        return max_element(wordCount.begin(), wordCount.end(), 
                           [](const pair<string, int>& a, const pair<string, int>& b) {
                               return a.second < b.second;
                           })->first;
    }
};

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

Задача: 288. Unique Word Abbreviation
Сложность: medium

Дано множество слов. Необходимо определить, является ли слово уникальным по своей аббревиатуре среди слов в словаре.

Пример:

Input: dictionary = ["deer", "door", "cake", "card"]
isUnique("dear") → false
isUnique("cart") → true
isUnique("cake") → true

👨‍💻 Алгоритм

1⃣Создание сокращения слова
Если длина слова ≤ 2, возвращаем его как есть. Иначе создаем строку: первая буква + количество символов между + последняя буква. Например:
"dog" → "d1g"
"it" → "it"

2⃣Инициализация
Создаем множество dict, в которое помещаем все слова словаря (для точной проверки совпадения), и abbrDict, где ключ — сокращение, а значение — уникальность (true/false). Если для одной аббревиатуры встречается несколько разных слов, устанавливаем флаг как false.

3⃣Проверка isUnique
Если сокращение не найдено — возвращаем true.
Если найдено и уникально, проверяем, есть ли само слово в оригинальном словаре. Если есть — true, иначе — false.

😎 Решение

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string>& dictionary) {
        for (const string& word : dictionary) {
            dict.insert(word);
            string abbr = toAbbr(word);
            if (abbrDict.count(abbr)) {
                abbrDict[abbr] = abbrDict[abbr] == word;
            } else {
                abbrDict[abbr] = true;
            }
        }
    }

    bool isUnique(string word) {
        string abbr = toAbbr(word);
        auto it = abbrDict.find(abbr);
        return it == abbrDict.end() || (it->second && dict.count(word));
    }

private:
    unordered_map<string, bool> abbrDict;
    unordered_set<string> dict;

    string toAbbr(const string& word) {
        int n = word.length();
        if (n <= 2) return word;
        return word.front() + to_string(n - 2) + word.back();
    }
};

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

Задача: 1427. Perform String Shifts
Сложность: easy

Вам дана строка s, содержащая строчные английские буквы, и матрица shift, где shift[i] = [directioni, amounti]:
directioni может быть 0 (для сдвига влево) или 1 (для сдвига вправо).
amounti - это количество, на которое строка s должна быть сдвинута.
Сдвиг влево на 1 означает удаление первого символа строки s и добавление его в конец.
Аналогично, сдвиг вправо на 1 означает удаление последнего символа строки s и добавление его в начало.
Верните итоговую строку после всех операций.

Пример:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

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

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

2⃣Определите, какое из значений больше, и частично компенсируйте его другим. Затем выполните соответствующий сдвиг с оставшимся значением. Если оба значения равны, строка останется неизменной.

3⃣Выполните сдвиг строки на основе вычисленного значения и верните итоговую строку.

😎 Решение:

class Solution {
public:
    string stringShift(string s, vector<vector<int>>& shift) {
        int leftShifts = 0, rightShifts = 0;
        for (auto& move : shift) {
            if (move[0] == 0) {
                leftShifts += move[1];
            } else {
                rightShifts += move[1];
            }
        }
        
        int netShifts = (rightShifts - leftShifts) % s.length();
        if (netShifts < 0) {
            netShifts += s.length();
        }
        
        if (netShifts == 0) {
            return s;
        }
        
        return s.substr(s.length() - netShifts) + s.substr(0, s.length() - netShifts);
    }
};

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

Задача: 783. Minimum Distance Between BST Nodes
Сложность: easy

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

Пример:

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

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

1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы.

2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes.

3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance.
Верните minDistance.

😎 Решение:

class Solution {
public:
    vector<int> inorderNodes;
    
    void inorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        
        inorderTraversal(root->left);
        inorderNodes.push_back(root->val);
        inorderTraversal(root->right);
    }
    
    int minDiffInBST(TreeNode* root) {
        inorderTraversal(root);
        
        int minDistance = INT_MAX;
        for (int i = 1; i < inorderNodes.size(); i++) {
            minDistance = min(minDistance, inorderNodes[i] - inorderNodes[i - 1]);
        }
        
        return minDistance;
    }
};

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

Задача: 1018. Binary Prefix Divisible By 5
Сложность: easy

Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5.

Пример:

Input: nums = [0,1,1]
Output: [true,false,false]

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

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

2⃣Итерация по массиву:
Пройдите по всем элементам массива nums. Для каждого элемента:
Обновите значение x, учитывая текущий бит.
Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer.
Чтобы избежать переполнения, используйте модуль 5 для переменной x.

3⃣Возврат результата:
Верните массив answer с результатами проверки делимости на 5.

😎 Решение:

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        int x = 0;
        vector<bool> answer;
        for (int num : nums) {
            x = (x * 2 + num) % 5;
            answer.push_back(x == 0);
        }
        return answer;
    }
};

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

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

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

class Solution {
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        int m = grid.size(), n = grid[0].size();
        int original_color = grid[row][col];
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<pair<int, int>> borders;

        function<void(int, int)> dfs = [&](int r, int c) {
            visited[r][c] = true;
            bool is_border = false;
            for (auto [dr, dc] : vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    if (!visited[nr][nc]) {
                        if (grid[nr][nc] == original_color) {
                            dfs(nr, nc);
                        } else {
                            is_border = true;
                        }
                    }
                } else {
                    is_border = true;
                }
            }
            if (is_border || r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                borders.emplace_back(r, c);
            }
        };

        dfs(row, col);
        for (auto [r, c] : borders) {
            grid[r][c] = color;
        }

        return grid;
    }
};

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