Задача: 67. Add Binary
Сложность: easy

Даны две строки a и b, представляющие двоичные числа. Верните их сумму также в виде двоичной строки.

Пример:

Input: a = "11", b = "1" Output: "100"

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

1⃣Инициализируем переменные: carry = 0, указатели на последние символы строк a и b, и пустую строку result

2⃣Идем с конца строк, складываем соответствующие биты и carry, добавляем результат по модулю 2 в result, переносим carry на следующий разряд

3⃣После завершения всех итераций, если carry == 1, добавляем '1' в result, затем переворачиваем строку и возвращаем результат

😎 Решение:

class Solution {
public:
    string addBinary(string a, string b) {
        int n = a.size(), m = b.size();
        if (n < m)
            return addBinary(b, a);

        string result;
        int carry = 0, j = m - 1;

        for (int i = n - 1; i >= 0; --i) {
            if (a[i] == '1') ++carry;
            if (j >= 0 && b[j--] == '1') ++carry;

            result.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry == 1) result.push_back('1');

        reverse(result.begin(), result.end());
        return result;
    }
};

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

Задача: 750. Number Of Corner Rectangles
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = i + 1; j < grid.size(); j++) {
                int numPairs = 0;
                for (int k = 0; k < grid[0].size(); k++) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        numPairs++;
                    }
                }
                if (numPairs > 1) {
                    count += numPairs * (numPairs - 1) / 2;
                }
            }
        }
        return count;
    }
};

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

Задача: 1325. Delete Leaves With a Given Value
Сложность: medium

Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.

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

Пример:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

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

1⃣Базовый случай: Если root равен null, верните null, чтобы обработать условия пустого дерева или прохождения за пределы листовых узлов.

2⃣Рекурсивный обход: Выполните обход в постфиксном порядке, чтобы гарантировать обработку всех потомков перед текущим узлом (root):
— Рекурсивно вызовите removeLeafNodes для левого дочернего узла root и обновите левый дочерний узел возвращаемым значением.
— Аналогично, рекурсивно вызовите removeLeafNodes для правого дочернего узла root и обновите правый дочерний узел возвращаемым значением.

3⃣Оценка узла:
— Проверьте, является ли текущий узел root листовым узлом и совпадает ли его значение с target. Если оба условия выполнены, верните null, чтобы эффективно удалить узел, не присоединяя его к родителю.
— Если узел не является листом или не совпадает с target, верните сам root.

😎 Решение:

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (root == nullptr) {
            return nullptr;
        }

        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);

        if (root->left == nullptr && root->right == nullptr && root->val == target) {
            return nullptr;
        }
        return root;
    }
};

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

Задача: 79. Word Search
Сложность: medium

Дана сетка символов board размером m на n и строка word.
Верните true, если word существует в сетке.
Слово можно составить из букв смежных ячеек по вертикали или горизонтали.
Одна ячейка не может быть использована более одного раза.

Пример:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

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

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

2⃣В backtrack() проверяем:
Достигнут ли конец слова (index == word.length()) — вернуть true
Не вышли ли за границы или текущий символ не совпадает — вернуть false

3⃣Если текущий символ совпадает — временно помечаем его (например, '#'),
запускаем DFS в 4 направлениях, а после — восстанавливаем значение ячейки.
Если из одного из направлений вернётся true, значит слово найдено.

😎 Решение:

class Solution {
private:
    vector<vector<char>> board;
    int ROWS;
    int COLS;

public:
    bool exist(vector<vector<char>>& board, string word) {
        this->board = board;
        ROWS = board.size();
        COLS = board[0].size();
        for (int row = 0; row < ROWS; ++row)
            for (int col = 0; col < COLS; ++col)
                if (backtrack(row, col, word, 0)) return true;
        return false;
    }

protected:
    bool backtrack(int row, int col, const string& word, int index) {
        if (index >= word.length()) return true;
        if (row < 0 || row == ROWS || col < 0 || col == COLS ||
            board[row][col] != word[index])
            return false;
        
        bool ret = false;
        board[row][col] = '#';
        int rowOffsets[4] = {0, 1, 0, -1};
        int colOffsets[4] = {1, 0, -1, 0};
        for (int d = 0; d < 4; ++d) {
            ret = backtrack(row + rowOffsets[d], col + colOffsets[d], word, index + 1);
            if (ret) break;
        }
        board[row][col] = word[index];
        return ret;
    }
};

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

