Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

Input: n = 2, trust = [[1,2]]
Output: 2

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.

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

😎 Решение:

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

class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if (!root || val > root->val) {
            TreeNode* newNode = new TreeNode(val);
            newNode->left = root;
            return newNode;
        }
        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};

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

Задача: 1146. Snapshot Array
Сложность: medium

Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.

Пример:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

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

1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].

2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].

3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].

😎 Решение:

class SnapshotArray {
public:
    int snapId = 0;
    vector<map<int, int>> historyRecords;
    
    SnapshotArray(int length) {
        historyRecords.resize(length);
        for (int i = 0; i < length; i++) {
            historyRecords[i][0] = 0;
        }
    }

    void set(int index, int val) {
        historyRecords[index][snapId] = val;
    }

    int snap() {
        return snapId++;
    }

    int get(int index, int snapId) {
        auto it = historyRecords[index].upper_bound(snapId);
        return prev(it)->second;
    }
};

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

Задача: 95. Unique Binary Search Trees II
Сложность: medium

Дано число n.
Нужно вернуть все уникальные бинарные деревья поиска (BST),
которые можно построить из значений от 1 до n.

Пример:

Input: n = 3
Output: [[1,null,2,null,3], [1,null,3,2], [2,1,3], [3,1,null,null,2], [3,2,null,1]]

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

1⃣Реализуем рекурсивную функцию allPossibleBST(start, end),
которая возвращает список всех возможных деревьев с корнями в диапазоне [start, end].
Используем memo для кэширования уже рассчитанных поддиапазонов.

2⃣Базовый случай: если start > end, добавляем nullptr как возможный пустой поддерево.

3⃣Для каждого i в диапазоне от start до end:
рекурсивно генерируем все левые поддеревья от start до i - 1
рекурсивно генерируем все правые поддеревья от i + 1 до end
для каждой комбинации левого и правого поддерева создаём новый TreeNode(i) и добавляем его в результат

😎 Решение:

class Solution {
public:
    vector<TreeNode*> allPossibleBST(
        int start, int end, map<pair<int, int>, vector<TreeNode*>>& memo) {
        
        vector<TreeNode*> res;
        if (start > end) {
            res.push_back(nullptr);
            return res;
        }

        if (memo.find({start, end}) != memo.end()) {
            return memo[{start, end}];
        }

        for (int i = start; i <= end; ++i) {
            vector<TreeNode*> leftSubTrees = allPossibleBST(start, i - 1, memo);
            vector<TreeNode*> rightSubTrees = allPossibleBST(i + 1, end, memo);

            for (auto left : leftSubTrees) {
                for (auto right : rightSubTrees) {
                    TreeNode* root = new TreeNode(i, left, right);
                    res.push_back(root);
                }
            }
        }

        return memo[{start, end}] = res;
    }

    vector<TreeNode*> generateTrees(int n) {
        map<pair<int, int>, vector<TreeNode*>> memo;
        return allPossibleBST(1, n, memo);
    }
};

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

Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

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

1⃣Представить каждую строку и столбец как узлы в графе.

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

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

😎 Решение:

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        unordered_map<int, int> parent;
        
        function<int(int)> find = [&](int x) {
            if (!parent.count(x)) parent[x] = x;
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };
        
        auto unionFind = [&](int x, int y) {
            parent[find(x)] = find(y);
        };
        
        for (auto& stone : stones) {
            unionFind(stone[0], ~stone[1]);
        }
        
        unordered_set<int> uniqueRoots;
        for (auto& p : parent) {
            uniqueRoots.insert(find(p.first));
        }
        
        return stones.size() - uniqueRoots.size();
    }
};

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

Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

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

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

1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).

2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).

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

😎 Решение:

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, vector<pair<int, int>>> colTable;
        queue<pair<TreeNode*, pair<int, int>>> queue;
        queue.push({root, {0, 0}});
        
        while (!queue.empty()) {
            auto [node, pos] = queue.front();
            queue.pop();
            int row = pos.first, col = pos.second;
            colTable[col].emplace_back(row, node->val);
            
            if (node->left) {
                queue.push({node->left, {row + 1, col - 1}});
            }
            if (node->right) {
                queue.push({node->right, {row + 1, col + 1}});
            }
        }
        
        vector<vector<int>> result;
        for (auto& [col, pairs] : colTable) {
            sort(pairs.begin(), pairs.end());
            vector<int> sortedCol;
            for (auto& [row, val] : pairs) {
                sortedCol.push_back(val);
            }
            result.push_back(sortedCol);
        }
        
        return result;
    }
};

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

