Задача: 1110. Delete Nodes And Return Forest
Сложность: medium

Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).

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

Пример:

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

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

1⃣Инициализация:
Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска.
Создайте пустой список forest для хранения корней деревьев в результирующем лесу.

2⃣Рекурсивный обход:
Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node):
- рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением.

3⃣Оценка узла:
Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить:
- если у узла есть левый или правый дочерний узел, добавьте их в forest.
- верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу.
Если узел не нужно удалять, верните сам узел.

😎 Решение:

class Solution {
    fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
        val toDeleteSet = to_delete.toSet()
        val forest = mutableListOf<TreeNode?>()

        fun processNode(node: TreeNode?): TreeNode? {
            if (node == null) return null

            node.left = processNode(node.left)
            node.right = processNode(node.right)

            if (toDeleteSet.contains(node.`val`)) {
                node.left?.let { forest.add(it) }
                node.right?.let { forest.add(it) }
                return null
            }
            return node
        }

        val root = processNode(root)
        if (root != null) forest.add(root)

        return forest
    }
}

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

Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎 Решение:

using namespace std;

class MyHeapNode {
public:
    int row;
    int column;
    int value;

    MyHeapNode(int v, int r, int c) : value(v), row(r), column(c) {}
};

class MyHeapComparator {
public:
    bool operator()(const MyHeapNode& x, const MyHeapNode& y) const {
        return x.value > y.value;
    }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int N = matrix.size();

        priority_queue<MyHeapNode, vector<MyHeapNode>, MyHeapComparator> minHeap;

        for (int r = 0; r < min(N, k); r++) {
            minHeap.push(MyHeapNode(matrix[r][0], r, 0));
        }

        MyHeapNode element = minHeap.top();
        while (k-- > 0) {
            element = minHeap.top();
            minHeap.pop();
            int r = element.row, c = element.column;

            if (c < N - 1) {
                minHeap.push(MyHeapNode(matrix[r][c + 1], r, c + 1));
            }
        }

        return element.value;
    }
};

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

Задача: 1469. Find All The Lonely Nodes
Сложность: easy

В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.

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

Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

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

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎 Решение:

#include <vector>
using namespace std;

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

class Solution {
public:
    void DFS(TreeNode* root, bool isLonely, vector<int>& ans) {
        if (root == NULL) {
            return;
        }
        
        if (isLonely) {
            ans.push_back(root->val);
        }
        
        DFS(root->left, root->right == NULL, ans);
        DFS(root->right, root->left == NULL, ans);
    }
    
    vector<int> getLonelyNodes(TreeNode* root) {
        vector<int> ans;
        DFS(root, false, ans);
        return ans;
    }
};

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

Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard

Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.

Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.

Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга.

Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.

Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

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

1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.

2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.

3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.

😎 Решение:

class Solution {
    vector<vector<int>> memo;
    int done;
    int n;
    const int MOD = 1000000007;
    unordered_map<int, vector<int>> hatsToPeople;
    
public:
    int numberWays(vector<vector<int>>& hats) {
        n = hats.size();
        
        for (int i = 0; i < n; i++) {
            for (int hat: hats[i]) {
                hatsToPeople[hat].push_back(i);
            }
        }
        
        done = (1 << n) - 1;
        memo = vector<vector<int>>(41, vector<int>(done, -1));
        
        return dp(1, 0);
    }
    
private:
    int dp(int hat, int mask) {
        if (mask == done) {
            return 1;
        }
        
        if (hat > 40) {
            return 0;
        }
        
        if (memo[hat][mask] != -1) {
            return memo[hat][mask];
        }
        
        int ans = dp(hat + 1, mask);
        
        if (hatsToPeople.count(hat)) {
            for (int person: hatsToPeople[hat]) {
                if ((mask & (1 << person)) == 0) {
                    ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD;
                }
            }
        }
        
        memo[hat][mask] = ans;
        return ans;
    }
};

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

Задача: 776. Split BST
Сложность: medium

Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.

Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.

Верните массив из двух корней двух поддеревьев в порядке.

Пример:

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

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

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

2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

😎 Решение:

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

