C/C++ | LeetCode

Задача: 58. Length of Last Word
Сложность: easy

Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова.
Слово — это максимальная подстрока без пробелов.

Пример:

Input: s = "Hello World" Output: 5

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

1⃣Идти с конца строки, пропуская пробелы, чтобы найти конец последнего слова

2⃣Затем считать символы до следующего пробела или начала строки — это и будет длина слова

3⃣Вернуть полученную длину

😎 Решение:

class Solution {
public:
    int lengthOfLastWord(string s) {
        int p = s.length() - 1;
        while (p >= 0 && s[p] == ' ') {
            p--;
        }
        int length = 0;
        while (p >= 0 && s[p] != ' ') {
            p--;
            length++;
        }
        return length;
    }
};

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

Задача: 846. Hand of Straights
Сложность: medium

У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт.

Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае.

Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

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

1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false.

2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand.

3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп:
Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount.
Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false.
Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount.

😎 Решение:

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) {
            return false;
        }

        unordered_map<int, int> cardCount;
        for (int card : hand) {
            cardCount[card]++;
        }

        sort(hand.begin(), hand.end());

        for (int card : hand) {
            if (cardCount[card] == 0) {
                continue;
            }

            for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
                if (cardCount[nextCard] == 0) {
                    return false;
                }
                cardCount[nextCard]--;
            }
        }

        return true;
    }
};

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

Задача: 1252. Cells with Odd Values in a Matrix
Сложность: easy

Имеется матрица m x n, которая инициализирована всеми 0. Имеется двумерный массив indices, в котором каждый indices[i] = [ri, ci] представляет собой местоположение с индексом 0 для выполнения некоторых операций инкремента над матрицей. Для каждого местоположения indices[i] выполните оба следующих действия: увеличьте все ячейки в строке ri. Увеличьте все ячейки в столбце ci. Учитывая m, n и indices, верните количество нечетных ячеек в матрице после применения инкремента ко всем местоположениям в indices.

Пример:

Input: nums = [12,5,7,23]
Output: true

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

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

2⃣Для каждого элемента в indices увеличьте счетчики соответствующих строк и столбцов.

3⃣Подсчитайте количество нечетных ячеек, используя информацию о количестве инкрементов каждой строки и столбца.

😎 Решение:

class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<int> row_count(m, 0);
        vector<int> col_count(n, 0);

        for (auto& index : indices) {
            row_count[index[0]]++;
            col_count[index[1]]++;
        }

        int odd_count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((row_count[i] + col_count[j]) % 2 == 1) {
                    odd_count++;
                }
            }
        }

        return odd_count;
    }
};

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

Input: nums = [1,-2,3,-2]
Output: 3

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

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

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

😎 Решение:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int kadane(vector<int>& arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.size(); ++i) {
                currentSum = max(arr[i], currentSum + arr[i]);
                maxSum = max(maxSum, currentSum);
            }
            return maxSum;
        }

        int maxKadane = kadane(nums);
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        for (int& num : nums) num = -num;
        int minKadane = kadane(nums);

        return max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
};

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

Задача: 1473. Paint House III
Сложность: hard

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

Соседство — это максимальная группа непрерывных домов, которые покрашены в один и тот же цвет.

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

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

1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.

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

3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎 Решение:

class Solution {
public:
    int memo[100][100][21];
    const int MAX_COST = 1000001;
    
    int findMinCost(vector<int>& houses, vector<vector<int>>& cost, int targetCount, int currIndex, int neighborhoodCount, int prevHouseColor) {
        if (currIndex == houses.size()) {
            return neighborhoodCount == targetCount ? 0 : MAX_COST;
        }
        
        if (neighborhoodCount > targetCount) {
            return MAX_COST;
        }
        
        if (memo[currIndex][neighborhoodCount][prevHouseColor] != -1) {
            return memo[currIndex][neighborhoodCount][prevHouseColor];
        }
        
        int minCost = MAX_COST;

        if (houses[currIndex] != 0) {
            int newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0);
            minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex]);
        } else {
            int totalColors = cost[0].size();
            for (int color = 1; color <= totalColors; ++color) {
                int newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0);
                int currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color);
                minCost = min(minCost, currCost);
            }
        }
        
        return memo[currIndex][neighborhoodCount][prevHouseColor] = minCost;
    }
    
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        memset(memo, -1, sizeof(memo));
        int answer = findMinCost(houses, cost, target, 0, 0, 0);
        return answer == MAX_COST ? -1 : answer;
    }
};

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

Задача: 128. Longest Consecutive Sequence
Сложность: medium

Найти длину самой длинной последовательности последовательных чисел в неотсортированном массиве. Время работы — O(n).

Пример:

Input: [100,4,200,1,3,2] → Output: 4

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

1⃣Помещаем все числа в unordered_set, чтобы можно было быстро проверять наличие элемента (O(1) время доступа).

