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

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.
Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

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

1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1.

3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask.

😎 Решение:

class Solution {
public:
    int findComplement(int num) {
        int bitmask = num;
        bitmask |= (bitmask >> 1);
        bitmask |= (bitmask >> 2);
        bitmask |= (bitmask >> 4);
        bitmask |= (bitmask >> 8);
        bitmask |= (bitmask >> 16);
        return bitmask ^ num;
    }
};

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

Задача: 643. Maximum Average Subarray I
Сложность: easy

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

1⃣Инициализация скользящего окна: Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.

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

3⃣Обновление максимальной суммы: На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.

😎 Решение:

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int currentSum = accumulate(nums.begin(), nums.begin() + k, 0);
        int maxSum = currentSum;
        
        for (int i = k; i < nums.size(); i++) {
            currentSum += nums[i] - nums[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        return (double) maxSum / k;
    }
};

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

Задача: 743. Network Delay Time
Сложность: medium

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

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

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

😎 Решение:

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int, vector<pair<int, int>>> graph;
        for (int i = 1; i <= n; ++i) {
            graph[i] = vector<pair<int, int>>();
        }
        for (auto& time : times) {
            graph[time[0]].emplace_back(time[1], time[2]);
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
        minHeap.emplace(0, k);
        unordered_map<int, int> minTime;
        for (int i = 1; i <= n; ++i) {
            minTime[i] = INT_MAX;
        }
        minTime[k] = 0;

        while (!minHeap.empty()) {
            auto [time, node] = minHeap.top(); minHeap.pop();
            for (auto& [neighbor, t] : graph[node]) {
                int newTime = time + t;
                if (newTime < minTime[neighbor]) {
                    minTime[neighbor] = newTime;
                    minHeap.emplace(newTime, neighbor);
                }
            }
        }

        int maxTime = *max_element(minTime.begin(), minTime.end());
        return maxTime == INT_MAX ? -1 : maxTime;
    }
};

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

Задача: 96. Unique Binary Search Trees
Сложность: medium

Дано число n.
Нужно вычислить количество структурно уникальных бинарных деревьев поиска (BST),
состоящих из n узлов с уникальными значениями от 1 до n.

Пример:

Input: n = 3
Output: 5

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

1⃣Обозначим G(n) — количество уникальных BST, построенных из n узлов.
Пусть F(i, n) — количество BST, в которых i является корнем.
Тогда:
G(n) = F(1, n) + F(2, n) + ... + F(n, n)

2⃣Для фиксированного i:
в левой части — i - 1 узел, в правой — n - i.
Т.е.
F(i, n) = G(i - 1) * G(n - i)

3⃣Тогда:
G(n) = ∑ G(i - 1) * G(n - i), i = 1..n
Сохраняем значения G[0] = 1 и G[1] = 1, и далее строим по формуле.

😎 Решение:

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1, 0);
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }

        return G[n];
    }
};

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

Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy

Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.

2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.

3⃣Проверка остатка изменений:
Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму.

😎 Решение:

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

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

Задача: 1063. Number of Valid Subarrays
Сложность: hard

Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

class Solution {
public:
    int validSubarrays(vector<int>& nums) {
        int ans = 0;
        stack<int> st;
        
        for (int i = 0; i < nums.size(); i++) {
            while (!st.empty() && nums[i] < nums[st.top()]) {
                ans += (i - st.top());
                st.pop();
            }
            st.push(i);
        }
        
        while (!st.empty()) {
            ans += (nums.size() - st.top());
            st.pop();
        }
        
        return ans;
    }
};

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