class Solution {
public:
    vector<TreeNode*> splitBST(TreeNode* root, int target) {
        if (!root) {
            return {nullptr, nullptr};
        }

        if (root->val > target) {
            auto left = splitBST(root->left, target);
            root->left = left[1];
            return {left[0], root};
        } else {
            auto right = splitBST(root->right, target);
            root->right = right[0];
            return {root, right[1]};
        }
    }
};

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

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

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        vector<unordered_set<int>> components;
        unordered_set<int> visited;
        
        auto dfs = [&](int node) {
            stack<int> stk;
            stk.push(node);
            unordered_set<int> component;
            while (!stk.empty()) {
                int u = stk.top();
                stk.pop();
                if (!visited.count(u)) {
                    visited.insert(u);
                    component.insert(u);
                    for (int v = 0; v < n; ++v) {
                        if (graph[u][v] == 1 && !visited.count(v)) {
                            stk.push(v);
                        }
                    }
                }
            }
            components.push_back(component);
        };
        
        for (int i = 0; i < n; ++i) {
            if (!visited.count(i)) {
                dfs(i);
            }
        }
        
        vector<int> infectedInComponent(components.size(), 0);
        vector<int> nodeToComponent(n, -1);
        
        for (int i = 0; i < components.size(); ++i) {
            for (int node : components[i]) {
                nodeToComponent[node] = i;
                if (find(initial.begin(), initial.end(), node) != initial.end()) {
                    infectedInComponent[i]++;
                }
            }
        }
        
        int minInfected = INT_MAX;
        int resultNode = *min_element(initial.begin(), initial.end());
        
        for (int node : initial) {
            int componentIdx = nodeToComponent[node];
            if (infectedInComponent[componentIdx] == 1) {
                int componentSize = components[componentIdx].size();
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize;
                    resultNode = node;
                }
            }
        }
        
        return resultNode;
    }
};

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

2⃣Поиск максимальной суммы:
Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

class Solution {
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums, secondLen, firstLen));
    }
    
