C/C++ | LeetCode

Как джуну без опыта составить себе крутое резюме? Просто скачай наш гайд с 5 примерами реальных резюмешек ребят, которые недавно нашли работу. В этом гайде рассказали как: 1. Оформить свой опыт, даже если его нет. 2. Добавили 5 крутых примеров настоящих резюме junior разработчиков без опыта, которые нашли работу. А писала этот гайд команда, которая трудоустроила уже больше 150 джунов! Меняем его на подписку на канал 😊 👉 Скачать можно бесплатно по этой ссылочке.

#easy Задача: 66. Plus One Вам дано большое число, представленное в виде массива целых чисел digits, где каждый элемент digits[i] — это i-я цифра числа. Цифры расположены в порядке от старшей к младшей слева направо. Большое число не содержит ведущих нулей. Увеличьте большое число на один и верните результирующий массив цифр. Пример:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

👨‍💻 Алгоритм: 1️⃣Проходим по входному массиву, начиная с конца массива. 2️⃣Устанавливаем все девятки на конце массива в ноль. Если мы встречаем цифру, не равную девяти, увеличиваем её на один. Работа выполнена — возвращаем массив цифр. 3️⃣Мы здесь, потому что все цифры были равны девяти. Теперь они все установлены в ноль. Затем мы добавляем цифру 1 в начало остальных цифр и возвращаем результат. 😎 Решение:

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i]++;
                return digits;
            }
        }
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#hard Задача: 65. Valid Number Учитывая строку s, определите, является ли s валидным числом. Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53". Формально, валидное число определяется с использованием одного из следующих определений: Целое число с необязательным показателем степени. Десятичное число с необязательным показателем степени. Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры. Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений: Цифры, за которыми следует точка '.'. Цифры, за которыми следует точка '.', за которой следуют цифры. Точка '.', за которой следуют цифры. Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число. Цифры определяются как одна или более цифр. Пример:

Input: s = "0"

Output: true

👨‍💻 Алгоритм: 1️⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true. 2️⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число. 3️⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры. 😎 Решение:

class Solution {
public:
    bool isNumber(string s) {
        bool seenDigit = false;
        bool seenExponent = false;
        bool seenDot = false;
        for (int i = 0; i < s.length(); i++) {
            char curr = s[i];
            if (curr >= '0' && curr <= '9') {
                seenDigit = true;
            } else if (curr == '+' || curr == '-') {
                if (i > 0 && s[i - 1] != 'e' && s[i - 1] != 'E') {
                    return false;
                }
            } else if (curr == 'e' || curr == 'E') {
                if (seenExponent || !seenDigit) {
                    return false;
                }
                seenExponent = true;
                seenDigit = false;
            } else if (curr == '.') {
                if (seenDot || seenExponent) {
                    return false;
                }
                seenDot = true;
            } else {
                return false;
            }
        }
        return seenDigit;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 64. Minimum Path Sum На сетке размером m на n, заполненной неотрицательными числами, найдите путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути. Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени. Пример:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

👨‍💻 Алгоритм: 1️⃣Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего элемента. Начинаем с инициализации самого правого нижнего элемента dp как последнего элемента заданной матрицы. 2️⃣Для каждого элемента, начиная с правого нижнего угла, мы обходим матрицу в обратном порядке и заполняем её требуемыми минимальными суммами. Важно отметить, что на каждом элементе мы можем перемещаться либо вправо, либо вниз. 3️⃣Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий. 😎 Решение:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j != n - 1)
                    dp[i][j] = grid[i][j] + dp[i][j + 1];
                else if (j == n - 1 && i != m - 1)
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (j != n - 1 && i != m - 1)
                    dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);
                else
                    dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Cамый простой способ изучить Java — залезть в голову профи Один из лучших айтишников России учит базе кодинга в Telegram. Даже гуманитарий поймёт, как создавать приложения, сайты, игры и чат-боты. Достаточно подписаться на «Секреты Java», где каждый день появляются гайды, готовые примеры кода и лучших практик. И всё это бесплатно — вместо сотен тысяч рублей за курсы. Стартовать в прибыльной профессии с нуля вы сможете гораздо проще! Теперь обучиться Java может каждый: @java_secrets

#medium Задача: 63. Unique Paths II Вам дана матрица размером m на n, содержащая целые числа. Робот находится в начальный момент в верхнем левом углу (то есть в ячейке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть в ячейку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени. Препятствия и свободные пространства отмечены в матрице как 1 и 0 соответственно. Путь, который проходит робот, не может включать клетки, которые являются препятствиями. Верните количество возможных уникальных путей, по которым робот может добраться до нижнего правого угла. Тестовые примеры сгенерированы таким образом, что ответ будет не более 2 * 10^9. Пример:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

