Задача: 678. Valid Parenthesis String
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.

Следующие правила определяют допустимую строку:

Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

class Solution {
public: 
    bool checkValidString(string s) {
        vector<vector<int>> memo(s.size(), vector<int>(s.size(), -1));
        return isValidString(0, 0, s, memo);
    }
private: 
    bool isValidString(int index, int openCount, const string & str, vector < vector < int >> & memo) {
        if (index == str.size()) {
            return openCount == 0;
        }

        if (memo[index][openCount] != -1) {
            return memo[index][openCount];
        }

        bool isValid = false;
        if (str[index] == '*') {
            isValid |= isValidString(index + 1, openCount + 1, str, memo);
            if (openCount) {
                isValid |= isValidString(index + 1, openCount - 1, str, memo);
            }
            isValid |= isValidString(index + 1, openCount, str, memo);
        } else {
            if (str[index] == '(') {
                isValid = isValidString(index + 1, openCount + 1, str, memo);
            } else if (openCount) {
                isValid = isValidString(index + 1, openCount - 1, str, memo);
            }
        }

        return memo[index][openCount] = isValid;
    }
};

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

Задача: 210. Course Schedule II
Сложность: medium

Дано число numCourses и список пар prerequisites, где каждая пара [a, b] означает: чтобы взять курс a, нужно сначала пройти курс b.
Верните один из возможных порядков прохождения курсов.
Если пройти все курсы невозможно (из-за циклов) — верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3]

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

1⃣Построение графа и подготовка к DFS
Создаем список смежности adjList, где adjList[b] содержит все курсы, зависящие от b.
Каждый курс помечаем цветом:
WHITE = 1 — не посещён
GRAY = 2 — в процессе обработки
BLACK = 3 — полностью обработан

2⃣Обход в глубину (DFS) и детектирование цикла
Для каждого непосещённого узла запускаем dfs.
Если во время обхода обнаруживаем цикл (возврат к GRAY узлу), значит, пройти курсы невозможно.

3⃣Формирование ответа
После завершения DFS по всем узлам формируем порядок курсов из стека (или массива) topologicalOrder, инвертируя его.

😎Решение:

cppКопироватьРедактироватьclass Solution {
public:
    int WHITE = 1;
    int GRAY = 2;
    int BLACK = 3;

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        bool isPossible = true;
        map<int, int> color;
        map<int, vector<int>> adjList;
        vector<int> topologicalOrder;

        for (int i = 0; i < numCourses; i++) color[i] = WHITE;

        for (vector<int> relation : prerequisites) {
            int dest = relation[0];
            int src = relation[1];
            adjList[src].push_back(dest);
        }

        for (int i = 0; i < numCourses && isPossible; i++) {
            if (color[i] == WHITE) {
                dfs(i, color, adjList, isPossible, topologicalOrder);
            }
        }

        vector<int> order;
        if (isPossible) {
            order.resize(numCourses);
            for (int i = 0; i < numCourses; i++) {
                order[i] = topologicalOrder[numCourses - i - 1];
            }
        }
        return order;
    }

    void dfs(int node, map<int, int>& color, map<int, vector<int>>& adjList,
             bool& isPossible, vector<int>& topologicalOrder) {
        if (!isPossible) return;
        color[node] = GRAY;

        for (int neighbor : adjList[node]) {
            if (color[neighbor] == WHITE) {
                dfs(neighbor, color, adjList, isPossible, topologicalOrder);
            } else if (color[neighbor] == GRAY) {
                isPossible = false;
            }
        }

        color[node] = BLACK;
        topologicalOrder.push_back(node);
    }
};

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

Задача: 931. Minimum Falling Path Sum
Сложность: medium

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

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

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

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

3⃣Вернуть минимальное значение в последней строке dp массива.

😎 Решение:

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> dp(matrix[0]);
        
        for (int i = 1; i < n; ++i) {
            vector<int> newDp(n, 0);
            for (int j = 0; j < n; ++j) {
                newDp[j] = matrix[i][j] + min({dp[j], j > 0 ? dp[j - 1] : INT_MAX, j < n - 1 ? dp[j + 1] : INT_MAX});
            }
            dp = newDp;
        }
        
        return *min_element(dp.begin(), dp.end());
    }
};

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

1⃣Пройти по всей сетке и для каждой башни (ячейки) посчитать начальную площадь поверхности: добавить площадь верхней и нижней граней, а также четыре боковые грани.

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

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

😎 Решение:

int surfaceArea(vector<vector<int>>& grid) {
    int n = grid.size();
    int area = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] > 0) {
                area += (grid[i][j] * 4) + 2;
            }
            if (i > 0) {
                area -= min(grid[i][j], grid[i-1][j]) * 2;
            }
            if (j > 0) {
                area -= min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
    }
    return area;
}

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

Задача: 1802. Maximum Value at a Given Index in a Bounded Array
Сложность: medium

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

- nums.length == n
- nums[i] является положительным целым числом, где 0 <= i < n.
- abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1.
- Сумма всех элементов массива nums не превышает maxSum.
- nums[index] максимально возможен.

Верните значение nums[index] в построенном массиве.

Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае.

Пример:

Input: n = 4, index = 2,  maxSum = 6
Output: 2

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

1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value.

2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1.

3⃣Верните left по завершении бинарного поиска.

😎 Решение:

class Solution {
private:
    long getSum(int index, int value, int n) {
        long count = 0;
        if (value > index) {
            count += (long)(value + value - index) * (index + 1) / 2;
        } else {
            count += (long)(value + 1) * value / 2 + index - value + 1;
        }
        if (value >= n - index) {
            count += (long)(value + value - n + 1 + index) * (n - index) / 2;
        } else {
            count += (long)(value + 1) * value / 2 + n - index - value;
        }
        return count - value;
    }

public:
    int maxValue(int n, int index, int maxSum) {
        int left = 1, right = maxSum;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (getSum(index, mid, n) <= maxSum) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

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

Задача: 965. Univalued Binary Tree
Сложность: easy

Бинарное дерево является одноценным, если каждый узел в дереве имеет одинаковое значение.

Дан корень бинарного дерева, верните true, если данное дерево является одноценным, или false в противном случае.

Пример:

Input: root = [1,1,1,1,1,null,1]
Output: true

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

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

2⃣Проверьте, что все значения в списке одинаковы.

3⃣Если все значения одинаковы, верните true, иначе верните false.

😎 Решение:

class Solution {
public:
    vector<int> vals;
    
    bool isUnivalTree(TreeNode* root) {
        dfs(root);
        for (int v : vals) {
            if (v != vals[0]) {
                return false;
            }
        }
        return true;
    }

    void dfs(TreeNode* node) {
        if (node) {
            vals.push_back(node->val);
            dfs(node->left);
            dfs(node->right);
        }
    }
};

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

Задача: 1220. Count Vowels Permutation
Сложность: hard

Дано целое число n, ваша задача состоит в том, чтобы посчитать, сколько строк длины n можно сформировать по следующим правилам:
Каждый символ является строчной гласной буквой ('a', 'e', 'i', 'o', 'u')
Каждая гласная 'a' может быть только перед 'e'.
Каждая гласная 'e' может быть только перед 'a' или 'i'.
Каждая гласная 'i' не может быть перед другой 'i'.
Каждая гласная 'o' может быть только перед 'i' или 'u'.
Каждая гласная 'u' может быть только перед 'a'.
Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

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

1⃣Инициализация массивов и начальных условий:
Инициализируйте пять одномерных массивов размером n для хранения количества строк, оканчивающихся на каждую гласную.
Установите первый элемент в каждом массиве равным 1, так как для строк длиной 1 существует только одна возможная строка для каждой гласной.

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

3⃣Суммирование и возврат результата:
Возьмите сумму последних элементов всех пяти массивов.
Верните результат по модулю 10^9 + 7.

😎 Решение:

class Solution {
public:
    int countVowelPermutation(int n) {
        const int MOD = 1000000007;
        vector<long> a(n), e(n), i(n), o(n), u(n);
        
        a[0] = e[0] = i[0] = o[0] = u[0] = 1;

        for (int k = 1; k < n; ++k) {
            a[k] = (e[k - 1] + i[k - 1] + u[k - 1]) % MOD;
            e[k] = (a[k - 1] + i[k - 1]) % MOD;
            i[k] = (e[k - 1] + o[k - 1]) % MOD;
            o[k] = i[k - 1] % MOD;
            u[k] = (i[k - 1] + o[k - 1]) % MOD;
        }

        return (a[n - 1] + e[n - 1] + i[n - 1] + o[n - 1] + u[n - 1]) % MOD;
    }
};

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

Задача: 66. Plus One
Сложность: easy

Дано число в виде массива цифр digits, где каждая цифра — это элемент массива. Нужно увеличить число на единицу и вернуть обновлённый массив.

Пример:

Input: digits = [1,2,3] Output: [1,2,4]

Алгоритм:

1⃣Начать проход с конца массива — увеличиваем самую младшую цифру

2⃣Если встречаем 9, заменяем её на 0 и продолжаем — т.к. будет перенос

3⃣Если перенос дошёл до начала и все цифры стали 0 — добавляем 1 в начало

😎 Решение:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i]++;
                return digits;
            }
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

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

