C/C++ | LeetCode

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

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

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

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

Искусственный интеллект помогает больше продавать Битрикс24 CRM + Ai упрощает работу менеджера. Расшифровывает записи звонков клиентам и сам заполняет карточку сделки. Менеджер в это время уже звонит следующему клиенту. Попробуйте умную CRM Попробовать #реклама 16+ bitrix24.ru О рекламодателе

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

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

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

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

Онлайн-магистратура Кибербезопасность от Яндекса и МИФИ День открытых дверей 23 апреля в 19:00 мск | Онлайн Эксперты Яндекса и НИЯУ МИФИ расскажут об очной онлайн-магистратуре для карьеры в IT. Всё о поступлении и обучении, выступления экспертов, ответы на вопросы. Выбирайте всё: работу и учёбу, навыки и диплом магистра. Узнать больше #реклама 16+ practicum.yandex.ru О рекламодателе

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

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

📅 Осталось 7 дней до конца краудфандинга Мы на финишной прямой! Если ты планировал присоединиться, но ещё не успел, сейчас идеальный момент. Вознаграждения за поддержку: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование 👉 Поддержать easyoffer 2.0 Не откладывай на последний момент 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

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

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

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

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

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

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

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

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

Классный обучающий канал по C++ C++ Learning

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

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

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

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

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