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

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

Задача: 1244. Design A Leaderboard
Сложность: medium

Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста.

Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

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

1⃣addScore(playerId, score):
Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение.
Если игрок не существует, добавляем его с заданным счетом.

2⃣top(K):
Сортируем игроков по их счету в порядке убывания.
Возвращаем сумму очков K лучших игроков.

3⃣reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Leaderboard {
private:
    std::unordered_map<int, int> scores;

public:
    Leaderboard() {}

    void addScore(int playerId, int score) {
        scores[playerId] += score;
    }

    int top(int K) {
        std::vector<int> all_scores;
        for (auto& [playerId, score] : scores) {
            all_scores.push_back(score);
        }
        std::sort(all_scores.rbegin(), all_scores.rend());
        int sum = 0;
        for (int i = 0; i < K && i < all_scores.size(); ++i) {
            sum += all_scores[i];
        }
        return sum;
    }

    void reset(int playerId) {
        scores[playerId] = 0;
    }
};

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

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

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

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int maxCandies = *max_element(candies.begin(), candies.end());
        vector<bool> result;
        for (int candy : candies) {
            result.push_back(candy + extraCandies >= maxCandies);
        }
        return result;
    }
};

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

Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

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

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

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

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

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

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        const int MOD = 1'000'000'007;
        priority_queue<pair<int, int>> buyOrders;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> sellOrders;

        for (const auto& order : orders) {
            int price = order[0], amount = order[1], orderType = order[2];
            auto& primaryQueue = orderType == 0 ? sellOrders : buyOrders;
            auto& secondaryQueue = orderType == 0 ? buyOrders : sellOrders;

            while (amount > 0 && !primaryQueue.empty() &&
                  (orderType == 0 ? primaryQueue.top().first <= price : primaryQueue.top().first >= price)) {
                auto [topPrice, topAmount] = primaryQueue.top();
                primaryQueue.pop();
                int executedAmount = min(amount, topAmount);
                amount -= executedAmount;
                if (topAmount > executedAmount)
                    primaryQueue.emplace(topPrice, topAmount - executedAmount);
            }
            if (amount > 0)
                secondaryQueue.emplace(price, amount);
        }

        auto countTotalOrders = [](auto& queue) {
            long long total = 0;
            while (!queue.empty()) {
                total = (total + queue.top().second) % MOD;
                queue.pop();
            }
            return total;
        };

        return (countTotalOrders(buyOrders) + countTotalOrders(sellOrders)) % MOD;
    }
};

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int evenCount = 0;
        int oddCount = 0;
        
        for (int pos : position) {
            if (pos % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        
        return min(evenCount, oddCount);
    }
};

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

Задача: 780. Reaching Points
Сложность: hard

Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false.

Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y).

Пример:

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

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

1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}.

2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно.

3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy.

😎 Решение:

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) return true;
            if (tx > ty) {
                tx -= ty;
            } else {
                ty -= tx;
            }
        }
        return false;
    }
};

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

🚨 60 минут до финала

Через час мы закроем краудфандинг easyoffer 2.0
Это последний шанс вписаться в самые выгодные условия.

👉 https://planeta.ru/campaigns/easyoffer

Задача: 240. Search a 2D Matrix II
Сложность: medium

Целые числа в каждой строке отсортированы по возрастанию слева направо
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

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

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

2⃣Для каждой позиции i ищем target сначала по строке, затем по столбцу, начиная с i-й строки и i-го столбца

3⃣Если target найден хотя бы в одном из направлений, возвращаем true, иначе false

😎 Решение:

class Solution {
public:
    bool binarySearch(vector<vector<int>>& matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].size() - 1 : matrix.size() - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            if (vertical) {
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else {
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int shorterDim = min(matrix.size(), matrix[0].size());
        for (int i = 0; i < shorterDim; i++) {
            if (binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
};

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