Задача: 1134. Armstrong Number
Сложность: easy

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

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

1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину.

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣ Верните true, если результат равен исходному числу n.

😎 Решение:

class Solution {
public:
    int getSumOfKthPowerOfDigits(int n, int k) {
        int result = 0;
        while (n != 0) {
            int digit = n % 10;
            result += pow(digit, k);
            n /= 10;
        }
        return result;
    }

    bool isArmstrong(int n) {
        int length = to_string(n).length();
        return getSumOfKthPowerOfDigits(n, length) == n;
    }
};

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

Задача: 945. Minimum Increment to Make Array Unique
Сложность: medium

Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: nums = [1,2,2]
Output: 1

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

1⃣Отсортировать массив nums.
Инициализировать переменную moves для подсчета количества ходов.

2⃣Пройти по массиву и для каждого элемента, начиная со второго:
Если текущий элемент меньше или равен предыдущему элементу, увеличить текущий элемент до значения предыдущего элемента + 1 и обновить счетчик ходов.

3⃣Вернуть общее количество ходов.

😎 Решение:

class Solution {
public:
    int minIncrementForUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int moves = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] <= nums[i - 1]) {
                moves += nums[i - 1] + 1 - nums[i];
                nums[i] = nums[i - 1] + 1;
            }
        }
        return moves;
    }
};

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int shiftAndCount(int xShift, int yShift, vector<vector<int>>& M, vector<vector<int>>& R) {
        int leftShiftCount = 0, rightShiftCount = 0;
        int rRow = 0;
        for (int mRow = yShift; mRow < M.size(); ++mRow) {
            int rCol = 0;
            for (int mCol = xShift; mCol < M.size(); ++mCol) {
                if (M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol])
                    leftShiftCount++;
                if (M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol])
                    rightShiftCount++;
                rCol++;
            }
            rRow++;
        }
        return max(leftShiftCount, rightShiftCount);
    }

    int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
        int maxOverlaps = 0;
        for (int yShift = 0; yShift < A.size(); ++yShift) {
            for (int xShift = 0; xShift < A.size(); ++xShift) {
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B));
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A));
            }
        }
        return maxOverlaps;
    }
};

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

Задача: 690. Employee Importance
Сложность: medium

У вас есть структура данных с информацией о сотрудниках, включая уникальный идентификатор сотрудника, значение его важности и идентификаторы его прямых подчиненных.

Вам дан массив сотрудников employees, где:

employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.

Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

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

1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.

2⃣Реализуйте функцию DFS для подсчета общей важности, которая включает важность сотрудника и всех его подчиненных.

3⃣Используйте DFS для вычисления общей важности, начиная с заданного идентификатора сотрудника.

😎 Решение:

class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};

class Solution {
    unordered_map<int, Employee*> emap;
    
public:
    int getImportance(vector<Employee*> employees, int queryid) {
        for (Employee* e : employees) {
            emap[e->id] = e;
        }
        return dfs(queryid);
    }
    
    int dfs(int eid) {
        Employee* employee = emap[eid];
        int ans = employee->importance;
        for (int subid : employee->subordinates) {
            ans += dfs(subid);
        }
        return ans;
    }
};

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

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

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