C/C++ | LeetCode

Задача: 1424. Diagonal Traverse II Сложность: medium Дан двумерный целочисленный массив nums, верните все элементы nums в диагональном порядке. Пример:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь с (0, 0) и список ответов ans. 2⃣Пока очередь не пуста: Извлеките (row, col) из очереди. Добавьте nums[row][col] в ans. Если col == 0 и row + 1 в пределах массива, добавьте (row + 1, col) в очередь. Если col + 1 в пределах текущей строки, добавьте (row, col + 1) в очередь. 3⃣Верните ans. 😎 Решение:

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        queue<pair<int, int>> q;
        q.push({0, 0});
        vector<int> ans;
        
        while (!q.empty()) {
            auto [row, col] = q.front(); q.pop();
            ans.push_back(nums[row][col]);
            
            if (col == 0 && row + 1 < nums.size()) {
                q.push({row + 1, col});
            }
            
            if (col + 1 < nums[row].size()) {
                q.push({row, col + 1});
            }
        }
        
        return ans;
    }
};

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

Задача: 957. Prison Cells After N Days Сложность: medium Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста. Каждый день статус камеры, занята она или пуста, меняется по следующим правилам: Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой. В противном случае, она становится пустой. Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей. Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n. Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше). Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

👨‍💻 Алгоритм: 1⃣Преобразуйте текущее состояние камер в целое число с помощью битовой маски. Это позволит удобно отслеживать повторяющиеся состояния. 2⃣Симулируйте изменение состояния камер день за днем, записывая каждое состояние в хэш-таблицу. Если обнаруживается повторяющееся состояние, вычислите длину цикла и уменьшите количество оставшихся дней с учетом этого цикла. 3⃣Продолжайте симуляцию, пока не достигнете заданного числа дней, либо используйте цикл для ускорения процесса. 😎 Решение:

class Solution {
public:
    int cellsToBitmap(vector<int>& cells) {
        int stateBitmap = 0;
        for (int cell : cells) {
            stateBitmap = (stateBitmap << 1) | cell;
        }
        return stateBitmap;
    }

    vector<int> nextDay(vector<int>& cells) {
        vector<int> newCells(cells.size(), 0);
        for (int i = 1; i < cells.size() - 1; ++i) {
            newCells[i] = (cells[i - 1] == cells[i + 1]) ? 1 : 0;
        }
        return newCells;
    }

    vector<int> prisonAfterNDays(vector<int>& cells, int N) {
        unordered_map<int, int> seen;
        bool isFastForwarded = false;

        while (N > 0) {
            if (!isFastForwarded) {
                int stateBitmap = cellsToBitmap(cells);
                if (seen.find(stateBitmap) != seen.end()) {
                    N %= seen[stateBitmap] - N;
                    isFastForwarded = true;
                } else {
                    seen[stateBitmap] = N;
                }
            }

            if (N > 0) {
                N--;
                cells = nextDay(cells);
            }
        }
        return cells;
    }
};

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

Задача: 1246. Palindrome Removal Сложность: hard Вам дан целочисленный массив arr. За один ход вы можете выбрать палиндромный подмассив arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подмассив из данного массива. Обратите внимание, что после удаления подмассива элементы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. Верните минимальное количество ходов, необходимое для удаления всех чисел из массива. Пример:

Input: arr = [1,2]
Output: 2

👨‍💻 Алгоритм: 1⃣Базовый случай: Если подмассив состоит из одного элемента, то его удаление займет 1 ход, поэтому dp[i][i] = 1. 2⃣Рекурсивный случай: Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подмассив arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подмассив arr[i+1...j-1] и затем удалим arr[i] и arr[j]). 3⃣В противном случае, минимальное количество ходов для удаления подмассива arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подмассивов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1. 😎 Решение:

int minMovesToDelete(vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }

    for (int length = 2; length <= n; ++length) {
        for (int i = 0; i <= n - length; ++i) {
            int j = i + length - 1;
            if (arr[i] == arr[j]) {
                dp[i][j] = (length > 2) ? dp[i + 1][j - 1] : 1;
            } else {
                dp[i][j] = INT_MAX;
                for (int k = i; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
    }

    return dp[0][n - 1];
}

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

Задача: 56. Merge Intervals Сложность: medium Дан массив интервалов intervals, где intervals[i] = [start_i, end_i]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, покрывающий те же отрезки. Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]

👨‍💻 Алгоритм: 1⃣Построение графа: Каждый интервал — вершина. Если два интервала пересекаются, между ними проводится ребро. 2⃣Поиск компонент связности: Обход графа (DFS), чтобы найти все интервалы, входящие в одну компоненту — они образуют один объединённый интервал. 3⃣Слияние компонент: Для каждой компоненты берём минимальное начало и максимальный конец интервалов и создаём один новый интервал. Решение:

#include <vector>
#include <map>
#include <set>
#include <stack>
using namespace std;

class Solution {
public:
    map<vector<int>, vector<vector<int>>> graph;
    map<int, vector<vector<int>>> nodes_in_comp;
    set<vector<int>> visited;

    bool overlap(vector<int>& a, vector<int>& b) {
        return a[0] <= b[1] && b[0] <= a[1];
    }

    void buildGraph(vector<vector<int>>& intervals) {
        for (auto interval1 : intervals) {
            for (auto interval2 : intervals) {
                if (overlap(interval1, interval2)) {
                    graph[interval1].push_back(interval2);
                    graph[interval2].push_back(interval1);
                }
            }
        }
    }

    vector<int> mergeNodes(vector<vector<int>>& nodes) {
        int min_start = nodes[0][0];
        int max_end = nodes[0][1];

        for (auto node : nodes) {
            min_start = min(min_start, node[0]);
            max_end = max(max_end, node[1]);
        }

        return {min_start, max_end};
    }

    void markComponentDFS(vector<int>& start, int comp_number) {
        stack<vector<int>> stk;
        stk.push(start);

        while (!stk.empty()) {
            vector<int> node = stk.top();
            stk.pop();

            if (visited.find(node) == visited.end()) {
                visited.insert(node);
                nodes_in_comp[comp_number].push_back(node);

                for (auto child : graph[node]) {
                    stk.push(child);
                }
            }
        }
    }

    void buildComponents(vector<vector<int>>& intervals) {
        int comp_number = 0;

        for (auto interval : intervals) {
            if (visited.find(interval) == visited.end()) {
                markComponentDFS(interval, comp_number);
                comp_number++;
            }
        }
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        buildGraph(intervals);
        buildComponents(intervals);

        vector<vector<int>> merged;
        for (size_t comp = 0; comp < nodes_in_comp.size(); comp++) {
            merged.push_back(mergeNodes(nodes_in_comp[comp]));
        }

        return merged;
    }
};

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

Задача: 1425. Constrained Subsequence Sum Сложность: hard Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k. Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке. Пример:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums. 2⃣Итерируйте i по индексам nums: Если i минус первый элемент queue больше k, удалите элемент из начала queue. Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()]. Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue. Если dp[i] > 0, добавьте i в конец queue. 3⃣Верните максимальное значение в массиве dp. 😎 Решение:

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        deque<int> queue;
        vector<int> dp(nums.size());
        int maxSum = INT_MIN;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (!queue.empty() && i - queue.front() > k) {
                queue.pop_front();
            }
            
            dp[i] = (queue.empty() ? 0 : dp[queue.front()]) + nums[i];
            
            while (!queue.empty() && dp[queue.back()] < dp[i]) {
                queue.pop_back();
            }
            
            if (dp[i] > 0) {
                queue.push_back(i);
            }
            
            maxSum = max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
};

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

Задача: 1531. String Compression II Сложность: hard Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной. Найдите минимальную длину сжатой версии строки s после удаления не более k символов. Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

👨‍💻 Алгоритм: 1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования. 2⃣Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить. 3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия. 😎 Решение:

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>

class Solution {
    std::unordered_map<int, int> memo;
    std::unordered_set<int> add = {1, 9, 99};

public:
    int getLengthOfOptimalCompression(std::string s, int k) {
        return dp(s, 0, 'a' + 26, 0, k);
    }

private:
    int dp(const std::string& s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return INT_MAX / 2;
        }

        if (idx == s.size()) {
            return 0;
        }