private:
    int maxSumNonOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        vector<int> max_first(n, 0);
        for (int i = firstLen - 1; i < n; ++i) {
            max_first[i] = max((i > 0 ? max_first[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
        }
        
        vector<int> max_second(n, 0);
        for (int i = secondLen - 1; i < n; ++i) {
            max_second[i] = max((i > 0 ? max_second[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
        }
        
        int max_sum = 0;
        for (int i = firstLen + secondLen - 1; i < n; ++i) {
            max_sum = max(max_sum, max_first[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
        }
        
        return max_sum;
    }
};

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

Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

Дано бинарное дерево, такое что каждый узел содержит дополнительный случайный указатель, который может указывать на любой узел в дереве или быть null.
Верните глубокую копию дерева.

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

2⃣Сопоставление случайных указателей:
Создайте функцию mapRandomPointers(oldNode), которая принимает корень старого дерева и рекурсивно сопоставляет случайные указатели нового дерева с соответствующими узлами старого дерева, используя хэш-таблицу newOldPairs.

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* random;

    Node(int _val) {
        val = _val;
        left = nullptr;
        right = nullptr;
        random = nullptr;
    }
};

class NodeCopy {
public:
    int val;
    NodeCopy* left;
    NodeCopy* right;
    NodeCopy* random;

    NodeCopy(int _val) {
        val = _val;
        left = nullptr;
        right = nullptr;
        random = nullptr;
    }
};

class Solution {
    unordered_map<Node*, NodeCopy*> newOldPairs;

    NodeCopy* deepCopy(Node* root) {
        if (!root) return nullptr;
        NodeCopy* newRoot = new NodeCopy(root->val);
        newRoot->left = deepCopy(root->left);
        newRoot->right = deepCopy(root->right);
        newOldPairs[root] = newRoot;
        return newRoot;
    }

    void mapRandomPointers(Node* oldNode) {
        if (!oldNode) return;
        NodeCopy* newNode = newOldPairs[oldNode];
        if (newNode) {
            newNode->random = newOldPairs[oldNode->random];
            mapRandomPointers(oldNode->left);
            mapRandomPointers(oldNode->right);
        }
    }

public:
    NodeCopy* copyRandomBinaryTree(Node* root) {
        NodeCopy* newRoot = deepCopy(root);
        mapRandomPointers(root);
        return newRoot;
    }
};

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

Задача: 334. Increasing Triplet Subsequence
Сложность: medium

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

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

1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.

2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.

3⃣Возврат результата:
Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false.

😎 Решение:

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int first_num = INT_MAX;
        int second_num = INT_MAX;
        
        for (int n : nums) {
            if (n <= first_num) {
                first_num = n;
            } else if (n <= second_num) {
                second_num = n;
            } else {
                return true;
            }
        }
        return false;
    }
};

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

Задача: №29. Divide Two Integers
Сложность: medium

Учитывая два целых числа dividend и divisor, выполните целочисленное деление без использования операторов *, / и %. Округление результата должно быть в сторону нуля. Если результат выходит за пределы 32-битного диапазона знаковых целых чисел — верните INT_MAX или INT_MIN.

Пример:

Input: dividend = 10, divisor = 3 Output: 3

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

1⃣Выполняем деление как есть, используя dividend / divisor, но предварительно кастуем к long long, чтобы избежать переполнения.

2⃣Проверяем результат: если он превышает диапазон [-2^31, 2^31 - 1], возвращаем соответствующую границу.

3⃣Возвращаем результат, округлённый к нулю.

😎 Решение:

class Solution {
public:
  int divide(int dividend, int divisor) {
    long long result = (long long)dividend / divisor;

    if(result > INT_MAX) return INT_MAX;
    if(result < INT_MIN) return INT_MIN;

    return result;
  }
};

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

Задача: 250. Count Univalue Subtrees
Сложность: medium

Пример:

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

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

1⃣Обход в глубину (DFS): для каждого узла рекурсивно определяем, является ли его левое и правое поддерево "однотипным" (все значения одинаковы).

2⃣Проверка значений: если левое и правое поддерево являются однотипными, дополнительно проверяем, совпадают ли значения дочерних узлов с текущим значением.

3⃣Подсчет: если все условия выполнены — увеличиваем счетчик и возвращаем true, иначе — false.

😎 Решение:

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

class Solution {
public:
    int count = 0;

    bool dfs(TreeNode* node) {
        if (node == nullptr) {
            return true;
        }

        bool isLeftUniValue = dfs(node->left);
        bool isRightUniValue = dfs(node->right);

        if (isLeftUniValue && isRightUniValue) {
            if (node->left != nullptr && node->left->val != node->val) {
                return false;
            }
            if (node->right != nullptr && node->right->val != node->val) {
                return false;
            }
            count++;
            return true;
        }
        return false;
    }

    int countUnivalSubtrees(TreeNode* root) {
        dfs(root);
        return count;
    }
};

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

Задача: 348. Design Tic-Tac-Toe
Сложность: medium

Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:

Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:

TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.

Пример:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

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

1⃣Инициализация:
Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно.
Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно.
Инициализируйте размер доски n.

2⃣Выполнение хода:
Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода.
Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal.

3⃣Проверка победы:
Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя.
Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода.

😎 Решение:

class TicTacToe {
public:
    TicTacToe(int n) : n(n), rows(n, 0), cols(n, 0), diagonal(0), antiDiagonal(0) {}
    
    int move(int row, int col, int player) {
        int add = (player == 1) ? 1 : -1;
        rows[row] += add;
        cols[col] += add;
        if (row == col) {
            diagonal += add;
        }
        if (row + col == n - 1) {
            antiDiagonal += add;
        }
        if (abs(rows[row]) == n || abs(cols[col]) == n || abs(diagonal) == n || abs(antiDiagonal) == n) {
            return player;
        }
        return 0;
    }

private:
    int n;
    vector<int> rows;
    vector<int> cols;
    int diagonal;
    int antiDiagonal;
};

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

Задача: 495. Teemo Attacking
Сложность: easy

Наш герой Тимо атакует врага Эшу ядовитыми атаками! Когда Тимо атакует Эшу, она оказывается отравленной на ровно duration секунд. Более формально, атака в секунду t означает, что Эша будет отравлена в течение интервала времени [t, t + duration - 1] включительно. Если Тимо атакует снова до окончания эффекта яда, таймер для него сбрасывается, и эффект яда закончится через duration секунд после новой атаки.

Вам дано неубывающее целое число timeSeries, где timeSeries[i] обозначает, что Тимо атакует Эшу во вторую timeSeries[i], и целое число duration.
Верните общее количество секунд, в течение которых Эша была отравлена.

Пример:

Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

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

1⃣Инициализация
Инициализируйте переменную total для хранения общего времени, в течение которого Эша была отравлена. Проверьте, если массив timeSeries пуст, верните 0.

2⃣Итерация
Пройдите по всем элементам массива timeSeries, кроме последнего. На каждой итерации добавьте к total минимальное значение между длительностью интервала и временем действия яда duration.

3⃣Возврат результата
Верните сумму total и duration, чтобы учесть последнюю атаку.

😎 Решение:

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size();
        if (n == 0) return 0;

        int total = 0;
        for (int i = 0; i < n - 1; ++i) {
            total += min(timeSeries[i + 1] - timeSeries[i], duration);
        }
        return total + duration;
    }
};

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

Задача: 1480. Running Sum of 1d Array
Сложность: easy

Дан массив nums. Мы определяем текущую сумму массива как runningSum[i] = сумма(nums[0]…nums[i]).

Верните массив текущих сумм для nums.

Пример:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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

1⃣Инициализация:
Определите массив result.
Инициализируйте первый элемент массива result первым элементом входного массива nums.

2⃣Вычисление текущих сумм:
На индексе i добавьте сумму элемента nums[i] и предыдущей текущей суммы result[i - 1] в массив result.

3⃣Повторение для всех индексов:
Повторите шаг 2 для всех индексов от 1 до n-1.

😎 Решение:

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        vector<int> result(nums.size());
        result[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            result[i] = result[i - 1] + nums[i];
        }
        return result;
    }
};

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

