Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium

Вам дан массив целых чисел nums и целое число target.

Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

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

1⃣Инициализация и подготовка:
Инициализируйте переменные answer равным 0 и n как длину массива nums.
Отсортируйте массив nums.
Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7.

2⃣Итерация и бинарный поиск:
Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left].
Если left <= right, добавьте количество допустимых подпоследовательностей к answer.

3⃣Возврат результата:
Верните answer по модулю 10^9+7.

😎 Решение:

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int mod = 1'000'000'007;
        
        vector<int> power(n, 1);
        for (int i = 1; i < n; ++i) {
            power[i] = (power[i - 1] * 2) % mod;
        }
        
        int answer = 0;
        int left = 0, right = n - 1;
        
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                answer = (answer + power[right - left]) % mod;
                left++;
            } else {
                right--;
            }
        }
        
        return answer;
    }
};

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

Задача: 99. Recover Binary Search Tree
Сложность: medium

Вам дан корень бинарного дерева поиска (BST), в котором значения ровно двух узлов дерева были поменяны местами по ошибке. Восстановите дерево, не изменяя его структуру.

Пример:

Input: root = [1,3,null,null,2] Output: [3,1,null,null,2]

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

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

2⃣Найдите два нарушающих порядок элемента (x и y), используя один проход.

3⃣Повторно обойдите дерево и поменяйте значения x и y в узлах.

😎 Решение:

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& nums) {
        if (root == nullptr) return;
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }
    vector<int> findTwoSwapped(vector<int> nums) {
        int n = nums.size();
        int x = -1, y = -1;
        bool swapped_first_occurrence = false;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i + 1] < nums[i]) {
                y = nums[i + 1];
                if (!swapped_first_occurrence) {
                    x = nums[i];
                    swapped_first_occurrence = true;
                } else {
                    break;
                }
            }
        }
        return vector<int>{x, y};
    }
    void recover(TreeNode* r, int count, int x, int y) {
        if (r != nullptr) {
            if (r->val == x || r->val == y) {
                r->val = r->val == x ? y : x;
                if (--count == 0) return;
            }
            recover(r->left, count, x, y);
            recover(r->right, count, x, y);
        }
    }
    void recoverTree(TreeNode* root) {
        vector<int> nums;
        inorder(root, nums);
        vector<int> swapped = findTwoSwapped(nums);
        recover(root, 2, swapped[0], swapped[1]);
    }
};

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

Задача: 37. Sudoku Solver
Сложность: hard

Напишите программу, которая решает судоку, заполняя пустые клетки, соблюдая правила: цифры от 1 до 9 должны встречаться ровно один раз в каждой строке, столбце и каждом из девяти 3×3 блоков.

Пример:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

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

1⃣Создаем матрицы для отслеживания наличия цифр 1–9 в строках, столбцах и блоках 3×3. Заполняем их по уже заданным цифрам на доске.

2⃣Запускаем рекурсивную функцию backtrack, которая ищет пустые клетки и пытается поместить туда цифры от 1 до 9, проверяя допустимость по строке, столбцу и блоку.

3⃣Если дошли до конца доски — судоку решено. Иначе откатываемся (backtrack) и пробуем другие варианты.

😎 Решение:

class Solution {
    int n = 3;
    int N = n * n;
    std::vector<std::vector<int>> rows, cols, boxes;
    std::vector<std::vector<char>> board;
    bool sudoku_solved = false;

public:
    Solution() : rows(N, std::vector<int>(N + 1, 0)), cols(N, std::vector<int>(N + 1, 0)), boxes(N, std::vector<int>(N + 1, 0)) {}

    bool could_place(int d, int row, int col) {
        int idx = (row / n) * n + col / n;
        return rows[row][d] == 0 && cols[col][d] == 0 && boxes[idx][d] == 0;
    }

    void place_or_remove(int d, int row, int col, bool place) {
        int idx = (row / n) * n + col / n;
        int delta = place ? 1 : -1;
        rows[row][d] += delta;
        cols[col][d] += delta;
        boxes[idx][d] += delta;
        board[row][col] = place ? d + '0' : '.';
    }

