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

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