2⃣Проходим по каждому числу, и если num - 1 не существует в сете — это начало новой последовательности. Затем увеличиваем currentNum, пока currentNum + 1 есть в сете, считая длину последовательности.

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

😎 Решение:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.count(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};

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

Задача: 100. Same Tree
Сложность: easy

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.
Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.

Пример:

Input: p = [1,2,3], q = [1,2,3] Output: true

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

1⃣Если оба узла равны null, значит на этом участке деревья одинаковы.

2⃣Если один из узлов равен null, а второй — нет, или значения узлов различаются, значит деревья не равны.

3⃣Рекурсивно проверьте левое и правое поддерево.

😎 Решение:

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!q || !p) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->right, q->right) && isSameTree(p->left, q->left);
    }
};

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

Задача: 1318. Minimum Flips to Make a OR b Equal to c
Сложность: medium

Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении.

Пример:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

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

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

2⃣Итеративно обрабатывайте каждый бит двоичного представления чисел a, b и c одновременно:

Если (c & 1) == 0, обновите answer как answer += (a & 1) + (b & 1).
Если (c & 1) == 1, и если оба значения a & 1 и b & 1 равны 0, увеличьте answer на 1.

3⃣Сдвигайте все числа вправо с помощью a >>= 1, b >>= 1, c >>= 1. Если все числа равны 0, верните answer, в противном случае, повторите шаги 2 и 3.

😎 Решение:

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int answer = 0;
        while (a != 0 || b != 0 || c != 0) {
            if ((c & 1) == 1) {
                if ((a & 1) == 0 && (b & 1) == 0) {
                    answer++;
                }
            } else {
                answer += (a & 1) + (b & 1);
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return answer;
    }
};

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

Задача: 1295. Find Numbers with Even Number of Digits
Сложность: easy

Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр.

Пример:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

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

1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false.

2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0.

3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount.

😎 Решение:

class Solution {
public:
    bool hasEvenDigits(int num) {
        int digitCount = 0;
        while (num) {
            digitCount++;
            num /= 10;
        }
        return (digitCount & 1) == 0;
    }

    int findNumbers(vector<int>& nums) {
        int evenDigitCount = 0;
        for (int num : nums) {
            if (hasEvenDigits(num))
                evenDigitCount++;
        }
        return evenDigitCount;
    }
};

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

Задача: 320. Generalized Abbreviation
Сложность: medium

Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.
Например, "abcde" можно сократить следующим образом:
"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:
"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.

Пример:

Input: word = "a"
Output: ["1","a"]

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

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> ans;
        for (int x = 0; x < (1 << word.length()); ++x)
            ans.push_back(abbr(word, x));
        return ans;
    }

private:
    string abbr(const string& word, int x) {
        string builder;
        int k = 0, n = word.length();
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) {
                if (k != 0) {
                    builder += to_string(k);
                    k = 0;
                }
                builder += word[i];
            } else {
                ++k;
            }
        }
        if (k != 0) builder += to_string(k);
        return builder;
    }
};

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

Задача: 987. Vertical Order Traversal of a Binary Tree
Сложность: medium

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

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

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

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

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

1⃣Инициализация указателей:
Создать словарь для хранения узлов по их координатам (col, row).
Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)).

2⃣Поиск пересечений:
Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row).
Добавить левый потомок в очередь с координатами (row + 1, col - 1).
Добавить правый потомок в очередь с координатами (row + 1, col + 1).

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

😎 Решение:

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, vector<pair<int, int>>> colTable;
        queue<pair<TreeNode*, pair<int, int>>> queue;
        queue.push({root, {0, 0}});
        
        while (!queue.empty()) {
            auto [node, pos] = queue.front();
            queue.pop();
            int row = pos.first, col = pos.second;
            colTable[col].emplace_back(row, node->val);
            
            if (node->left) {
                queue.push({node->left, {row + 1, col - 1}});
            }
            if (node->right) {
                queue.push({node->right, {row + 1, col + 1}});
            }
        }
        
        vector<vector<int>> result;
        for (auto& [col, pairs] : colTable) {
            sort(pairs.begin(), pairs.end());
            vector<int> sortedCol;
            for (auto& [row, val] : pairs) {
                sortedCol.push_back(val);
            }
            result.push_back(sortedCol);
        }
        
        return result;
    }
};

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

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

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

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

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: num = 23
Output: "1000"

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

1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n)

2⃣Из таблицы видно, что последовательность строк соответствует последовательности чисел в двоичной системе счисления за исключением начального значения n = 0.

3⃣Таким образом, можно вывести, что:
Для каждого значения n > 0, функция f(n) представляет собой двоичное представление числа (n - 1).

😎 Решение:

class Solution {
public:
    string encode(int num) {
        if (num == 0) return "";
        string binary = "";
        num -= 1;
        while (num > 0) {
            binary = (num % 2 == 0 ? "0" : "1") + binary;
            num /= 2;
        }
        return binary;
    }
};

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

