Задача: 760. Find Anagram Mappings
Сложность: easy

Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a.

Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

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

1⃣Создайте словарь для хранения индексов элементов в nums2.

2⃣Пройдите по элементам массива nums1 и для каждого элемента найдите соответствующий индекс в nums2, используя словарь.

3⃣Верните массив индексов.

😎 Решение:

vector<int> anagramMapping(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, vector<int>> indexMap;
    for (int i = 0; i < nums2.size(); i++) {
        indexMap[nums2[i]].push_back(i);
    }
    
    vector<int> mapping;
    for (int num : nums1) {
        mapping.push_back(indexMap[num].back());
        indexMap[num].pop_back();
    }
    
    return mapping;
}

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

Задача: 1344. Angle Between Hands of a Clock
Сложность: medium

Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками.

Ответы с точностью до 10^-5 от фактического значения будут считаться правильными.

Пример:

Input: hour = 12, minutes = 30
Output: 165

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

1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30.

2⃣Найти разницу: diff = abs(hour_angle - minutes_angle).

3⃣Вернуть меньший угол: min(diff, 360 - diff).

😎 Решение:

class Solution {
public:
    double angleClock(int hour, int minutes) {
        int oneMinAngle = 6;
        int oneHourAngle = 30;

        double minutesAngle = oneMinAngle * minutes;
        double hourAngle = (hour % 12 + minutes / 60.0) * oneHourAngle;

        double diff = abs(hourAngle - minutesAngle);
        return min(diff, 360 - diff);
    }
};

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

Задача: 912. Sort an Array
Сложность: medium

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

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

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

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

2⃣Разделить массив на две половины.
Рекурсивно отсортировать каждую половину.

3⃣Слить две отсортированные половины.

😎 Решение:

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> left_half(nums.begin() + left, nums.begin() + mid + 1);
    vector<int> right_half(nums.begin() + mid + 1, nums.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < left_half.size() && j < right_half.size()) {
        if (left_half[i] <= right_half[j]) {
            nums[k++] = left_half[i++];
        } else {
            nums[k++] = right_half[j++];
        }
    }

    while (i < left_half.size()) {
        nums[k++] = left_half[i++];
    }

    while (j < right_half.size()) {
        nums[k++] = right_half[j++];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

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

Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium

Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.

Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.

Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1.

Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

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

1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1.

2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0.

3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:

Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
Верните numberOfConnectedComponents - 1.

😎 Решение:

class Solution {
public:
    void dfs(int node, unordered_map<int, vector<int>>& adj, vector<bool>& visit) {
        visit[node] = true;
        if (adj.find(node) == adj.end()) {
            return;
        }
        for (int neighbor : adj[node]) {
            if (!visit[neighbor]) {
                visit[neighbor] = true;
                dfs(neighbor, adj, visit);
            }
        }
    }

    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) {
            return -1;
        }

        unordered_map<int, vector<int>> adj;
        for (auto& connection : connections) {
            adj[connection[0]].push_back(connection[1]);
            adj[connection[1]].push_back(connection[0]);
        }

        int numberOfConnectedComponents = 0;
        vector<bool> visit(n, false);
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                numberOfConnectedComponents++;
                dfs(i, adj, visit);
            }
        }

        return numberOfConnectedComponents - 1;
    }
};

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

Задача: 1094. Car Pooling
Сложность: medium

Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).

Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.

Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае.

Пример:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity.

2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени.

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

😎 Решение:

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

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        map<int, int> timestamp;
        for (auto& trip : trips) {
            timestamp[trip[1]] += trip[0];
            timestamp[trip[2]] -= trip[0];
        }
        int usedCapacity = 0;
        for (auto& change : timestamp) {
            usedCapacity += change.second;
            if (usedCapacity > capacity) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium

Дан массив preorder, содержащий уникальные целые числа.
Нужно определить, может ли данный массив представлять собой префиксный (preorder) обход бинарного дерева поиска (BST).

Пример:

Input: preorder = [5,2,1,3,6] Output: true

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

1⃣Инициализация
Объявляем переменную minLimit = -∞ (используем INT_MIN) и создаём стек stack, в котором будем хранить предков текущего узла.

2⃣Обход массива
Для каждого числа num в preorder:
– Если stack.top() < num, значит, мы поднимаемся по дереву вправо, поэтому извлекаем все такие элементы из стека и обновляем minLimit.
– Если num <= minLimit, это значит, что текущий элемент нарушает свойства BST — возвращаем false.
– Иначе, помещаем num в стек.

3⃣Результат
Если весь массив обработан без нарушений — возвращаем true.

😎 Решение:

#include <vector>
#include <stack>
#include <limits.h>

using namespace std;

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int minLimit = INT_MIN;
        stack<int> stack;

        for (int num : preorder) {
            while (!stack.empty() && stack.top() < num) {
                minLimit = stack.top();
                stack.pop();
            }

            if (num <= minLimit) {
                return false;
            }

            stack.push(num);
        }

        return true;
    }
};

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

Задача: 78. Subsets
Сложность: medium

Дан массив целых чисел nums, содержащий уникальные элементы.
Верните все возможные подмножества (степенной набор).
Результат не должен содержать повторяющихся подмножеств и может быть в любом порядке.

Пример:

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

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

1⃣Определим функцию backtrack(first, curr), где
first — индекс, с которого начинаем выбирать элементы,
curr — текущее подмножество.

2⃣Если curr.size() == k, добавляем его копию в итог output.

3⃣Перебираем индексы i от first до n, добавляем nums[i] в curr,
вызываем backtrack(i + 1, curr), затем удаляем nums[i].

😎 Решение:

class Solution {
public:
    vector<vector<int>> output;
    int n, k;

    void backtrack(int first, vector<int> curr, vector<int>& nums) {
        if (curr.size() == k) output.push_back(curr);
        for (int i = first; i < n; ++i) {
            curr.push_back(nums[i]);
            backtrack(i + 1, curr, nums);
            curr.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        for (k = 0; k < n + 1; ++k) {
            vector<int> curr;
            backtrack(0, curr, nums);
        }
        return output;
    }
};

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

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

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