Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy

Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.

Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.

Пример:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

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

1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..

2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.

3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.

😎 Решение:

class Solution {
public:
    bool isMajorityElement(vector<int>& nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num == target) {
                count++;
            }
        }
        return count > nums.size() / 2;
    }
};

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

Задача: 1263. Minimum Moves to Move a Box to Their Target Location
Сложность: hard

Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1.

Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

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

1⃣Выполните поиск в ширину (BFS) для всех возможных позиций игрока и коробки, отслеживая количество толчков.

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

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

😎 Решение:

class Solution {
public:
    int minPushBox(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        auto isValid = [&](int x, int y) {
            return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
        };
        
        queue<tuple<int, int, int, int, int>> q;
        unordered_set<string> visited;
        
        int px, py, bx, by, tx, ty;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'S') {
                    px = i;
                    py = j;
                } else if (grid[i][j] == 'B') {
                    bx = i;
                    by = j;
                } else if (grid[i][j] == 'T') {
                    tx = i;
                    ty = j;
                }
            }
        }
        
        q.push({px, py, bx, by, 0});
        visited.insert(to_string(px) + "," + to_string(py) + "," + to_string(bx) + "," + to_string(by));
        
        while (!q.empty()) {
            auto [px, py, bx, by, pushes] = q.front();
            q.pop();
            if (bx == tx && by == ty) {
                return pushes;
            }
            for (auto [dx, dy] : directions) {
                int npx = px + dx, npy = py + dy;
                if (isValid(npx, npy)) {
                    if (npx == bx && npy == by) {
                        int nbx = bx + dx, nby = by + dy;
                        if (isValid(nbx, nby) && visited.insert(to_string(npx) + "," + to_string(npy) + "," + to_string(nbx) + "," + to_string(nby)).second) {
                            q.push({npx, npy, nbx, nby, pushes + 1});
                        }
                    } else if (visited.insert(to_string(npx) + "," + to_string(npy) + "," + to_string(bx) + "," + to_string(by)).second) {
                        q.push({npx, npy, bx, by, pushes});
                    }
                }
            }
        }
        
        return -1;
    }
};

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

Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица m x n, нужно обнулить всю строку и столбец, если хотя бы один элемент равен 0.
Решение должно быть на месте, без использования дополнительной матрицы.

Пример:

Input: [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

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

1⃣Обход всей матрицы:
Если элемент matrix[i][j] == 0, помечаем:
matrix[0][j] = 0 (нужен обнулить весь столбец j)
matrix[i][0] = 0 (нужен обнулить всю строку i)
Первый столбец не может пересекаться с первой строкой → используем флаг isCol

2⃣Второй проход (снизу вверх, слева направо):
Если matrix[i][0] == 0 или matrix[0][j] == 0, то matrix[i][j] = 0

3⃣В конце отдельно обрабатываем первую строку и первый столбец:
Если matrix[0][0] == 0 → обнулить всю первую строку
Если isCol == true → обнулить весь первый столбец

😎 Решение:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool isCol = false;
        int R = matrix.size();
        int C = matrix[0].size();

        for (int i = 0; i < R; i++) {
            if (matrix[i][0] == 0) {
                isCol = true;
            }
            for (int j = 1; j < C; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (matrix[0][0] == 0) {
            for (int j = 0; j < C; j++) {
                matrix[0][j] = 0;
            }
        }

        if (isCol) {
            for (int i = 0; i < R; i++) {
                matrix[i][0] = 0;
            }
        }
    }
};

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

Задача: 179. Largest Number
Сложность: medium

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

Пример:

Input: nums = [10,2] Output: "210"

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

1⃣Преобразование и сортировка:
Преобразовать каждое число в строку и отсортировать массив строк по убыванию, используя компаратор, сравнивающий a + b и b + a.

2⃣Проверка на нули:
Если после сортировки первый элемент равен "0", вернуть "0", так как все элементы — нули.

3⃣Формирование результата:
Сконкатенировать отсортированные строки и вернуть
результат.

😎 Решение:

cppКопироватьРедактироватьclass Solution {
public:
    string largestNumber(vector<int> &nums) {
        vector<string> strNums(nums.size());
        for (int i = 0; i < nums.size(); ++i) {
            strNums[i] = to_string(nums[i]);
        }

        sort(strNums.begin(), strNums.end(),
             [](string &a, string &b) { return a + b > b + a; });

        if (strNums[0] == "0") {
            return "0";
        }

        string largestNumberStr;
        for (string numAsStr : strNums) {
            largestNumberStr += numAsStr;
        }

        return largestNumberStr;
    }
};

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

Задача: 480. Sliding Window Median
Сложность: hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.

Пример:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

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

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

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

3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.

😎 Решение:

#include <vector>
#include <algorithm>

std::vector<double> medianSlidingWindow(std::vector<int>& nums, int k) {
    std::vector<double> medians;

    for (int i = 0; i + k <= nums.size(); i++) {
        std::vector<int> window(nums.begin() + i, nums.begin() + i + k);
        std::sort(window.begin(), window.end());

        if (k % 2 == 1) {
            medians.push_back(window[k / 2]);
        } else {
            medians.push_back((window[k / 2 - 1] + window[k / 2]) / 2.0);
        }
    }

    return medians;
}

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

Задача: 305. Number of Islands II
Сложность: hard

Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.

Пример:

Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]

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

