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

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

Задача: 1323. Maximum 69 Number
Сложность: easy

Дано положительное целое число num, состоящее только из цифр 6 и 9.

Верните максимальное число, которое можно получить, изменив не более одной цифры (6 становится 9, а 9 становится 6).

Пример:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

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

1⃣Преобразуйте входное целое число num в итерируемый и изменяемый объект num_obj.

2⃣Пройдитесь по num_obj и, если найдете цифру 6, замените её на 9 и прекратите итерацию.

3⃣Верните целое число, преобразованное из измененного num_obj.

😎 Решение:

class Solution {
public:
    int maximum69Number (int num) {
        string numStr = to_string(num);
        for (char &c : numStr) {
            if (c == '6') {
                c = '9';
                break;
            }
        }
        return stoi(numStr);
    }
};

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

Задача: 772. Basic Calculator III
Сложность: medium

Реализуйте базовый калькулятор для вычисления простого строкового выражения.

Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.

Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].

Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval().

Пример:

Input: s = "1+1"
Output: 2

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

1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@".

2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+".

3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке.

😎 Решение:

class Solution {
public:
    string evaluate(char operator, string first, string second) {
        int x = stoi(first);
        int y = stoi(second);
        int res = 0;
        
        if (operator == '+') {
            res = x;
        } else if (operator == '-') {
            res = -x;
        } else if (operator == '*') {
            res = x * y;
        } else {
            res = x / y;
        }
        
        return to_string(res);
    }
    
    int calculate(string s) {
        stack<string> stack;
        string curr = "";
        char previousOperator = '+';
        s += "@";
        unordered_set<string> operators = {"+", "-", "*", "/"};
        
        for (char c: s) {
            if (isdigit(c)) {
                curr += c;
            } else if (c == '(') {
                stack.push(string(1, previousOperator));
                previousOperator = '+';
            } else {
                if (previousOperator == '*' || previousOperator == '/') {
                    stack.push(evaluate(previousOperator, stack.top(), curr));
                    stack.pop();
                } else {
                    stack.push(evaluate(previousOperator, curr, "0"));
                }
                
                curr = "";
                previousOperator = c;
                if (c == ')') {
                    int currentTerm = 0;
                    while (operators.find(stack.top()) == operators.end()) {
                        currentTerm += stoi(stack.top());
                        stack.pop();
                    }
                    
                    curr = to_string(currentTerm);
                    previousOperator = stack.top()[0];
                    stack.pop();
                }
            }
        }
        
        int ans = 0;
        while (!stack.empty()) {
            ans += stoi(stack.top());
            stack.pop();
        }

        return ans;
    }
};

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

Задача: 302. Smallest Rectangle Enclosing Black Pixels
Сложность: hard

Вам дана бинарная матрица размером m x n, где 0 представляет собой белый пиксель, а 1 представляет собой черный пиксель.
Черные пиксели соединены (то есть существует только одна черная область). Пиксели соединены по горизонтали и вертикали.
Даны два целых числа x и y, которые представляют местоположение одного из черных пикселей. Верните площадь наименьшего (выравненного по осям) прямоугольника, который охватывает все черные пиксели.
Вы должны написать алгоритм со сложностью менее O(mn).

Пример:

Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
Output: 6

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

1⃣Инициализация границ прямоугольника: Инициализируйте переменные left, right, top и bottom. left и top задаются значениями координат (x, y), right и bottom - значениями x + 1 и y + 1 соответственно.

2⃣Обход всех пикселей: Пройдите по всем координатам (x, y) матрицы. Если текущий пиксель является черным (image[x][y] == 1), обновите границы прямоугольника:
left = min(left, x)
right = max(right, x + 1)
top = min(top, y)
bottom = max(bottom, y + 1)

3⃣Вычисление и возврат площади: После завершения обхода матрицы, верните площадь прямоугольника, используя формулу (right - left) * (bottom - top).

😎 Решение:

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int m = image.size(), n = image[0].size();
        int left = searchColumns(image, 0, y, 0, m, true);
        int right = searchColumns(image, y + 1, n, 0, m, false);
        int top = searchRows(image, 0, x, left, right, true);
        int bottom = searchRows(image, x + 1, m, left, right, false);
        return (right - left) * (bottom - top);
    }