    void backtrack(int row = 0, int col = 0) {
        if (col == N) col = 0, row++;
        if (row == N) {
            sudoku_solved = true;
            return;
        }

        if (board[row][col] == '.') {
            for (int d = 1; d <= 9 && !sudoku_solved; d++) {
                if (could_place(d, row, col)) {
                    place_or_remove(d, row, col, true);
                    backtrack(row, col + 1);
                    if (!sudoku_solved) place_or_remove(d, row, col, false);
                }
            }
        } else
            backtrack(row, col + 1);
    }

    void solveSudoku(std::vector<std::vector<char>>& in_board) {
        board = in_board;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] != '.') {
                    int d = board[i][j] - '0';
                    place_or_remove(d, i, j, true);
                }
            }
        }
        backtrack();
        in_board = board;
    }
};

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

Задача: 1014. Best Sightseeing Pair
Сложность: easy

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int max_score = 0;
        int max_i_plus_value = values[0];
        
        for (int j = 1; j < values.size(); ++j) {
            max_score = max(max_score, max_i_plus_value + values[j] - j);
            max_i_plus_value = max(max_i_plus_value, values[j] + j);
        }
        
        return max_score;
    }
};

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

Задача: 1502. Can Make Arithmetic Progression From Sequence
Сложность: easy

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

Дан массив чисел arr, верните true, если массив можно переставить так, чтобы он образовал арифметическую прогрессию. В противном случае верните false.

Пример:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

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

1⃣Отсортируйте массив arr.

2⃣Запишите разницу первой пары элементов: diff = arr[1] - arr[0].

3⃣Итерируйтесь по отсортированному массиву начиная с i = 2, проверяя, равна ли разница каждой пары элементов значению diff. Если нет, верните False. Если итерация завершена без нахождения различий, верните True.

😎 Решение:

class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int diff = arr[1] - arr[0];
        
        for (int i = 2; i < arr.size(); ++i) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        
        return true;
    }
};

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

Задача: 463. Island Perimeter
Сложность: easy

Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду.
Клетки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и на ней находится ровно один остров (т.е. одна или более соединённых ячеек суши).
У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова.

Пример:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

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

1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки.

2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши.

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

😎 Решение:

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        
        int result = 0;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int up = (r == 0) ? 0 : grid[r-1][c];
                    int left = (c == 0) ? 0 : grid[r][c-1];
                    int down = (r == rows-1) ? 0 : grid[r+1][c];
                    int right = (c == cols-1) ? 0 : grid[r][c+1];
                    
                    result += 4 - (up + left + right + down);
                }
            }
        }
        
        return result;
    }
};

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

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

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

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

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

1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

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

😎 Решение:

class Solution {
public:
    int numDistinctIslands2(vector<vector<int>>& grid) {
        unordered_set<string> uniqueIslands;
        
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    vector<pair<int, int>> shape;
                    dfs(grid, i, j, i, j, shape);
                    uniqueIslands.insert(normalize(shape));
                }
            }
        }
        
        return uniqueIslands.size();
    }
    
private:
    void dfs(vector<vector<int>>& grid, int i, int j, int baseI, int baseJ, vector<pair<int, int>>& shape) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {
            return;
        }
        grid[i][j] = 0;
        shape.emplace_back(i - baseI, j - baseJ);
        dfs(grid, i + 1, j, baseI, baseJ, shape);
        dfs(grid, i - 1, j, baseI, baseJ, shape);
        dfs(grid, i, j + 1, baseI, baseJ, shape);
        dfs(grid, i, j - 1, baseI, baseJ, shape);
    }
    
    string normalize(vector<pair<int, int>>& shape) {
        vector<vector<pair<int, int>>> shapes(8);
        for (auto& p : shape) {
            int x = p.first, y = p.second;
            shapes[0].emplace_back(x, y);
            shapes[1].emplace_back(x, -y);
            shapes[2].emplace_back(-x, y);
            shapes[3].emplace_back(-x, -y);
            shapes[4].emplace_back(y, x);
            shapes[5].emplace_back(y, -x);
            shapes[6].emplace_back(-y, x);
            shapes[7].emplace_back(-y, -x);
        }
        for (auto& s : shapes) {
            sort(s.begin(), s.end());
        }
        string minShape = to_string(shapes[0][0].first) + "," + to_string(shapes[0][0].second);
        for (auto& s : shapes) {
            string sStr;
            for (auto& p : s) {
                sStr += to_string(p.first) + "," + to_string(p.second) + ";";
            }
            minShape = min(minShape, sStr);
        }
        return minShape;
    }
};

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