Задача: 501. Find Mode in Binary Search Tree
Сложность: easy

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

Предположим, что BST определяется следующим образом:
Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу этого узла.
Правое поддерево узла содержит только узлы с ключами, большими или равными ключу этого узла.
Оба поддерева также должны быть бинарными деревьями поиска.

Пример:

Input: root = [1,null,2,2]
Output: [2]

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

1⃣Обход дерева
Выполните обход дерева (inorder DFS) с использованием рекурсивной функции dfs, чтобы пройти по всем узлам дерева. На каждом узле добавьте node.val в список values.

2⃣Поиск мод
Инициализируйте переменные maxStreak, currStreak, currNum как 0 и пустой список ans. Пройдите по списку values. Для каждого числа num: если num равно currNum, увеличьте currStreak. Иначе, установите currStreak равным 1, а currNum равным num. Если currStreak больше maxStreak, обновите maxStreak и сбросьте ans. Если currStreak равен maxStreak, добавьте num в ans.

3⃣Возврат результата
Верните список ans.

😎 Решение:

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> values;
        dfs(root, values);
        
        int maxStreak = 0, currStreak = 0, currNum = 0;
        vector<int> ans;
        
        for (int num : values) {
            if (num == currNum) {
                currStreak++;
            } else {
                currStreak = 1;
                currNum = num;
            }
            
            if (currStreak > maxStreak) {
                ans = {num};
                maxStreak = currStreak;
            } else if (currStreak == maxStreak) {
                ans.push_back(num);
            }
        }
        
        return ans;
    }
    
private:
    void dfs(TreeNode* node, vector<int>& values) {
        if (!node) return;
        dfs(node->left, values);
        values.push_back(node->val);
        dfs(node->right, values);
    }
};

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

Задача: 323. Number of Connected Components in an Undirected Graph
Сложность: medium

У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.
Верните количество связных компонентов в графе.

Пример:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

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

1⃣Создание списка смежности
Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v.

2⃣Инициализация посещенных узлов
Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин.

3⃣Подсчет компонентов
Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе.

😎 Решение:

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        vector<bool> visited(n, false);
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                count++;
            }
        }

        return count;
    }

private:
    void dfs(int node, const vector<vector<int>>& adj, vector<bool>& visited) {
        stack<int> stack;
        stack.push(node);
        while (!stack.empty()) {
            int current = stack.top();
            stack.pop();
            if (!visited[current]) {
                visited[current] = true;
                for (int neighbor : adj[current]) {
                    if (!visited[neighbor]) stack.push(neighbor);
                }
            }
        }
    }
};

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

Задача: 1013. Partition Array Into Three Parts With Equal Sum
Сложность: easy

Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Пример:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true

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

1⃣Вычисление общей суммы:
Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой.

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

3⃣Проверка третьей части:
Убедитесь, что оставшаяся часть массива также имеет ту же сумму, что и две найденные части. Если да, вернуть true, иначе false.

😎 Решение:

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int total_sum = accumulate(arr.begin(), arr.end(), 0);
        if (total_sum % 3 != 0) {
            return false;
        }
        
        int target = total_sum / 3, part_sum = 0, count = 0, n = arr.size();
        
        for (int i = 0; i < n; ++i) {
            part_sum += arr[i];
            if (part_sum == target) {
                ++count;
                part_sum = 0;
                if (count == 2 && i < n - 1) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

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

Задача: 362. Design Hit Counter
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

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

1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.

2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.

3⃣Верните размер очереди как количество попаданий за последние 5 минут.

😎 Решение:

#include <queue>

class HitCounter {
public:
    HitCounter() {}

    void hit(int timestamp) {
        hits.push(timestamp);
    }

    int getHits(int timestamp) {
        while (!hits.empty() && timestamp - hits.front() >= 300) {
            hits.pop();
        }
        return hits.size();
    }

private:
    std::queue<int> hits;
};

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

Задача: 100. Same Tree
Сложность: easy

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.
Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.

Пример:

Input: p = [1,2,3], q = [1,2,3] Output: true

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

1⃣Если оба узла равны null, значит на этом участке деревья одинаковы.

2⃣Если один из узлов равен null, а второй — нет, или значения узлов различаются, значит деревья не равны.

3⃣Рекурсивно проверьте левое и правое поддерево.

😎 Решение:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!q || !p) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->right, q->right) && isSameTree(p->left, q->left);
    }
};

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