1⃣Инициализация
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

2⃣Обработка позиций
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.

3⃣Определение количества островов
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.

😎 Решение

class UnionFind {
    vector<int> parent, rank; int count;
public:
    UnionFind(int size) : parent(size, -1), rank(size, 0), count(0) {}
    void addLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
    bool isLand(int x) { return parent[x] >= 0; }
    int numberOfIslands() { return count; }
    int find(int x) { return parent[x] != x ? parent[x] = find(parent[x]) : x; }
    void unionSet(int x, int y) { int xset = find(x), yset = find(y);
        if (xset != yset) { if (rank[xset] < rank[yset]) parent[xset] = yset;
        else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
};

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
        UnionFind dsu(m * n); vector<int> answer;
        vector<int> x = {-1, 1, 0, 0}, y = {0, 0, -1, 1};
        for (auto& pos : positions) {
            int land = pos[0

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

Задача: 636. Exclusive Time of Functions
Сложность: medium

На однопоточном процессоре выполняется программа, содержащая n функций. Каждая функция имеет уникальный ID от 0 до n-1. Вызовы функций хранятся в стеке вызовов: когда начинается вызов функции, ее ID заталкивается в стек, а когда вызов функции заканчивается, ее ID выгружается из стека. Функция, чей идентификатор находится в верхней части стека, является текущей выполняемой функцией. Каждый раз, когда функция запускается или завершается, мы пишем лог с идентификатором, началом или завершением и меткой времени. Вам предоставляется список logs, где logs[i] представляет собой i-е сообщение лога, отформатированное как строка "{function_id}:{"start" | "end"}:{timestamp}". Например, "0:start:3" означает, что вызов функции с идентификатором 0 начался в начале временной метки 3, а "1:end:2" означает, что вызов функции с идентификатором 1 завершился в конце временной метки 2. Обратите внимание, что функция может быть вызвана несколько раз, возможно, рекурсивно. Исключительное время функции - это сумма времен выполнения всех вызовов функции в программе. Например, если функция вызывается дважды, причем один вызов выполняется за 2 единицы времени, а другой - за 1 единицу, то эксклюзивное время равно 2 + 1 = 3. Верните эксклюзивное время каждой функции в массив, где значение по i-му индексу представляет собой эксклюзивное время для функции с идентификатором i.

Пример:

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3,4]

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

1⃣Парсинг логов: Пройдитесь по каждому логу, чтобы распознать действие (start или end) и идентификатор функции вместе с временной меткой.

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

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

😎 Решение:

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        stack<int> stack;
        vector<int> times(n, 0);
        int prevTime = 0;
        
        for (const string& log : logs) {
            stringstream ss(log);
            string fidStr, type, timeStr;
            getline(ss, fidStr, ':');
            getline(ss, type, ':');
            getline(ss, timeStr, ':');
            int fid = stoi(fidStr);
            int time = stoi(timeStr);
            
            if (type == "start") {
                if (!stack.empty()) {
                    times[stack.top()] += time - prevTime;
                }
                stack.push(fid);
                prevTime = time;
            } else {
                times[stack.top()] += time - prevTime + 1;
                stack.pop();
                prevTime = time + 1;
            }
        }
        
        return times;
    }
};

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

Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium

Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.

Пример:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

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

1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.

2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.

3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.

😎 Решение:

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

class Solution {
public:
    int index = 0;

    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return constructBST(preorder, INT_MIN, INT_MAX);
    }