private:
    int searchColumns(vector<vector<char>>& image, int i, int j, int top, int bottom, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int t = top;
            while (t < bottom && image[t][k] == '0') t++;
            if ((t < bottom) == opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }

    int searchRows(vector<vector<char>>& image, int i, int j, int left, int right, bool opt) {
        while (i != j) {
            int k = (i + j) / 2;
            int l = left;
            while (l < right && image[k][l] == '0') l++;
            if ((l < right) == opt) {
                j = k;
            } else {
                i = k + 1;
            }
        }
        return i;
    }
};

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

Задача: 115. Distinct Subsequences
Сложность: hard

Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t.

Пример:

Input: s = "rabbbit", t = "rabbit" Output: 3
Explanation:
Из строки s = "rabbbit" можно получить "rabbit" тремя разными способами, выбирая разные b на позиции 2, 3 и 4.

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

1⃣Реализуем рекурсивную функцию recurse(i, j), где i — текущий индекс в строке s, а j — в строке t. Используем хэш-таблицу memo для кэширования результатов recurse(i, j).

2⃣Базовые случаи:
Если j == t.length() — вся строка t успешно сопоставлена, возвращаем 1.
Если i == s.length() — строка s закончилась до завершения t, возвращаем 0.

3⃣Если s[i] == t[j], то у нас два варианта:
использовать символ s[i] → recurse(i+1, j+1)
пропустить символ s[i] → recurse(i+1, j)
Если s[i] != t[j], продолжаем только с recurse(i+1, j). Результат сохраняем в memo и возвращаем.

😎 Решение:

class Solution {
private:
    unordered_map<string, int> memo;

public:
    int numDistinct(string s, string t) {
        if (s.size() < t.size()) return 0;
        if (s == t || t.empty()) return 1;

        string key = to_string(s.size()) + "," + to_string(t.size());
        if (memo.find(key) != memo.end()) return memo[key];

        int N = s.size(), M = t.size();
        int ans = numDistinct(s.substr(0, N - 1), t);

        if (s[N - 1] == t[M - 1])
            ans += numDistinct(s.substr(0, N - 1), t.substr(0, M - 1));

        memo[key] = ans;
        return ans;
    }
};

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

Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

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

😎 Решение:

using namespace std;

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string, double>> graph;

        for (int i = 0; i < equations.size(); ++i) {
            string A = equations[i][0], B = equations[i][1];
            double value = values[i];
            graph[A][B] = value;
            graph[B][A] = 1.0 / value;
        }

        vector<double> results;
        for (auto& query : queries) {
            string C = query[0], D = query[1];
            if (!graph.count(C) || !graph.count(D)) {
                results.push_back(-1.0);
            } else {
                results.push_back(bfs(C, D, graph));
            }
        }
        return results;
    }

private:
    double bfs(const string& start, const string& end, unordered_map<string, unordered_map<string, double>>& graph) {
        queue<pair<string, double>> q;
        q.push({start, 1.0});
        unordered_set<string> visited;

        while (!q.empty()) {
            auto [current, product] = q.front(); q.pop();
            if (current == end) return product;
            visited.insert(current);
            for (auto& [neighbor, value] : graph[current]) {
                if (!visited.count(neighbor)) {
                    q.push({neighbor, product * value});
                }
            }
        }
        return -1.0;
    }
};

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

Задача: 1360. Number of Days Between Two Dates
Сложность: easy

Напишите программу для подсчета количества дней между двумя датами.

Даты даны в виде строк в формате YYYY-MM-DD, как показано в примерах.

Пример:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

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

1⃣Преобразование строк в даты
Используйте встроенные функции для преобразования строковых представлений дат в объекты дат.

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

3⃣Возвращение результата
Верните абсолютное значение разницы в днях для получения положительного числа.

😎 Решение:

#include <iostream>
#include <string>
#include <cmath>
#include <ctime>

class Solution {
public:
    int daysBetweenDates(std::string date1, std::string date2) {
        std::tm tm1 = {}, tm2 = {};
        strptime(date1.c_str(), "%Y-%m-%d", &tm1);
        strptime(date2.c_str(), "%Y-%m-%d", &tm2);
        std::time_t time1 = std::mktime(&tm1);
        std::time_t time2 = std::mktime(&tm2);
        return std::abs((time2 - time1) / (60 * 60 * 24));
    }
};

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