Дана строка s. Переставьте символы строки, используя следующий алгоритм:

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

2⃣Перебор и добавление символов:
Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре.

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

#include <string>
#include <vector>

class Solution {
public:
    std::string sortString(std::string s) {
        std::vector<int> charCount(26, 0);
        for (char c : s) {
            charCount[c - 'a']++;
        }
        
        std::string result;
        while (result.size() < s.size()) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (charCount[c - 'a'] > 0) {
                    result += c;
                    charCount[c - 'a']--;
                }
            }
            for (char c = 'z'; c >= 'a'; c--) {
                if (charCount[c - 'a'] > 0) {
                    result += c;
                    charCount[c - 'a']--;
                }
            }
        }
        
        return result;
    }
};

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:

Input: num = "257"
Output: "IOI"

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

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

class Solution {
public:
    string toHexString(string num) {
        stringstream ss;
        ss << hex << uppercase << stol(num);
        string hexStr = ss.str();
        for (char& c : hexStr) {
            if (c == '0') c = 'O';
            else if (c == '1') c = 'I';
            else if (string("ABCDEFIO").find(c) == string::npos) return "ERROR";
        }
        return hexStr;
    }
};

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

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

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

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

3⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге.

😎 Решение:

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int mod = 1e9 + 7;
        int max_pos = min(arrLen - 1, steps);
        vector<int> dp(max_pos + 1, 0);
        dp[0] = 1;
        for (int step = 0; step < steps; ++step) {
            vector<int> new_dp(max_pos + 1, 0);
            for (int i = 0; i <= max_pos; ++i) {
                new_dp[i] = dp[i] % mod;
                if (i > 0) new_dp[i] = (new_dp[i] + dp[i - 1]) % mod;
                if (i < max_pos) new_dp[i] = (new_dp[i] + dp[i + 1]) % mod;
            }
            dp = new_dp;
        }
        return dp[0];
    }
};

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, обозначающие диапазон [left, right].
Нужно вернуть результат побитового AND всех чисел в этом диапазоне (включительно).

Пример:

Input: left = 5, right = 7 Output: 4

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

1⃣Пока left < right, сдвигаем оба числа вправо (>>= 1), пока они не станут равны. Это находит общий префикс битов.

2⃣Подсчитываем количество сдвигов — это количество младших битов, которые могут изменяться в диапазоне, и обнуляются при AND.

3⃣После этого сдвигаем результат left обратно влево (<< shift) — возвращаем биты на место.

😎 Решение:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
};

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

Задача: 1043. Partition Array for Maximum Sum
Сложность: medium

Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

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

1⃣Инициализация:
Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i.

2⃣Заполнение массива dp:
Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой.

3⃣Поддержание максимального значения в подмассиве:
Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i].

😎 Решение:

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> dp(n, 0);
        
        for (int i = 0; i < n; ++i) {
            int max_val = 0;
            for (int j = 1; j <= k; ++j) {
                if (i - j + 1 >= 0) {
                    max_val = max(max_val, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = max(dp[i], dp[i - j] + max_val * j);
                    } else {
                        dp[i] = max(dp[i], max_val * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
};

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

Задача: 748. Shortest Completing Word
Сложность: easy

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

Пример:

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

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

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

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> licenseCount = getCharCount(licensePlate);
        
        string result;
        for (const string& word : words) {
            if (isCompletingWord(word, licenseCount)) {
                if (result.empty() || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
    
private:
    unordered_map<char, int> getCharCount(const string& s) {
        unordered_map<char, int> count;
        for (char c : s) {
            if (isalpha(c)) {
                count[tolower(c)]++;
            }
        }
        return count;
    }
    
    bool isCompletingWord(const string& word, const unordered_map<char, int>& licenseCount) {
        unordered_map<char, int> wordCount;
        for (char c : word) {
            wordCount[c]++;
        }
        for (const auto& entry : licenseCount) {
            if (wordCount[entry.first] < entry.second) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy

Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.

Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.

Пример:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

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

1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.

2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].

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

😎 Решение:

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        int N = matrix.size(), M = matrix[0].size();

        vector<int> rowMin;
        for (int i = 0; i < N; i++) {
            int rMin = INT_MAX;
            for (int j = 0; j < M; j++) {
                rMin = min(rMin, matrix[i][j]);
            }
            rowMin.push_back(rMin);
        }

        vector<int> colMax;
        for (int i = 0; i < M; i++) {
            int cMax = INT_MIN;
            for (int j = 0; j < N; j++) {
                cMax = max(cMax, matrix[j][i]);
            }
            colMax.push_back(cMax);
        }

        vector<int> luckyNumbers;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                    luckyNumbers.push_back(matrix[i][j]);
                }
            }
        }

        return luckyNumbers;
    }
};

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