    TreeNode* constructBST(vector<int>& preorder, int lower, int upper) {
        if (index == preorder.size()) {
            return NULL;
        }

        int val = preorder[index];
        if (val < lower || val > upper) {
            return NULL;
        }

        index++;
        TreeNode* root = new TreeNode(val);
        root.left = constructBST(preorder, lower, val);
        root.right = constructBST(preorder, val, upper);
        return root;
    }
};

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

Задача: 1016. Binary String With Substrings Representing 1 To N
Сложность: medium

Если задана двоичная строка s и положительное целое число n, верните true, если двоичное представление всех целых чисел в диапазоне [1, n] является подстрокой s, или false в противном случае. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "0110", n = 3
Output: true

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

1⃣Генерация двоичных строк:
Для каждого числа в диапазоне [1, n] сгенерируйте его двоичное представление.

2⃣Проверка подстрок:
Проверьте, является ли каждое из двоичных представлений подстрокой строки s.

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

😎 Решение:

class Solution {
public:
    bool queryString(string s, int n) {
        for (int i = 1; i <= n; ++i) {
            string binary = bitset<32>(i).to_string();
            binary.erase(0, binary.find_first_not_of('0'));
            if (s.find(binary) == string::npos) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 1506. Find Root of N-Ary Tree
Сложность: medium

Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение.

Верните корень N-арного дерева.

Пример:

Input: tree = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]
Explanation: The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

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

1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве.

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

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

😎 Решение:

class Solution {
public:
    Node* findRoot(vector<Node*> tree) {
        unordered_set<int> seen;

        for (Node* node : tree) {
            for (Node* child : node->children) {
                seen.insert(child->val);
            }
        }

        Node* root = nullptr;
        for (Node* node : tree) {
            if (seen.find(node->val) == seen.end()) {
                root = node;
                break;
            }
        }
        return root;
    }
};

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

Задача: 1538. Guess the Majority in a Hidden Array
Сложность: medium

У нас есть целочисленный массив nums, где все числа в nums равны 0 или 1. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int query(int a, int b, int c, int d): где 0 <= a < b < c < d < ArrayReader.length(). Функция возвращает распределение значений 4 элементов и возвращает:
4: если значения всех 4 элементов одинаковы (0 или 1).
2: если три элемента имеют значение 0 и один элемент имеет значение 1 или наоборот.
0: если два элемента имеют значение 0 и два элемента имеют значение 1.

int length(): Возвращает размер массива.

Вам разрешено вызывать query() не более 2 * n раз, где n равно ArrayReader.length().

Верните любой индекс самого частого значения в nums, в случае ничьей верните -1.

Пример:

Input: nums = [0,0,1,0,1,1,1,1]
Output: 5
Explanation: The following calls to the API
reader.length() // returns 8 because there are 8 elements in the hidden array.
reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3]
// Three elements have a value equal to 0 and one element has value equal to 1 or viceversa.
reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value.
we can infer that the most frequent value is found in the last 4 elements.
Index 2, 4, 6, 7 is also a correct answer.

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

1⃣Получите n вызовом функции length. Объявите и инициализируйте переменные cntEqual = 1, cntDiffer = 0, indexDiffer = -1. Вызовите query(0, 1, 2, 3) и сохраните результат в переменной query0123. Вызовите query(1, 2, 3, 4) и сохраните результат в переменной query1234. Если query1234 равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 4.

2⃣Итерация от i = 5 до n-1. Если значение query(1, 2, 3, i) равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = i. Дополнительные проверки для первых элементов: если query(0, 2, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 1. Если query(0, 1, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 2. Если query(0, 1, 2, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 3.

3⃣Если cntEqual > cntDiffer, верните 0. Если cntDiffer > cntEqual, верните indexDiffer. Верните -1.

😎 Решение:

class Solution {
    int cntEqual = 1, cntDiffer = 0, indexDiffer = -1;

    void f(bool equal, int i) {
        if (equal) {
            cntEqual++;
        } else {
            cntDiffer++;
            indexDiffer = i;
        }
    }

public:
    int guessMajority(ArrayReader& reader) {
        int n = reader.length(), query0123 = reader.query(0, 1, 2, 3), query1234 = reader.query(1, 2, 3, 4);
        f(query1234 == query0123, 4);
        for (int i = 5; i < n; i++) {
            f(reader.query(1, 2, 3, i) == query0123, i);
        }
        f(reader.query(0, 2, 3, 4) == query1234, 1);
        f(reader.query(0, 1, 3, 4) == query1234, 2);
        f(reader.query(0, 1, 2, 4) == query1234, 3);
        return cntEqual > cntDiffer ? 0 : cntDiffer > cntEqual ? indexDiffer : -1;
    }
};

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

Задача: 60. Permutation Sequence
Сложность: hard

Дано n, представляющее числа от 1 до n, и k — порядковый номер.
Нужно вернуть k-ю лексикографическую перестановку этих чисел.

Пример:

Input: n = 3, k = 3 Output: "213"

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

1⃣Сформировать массив nums из символов '1' до 'n' и массив факториалов от 0! до (n-1)!

2⃣Уменьшить k на 1 (чтобы перейти к 0-индексации)

3⃣На каждой позиции определить индекс следующего числа:
idx = k / factorial[i], далее обновить k -= idx * factorial[i]
Удалить выбранный элемент из nums и добавить к результату

😎 Решение:

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorials(n);
        vector<char> nums;
        factorials[0] = 1;
        nums.push_back('1');
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.push_back(char(i + 1 + '0'));
        }

        --k;
        string result = "";
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];
            result += nums[idx];
            nums.erase(nums.begin() + idx);
        }
        return result;
    }
};

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

