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

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

Задача: 856. Score of Parentheses
Сложность: medium

Дана строка s, состоящая из сбалансированных скобок, верните счёт строки.

Счёт сбалансированной строки скобок основывается на следующих правилах:

"()" имеет счёт 1.
AB имеет счёт A + B, где A и B — сбалансированные строки скобок.
(A) имеет счёт 2 * A, где A — сбалансированная строка скобок.

Пример:

Input: s = "()"
Output: 1

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

1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки.

2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n).

3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]).

😎 Решение:

class Solution {
public:
    int scoreOfParentheses(string S) {
        return F(S, 0, S.size());
    }

    int F(string S, int i, int j) {
        int ans = 0, bal = 0;

        for (int k = i; k < j; ++k) {
            bal += S[k] == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }

        return ans;
    }
};

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

📺 База 1000+ реальных собеседований

На программиста, тестировщика, аналитика, проджекта и другие IT профы.

Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.

🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 637. Average of Levels in Binary Tree
Сложность: easy

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]

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

1⃣Обход дерева: Используйте обход в ширину (BFS) для обхода каждого уровня дерева.

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

3⃣Сохранение результата: Сохраните среднее значение каждого уровня в массив и верните его.

😎 Решение:

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> queue;
        queue.push(root);
        
        while (!queue.empty()) {
            long sum = 0;
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                sum += node->val;
                if (node->left) queue.push(node->left);
                if (node->right) queue.push(node->right);
            }
            result.push_back((double) sum / count);
        }
        
        return result;
    }
};

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

Задача: 667. Beautiful Arrangement II
Сложность: medium

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

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

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:

class Solution {
public:
    vector<int> constructArray(int n, int k) {
        vector<int> answer;
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer.push_back(left++);
            } else {
                answer.push_back(right--);
            }
        }
        
        if (k % 2 == 0) {
            for (int i = right; i >= left; i--) {
                answer.push_back(i);
            }
        } else {
            for (int i = left; i <= right; i++) {
                answer.push_back(i);
            }
        }
        
        return answer;
    }
};

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

Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium

Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].

Пример:

Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]

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

1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах.

2⃣Решите систему уравнений:
4J + 2S = tomatoSlices
J + S = cheeseSlices

3⃣Если решение существует, верните его, иначе верните пустой список.

😎 Решение:

class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if (tomatoSlices % 2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
            return {};
        }
        int total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
        int total_small = cheeseSlices - total_jumbo;
        return {total_jumbo, total_small};
    }
};

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