Задача: 930. Binary Subarrays With Sum
Сложность: medium

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

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

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int, int> prefixSumCount;
        prefixSumCount[0] = 1;
        int currentSum = 0;
        int count = 0;
        
        for (int num : nums) {
            currentSum += num;
            count += prefixSumCount[currentSum - goal];
            prefixSumCount[currentSum]++;
        }
        
        return count;
    }
};

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени.

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски.

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

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

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение:

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans = 0;
        for (int num : left) {
            ans = max(ans, num);
        }
        for (int num : right) {
            ans = max(ans, n - num);
        }
        return ans;
    }
};

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

Задача: 660. Remove 9
Сложность: hard

Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29...

Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...].

Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности.

Пример:

Input: n = 9
Output: 10

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

1⃣Инициализация:
Начните с числа 1 и создайте переменную для отслеживания количества найденных чисел, не содержащих цифру 9.

2⃣Итерация и проверка:
Последовательно увеличивайте число и проверяйте, содержит ли оно цифру 9.
Если не содержит, увеличьте счетчик.

3⃣Поиск n-го числа:
Продолжайте процесс до тех пор, пока не найдете n-е число, не содержащее цифру 9.

😎 Решение:

class Solution {
public:
    int newInteger(int n) {
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (to_string(num).find('9') == string::npos) {
                count++;
            }
        }
        return num;
    }
};

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

Задача: 861. Score After Flipping Matrix
Сложность: hard

Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1], k = 1
Output: 1

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

1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались.

2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались.

3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека.

😎 Решение:

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int N = A.size();
        vector<long> P(N + 1);
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];

        int ans = N + 1;
        deque<int> monoq;

        for (int y = 0; y < P.size(); ++y) {
            while (!monoq.empty() && P[y] <= P[monoq.back()])
                monoq.pop_back();
            while (!monoq.empty() && P[y] >= P[monoq.front()] + K)
                ans = min(ans, y - monoq.pop_front());
            monoq.push_back(y);
        }

        return ans < N + 1 ? ans : -1;
    }
};

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

Задача: 230. Kth Smallest Element in a BST
Сложность: medium

Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве.

Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

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

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

2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение.

3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение.

😎 Решение:

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stack;
        
        while (true) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            if (--k == 0) return root->val;
            root = root->right;
        }
    }
};

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

Задача: 543. Diameter of Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.

Пример:

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

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

1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.

2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.

3⃣Вызвать longestPath с root.

😎 Решение:

class Solution {
    int diameter;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        diameter = 0;
        longestPath(root);
        return diameter;
    }
    
private:
    int longestPath(TreeNode* node) {
        if (node == nullptr) return 0;
        
        int leftPath = longestPath(node->left);
        int rightPath = longestPath(node->right);
        
        diameter = std::max(diameter, leftPath + rightPath);
        
        return std::max(leftPath, rightPath) + 1;
    }
};

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

Задача: 899. Orderly Queue
Сложность: hard

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

Пример:

Input: s = "cba", k = 1
Output: "acb"

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

1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта.

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

3⃣Вернуть результат.

😎 Решение:

class Solution {
public:
    string orderlyQueue(string s, int k) {
        if (k == 1) {
            string minString = s;
            for (int i = 1; i < s.length(); i++) {
                string rotated = s.substr(i) + s.substr(0, i);
                if (rotated < minString) {
                    minString = rotated;
                }
            }
            return minString;
        } else {
            sort(s.begin(), s.end());
            return s;
        }
    }
};

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

Задача: 509. Fibonacci Number
Сложность: easy

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int current = 0, prev1 = 1, prev2 = 0;
        for (int i = 2; i <= N; ++i) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
};

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

Задача: 75. Sort Colors
Сложность: medium

Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет.
Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета шли в порядке:
красный (0), белый (1), синий (2).
Запрещено использовать встроенные функции сортировки.

Пример:

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

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

1⃣Инициализация указателя p0 = 0, отвечающего за край для нулей.

2⃣Инициализация указателя p2 = n - 1, отвечающего за край для двоек.

3⃣Индекс текущего элемента: curr = 0.
Пока curr <= p2:
если nums[curr] == 0 → меняем с nums[p0], сдвигаем p0 и curr вправо
если nums[curr] == 2 → меняем с nums[p2], сдвигаем p2 влево
если nums[curr] == 1 → просто двигаем curr