Задача: 723. Candy Crush
Сложность: medium

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

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

2⃣Удалите отмеченные конфеты, установив их значение в 0.

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

😎 Решение:

vector<vector<int>> candyCrush(vector<vector<int>>& board) {
    int m = board.size();
    int n = board[0].size();
    bool stable = false;

    while (!stable) {
        stable = true;
        vector<vector<bool>> crush(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n - 2; ++j) {
                int v = abs(board[i][j]);
                if (v != 0 && v == abs(board[i][j + 1]) && v == abs(board[i][j + 2])) {
                    stable = false;
                    crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = true;
                }
            }
        }

        for (int i = 0; i < m - 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int v = abs(board[i][j]);
                if (v != 0 && v == abs(board[i + 1][j]) && v == abs(board[i + 2][j])) {
                    stable = false;
                    crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = true;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (crush[i][j]) {
                    board[i][j] = 0;
                }
            }
        }

        for (int j = 0; j < n; ++j) {
            int idx = m - 1;
            for (int i = m - 1; i >= 0; --i) {
                if (board[i][j] != 0) {
                    board[idx][j] = board[i][j];
                    idx--;
                }
            }
            for (int i = idx; i >= 0; --i) {
                board[i][j] = 0;
            }
        }
    }

    return board;
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка по k за раз и верните измененный список. Если количество узлов не кратно k, то оставшиеся узлы должны остаться в исходном порядке. Значения в узлах менять нельзя — разрешено только изменять указатели.

Пример:

Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]

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

1⃣Подсчитываем количество узлов — если их меньше k, возвращаем head без изменений.

2⃣Разворачиваем первые k узлов обычным способом с помощью трех указателей.

3⃣Рекурсивно обрабатываем оставшуюся часть списка и присоединяем к текущему развороту.

😎 Решение:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int count(ListNode* head){
        int n = 0;
        while (head) {
            head = head->next;
            n++;
        }
        return n;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        int num = count(head);
        if (num < k) return head;

        ListNode *next, *prev = NULL;
        ListNode *curr = head;
        int x = k;

        while (x--) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        head->next = reverseKGroup(next, k);
        return prev;
    }
};

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

Задача: 331. Verify Preorder Serialization of a Binary Tree
Сложность: medium

Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.
Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.
Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.

Пример:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

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

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

2⃣Итерация по элементам и проверка:
Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1.
Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию.
Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота.

3⃣Проверка завершения:
После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false.

😎 Решение:

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int slots = 1;
        stringstream ss(preorder);
        string node;
        
        while (getline(ss, node, ',')) {
            slots -= 1;
            if (slots < 0) {
                return false;
            }
            if (node != "#") {
                slots += 2;
            }
        }
        
        return slots == 0;
    }
};

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

Задача: 913. Cat and Mouse
Сложность: hard

В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья.

Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

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

2⃣Проверить три условия окончания игры:
Мышь достигает дырки (победа мыши).
Кот достигает мыши (победа кота).
Позиция повторяется (ничья).

3⃣Использовать BFS (поиск в ширину) для определения результатов игры, начиная с конечных состояний и работая назад.

😎 Решение:

class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        int n = graph.size();
        const int DRAW = 0, MOUSE = 1, CAT = 2;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, DRAW)));
        queue<array<int, 4>> q;

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

        while (!q.empty()) {
            auto [mouse, cat, turn, winner] = q.front();
            q.pop();
            for (auto [m, c, t] : parents(graph, mouse, cat, turn)) {
                if (dp[m][c][t] == DRAW) {
                    if ((t == 0 && winner == MOUSE) || (t == 1 && winner == CAT)) {
                        dp[m][c][t] = winner;
                        q.push({m, c, t, winner});
                    } else {
                        int degrees = 0;
                        for (auto _ : parents(graph, m, c, t)) degrees++;
                        if (degrees == 0) {
                            dp[m][c][t] = winner;
                            q.push({m, c, t, winner});
                        }
                    }
                }
            }
        }

        return dp[1][2][0];
    }

private:
    vector<array<int, 3>> parents(const vector<vector<int>>& graph, int mouse, int cat, int turn) {
        vector<array<int, 3>> res;
        if (turn == 1) {
            for (int m : graph[mouse]) {
                res.push_back({m, cat, 0});
            }
        } else {
            for (int c : graph[cat]) {
                if (c > 0) res.push_back({mouse, c, 1});
            }
        }
        return res;
    }
};

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

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

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