        int key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k;

        if (memo.count(key)) {
            return memo[key];
        }

        int deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        int keepChar;
        if (s[idx] == lastChar) {
            keepChar = dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.count(lastCharCount) ? 1 : 0);
        } else {
            keepChar = dp(s, idx + 1, s[idx], 1, k) + 1;
        }

        int res = std::min(keepChar, deleteChar);
        memo[key] = res;

        return res;
    }
};

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

Задача: 744. Find Smallest Letter Greater Than Target Сложность: easy Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах. Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

👨‍💻 Алгоритм: 1⃣Использовать бинарный поиск для нахождения позиции первого символа в letters, который лексикографически больше target. 2⃣Если найденный символ существует, вернуть его. 3⃣Если такого символа не существует, вернуть первый символ в letters. 😎 Решение:

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        int left = 0, right = letters.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return letters[left % letters.size()];
    }
};

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

Задача: 70. Climbing Stairs Сложность: easy Чтобы добраться до вершины лестницы с n ступенями, можно каждый раз делать шаг на 1 или 2 ступеньки. Нужно посчитать, сколькими способами можно подняться на вершину. Пример:

Input: n = 2 Output: 2
Варианты:
1 + 1
2

👨‍💻 Алгоритм: 1⃣На каждом шаге есть 2 варианта: подняться на 1 или на 2 ступеньки — задача сводится к подсчёту всех таких комбинаций 2⃣Используем рекурсивную функцию: climb(i, n) = climb(i + 1, n) + climb(i + 2, n) — сумма способов дойти с текущей позиции i до цели n 3⃣Базовые случаи: если i == n — достигли цели, вернуть 1 если i > n — вышли за пределы, вернуть 0 😎 Решение:

class Solution {
public:
    int climbStairs(int n) { return climb_Stairs(0, n); }

    int climb_Stairs(int i, int n) {
        if (i > n) return 0;
        if (i == n) return 1;
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
    }
};

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

Задача: 1493. Longest Subarray of 1's After Deleting One Element Сложность: medium Дан бинарный массив nums, из которого следует удалить один элемент. Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует. Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

👨‍💻 Алгоритм: 1⃣Инициализация переменных: zeroCount для подсчёта нулей в текущем окне, longestWindow для хранения максимальной длины окна, содержащего не более одного нуля, и start для левой границы окна. 2⃣Итерация по массиву: При каждом элементе увеличиваем zeroCount, если это ноль. Если zeroCount превышает 1, сокращаем окно, перемещая левую границу вправо и уменьшая zeroCount, пока количество нулей не станет меньше или равно 1. Обновляем longestWindow текущей длиной окна i - start. 3⃣Возврат результата: Вернуть longestWindow. 😎 Решение:

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int zeroCount = 0;
        int longestWindow = 0;
        int start = 0;

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 0) {
                zeroCount++;
            }

            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }

            longestWindow = max(longestWindow, i - start);
        }

        return longestWindow;
    }
};

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

Задача: 1167. Minimum Cost to Connect Sticks Сложность: medium У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки. Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка. Верните минимальную стоимость соединения всех данных палочек в одну палочку таким образом. Пример:

Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

👨‍💻 Алгоритм: 1⃣Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4). 2⃣Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость. 3⃣Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций. 😎 Решение:

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        int totalCost = 0;
        priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end());
        
        while (pq.size() > 1) {
            int stick1 = pq.top(); 
            pq.pop();
            int stick2 = pq.top(); 
            pq.pop();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.push(cost);
        }
        
        return totalCost;
    }
};

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

Задача: 841. Keys and Rooms Сложность: medium Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее. Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты. Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае. Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

👨‍💻 Алгоритм: 1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать. 2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную. 3⃣Пока стек не пуст, извлекайте ключи из стека и используйте их для открытия новых комнат, добавляя найденные ключи в стек. Если все комнаты посещены, верните true, иначе false. 😎 Решение:

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> seen(rooms.size(), false);
        seen[0] = true;
        stack<int> stk;
        stk.push(0);

        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            for (int nei : rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true;
                    stk.push(nei);
                }
            }
        }

        for (bool v : seen) {
            if (!v) return false;
        }
        return true;
    }
};

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