👨‍💻 Алгоритм: 1️⃣Если первая ячейка, то есть obstacleGrid[0,0], содержит 1, это означает, что в первой ячейке есть препятствие. Следовательно, робот не сможет сделать ни одного хода, и мы должны вернуть количество возможных путей как 0. Если же obstacleGrid[0,0] изначально равно 0, мы устанавливаем его равным 1 и продолжаем. 2️⃣Итерация по первой строке. Если ячейка изначально содержит 1, это означает, что текущая ячейка имеет препятствие и не должна учитываться в каком-либо пути. Следовательно, значение этой ячейки устанавливается равным 0. В противном случае, устанавливаем его равным значению предыдущей ячейки, то есть obstacleGrid[i,j] = obstacleGrid[i,j-1]. Повторяем аналогичные действия для первого столбца. 3️⃣Далее, итерация по массиву начиная с ячейки obstacleGrid[1,1]. Если ячейка изначально не содержит препятствий, то количество способов добраться до этой ячейки будет равно сумме количества способов добраться до ячейки над ней и количества способов добраться до ячейки слева от неё, то есть obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]. Если в ячейке есть препятствие, устанавливаем её значение равным 0 и продолжаем. Это делается для того, чтобы она не учитывалась в других путях. 😎 Решение:

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int R = obstacleGrid.size();
        int C = obstacleGrid[0].size();
        
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        
        obstacleGrid[0][0] = 1;
        
        for (int i = 1; i < R; i++) {
            obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
        }
        
        for (int i = 1; i < C; i++) {
            obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
        }
        
        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }
        
        return obstacleGrid[R - 1][C - 1];
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

#medium Задача: 62. Unique Paths На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени. Даны два целых числа m и n, верните количество возможных уникальных путей, которые робот может пройти, чтобы достичь нижнего правого угла. Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9. Пример:

Input: m = 3, n = 7
Output: 28

👨‍💻 Алгоритм: 1️⃣Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами. 2️⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1]. 3️⃣Вернуть d[m - 1][n - 1]. 😎 Решение:

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Сливаем вам 2 архива на 500 курсов! ➤ Backend и языки программирования: - Python - REST - Java - PHP - Go - SQL - NoSQL - C# - C++ - Rust - JavaScript - Другое ➤ Frontend и Web-дизайн: - JavaScript - Figma - Web-Дизайн - HTML/CSS - Верстка - UI/UX - Другое

#medium Задача: 61. Rotate List Дан указатель на начало связного списка, поверните список вправо на k позиций. Пример:

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

👨‍💻 Алгоритм: 1️⃣Найдите старый хвост и соедините его с головой (old_tail.next = head), чтобы замкнуть кольцо. Одновременно вычислите длину списка n. 2️⃣Найдите новый хвост, который находится на позиции (n - k % n - 1) от головы, и новую голову, которая находится на позиции (n - k % n). 3️⃣Разорвите кольцо (new_tail.next = None) и верните new_head. 😎 Решение:

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL) return NULL;
        if (head->next == NULL) return head;
        ListNode* old_tail = head;
        int n;
        for (n = 1; old_tail->next != NULL; n++) old_tail = old_tail->next;
        old_tail->next = head;
        ListNode* new_tail = head;
        for (int i = 0; i < n - k % n - 1; i++) new_tail = new_tail->next;
        ListNode* new_head = new_tail->next;
        new_tail->next = NULL;
        return new_head;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#hard Задача: 60. Permutation Sequence Множество [1, 2, 3, ..., n] содержит в общей сложности n! уникальных перестановок. Списком и маркировкой всех перестановок по порядку, мы получаем следующую последовательность для n = 3: "123" "132" "213" "231" "312" "321" Дано n и k, верните k-ю перестановку последовательности. Пример:

Input: n = 3, k = 3
Output: "213"

👨‍💻 Алгоритм: 1️⃣Сгенерируйте входной массив nums чисел от 1 до N. 2️⃣Вычислите все факториальные основы от 0 до (N−1)!. 3️⃣Уменьшите k на 1, чтобы значение попало в интервал (0, N!−1). Используйте коэффициенты факториалов для построения перестановки. Верните строку перестановки. 😎 Решение:

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorials(n);
        vector<char> nums;
        factorials[0] = 1;
        nums.push_back('1');
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.push_back(char(i + 1 + '0'));
        }
        --k;
        string result = "";
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];
            result += nums[idx];
            nums.erase(nums.begin() + idx);
        }
        return result;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