Задача: 687. Longest Univalue Path
Сложность: medium

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

Длина пути между двумя узлами представлена количеством рёбер между ними.

Пример:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

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

1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.

2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.

3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..

😎 Решение:

class Solution {
public:
    int ans = 0;

    int solve(TreeNode* root, int parent) {
        if (root == nullptr) {
            return 0;
        }

        int left = solve(root->left, root->val);
        int right = solve(root->right, root->val);
        
        ans = std::max(ans, left + right);
        
        return root->val == parent ? std::max(left, right) + 1 : 0;
    }

    int longestUnivaluePath(TreeNode* root) {
        solve(root, -1);
        return ans;
    }
};

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

Задача: 506. Relative Ranks
Сложность: easy

Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны.
Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг:
Ранг спортсмена, занявшего 1-е место, — "Gold Medal".
Ранг спортсмена, занявшего 2-е место, — "Silver Medal".
Ранг спортсмена, занявшего 3-е место, — "Bronze Medal".
Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x").
Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена.

Пример:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

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

1⃣Инициализация и нахождение максимального значения
Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score.

2⃣Создание вспомогательных структур
Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]].

3⃣Присваивание рангов и формирование ответа
Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего.

😎 Решение:

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        int N = score.size();
        int maxScore = *max_element(score.begin(), score.end());
        vector<int> scoreToIndex(maxScore + 1, 0);
        
        for (int i = 0; i < N; i++) {
            scoreToIndex[score[i]] = i + 1;
        }
        
        vector<string> rank(N);
        vector<string> MEDALS = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        int place = 1;
        
        for (int i = maxScore; i >= 0; i--) {
            if (scoreToIndex[i] != 0) {
                int originalIndex = scoreToIndex[i] - 1;
                if (place < 4) {
                    rank[originalIndex] = MEDALS[place - 1];
                } else {
                    rank[originalIndex] = to_string(place);
                }
                place++;
            }
        }
        
        return rank;
    }
};

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

Задача: 1473. Paint House III
Сложность: hard

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

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

1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.

2⃣Рекурсивное вычисление минимальной стоимости:
Если дом уже покрашен, обновите количество соседств и вызовите рекурсивный метод для следующего дома.
Если дом не покрашен, попробуйте покрасить его в каждый возможный цвет, обновите количество соседств и вызовите рекурсивный метод для следующего дома. Храните минимальную стоимость.

3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎 Решение:

class Solution {
public:
    int memo[100][100][21];
    const int MAX_COST = 1000001;
    
