Задача: 1125. Smallest Sufficient Team
Сложность: hard

В проекте у вас есть список необходимых навыков req_skills и список людей. i-й человек people[i] содержит список навыков, которыми обладает этот человек.

Рассмотрим достаточную команду: набор людей, такой что для каждого необходимого навыка из req_skills, есть по крайней мере один человек в команде, который обладает этим навыком. Мы можем представить эти команды индексами каждого человека.

Например, команда = [0, 1, 3] представляет людей с навыками people[0], people[1] и people[3].
Верните любую достаточную команду наименьшего возможного размера, представленную индексами каждого человека. Вы можете вернуть ответ в любом порядке.

Гарантируется, что ответ существует.

Пример:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [["algorithms","math","java"],["algorithms","math","reactjs"],
["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

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

1⃣Инициализация и создание масок навыков:
Определите количество людей n и количество необходимых навыков m.
Создайте хэш-таблицу skillId, чтобы сопоставить каждому навыку уникальный индекс.
Создайте массив skillsMaskOfPerson, который будет содержать битовые маски навыков для каждого человека.

2⃣Динамическое программирование (DP):
Создайте массив dp размера 2^m и заполните его значениями (1 << n) - 1.
Установите dp[0] в 0 (базовый случай).
Для каждого skillsMask от 1 до 2^m - 1:
- для каждого человека i:
- вычислите smallerSkillsMask как skillsMask & ~skillsMaskOfPerson[i].
- если smallerSkillsMask отличается от skillsMask, обновите dp[skillsMask], если новая команда лучше (имеет меньше установленных битов).

3⃣Формирование ответа:
Извлеките ответ из dp и верните массив индексов людей, составляющих минимальную достаточную команду.

😎 Решение:

class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        int n = people.size(), m = req_skills.size();
        unordered_map<string, int> skillId;
        for (int i = 0; i < m; i++) {
            skillId[req_skills[i]] = i;
        }
        vector<int> skillsMaskOfPerson(n, 0);
        for (int i = 0; i < n; i++) {
            for (const string& skill : people[i]) {
                skillsMaskOfPerson[i] |= 1 << skillId[skill];
            }
        }
        vector<long> dp(1 << m, (1L << n) - 1);
        dp[0] = 0;
        for (int skillsMask = 1; skillsMask < (1 << m); skillsMask++) {
            for (int i = 0; i < n; i++) {
                int smallerSkillsMask = skillsMask & ~skillsMaskOfPerson[i];
                if (smallerSkillsMask != skillsMask) {
                    long peopleMask = dp[smallerSkillsMask] | (1L << i);
                    if (__builtin_popcountll(peopleMask) < __builtin_popcountll(dp[skillsMask])) {
                        dp[skillsMask] = peopleMask;
                    }
                }
            }
        }
        long answerMask = dp[(1 << m) - 1];
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if ((answerMask >> i) & 1) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

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

Задача: 727. Minimum Window Subsequence
Сложность: hard

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

1⃣Используйте два указателя для определения текущего окна.

2⃣Поддерживайте счетчики для символов в текущем окне и требуемых символов из s2.

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

😎 Решение:

class Solution {
public:
    string minWindow(string s1, string s2) {
        if (s1.empty() || s2.empty()) {
            return "";
        }

        unordered_map<char, int> dictT;
        for (char c : s2) {
            dictT[c]++;
        }

        int required = dictT.size();
        int l = 0, r = 0, formed = 0;
        unordered_map<char, int> windowCounts;
        int ans[3] = {INT_MAX, 0, 0};

        while (r < s1.size()) {
            char c = s1[r];
            windowCounts[c]++;

            if (dictT.count(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s1[l];

                if (r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts[c]--;
                if (dictT.count(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == INT_MAX ? "" : s1.substr(ans[1], ans[0]);
    }
};

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

Задача: 508. Most Frequent Subtree Sum
Сложность: medium

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

Сумма поддерева узла определяется как сумма всех значений узлов, образованных поддеревом, укорененным в этом узле (включая сам узел).

Пример:

Input: root = [5,2,-3]
Output: [2,-3,4]

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

1⃣Инициализация переменных
Инициализируйте переменные sumFreq для хранения частоты всех сумм поддеревьев. Инициализируйте maxFreq для хранения максимальной частоты. Создайте массив maxFreqSums для хранения всех сумм поддеревьев, частота которых равна максимальной.

2⃣Обход дерева и вычисление сумм
Выполните обход дерева в порядке post-order. Используйте суммы поддеревьев левого и правого дочерних узлов для вычисления суммы текущего поддерева. Увеличьте частоту текущей суммы в sumFreq. Обновите maxFreq, если частота текущей суммы больше текущего maxFreq.

3⃣Сборка результата
Пройдитесь по sumFreq и добавьте все суммы с частотой, равной maxFreq, в массив maxFreqSums. Верните массив maxFreqSums.

😎 Решение:

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <queue>

using namespace std;

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

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int, int> sumFreq;
        int maxFreq = 0;
        
        function<int(TreeNode*)> subtreeSum = [&](TreeNode* node) {
            if (!node) return 0;
            int leftSum = subtreeSum(node->left);
            int rightSum = subtreeSum(node->right);
            int currSum = node->val + leftSum + rightSum;
            sumFreq[currSum]++;
            maxFreq = max(maxFreq, sumFreq[currSum]);
            return currSum;
        };
        
        subtreeSum(root);
        vector<int> result;
        for (const auto& [sum, freq] : sumFreq) {
            if (freq == maxFreq) {
                result.push_back(sum);
            }
        }
        return result;
    }
};

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

Задача: 935. Knight Dialer
Сложность: medium

Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

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

2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

class Solution {
public:
    int knightDialer(int n) {
        int MOD = 1000000007;
        vector<vector<int>> moves = {
            {4, 6},
            {6, 8},
            {7, 9},
            {4, 8},
            {0, 3, 9},
            {},
            {0, 1, 7},
            {2, 6},
            {1, 3},
            {2, 4}
        };
        
        vector<int> dp(10, 1);
        
        for (int step = 1; step < n; step++) {
            vector<int> newDp(10, 0);
            for (int i = 0; i < 10; i++) {
                for (int move : moves[i]) {
                    newDp[move] = (newDp[move] + dp[i]) % MOD;
                }
            }
            dp = newDp;
        }
        
        return accumulate(dp.begin(), dp.end(), 0, [&](int sum, int count) {
            return (sum + count) % MOD;
        });
    }
};

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

Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

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

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

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

3⃣Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.

😎 Решение:

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        size_t m = mat.size();
        size_t n = mat[0].size();

        map<int, priority_queue<int, vector<int>, greater<int>>> diagonals;

        for (size_t row = 0; row < m; row++) {
            for (size_t col = 0; col < n; col++) {
                diagonals[row - col].push(mat[row][col]);
            }
        }

        for (size_t row = 0; row < m; row++) {
            for (size_t col = 0; col < n; col++) {
                mat[row][col] = diagonals[row - col].top();
                diagonals[row - col].pop();
            }
        }

        return mat;
    }
};

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

Задача: 990. Satisfiability of Equality Equations
Сложность: medium

Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.

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

Пример:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

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

1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.

2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.

3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.

😎 Решение:

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UnionFind uf(26);
        
        for (const auto& eq : equations) {
            if (eq[1] == '=') {
                int x = eq[0] - 'a';
                int y = eq[3] - 'a';
                uf.unionSet(x, y);
            }
        }
        
        for (const auto& eq : equations) {
            if (eq[1] == '!') {
                int x = eq[0] - 'a';
                int y = eq[3] - 'a';
                if (uf.connected(x, y)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
private:
    class UnionFind {
    public:
        UnionFind(int n) : parent(n) {
            iota(parent.begin(), parent.end(), 0);
        }
        
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        void unionSet(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
        
        bool connected(int x, int y) {
            return find(x) == find(y);
        }
        
    private:
        vector<int> parent;
    };
};

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

Задача: 986. Interval List Intersections
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

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

1⃣Инициализация указателей:
Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.

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

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

😎 Решение:

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        
        while (i < firstList.size() && j < secondList.size()) {
            int start = max(firstList[i][0], secondList[j][0]);
            int end = min(firstList[i][1], secondList[j][1]);
            
            if (start <= end) {
                result.push_back({start, end});
            }
            
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        
        return result;
    }
};

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

Input: grid = [[0,1],[1,0]]
Output: 2

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.

😎 Решение:

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        if (grid[0][0] != 0 || grid[grid.size() - 1][grid[0].size() - 1] != 0) {
            return -1;
        }

        vector<vector<int>> directions = {
            {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
        };

        queue<pair<int, int>> q;
        q.push({0, 0});
        grid[0][0] = 1;

        while (!q.empty()) {
            auto [row, col] = q.front(); q.pop();
            int distance = grid[row][col];
            if (row == grid.size() - 1 && col == grid[0].size() - 1) {
                return distance;
            }
            for (auto& direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (newRow >= 0 && newCol >= 0 && newRow < grid.size() && newCol < grid[0].size() && grid[newRow][newCol] == 0) {
                    q.push({newRow, newCol});
                    grid[newRow][newCol] = distance + 1;
                }
            }
        }
        return -1;
    }
};

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

Зарплата 207.000р у Middle-разработчика в Яндекс

«В день уходит несколько часов на созвоны, в остальное время закрываю задачки из спринта, редко перерабатываю. У компании топовый офис, но с коллективом как-то не заладилось. Радуюсь классному ДМС и стабильной зарплате» - middle разработчик из Яндекса.

Бигтех по-русски - канал с реальными зарплатами и историями IT-специалистов российского БигТеха. Там уже опубликованы рассказы программистов Альфа-банка, Сбера и Тинькофф 🤯

Читайте: @bigtech_russia

Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

1⃣Инициализировать пустой стек.
Использовать указатель j для отслеживания текущей позиции в массиве popped.

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int j = 0;
        for (int x : pushed) {
            st.push(x);
            while (!st.empty() && j < popped.size() && st.top() == popped[j]) {
                st.pop();
                j++;
            }
        }
        return j == popped.size();
    }
};

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

Задача: 729. My Calendar I
Сложность: medium

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к двойному бронированию. Двойное бронирование происходит, когда два события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendar: MyCalendar() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая двойного бронирования. В противном случае возвращается false и событие не добавляется в календарь.

Пример:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

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

1⃣Создайте класс MyCalendar с инициализатором для хранения списка событий.

2⃣Реализуйте метод book(int start, int end) для проверки пересечения нового события с уже существующими событиями.

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

😎 Решение:

class MyCalendar {
public:
    MyCalendar() {}

    bool book(int start, int end) {
        for (const auto& event : events) {
            if (start < event[1] && end > event[0]) {
                return false;
            }
        }
        events.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> events;
};

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

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

Дано бинарное дерево. Нужно вернуть все возможные пути от корня до листьев, где путь представлен как строка вида "1->2->5".

Пример:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

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

1⃣Рекурсивный обход дерева
Если текущий узел не nullptr, добавляем его значение к строке path.

2⃣Проверка на лист
Если это лист (нет ни левого, ни правого потомка), добавляем текущий путь в список paths.

3⃣Обход дочерних узлов
Если узел не лист, продолжаем обход влево и вправо, дописывая "->" в строку пути.

😎 Решение:

class Solution {
public:
    void construct_paths(TreeNode* root, string path, vector<string>& paths) {
        if (root) {
            path += to_string(root->val);
            if (!root->left && !root->right) {
                paths.push_back(path);
            } else {
                path += "->";
                construct_paths(root->left, path, paths);
                construct_paths(root->right, path, paths);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        construct_paths(root, "", paths);
        return paths;
    }
};

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