Задача: 661. Image Smoother
Сложность: easy

Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.

Пример:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

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

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

2⃣Обработка каждой ячейки:
Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку).
Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы.

3⃣Возврат результата:
Верните результирующую матрицу после применения сглаживания ко всем ячейкам.

😎 Решение:

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m = img.size(), n = img[0].size();
        vector<vector<int>> result(m, vector<int>(n, 0));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = 0, total = 0;
                for (int ni = max(0, i - 1); ni <= min(m - 1, i + 1); ni++) {
                    for (int nj = max(0, j - 1); nj <= min(n - 1, j + 1); nj++) {
                        total += img[ni][nj];
                        count++;
                    }
                }
                result[i][j] = total / count;
            }
        }
        
        return result;
    }
};

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

Задача: 847. Shortest Path Visiting All Nodes
Сложность: hard

У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром.

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

Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

1⃣Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов.

2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps.

3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов.

😎 Решение:

#include <vector>
#include <queue>
#include <utility>

using namespace std;

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        if (n == 1) return 0;

        int endingMask = (1 << n) - 1;
        vector<vector<bool>> seen(n, vector<bool>(endingMask, false));
        queue<pair<int, int>> q;

        for (int i = 0; i < n; ++i) {
            q.push({i, 1 << i});
            seen[i][1 << i] = true;
        }

        int steps = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto [node, mask] = q.front();
                q.pop();
                for (int neighbor : graph[node]) {
                    int nextMask = mask | (1 << neighbor);
                    if (nextMask == endingMask) return 1 + steps;
                    if (!seen[neighbor][nextMask]) {
                        seen[neighbor][nextMask] = true;
                        q.push({neighbor, nextMask});
                    }
                }
            }
            ++steps;
        }

        return -1;
    }
};

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

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
Сложность: easy

Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве.