– Помощь с pet-проектом – Составление roadmap – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Здесь размещен список менторов, и многие из них предлагают бесплатную первую консультацию

#medium Задача: 59. Spiral Matrix II Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке. Пример:

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

👨‍💻 Алгоритм: 1️⃣Определение направлений движения: Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1). 2️⃣Перемещение по матрице: Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений. 3️⃣Изменение направления: Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4. 😎 Решение:

class Solution {
public:
    int floorMod(int x, int y) { return ((x % y) + y) % y; }

    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n));
        int cnt = 1;
        int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int d = 0;
        int row = 0;
        int col = 0;
        while (cnt <= n * n) {
            result[row][col] = cnt++;
            int r = floorMod(row + dir[d][0], n);
            int c = floorMod(col + dir[d][1], n);
            if (result[r][c] != 0) d = (d + 1) % 4;
            row += dir[d][0];
            col += dir[d][1];
        }
        return result;
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

#easy Задача: 58. Length of Last Word Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке. Слово — это максимальная подстрока, состоящая только из символов, не являющихся пробелами. Пример:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 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;
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

#medium Задача: 57. Insert Interval Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала. Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы). Верните массив intervals после вставки. Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его. Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

👨‍💻 Алгоритм: 1️⃣ Инициализация переменных: Инициализируются переменные n и i для хранения размера массива интервалов и текущего индекса соответственно, а также пустой массив res для хранения результата. 2️⃣Обработка случаев без перекрытия и с перекрытием: В случае отсутствия перекрытия до вставки, проходим через массив интервалов до тех пор, пока конечная точка текущего интервала меньше начальной точки нового интервала. Добавляем текущий интервал в массив res и переходим к следующему. В случае перекрытия, продолжаем обход, пока начальная точка нового интервала меньше или равна конечной точке текущего интервала. Обновляем начальные и конечные точки нового интервала, объединяя перекрывающиеся интервалы в один. 3️⃣Обработка интервалов после вставки: Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним. Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом. 😎 Решение:

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        vector<vector<int>> res;

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval);

        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

#medium Задача: 56. Merge Intervals Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных. Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

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

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

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

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

    vector<int> mergeNodes(vector<vector<int>>& nodes) {
        int min_start = nodes[0][0];
        for (auto node : nodes) {
            min_start = min(min_start, node[0]);
        }

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

        return {min_start, max_end};
    }

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

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

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

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

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

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

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

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

        return merged;
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

😮 Добавлена новая база слитых курсов на 800ГБ: Программирование: https://t.me/+tHab1ttNTE85Yjgy Python: https://t.me/+zpUxu2ScikwwZGJi Графика и дизайн: https://t.me/+GwFBZ4HOcOs2ZDcy Frontend и Web: https://t.me/+8op47ibl8thhYTIy

#medium Задача: 55. Jump Game Вам дан массив целых чисел nums. Изначально вы находитесь на первом индексе массива, и каждый элемент массива представляет вашу максимальную длину прыжка в этой позиции. Верните true, если вы можете достичь последнего индекса, или false в противном случае. Пример:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

👨‍💻Алгоритм: 1️⃣ Инициализация таблицы памяти: Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя). 2️⃣Модификация алгоритма обратного трассирования: Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD). Если индекс известен, тогда возвращается True/False. 3️⃣Выполнение и сохранение результатов: Если индекс не известен, выполняйте шаги обратного трассирования, как ранее. После определения значения текущего индекса, сохраните его в таблице памяти. 😎 Решение:

enum Index { GOOD, BAD, UNKNOWN };
class Solution {
public:
    vector<Index> memo;
    bool canJumpFromPosition(int position, vector<int>& nums) {
        if (memo[position] != UNKNOWN) {
            return memo[position] == GOOD;
        }
        int furthestJump = min(position + nums[position], (int)nums.size() - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                memo[position] = GOOD;
                return true;
            }
        }
        memo[position] = BAD;
        return false;
    }
    bool canJump(vector<int>& nums) {
        memo = vector<Index>(nums.size(), UNKNOWN);
        memo[memo.size() - 1] = GOOD;
        return canJumpFromPosition(0, nums);
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

#medium Задача: 46. Permutations Дан массив nums, состоящий из различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке. Пример:

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

👨‍💻 Алгоритм: 1️⃣Если длина curr равна длине nums, добавьте копию curr в ans и вернитесь. 2️⃣Итерируйтесь по nums. Для каждого num, если num не в curr, выполните следующее: Добавьте num в curr и вызовите backtrack(curr), затем удалите num из curr. 3️⃣Вызовите backtrack с изначально пустым curr. Верните ans. 😎 Решение:

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr = {};
        backtrack(curr, ans, nums);
        return ans;
    }

    void backtrack(vector<int>& curr, vector<vector<int>>& ans,
                   vector<int>& nums) {
        if (curr.size() == nums.size()) {
            ans.push_back(curr);
            return;
        }

        for (int num : nums) {
            if (find(curr.begin(), curr.end(), num) == curr.end()) {
                curr.push_back(num);
                backtrack(curr, ans, nums);
                curr.pop_back();
            }
        }
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

#medium Задача: 45. Jump Game II Вам дан массив целых чисел nums с индексацией с нуля и длиной n. Изначально вы находитесь в позиции nums[0]. Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь в nums[i], вы можете прыгнуть на любой nums[i + j], где: 0 <= j <= nums[i] и i + j < n Верните минимальное количество прыжков, чтобы достичь nums[n - 1]. Тестовые случаи сгенерированы таким образом, что вы можете достичь nums[n - 1]. Пример:

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

👨‍💻 Алгоритм: 1️⃣Инициализируйте curEnd = 0, curFar = 0 и количество прыжков как answer = 0. 2️⃣Итерируйтесь по массиву nums. Для каждого индекса i наибольший индекс, до которого мы можем добраться из i, равен i + nums[i]. Обновите curFar = max(curFar, i + nums[i]). 3️⃣Если i = curEnd, это означает, что текущий прыжок завершен, и следует перейти к следующему прыжку. Увеличьте answer и установите curEnd = curFar как наибольшее расстояние, которое мы можем преодолеть следующим прыжком. Повторите с шага 2. 😎 Решение:

class Solution {
public:
    int jump(vector<int>& nums) {
        int answer = 0, n = int(nums.size());
        int curEnd = 0, curFar = 0;

        for (int i = 0; i < n - 1; ++i) {
            curFar = max(curFar, i + nums[i]);
            if (i == curEnd) {
                answer++;
                curEnd = curFar;
            }
        }
        return answer;
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых

#hard Задача: 44. Wildcard Matching Дана входная строка (s) и шаблон (p), реализуйте сопоставление с шаблоном с поддержкой символов '?' и '*' где: '?' соответствует любому одиночному символу. '*' соответствует любой последовательности символов (включая пустую последовательность). Сопоставление должно покрывать всю входную строку (не частично). Пример:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

👨‍💻 Алгоритм: 1️⃣Очистите входные данные, заменив несколько звездочек подряд одной звездочкой: p = remove_duplicate_stars(p). Инициируйте хеш-карту для мемоизации dp. Верните вспомогательную функцию с очищенным входом: helper(s, p). 2️⃣Функция helper(s, p): Если пара (s, p) уже известна и сохранена в dp, верните значение. Если строки равны (p == s) или шаблон соответствует любой строке (p == '*'), добавьте dp[(s, p)] = True. В противном случае, если p пусто или s пусто, добавьте dp[(s, p)] = False. Если текущие символы совпадают (p[0] == s[0] или p[0] == '?'), то сравните следующие и добавьте dp[(s, p)] = helper(s[1:], p[1:]). 3️⃣Если текущий символ шаблона - звездочка (p[0] == '*'), то возможны две ситуации: звездочка не соответствует никаким символам, и звездочка соответствует одному или нескольким символам: dp[(s, p)] = helper(s, p[1:]) или helper(s[1:], p). Если p[0] != s[0], тогда добавьте dp[(s, p)] = False. Когда значение вычислено, верните его: dp[(s, p)]. 😎 Решение:

class Solution {
public:
    unordered_map<string, bool> dp;
    string p;
    string s;
    string remove_duplicate_stars(string p) {
        string new_string = "";
        for (auto &c : p) {
            if (new_string.empty() || c != '*')
                new_string += c;
            else if (new_string.back() != '*')
                new_string += c;
        }
        return new_string;
    }
    bool helper(int si, int pi) {
        string key = to_string(si) + "," + to_string(pi);
        if (dp.count(key)) return dp[key];
        if (pi == p.size())
            dp[key] = (si == s.size());
        else if (si == s.size())
            dp[key] = (pi + 1 == p.size() && p[pi] == '*');
        else if (p[pi] == s[si] || p[pi] == '?')
            dp[key] = helper(si + 1, pi + 1);
        else if (p[pi] == '*')
            dp[key] = helper(si, pi + 1) || helper(si + 1, pi);
        else
            dp[key] = false;
        return dp[key];
    }
    bool isMatch(string s, string p) {
        dp.clear();
        this->s = s;
        this->p = remove_duplicate_stars(p);
        return helper(0, 0);
    }
};

🪙 434 вопроса вопроса на С/С++ разработчика 🔒 База собесов | 🔒 База тестовых