Задача: 172. Factorial Trailing Zeroes
Сложность: medium

Дано число n. Нужно вернуть количество конечных нулей в числе n! (n-факториал).

Пример:

Input: 3 → Output: 0
Пояснение: 3! = 6, нулей на конце нет.

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

1⃣Заметим, что каждый конечный 0 в n! возникает из умножения на 10, а 10 = 2 × 5.
Так как в факториале всегда больше двойк, чем пятёрок, нужно только считать количество делений на 5.

2⃣Для каждого i, пока n / 5^i ≥ 1, прибавляем n / 5^i к счётчику нулей.
То есть: n / 5 + n / 25 + n / 125 + ...

3⃣Это решение работает за O(log₅ n) и не требует вычисления самого факториала.

😎 Решение:

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
};

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

Задача: 993. Cousins in Binary Tree
Сложность: easy

Дан корень бинарного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, иначе верните false.

Два узла бинарного дерева являются кузенами, если они находятся на одной глубине и имеют разных родителей.

Обратите внимание, что в бинарном дереве корневой узел находится на глубине 0, а дети каждого узла глубины k находятся на глубине k + 1.

Пример:

Input: root = [1,2,3,4], x = 4, y = 3
Output: false

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

1⃣Поиск глубины и родителя для каждого узла:
Используйте поиск в глубину (DFS) для обхода дерева.
Для каждого узла сохраняйте его глубину и родителя, если значение узла равно x или y.

2⃣Проверка условий на кузенов:
Узлы являются кузенами, если они находятся на одной глубине, но имеют разных родителей.

3⃣Возврат результата:
Если узлы удовлетворяют условиям на кузенов, верните true, иначе верните false.

😎 Решение:

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

class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        TreeNode* parentX = nullptr;
        TreeNode* parentY = nullptr;
        int depthX = -1;
        int depthY = -1;
        
        function<void(TreeNode*, TreeNode*, int)> dfs = [&](TreeNode* node, TreeNode* parent, int depth) {
            if (!node) return;
            if (node->val == x) {
                parentX = parent;
                depthX = depth;
            } else if (node->val == y) {
                parentY = parent;
                depthY = depth;
            } else {
                dfs(node->left, node, depth + 1);
                dfs(node->right, node, depth + 1);
            }
        };
        
        dfs(root, nullptr, 0);
        return depthX == depthY && parentX != parentY;
    }
};

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

Задача: 212. Word Search II
Сложность: hard

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1⃣Построение Trie
Создаём префиксное дерево (Trie) из всех слов из words. Это позволит эффективно проверять, существует ли текущий путь на доске как префикс или полное слово.

2⃣Запуск DFS (Backtracking)
Проходим по каждой ячейке доски. Если символ совпадает с началом одного из слов (т.е. присутствует в Trie), начинаем поиск с помощью backtrack.

3⃣Рекурсивный поиск и ограничения
Рекурсивно исследуем соседние ячейки. Храним найденное слово, как только дойдём до листа в Trie.
Метки:
– заменяем текущий символ board[row][col] на #, чтобы не вернуться в ту же ячейку
– по завершении пути восстанавливаем символ
Также удаляем ветки из Trie, если они больше не нужны (оптимизация).

😎 Решение:

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    string word;

    TrieNode() : word("") {}
};

class Solution {
private:
    vector<vector<char>> board;
    vector<string> result;

public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        TrieNode* root = buildTrie(words);
        this->board = board;

        for (int row = 0; row < board.size(); ++row) {
            for (int col = 0; col < board[0].size(); ++col) {
                if (root->children.find(board[row][col]) != root->children.end()) {
                    backtrack(row, col, root);
                }
            }
        }

        return result;
    }