    int findMinCost(vector<int>& houses, vector<vector<int>>& cost, int targetCount, int currIndex, int neighborhoodCount, int prevHouseColor) {
        if (currIndex == houses.size()) {
            return neighborhoodCount == targetCount ? 0 : MAX_COST;
        }
        
        if (neighborhoodCount > targetCount) {
            return MAX_COST;
        }
        
        if (memo[currIndex][neighborhoodCount][prevHouseColor] != -1) {
            return memo[currIndex][neighborhoodCount][prevHouseColor];
        }
        
        int minCost = MAX_COST;

        if (houses[currIndex] != 0) {
            int newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0);
            minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
        } else {
            int totalColors = cost[0].size();
            for (int color = 1; color <= totalColors; ++color) {
                int newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0);
                int currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
                minCost = min(minCost, currCost);
            }
        }
        
        return memo[currIndex][neighborhoodCount][prevHouseColor] = minCost;
    }
    
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        memset(memo, -1, sizeof(memo));
        int answer = findMinCost(houses, cost, target, 0, 0, 0);
        return answer == MAX_COST ? -1 : answer;
    }
};

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

Задача: 330. Patching Array
Сложность: hard

Дан отсортированный массив целых чисел nums и целое число n. Добавьте/дополните элементы в массив таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть сформировано как сумма некоторых элементов массива.
Верните минимальное количество дополнений, необходимых для этого.

Пример:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

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

1⃣Инициализация переменных:
Создайте переменную miss, представляющую наименьшее пропущенное число, которое еще не покрыто, и установите ее значение на 1. Создайте переменную patches для подсчета необходимых дополнений и переменную i для итерации по массиву nums.

2⃣Основной цикл:
Используйте цикл while, который будет выполняться до тех пор, пока miss не станет больше n.
Внутри цикла проверьте, покрывает ли текущий элемент nums[i] значение miss. Если да, добавьте nums[i] к miss и увеличьте i. Если нет, добавьте значение miss к самому себе (это означает добавление нового элемента в массив) и увеличьте счетчик patches.

3⃣Возврат результата:
После завершения цикла верните значение patches, которое представляет минимальное количество необходимых дополнений.

😎 Решение:

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int patches = 0, i = 0;
        long miss = 1;
        while (miss <= n) {
            if (i < nums.size() && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
};

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

Задача: 85. Maximal Rectangle
Сложность: hard

Дана бинарная матрица размера rows x cols, заполненная '0' и '1'.
Найдите наибольший прямоугольник, содержащий только '1', и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6

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

1⃣Для каждой строки i считаем количество подряд идущих '1' слева от текущей ячейки,
т.е. если matrix[i][j] == '1', то dp[i][j] = dp[i][j-1] + 1 (иначе 0).

2⃣Для каждой единицы на позиции (i,j) идём вверх по столбцу,
накапливая минимальную ширину width,
и вычисляем площадь текущего прямоугольника width * высота, обновляя максимум.

3⃣Повторяем для всех ячеек, возвращаем наибольшую найденную площадь.

😎 Решение:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.size() == 0) return 0;
        int maxarea = 0;
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));

        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
                    int width = dp[i][j];
                    for (int k = i; k >= 0; k--) {
                        width = std::min(width, dp[k][j]);
                        maxarea = std::max(maxarea, width * (i - k + 1));
                    }
                }
            }
        }
        return maxarea;
    }
};

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

Задача: 34. Find First and Last Position of Element in Sorted Array
Сложность: medium

Учитывая отсортированный по не убыванию массив целых чисел nums, необходимо найти начальную и конечную позиции заданного значения target. Если значение не найдено, вернуть [-1, -1]. Алгоритм должен работать за O(log n).

Пример:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

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

1⃣Используем lower_bound для нахождения первого вхождения target.

2⃣Используем upper_bound для нахождения позиции после последнего вхождения target.

3⃣Если target найден, заполняем результат позициями начала и конца.

😎 Решение:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans{-1,-1};
        auto l = lower_bound(nums.begin(), nums.end(), target);
        auto r = upper_bound(nums.begin(), nums.end(), target);
        if (l != nums.end() && *l == target) {
            ans[0] = l - nums.begin();
            ans[1] = r - nums.begin() - 1;
        }
        return ans;
    }
};

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