C/C++ | LeetCode

Задача: 717. 1-bit and 2-bit Characters
Сложность: easy

У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.

Пример:

Input: bits = [1,0,0]
Output: true

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

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

2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1.

3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат.

😎 Решение:

bool isOneBitCharacter(vector<int>& bits) {
    int i = 0;
    while (i < bits.size() - 1) {
        i += bits[i] + 1;
    }
    return i == bits.size() - 1;
}

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

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

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

Пример:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

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

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

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

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

😎 Решение:

class MyCalendarTwo {
public:
    MyCalendarTwo() {}

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

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

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

Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium

Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

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

😎 Решение:

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        int left = 0, right = 0;
        unordered_map<char, int> charCount;
        int maxLength = 0;
        
        while (right < s.length()) {
            charCount[s[right]]++;
            while (charCount.size() > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.erase(s[left]);
                }
                left++;
            }
            maxLength = max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
};

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

Задача: 1208. Get Equal Substrings Within Budget
Сложность: medium

Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).

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

Пример:

Input: s = "abcd", t = "bcdf", maxCost = 3
Output: 3
Explanation: "abc" of s can change to "bcd".
That costs 3, so the maximum length is 3.

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

1⃣Инициализация переменных:
maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost.
start для хранения начального индекса текущей подстроки.
currCost для хранения текущих затрат на преобразование подстроки s в t.

2⃣Итерация по индексам от 0 до N-1:
Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost.
Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost.
Обновить maxLen длиной текущей подстроки.

3⃣Возврат maxLen как результата.

😎 Решение:

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int N = s.length();
        
        int maxLen = 0;
        int start = 0;
        int currCost = 0;
        
        for (int i = 0; i < N; i++) {
            currCost += abs(s[i] - t[i]);
            
            while (currCost > maxCost) {
                currCost -= abs(s[start] - t[start]);
                start++;
            }
            
            maxLen = max(maxLen, i - start + 1);
        }
        
        return maxLen;
    }
};

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

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

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