private:
    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (string& word : words) {
            TrieNode* node = root;
            for (char letter : word) {
                if (node->children.find(letter) == node->children.end()) {
                    node->children[letter] = new TrieNode();
                }
                node = node->children[letter];
            }
            node->word = word;
        }
        return root;
    }

    void backtrack(int row, int col, TrieNode* parent) {
        char letter = board[row][col];
        TrieNode* currNode = parent->children[letter];

        if (!currNode->word.empty()) {
            result.push_back(currNode->word);
            currNode->word.clear(); // предотвращает повтор
        }

        board[row][col] = '#';

        int rowOffset[] = {-1, 0, 1, 0};
        int colOffset[] = {0, 1, 0, -1};
        for (int i = 0; i < 4; ++i) {
            int newRow = row + rowOffset[i];
            int newCol = col + colOffset[i];
            if (newRow >= 0 && newRow < board.size() &&
                newCol >= 0 && newCol < board[0].size()) {
                if (currNode->children.find(board[newRow][newCol]) != currNode->children.end()) {
                    backtrack(newRow, newCol, currNode);
                }
            }
        }

        board[row][col] = letter;

        if (currNode->children.empty()) {
            parent->children.erase(letter);
        }
    }
};

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

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах.

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

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

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

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

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

😎 Решение:

class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        map<int, int> counter;
        for (int e : arr1) counter[e]++;
        for (int e : arr2) counter[e]++;
        for (int e : arr3) counter[e]++;

        vector<int> ans;
        for (const auto& [key, value] : counter) {
            if (value == 3) ans.push_back(key);
        }

        return ans;
    }
};

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

Задача: 199. Binary Tree Right Side View
Сложность: medium

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

Пример:

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

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

1⃣Инициализируем список rightside и две очереди: currLevel (текущий уровень) и nextLevel (следующий уровень). В nextLevel помещаем корень.

2⃣Пока nextLevel не пуста:
– Копируем nextLevel в currLevel, очищаем nextLevel
– Извлекаем все узлы из currLevel, добавляя их дочерние элементы (сначала левые, потом правые) в nextLevel
– Последний обработанный узел на уровне — это тот, что виден справа, добавляем его в rightside

3⃣Возвращаем список rightside.

😎 Решение:

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) return vector<int>();

        deque<TreeNode*> nextLevel{root};
        deque<TreeNode*> currLevel;
        vector<int> rightside;

        TreeNode* node = nullptr;
        while (!nextLevel.empty()) {
            currLevel = nextLevel;
            nextLevel.clear();

            while (!currLevel.empty()) {
                node = currLevel.front();
                currLevel.pop_front();

                if (node->left != nullptr) nextLevel.push_back(node->left);
                if (node->right != nullptr) nextLevel.push_back(node->right);
            }

            if (currLevel.empty()) rightside.push_back(node->val);
        }
        return rightside;
    }
};

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

Задача: 236. Lowest Common Ancestor of a Binary Tree
Сложность: medium

Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве.
Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях.

2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву.

3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q.

😎 Решение:

class Solution {
private:
    TreeNode* ans;

public:
    Solution() {
        this->ans = nullptr;
    }

    bool recurseTree(TreeNode* currentNode, TreeNode* p, TreeNode* q) {
        if (currentNode == nullptr) {
            return false;
        }

        int left = this->recurseTree(currentNode->left, p, q) ? 1 : 0;
        int right = this->recurseTree(currentNode->right, p, q) ? 1 : 0;
        int mid = (currentNode == p || currentNode == q) ? 1 : 0;

        if (mid + left + right >= 2) {
            this->ans = currentNode;
        }

        return (mid + left + right > 0);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        this->recurseTree(root, p, q);
        return this->ans;
    }
};

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

Задача: 1672. Richest Customer Wealth
Сложность: easy

Вам дан целочисленный массив размером m x n под названием accounts, где accounts[i][j] — это сумма денег, которую i-й клиент имеет в j-м банке. Верните богатство самого богатого клиента.

Богатство клиента — это сумма денег, которую он имеет во всех своих банковских счетах. Самый богатый клиент — это клиент, который имеет максимальное богатство.