Дерево cloned является копией оригинального дерева.

Верните ссылку на тот же узел в дереве cloned.

Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned.

Пример:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

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

1⃣Добавьте корень в очередь.

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

3⃣Верните ссылку на найденный целевой узел.

😎 Решение:

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        queue<TreeNode*> queue_o;
        queue<TreeNode*> queue_c;
        
        queue_o.push(original);
        queue_c.push(cloned);
        
        while (!queue_o.empty()) {
            TreeNode* node_o = queue_o.front();
            queue_o.pop();
            TreeNode* node_c = queue_c.front();
            queue_c.pop();
            
            if (node_o == target) {
                return node_c;
            }
            
            if (node_o->left != nullptr) {
                queue_o.push(node_o->left);
                queue_c.push(node_c->left);
            }
            if (node_o->right != nullptr) {
                queue_o.push(node_o->right);
                queue_c.push(node_c->right);
            }
        }
        return nullptr;
    }
};

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

Задача: 346. Moving Average from Data Stream
Сложность: easy

Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне.

Реализуйте класс MovingAverage:

MovingAverage(int size) Инициализирует объект с размером окна size.
double next(int val) Возвращает скользящее среднее последних size значений потока.

Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

1⃣Инициализация:
Инициализируйте объект с фиксированным размером окна size.
Используйте очередь или список для хранения значений в текущем окне.
Храните текущую сумму значений в окне.

2⃣Добавление нового значения:
Добавьте новое значение в очередь.
Обновите текущую сумму, добавив новое значение.
Если размер очереди превышает size, удалите самое старое значение и обновите сумму, вычтя это значение.

3⃣Вычисление скользящего среднего:
Возвращайте текущее скользящее среднее как сумму значений в окне, деленную на количество значений в окне.

😎 Решение:

#include <queue>

class MovingAverage {
public:
    MovingAverage(int size) : size(size), sum(0) {}
    
    double next(int val) {
        q.push(val);
        sum += val;
        if (q.size() > size) {
            sum -= q.front();
            q.pop();
        }
        return (double) sum / q.size();
    }
    
private:
    int size;
    std::queue<int> q;
    int sum;
};

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

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.
Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

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

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

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

Задача: 898. Bitwise ORs of Subarrays
Сложность: medium

Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве.

Пример:

Input: arr = [0]
Output: 1

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

1⃣Создать множество для хранения уникальных результатов побитового ИЛИ.

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

3⃣Вернуть размер множества.

😎 Решение:

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> result, current, next;
        for (int num : arr) {
            next = {num};
            for (int x : current) {
                next.insert(x | num);
            }
            current = next;
            result.insert(current.begin(), current.end());
        }
        return result.size();
    }
};

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

Задача: 981. Time Based Key-Value Store
Сложность: medium

Спроектируйте структуру данных на основе времени для ключей и значений, которая может хранить несколько значений для одного и того же ключа в разные временные метки и извлекать значение ключа в определённый момент времени.

Реализуйте класс TimeMap:

TimeMap() Инициализирует объект структуры данных.
void set(String key, String value, int timestamp) Сохраняет ключ key с значением value в заданное время timestamp.
String get(String key, int timestamp) Возвращает значение, такое что set был вызван ранее с timestamp_prev <= timestamp. Если таких значений несколько, возвращается значение, связанное с наибольшим timestamp_prev. Если значений нет, возвращается "".

Пример:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

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

1⃣Создайте hashmap keyTimeMap, который хранит строку в качестве ключа и другой hashmap в качестве значения, как обсуждалось выше.

2⃣В функции set() сохраните значение в позиции timestamp в корзине ключа keyTimeMap, т.е. keyTimeMap[key][timestamp] = value.

3⃣В функции get() итерируйтесь по всем временам в порядке убывания от timestamp до 1. Для любого времени во время итерации, если существует значение в корзине ключа, верните это значение. В противном случае, в конце верните пустую строку.

😎 Решение:

#include <unordered_map>
#include <string>

class TimeMap {
public:
    std::unordered_map<std::string, std::unordered_map<int, std::string>> keyTimeMap;

    TimeMap() {}

    void set(const std::string& key, const std::string& value, int timestamp) {
        keyTimeMap[key][timestamp] = value;
    }

    std::string get(const std::string& key, int timestamp) {
        if (!keyTimeMap.count(key)) {
            return "";
        }

        for (int currTime = timestamp; currTime >= 1; --currTime) {
            if (keyTimeMap[key].count(currTime)) {
                return keyTimeMap[key][currTime];
            }
        }

        return "";
    }
};

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

Задача: 295. Find Median from Data Stream
Сложность: hard

Пример:

Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
Output: [null, null, null, 1.5, null, 2.0]

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

1⃣Используйте две кучи: max-heap (left) для хранения меньшей половины элементов и min-heap (right) для хранения большей половины. Это позволяет находить медиану за O(1) и вставлять за O(log n).

2⃣При добавлении числа:
Если left пуст или num <= top(left), добавьте его в left.
Иначе добавьте его в right.
После добавления сбалансируйте размеры куч: если одна куча больше другой более чем на 1 элемент, переместите элемент из большей в меньшую.

3⃣Для вычисления медианы:
Если размеры куч равны, верните среднее двух верхних элементов.
Если одна куча больше, верните её верхний элемент как медиану.

😎 Решение:

#include <queue>

class MedianFinder {
private:
    priority_queue<int> left; // max-heap
    priority_queue<int, vector<int>, greater<int>> right; // min-heap

public:
    MedianFinder() {}

    void addNum(int num) {
        if (left.empty() || num <= left.top()) {
            left.push(num);
        } else {
            right.push(num);
        }

        if (left.size() > right.size() + 1) {
            right.push(left.top());
            left.pop();
        } else if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }

    double findMedian() {
        if (left.size() == right.size()) {
            return (left.top() + right.top()) / 2.0;
        } else {
            return left.top();
        }
    }
};

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

Задача: 1402. Reducing Dishes
Сложность: hard

Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени.

Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i].

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

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

Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

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

1⃣Отсортируйте массив satisfaction в порядке возрастания.

2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан.

3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ: Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение. Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo. Рассчитайте максимум из двух вариантов: добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1. Пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time.

😎 Решение:

class Solution {
public:
    int findMaxSatisfaction(vector<int>& satisfaction, vector<vector<int>>& memo, int index, int time) {
        if (index == satisfaction.size()) return 0;
        if (memo[index][time] != -1) return memo[index][time];

        return memo[index][time] = max(satisfaction[index] * time + findMaxSatisfaction(satisfaction, memo, index + 1, time + 1),
                                       findMaxSatisfaction(satisfaction, memo, index + 1, time));
    }

    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        vector<vector<int>> memo(satisfaction.size() + 1, vector<int>(satisfaction.size() + 1, -1));
        return findMaxSatisfaction(satisfaction, memo, 0, 1);
    }
};

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