Задача: 1535. Find the Winner of an Array Game Сложность: medium Дан целочисленный массив arr из различных целых чисел и целое число k. Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов. Верните число, которое выиграет игру. Гарантируется, что у игры будет победитель. Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

👨‍💻 Алгоритм: 1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0. 2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1. 3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение. 😎 Решение:

class Solution {
public:
    int getWinner(vector<int>& arr, int k) {
        int maxElement = arr[0];
        queue<int> queue;
        for (int i = 1; i < arr.size(); i++) {
            maxElement = max(maxElement, arr[i]);
            queue.push(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (!queue.empty()) {
            int opponent = queue.front();
            queue.pop();
            
            if (curr > opponent) {
                queue.push(opponent);
                winstreak++;
            } else {
                queue.push(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
};

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

Задача: 243. Shortest Word Distance Сложность: easy Дан массив строк и два слова. Нужно вернуть минимальное расстояние между ними в массиве. Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice" Output: 3

👨‍💻 Алгоритм: 1⃣Проходим по массиву один раз, запоминая последние индексы, где встречались word1 и word2 2⃣При каждом новом вхождении одного из слов, если другое уже найдено — обновляем минимальное расстояние 3⃣Возвращаем минимальное расстояние 😎 Решение:

class Solution {
public:
    int shortestDistance(vector<string>& words, string word1, string word2) {
        int idx1 = -1, idx2 = -1, minDist = words.size();
        for (int i = 0; i < words.size(); ++i) {
            if (words[i] == word1) idx1 = i;
            else if (words[i] == word2) idx2 = i;
            if (idx1 != -1 && idx2 != -1) {
                minDist = min(minDist, abs(idx1 - idx2));
            }
        }
        return minDist;
    }
};

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

Задача: 484. Find Permutation Сложность: medium Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где: s[i] == 'I', если perm[i] < perm[i + 1], и s[i] == 'D', если perm[i] > perm[i + 1]. Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её. Пример:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

👨‍💻 Алгоритм: 1⃣Инициализация Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки. 2⃣Для каждого числа i Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result. 3⃣Завершение Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку. 😎 Решение:

class Solution {
public:
    vector<int> findPermutation(string s) {
        vector<int> res(s.length() + 1);
        stack<int> stack;
        int j = 0;
        for (int i = 1; i <= s.length(); i++) {
            if (s[i - 1] == 'I') {
                stack.push(i);
                while (!stack.empty()) {
                    res[j++] = stack.top();
                    stack.pop();
                }
            } else {
                stack.push(i);
            }
        }
        stack.push(s.length() + 1);
        while (!stack.empty()) {
            res[j++] = stack.top();
            stack.pop();
        }
        return res;
    }
};

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

Задача: 21. Merge Two Sorted Lists Сложность: easy Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка. Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps"

👨‍💻 Алгоритм: 1⃣Создаем фиктивный узел dummy и указатель cur, указывающий на него. 2⃣Пока list1 и list2 не пусты — сравниваем значения, добавляем меньший узел в результат, передвигаем соответствующий указатель. 3⃣После выхода из цикла, добавляем оставшиеся элементы от одного из списков (если остались). 😎 Решение:

class Solution { 
public: 
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { 
        ListNode* dummy = new ListNode(0); 
        ListNode* cur = dummy; 

        while (list1 && list2) { 
            if (list1->val > list2->val) { 
                cur->next = list2; 
                list2 = list2->next; 
            } else { 
                cur->next = list1; 
                list1 = list1->next; 
            } 
            cur = cur->next; 
        } 

        cur->next = list1 ? list1 : list2; 

        return dummy->next;         
    } 
};

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

Задача: 1254. Number of Closed Islands Сложность: medium Дана двумерная сетка, состоящая из 0 (земля) и 1 (вода).Остров - это максимальная 4-направленно связная группа из 0s, а закрытый остров - это остров, полностью (слева, сверху, справа, снизу) окруженный 1s. Верните количество закрытых островов. Пример:

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

👨‍💻 Алгоритм: 1⃣Пройдите по границам сетки и с помощью поиска в глубину (DFS) или поиска в ширину (BFS) замените все связанные земли (0) на воду (1). 2⃣Пройдите по всей сетке, используя DFS или BFS для поиска всех оставшихся островов (групп 0) 3⃣Подсчитайте количество таких островов. 😎 Решение:

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    dfs(grid, i, j);
                }
            }
        }

        int count = 0;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (grid[i][j] == 0) {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }

private:
    void dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 1) {
            return;
        }
        grid[x][y] = 1;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
};

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

Задача: 188. Best Time to Buy and Sell Stock IV Сложность: hard Дан массив целых чисел prices, где prices[i] — цена акции в i-й день, и целое число k. Найдите максимальную прибыль, которую можно получить, совершив не более k транзакций (одна транзакция = покупка + продажа). Нельзя участвовать в нескольких транзакциях одновременно — нужно сначала продать акцию, прежде чем покупать новую. Пример:

Input: k = 2, prices = [2,4,1] Output: 2

👨‍💻 Алгоритм: 1⃣Инициализация DP массива Создаем 3D массив dp[i][j][l], где: i — день, j — количество доступных транзакций, l — держим акцию (1) или нет (0). Базовые значения: dp[0][0][0] = 0, dp[0][1][1] = -prices[0]. 2⃣Переходы состояний dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) — максимальная прибыль без акции. dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) — максимальная прибыль с акцией. 3⃣Оптимизация при большом k Если k * 2 >= n, можно совершать сделки каждый день — используем жадный подсчет всех выгодных дней. Решение:

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();

        if (n <= 0 || k <= 0) {
            return 0;
        }

        if (k * 2 >= n) {
            int res = 0;
            for (int i = 1; i < n; i++) {
                res += max(0, prices[i] - prices[i - 1]);
            }
            return res;
        }

        vector<vector<vector<int>>> dp(
            n, vector<vector<int>>(k + 1, vector<int>(2, 0)));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][0] = INT_MIN / 2;
                dp[i][j][1] = INT_MIN / 2;
            }
        }

        dp[0][0][0] = 0;
        dp[0][1][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                if (j > 0) {
                    dp[i][j][1] =
                        max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
                }
            }
        }

        int res = 0;
        for (int j = 0; j <= k; j++) {
            res = max(res, dp[n - 1][j][0]);
        }

        return res;
    }
};

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