Пример:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

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

1⃣Пройдите по всем клиентам в массиве accounts.

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

3⃣Если текущее богатство больше максимального, обновите максимальное значение. Верните максимальное богатство.

😎 Решение:

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int maxWealthSoFar = 0;
        
        for (const auto& account : accounts) {
            int currCustomerWealth = accumulate(account.begin(), account.end(), 0);
            maxWealthSoFar = max(maxWealthSoFar, currCustomerWealth);
        }
        
        return maxWealthSoFar;
    }
};

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

Задача: 62. Unique Paths
Сложность: medium

Робот двигается в сетке m x n только вправо или вниз, начиная с (0, 0) и заканчивая в (m - 1, n - 1).
Нужно вернуть количество уникальных путей от начала до конца.

Пример:

Input: m = 3, n = 7 Output: 28

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

1⃣Инициализировать 2D-массив d[m][n], заполненный единицами — так как в первой строке и столбце всегда только один путь

2⃣Пройти по всем ячейкам начиная со второй строки и второго столбца:
d[i][j] = d[i-1][j] + d[i][j-1]

3⃣Вернуть d[m-1][n-1] — общее количество путей

😎 Решение:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> d(m, vector<int>(n, 1));
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                d[i][j] = d[i - 1][j] + d[i][j - 1];
            }
        }
        return d[m - 1][n - 1];
    }
};

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

2⃣На каждом шаге добавляйте наименьшее доступное значение в выходной список.

3⃣Верните выходной список.

😎 Решение:

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

class Solution {
public:
    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode*> stack1, stack2;
        vector<int> output;

        while (root1 || root2 || !stack1.empty() || !stack2.empty()) {
            while (root1) {
                stack1.push(root1);
                root1 = root1->left;
            }
            while (root2) {
                stack2.push(root2);
                root2 = root2->left;
            }
            if (stack2.empty() || (!stack1.empty() && stack1.top()->val <= stack2.top()->val)) {
                root1 = stack1.top();
                stack1.pop();
                output.push_back(root1->val);
                root1 = root1->right;
            } else {
                root2 = stack2.top();
                stack2.pop();
                output.push_back(root2->val);
                root2 = root2->right;
            }
        }
        return output;
    }
};

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

Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

class Solution {
public:
    bool isSubsequence(const string& x, const string& y) {
        int j = 0;
        for (int i = 0; i < y.size() && j < x.size(); ++i) {
            if (x[j] == y[i]) {
                ++j;
            }
        }
        return j == x.size();
    }

    string findLongestWord(string s, vector<string>& d) {
        string max_str = "";
        for (const string& str : d) {
            if (isSubsequence(str, s)) {
                if (str.size() > max_str.size() || (str.size() == max_str.size() && str < max_str)) {
                    max_str = str;
                }
            }
        }
        return max_str;
    }
};

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

Задача: 207. Course Schedule
Сложность: medium

У вас есть numCourses курсов, пронумерованных от 0 до numCourses - 1, и массив prerequisites, где prerequisites[i] = [ai, bi] означает, что курс ai требует предварительного прохождения курса bi.

Нужно вернуть true, если можно пройти все курсы, иначе — false.

Пример:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true

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

1⃣Построить граф зависимостей:
Создаем список смежности adj и массив входящих степеней indegree, чтобы отразить зависимости между курсами.

2⃣Найти стартовые узлы и запустить BFS:
Добавляем в очередь все курсы с indegree == 0 (те, которые можно взять сразу). Проходим в ширину по графу, уменьшая indegree зависимых курсов.

3⃣Проверка количества завершенных курсов:
Если количество завершённых курсов (nodesVisited) совпадает с numCourses, возвращаем true, иначе false. Это означает, что в графе нет циклов, мешающих прохождению.

😎 Решение:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses);
        vector<vector<int>> adj(numCourses);
        for (auto prerequisite : prerequisites) {
            adj[prerequisite[1]].push_back(prerequisite[0]);
            indegree[prerequisite[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int nodesVisited = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            nodesVisited++;

            for (auto& neighbor : adj[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return nodesVisited == numCourses;
    }
};

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