😎 Решение:

class Solution {
public:
  void sortColors(vector<int>& nums) {
    int p0 = 0, curr = 0;
    int p2 = nums.size() - 1;

    while (curr <= p2) {
      if (nums[curr] == 0) {
        swap(nums[curr++], nums[p0++]);
      }
      else if (nums[curr] == 2) {
        swap(nums[curr], nums[p2--]);
      }
      else curr++;
    }
  }
};

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

Задача: 679. 24 Game
Сложность: hard

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution {
public:
    vector<double> generatePossibleResults(double a, double b) {
        vector<double> res = { a + b, a - b, b - a, a * b };
        if (a != 0) res.push_back(b / a);
        if (b != 0) res.push_back(a / b);
        return res;
    }

    bool checkIfResultReached(vector<double> list) {
        if (list.size() == 1) return abs(list[0] - 24) <= 0.1;

        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                vector<double> newList;
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) newList.push_back(list[k]);
                }
                for (double res : generatePossibleResults(list[i], list[j])) {
                    newList.push_back(res);
                    if (checkIfResultReached(newList)) return true;
                    newList.pop_back();
                }
            }
        }
        return false;
    }

    bool judgePoint24(vector<int>& cards) {
        vector<double> list(cards.begin(), cards.end());
        return checkIfResultReached(list);
    }
};

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

Задача: 536. Construct Binary Tree from String
Сложность: medium

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

Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

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

1⃣ Извлечение числа:
Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть.

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

3⃣ Основная функция:
Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево.

😎 Решение:

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

class Solution {
public:
    TreeNode* str2tree(string s) {
        return str2treeInternal(s, 0).first;
    }

private:
    pair<int, int> getNumber(const string& s, int index) {
        bool isNegative = false;
        if (s[index] == '-') {
            isNegative = true;
            index++;
        }
        int number = 0;
        while (index < s.size() && isdigit(s[index])) {
            number = number * 10 + (s[index] - '0');
            index++;
        }
        return {isNegative ? -number : number, index};
    }

    pair<TreeNode*, int> str2treeInternal(const string& s, int index) {
        if (index == s.size()) return {nullptr, index};

        auto numberData = getNumber(s, index);
        int value = numberData.first;
        index = numberData.second;

        TreeNode* node = new TreeNode(value);

        if (index < s.size() && s[index] == '(') {
            auto leftData = str2treeInternal(s, index + 1);
            node->left = leftData.first;
            index = leftData.second;
        }

        if (index < s.size() && s[index] == '(') {
            auto rightData = str2treeInternal(s, index + 1);
            node->right = rightData.first;
            index = rightData.second;
        }

        return {node, index < s.size() && s[index] == ')' ? index + 1 : index};
    }
};

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

Задача: 1190. Reverse Substrings Between Each Pair of Parentheses
Сложность: medium

Дана строка s, состоящая из строчных букв английского алфавита и скобок.

Переверните строки в каждой паре соответствующих скобок, начиная с самой внутренней.

Ваш результат не должен содержать скобок.

Пример:

Input: s = "(abcd)"
Output: "dcba"

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

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

2⃣Для каждого символа currentChar во входной строке:

Если это '(', добавьте длину строки result в openParenthesesIndices, чтобы отметить потенциальную начальную точку разворота.
Если это ')', извлеките значение из openParenthesesIndices и переверните result от извлеченного индекса для выполнения необходимого разворота.
В противном случае добавьте currentChar к result для построения строки.

3⃣Верните result как окончательную строку со всеми примененными разворотами.

😎 Решение:

class Solution {
public:
    string reverseParentheses(string s) {
        stack<int> openParenthesesIndices;
        string result;

        for (char currentChar : s) {
            if (currentChar == '(') {
                openParenthesesIndices.push(result.size());
            } else if (currentChar == ')') {
                int start = openParenthesesIndices.top();
                openParenthesesIndices.pop();
                reverse(result.begin() + start, result.end());
            } else {
                result.push_back(currentChar);
            }
        }

        return result;
    }
};

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

Задача: 908. Smallest Range I
Сложность: easy

Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.

Пример:

Input: nums = [1], k = 0
Output: 0

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

1⃣Найти минимальное и максимальное значения массива nums.

2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции.

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

😎 Решение:

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        return max(0, (maxVal - k) - (minVal + k));
    }
};

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