Задача: 1422. Maximum Score After Splitting a String Сложность: easy Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку). Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке. Пример:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

👨‍💻 Алгоритм: 1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения. 2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц. 3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума. 😎 Решение:

class Solution {
public:
    int maxScore(string s) {
        int ones = count(s.begin(), s.end(), '1');
        int zeros = 0, ans = 0, countOnes = ones;

        for (int i = 0; i < s.length() - 1; ++i) {
            if (s[i] == '1') {
                countOnes--;
            } else {
                zeros++;
            }
            ans = max(ans, zeros + countOnes);
        }
        return ans;
    }
};

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

Задача: 233. Number of Digit One Сложность: hard Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n. Пример:

Input: n = 13
Output: 6

👨‍💻 Алгоритм: 1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n. 2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10). 3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i. 😎 Решение:

int countDigitOne(int n) {
    int countr = 0;
    for (long long i = 1; i <= n; i *= 10) {
        long long divider = i * 10;
        countr += (n / divider) * i + std::min(std::max(n % divider - i + 1, 0LL), i);
    }
    return countr;
}

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

Задача: 859. Buddy Strings Сложность: easy Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false. Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j]. Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad". Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

👨‍💻 Алгоритм: 1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false. 2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false. 3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена. 😎 Решение:

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if (s.size() != goal.size()) return false;
        if (s == goal) {
            vector<int> freq(26, 0);
            for (char ch : s) {
                if (++freq[ch - 'a'] > 1) return true;
            }
            return false;
        }

        int firstIndex = -1, secondIndex = -1;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != goal[i]) {
                if (firstIndex == -1) firstIndex = i;
                else if (secondIndex == -1) secondIndex = i;
                else return false;
            }
        }

        return secondIndex != -1 &&
               s[firstIndex] == goal[secondIndex] &&
               s[secondIndex] == goal[firstIndex];
    }
};

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