C/C++ | LeetCode

#medium Задача: 38. Count and Say Последовательность "считай и скажи" — это последовательность строк цифр, определяемая с помощью рекурсивной формулы: countAndSay(1) = "1" countAndSay(n) — это кодирование длин серий из countAndSay(n - 1). Кодирование длин серий (RLE) — это метод сжатия строк, который работает путём замены последовательных идентичных символов (повторяющихся 2 или более раз) на конкатенацию символа и числа, обозначающего количество символов (длину серии). Например, чтобы сжать строку "3322251", мы заменяем "33" на "23", "222" на "32", "5" на "15" и "1" на "11". Таким образом, сжатая строка становится "23321511". Для заданного положительного целого числа n верните n-й элемент последовательности "считай и скажи". Пример:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

👨‍💻 Алгоритм: 1️⃣Мы хотим использовать шаблон, который соответствует строкам из одинаковых символов, таких как "4", "7777", "2222222". Если у вас есть опыт работы с регулярными выражениями, вы можете обнаружить, что шаблон (.)\1* работает. 2️⃣Мы можем разбить это регулярное выражение на три части: (.): оно определяет группу, содержащую один символ, который может быть чем угодно. 3️⃣*: этот квалификатор, следующий за ссылкой на группу \1, указывает, что мы хотели бы видеть повторение группы ноль или более раз. Таким образом, шаблон соответствует строкам, которые состоят из некоторого символа, а затем ноль или более повторений этого символа после его первого появления. Это то, что нам нужно. Мы находим все совпадения с регулярным выражением, а затем конкатенируем результаты. 😎 Решение:

class Solution {
public:
    string countAndSay(int n) {
        regex e("(.)\\1*");
        string s = "1";
        for (int i = 2; i <= n; i++) {
            string t;
            for (sregex_iterator it = sregex_iterator(s.begin(), s.end(), e);
                 it != sregex_iterator(); it++) {
                t += to_string(it->str().size()) + it->str(1);
            }
            s = t;
        }
        return s;
    }
};

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

#hard Задача: 37. Sudoku Solver Напишите программу для решения головоломки Судоку, заполнив пустые ячейки. Решение Судоку должно удовлетворять всем следующим правилам: Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке. Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце. Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки. Символ '.' обозначает пустые ячейки. Пример:

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️⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки. 2️⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col). Если число d еще не в текущей строке, столбце и блоке: Поместите d в ячейку (row, col). Запишите, что d теперь присутствует в текущей строке, столбце и блоке. 3️⃣Если вы на последней ячейке row == 8, col == 8: Это означает, что судоку решено. В противном случае продолжайте размещать дальнейшие числа. Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col). 😎 Решение:

#include <vector>

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;
    }
};

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

#medium Задача: 36. Valid Sudoku Определите, является ли доска Судоку размером 9 на 9 валидной. Необходимо проверить только заполненные ячейки согласно следующим правилам: Каждая строка должна содержать цифры от 1 до 9 без повторений. Каждый столбец должен содержать цифры от 1 до 9 без повторений. Каждая из девяти подзон размером 3 на 3 в сетке должна содержать цифры от 1 до 9 без повторений. Пример:

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: true

👨‍💻 Алгоритм: 1️⃣Инициализируйте список из 9 хеш-множеств, где хеш-множество с индексом r будет использоваться для хранения ранее увиденных чисел в строке r судоку. Аналогично инициализируйте списки из 9 хеш-множеств для отслеживания столбцов и блоков. 2️⃣Итерируйтесь по каждой позиции (r, c) в судоку. На каждой итерации, если на текущей позиции есть число: Проверьте, существует ли это число в хеш-множестве для текущей строки, столбца или блока. Если да, верните false, потому что это второе появление числа в текущей строке, столбце или блоке. 3️⃣В противном случае обновите множество, отвечающее за отслеживание ранее увиденных чисел в текущей строке, столбце и блоке. Индекс текущего блока рассчитывается как (r / 3) * 3 + (c / 3), где / означает деление нацело. Если дубликаты не были найдены после посещения каждой позиции на доске судоку, то судоку валидно, поэтому верните true. 😎 Решение:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int N = 9;
        unordered_set<char> rows[9];
        unordered_set<char> cols[9];
        unordered_set<char> boxes[9];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                char val = board[r][c];
                if (val == '.') {
                    continue;
                }
                if (rows[r].find(val) != rows[r].end()) {
                    return false;
                }
                rows[r].insert(val);
                if (cols[c].find(val) != cols[c].end()) {
                    return false;
                }
                cols[c].insert(val);
                int idx = (r / 3) * 3 + c / 3;
                if (boxes[idx].find(val) != boxes[idx].end()) {
                    return false;
                }
                boxes[idx].insert(val);
            }
        }
        return true;
    }
};

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

#easy Задача: 35. Search Insert Position Дан отсортированный массив уникальных целых чисел и целевое значение. Верните индекс, если цель найдена. Если нет, верните индекс, где она должна быть вставлена в соответствии с порядком. Вы должны написать алгоритм со временной сложностью O(log n). Пример:

Input: nums = [1,3,5,6], target = 5
Output: 2

👨‍💻 Алгоритм: 1️⃣Инициализируйте указатели left и right: left = 0, right = n - 1. 2️⃣Пока left <= right: Сравните средний элемент массива nums[pivot] с целевым значением target. Если средний элемент является целевым, то есть target == nums[pivot]: верните pivot. Если цель не найдена: Если target < nums[pivot], продолжайте поиск в левом подмассиве. right = pivot - 1. Иначе продолжайте поиск в правом подмассиве. left = pivot + 1. 3️⃣Верните left. 😎 Решение:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int pivot, left = 0, right = nums.size() - 1;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            if (nums[pivot] == target) return pivot;
            if (target < nums[pivot])
                right = pivot - 1;
            else
                left = pivot + 1;
        }
        return left;
    }
};

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

Задача: 34. Find First and Last Position of Element in Sorted Array #medium Условие:

Учитывая массив целых чисел, отсортированных в порядке неубывания, найдите начальную и конечную позицию заданного целевого значения. Если цель не найдена в массиве, верните [-1, -1]. Вы должны написать алгоритм со сложностью выполнения O(log n).

Решение:

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
       vector<int> ans{-1,-1};
        auto l = lower_bound(nums.begin(),nums.end(),target);
        auto r = upper_bound(nums.begin(),nums.end(),target);
        if(l!=nums.end()&&*l==target){
        ans[0] = l-nums.begin();
        ans[1] = r-nums.begin()-1;
        }
        return ans;
    }
};

Пояснение: Этот код реализует функцию `searchRange`, которая находит диапазон (индексы начала и конца диапазона) в отсортированном списке `nums`, в котором находятся значения `target`. В данном коде используются функции `lower_bound` и `upper_bound` из стандартной библиотеки C++, которые возвращают итераторы на первое и последнее вхождение `target` в отсортированном диапазоне. 1. Создается вектор `ans` для хранения результатов. Изначально вектор заполняется значениями -1, что означает, что значения `target` не найдено в списке. 2. Используя функцию `lower_bound`, находим итератор на первое вхождение `target` в отсортированном диапазоне `nums`. 3. Используя функцию `upper_bound`, находим итератор на элемент, следующий за последним вхождением `target` в отсортированном диапазоне `nums`. 4. Проверяем, действительно ли значение `target` найдено (то есть итератор `l` не указывает на конец вектора и значение по итератору `l` равно `target`). 5. Если значение `target` найдено, мы обновляем диапазон `ans` с индексами начала (взятие расстояния от начала вектора до `l`) и конца (взятие расстояния от начала вектора до `r-1`) вхождения `target`. 6. Возвращаем вектор `ans`. Этот подход к поиску диапазона работает за время O(log n), где n - количество элементов в массиве `nums`, так как `lower_bound` и `upper_bound` используют бинарный поиск для нахождения элементов.

Задача: 33. Search in Rotated Sorted Array #medium Условие:

Существует целочисленный массив nums, отсортированный по возрастанию (с разными значениями). Перед передачей в вашу функцию nums, возможно, поворачивается с неизвестным индексом поворота k (1 <= k < nums.length), так что результирующий массив имеет вид [nums[k], nums[k+1],... , nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексом 0). Например, [0,1,2,4,5,6,7] можно повернуть с опорным индексом 3 и превратить в [4,5,6,7,0,1,2]. Учитывая массив nums после возможного поворота и целочисленную цель, верните индекс цели, если он находится в nums, или -1, если он не в nums. Вы должны написать алгоритм со сложностью выполнения O(log n).

Решение:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            if (nums[left] == target) {
                return left;
            } else if (nums[right] == target) {
                return right;
            }
            int m = (left + right) / 2;
            if (nums[m] == target) {
                return m;
            }
            if (nums[left] > nums[right]) {
                left++, right--;
            } else {
                if (nums[m] > target) {
                    right = m - 1, left++;
                } else {
                    left = m + 1, right--;
                }
            }
        }
        return -1;
    }
};

Пояснение: Данный код реализует функцию `search`, которая выполняет поиск элемента `target` в отсортированном массиве `nums`. В данном случае массив может быть как отсортированным по возрастанию, так и массивом, который был "повернут" (то есть началом может быть какой-то элемент из середины массива). 1. Начальная инициализация левой и правой границ массива. 2. В цикле `while` происходит поиск элемента `target` путем деления текущего отрезка пополам. 3. Если левый, правый или средний элемент равен `target`, то метод возвращает соответствующий индекс. 4. Если массив "повернут", мы уменьшаем правую и увеличиваем левую границу, чтобы сблизиться к участку массива, где нет поворота. 5. Если массив отсортирован, то в зависимости от значения в середине выбирается в какую сторону двигаться. 6. Если ни одно из условий не выполнилось и цикл завершился, то метод возвращает `-1`, что означает, что элемент `target` не найден в массиве. Этот подход к поиску элемента в отсортированном массиве работает за время O(log n), где n - количество элементов в массиве `nums`.

Задача: 32. Longest Valid Parentheses #hard Условие:

Учитывая строку, содержащую только символы «(» и «)», верните длину самых длинных допустимых (правильно сформированных) круглых скобок. подстрока

Решение:

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stack;
        int m = 0;
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    m = max(m, (i - stack.top()));
                }
            }
        }
        return m;
    }
};

Пояснение: Этот код реализует функцию `longestValidParentheses`, которая находит длину самой длинной правильной скобочной последовательности в строке `s`. В данной задаче правильная скобочная последовательность - это такая последовательность символов, в которой открывающиеся скобки правильно закрываются. 1. Создается стек `stack`, в котором будут храниться индексы открывающихся скобок. 2. Инициализируется переменная `m` для хранения максимальной длины правильной скобочной последовательности. 3. В стек помещается начальное значение -1, чтобы при открывающейся скобке можно было вычислить длину последовательности. 4. Происходит итерация по всем символам строки `s`. 5. Если символ - открывающая скобка, его индекс помещается в стек. 6. Если символ - закрывающая скобка, из стека удаляется индекс последней открывающей скобки. Если стек пуст, то текущий индекс добавляется в стек, так как некорректная последовательность. 7. Иначе вычисляется длина текущей правильной последовательности и обновляется значение `m`, если это значение больше текущего максимума. 8. В конце возвращается максимальная длина правильной скобочной последовательности. Этот подход использует стек для отслеживания индексов открывающихся скобок и может быть выполнен за O(n), где n - длина строки `s`.

Задача: 31. Next Permutation #medium Условие:

Перестановка массива целых чисел — это расположение его членов в последовательность или линейный порядок. Например, для arr = [1,2,3] следующие перестановки arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его целого числа. Более формально, если все перестановки массива отсортированы в одном контейнере в соответствии с их лексикографическим порядком, то следующей перестановкой этого массива будет перестановка, следующая за ней в отсортированном контейнере. Если такое расположение невозможно, массив необходимо переупорядочить в наименьшем возможном порядке (т. е. отсортировать по возрастанию). Например, следующая перестановка arr = [1,2,3] — это [1,3,2]. Аналогично, следующая перестановка arr = [2,3,1] — это [3,1,2]. А следующая перестановка arr = [3,2,1] — это [1,2,3], потому что [3,2,1] не имеет более крупной лексикографической перестановки. Учитывая массив целых чисел nums, найдите следующую перестановку чисел. Замена должна быть на месте и использовать только постоянную дополнительную память.

Решение:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        
        int n = nums.size()-1;
        int index = n-1;
        while(index >= 0 && nums[index] >= nums[index+1])
            index--;
        
        if(index >= 0) {
            int nextGreaterElement = nums[index+1];
            int nextGreaterIndex = index+1;

            for(int i=index+1; i <= n; i++)
            {
                if(nums[i] > nums[index] && nums[i] < nextGreaterElement)
                {
                    nextGreaterElement = nums[i];
                    nextGreaterIndex = i;
                }
            }
            swap(nums[index], nums[nextGreaterIndex]);
        }
        sort(nums.begin()+index+1, nums.end());
    }
};

Пояснение: Этот код реализует функцию `nextPermutation`, которая изменяет вектор `nums` на следующую перестановку элементов в лексикографическом порядке. 1. Определяется переменная `n`, содержащая индекс последнего элемента вектора `nums`. 2. Начинается поиск элемента, который можно обменять. 3. Индекс `index` уменьшается до тех пор, пока элементы в векторе упорядочены по убыванию. 4. Если нашелся элемент, который можно обменять, находим следующий наименьший элемент, но больший обменяемого элемента. 5. Обменяем найденные элементы. 6. Сортируем элементы вектора, начиная с позиции `index+1`, чтобы получить следующую перестановку в лексикографическом порядке. Этот алгоритм работает за O(nlogn) времени из-за сортировки элементов вектора, и может изменить вектор `nums` на следующую перестановку в лексикографическом порядке.

Задача: 30. Substring with Concatenation of All Words #hard Условие:

Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину. Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов. Например, если слова = ["ab", "cd", "ef"], то "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" и "efcdab" являются объединенными строками. «acdbef» не является объединенной строкой, поскольку не является объединением какой-либо перестановки слов. Возвращает массив начальных индексов всех объединенных подстрок в s. Вы можете вернуть ответ в любом порядке.

Решение:

    vector<int> findSubstring(string str, vector<string>& words) {
        int len = words[0].length();
        
        unordered_map<string, int> contain;
        for(string s: words) contain[s]++;
        
        vector<int> res;
        for(int j = 0; j < len; j++) {
            unordered_map<string, int> found;
            int st = j;
            for(int i = 0 + j; i < str.size() - len + 1; i += len) {
                string curr = str.substr(i, len);
                if(contain.find(curr) != contain.end()) {
                    found[curr]++;
                    while(found[curr] > contain[curr]) {
                        found[str.substr(st, len)]--;
                        st += len;
                    }
                    int size = (i - st + len) / len;
                    if(size == words.size()) {
                        cout << j << " " << st << " " << i << endl;
                        res.push_back(st);
                    }
                } else {
                    found.clear();
                    st = i + len;
                }
            }
        }
        
        return res;
    }

Пояснение: Этот код находит все подстроки в строке `str`, которые содержат все слова из вектора `words` в произвольном порядке. 1. Сначала определяется длина слова в векторе `words`. 2. Создается unordered_map `contain`, чтобы хранить количество вхождений каждого слова из `words`. 3. Далее происходит итерация по всем возможным смещениям начала подстроки `j`. 4. Внутри цикла идет итерация по строке `str` с шагом, равным длине слова. 5. Для каждой подстроки текущее слово проверяется на его наличие в `contain`. 6. Если слово содержится в `contain`, увеличивается его количество в текущей найденной подстроке `found`. 7. Затем проверяется, не превосходит ли количество данного слова в `found` их количества в `contain`. Если превосходит, сдвигаем начало найденной подстроки `st` до тех пор, пока это условие не выполняется. 8. Если количество слов в найденной подстроке равно количеству слов в `words`, добавляем индекс начала найденной подстроки в результат `res`. 9. Если текущее слово не содержится в `contain`, сбрасываем `found` и сдвигаем начало найденной подстроки `st` на следующее слово. 10. По окончании всех итераций возвращаем вектор с индексами начала всех найденных подстрок. Этот код использует сложность O(n), где n - это длина строки `str`, так как он проходит по строке только один раз.

Задача: 29. Divide Two Integers #medium Условие:

Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора. Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2. Возвращает частное после деления делимого на делитель. Примечание. Предположим, мы имеем дело со средой, которая может хранить целые числа только в пределах 32-битного целого диапазона со знаком: [−2^31, 2^31 − 1]. В этой задаче, если частное строго больше 2^31 - 1, верните 2^31 - 1, а если частное строго меньше -2^31, верните -2^31.

Решение:

class Solution {
public:
  int divide(int dividend, int divisor) {
    if((long long int)dividend/divisor>pow(2,31)-1){return pow(2,31)-1;}
    if((long long int)dividend/divisor<(-1)*(pow(2,31))){return -1*pow(2,31);}
    return dividend/divisor;
  }
};

Пояснение: Данный код реализует функцию divide для деления целых чисел dividend на divisor. Вот краткое объяснение кода: 1. Проверка на переполнение: - Первое условие проверяет, если результат деления dividend на divisor больше, чем максимальное значение int (2^31 - 1), то возвращается максимальное значение int (2^31 - 1). Это делается для предотвращения переполнения. - Второе условие проверяет, если результат деления dividend на divisor меньше, чем минимальное значение int (-2^31), то возвращается минимальное значение int (-2^31). Это также сделано для предотвращения переполнения. 2. Выполнение деления: - Если результат деления находится в допустимом диапазоне, происходит само деление dividend на divisor. 3. Возвращение результата: - Функция возвращает результат деления dividend на divisor, если он находится в допустимом диапазоне. Данный код не учитывает вариант деления на 0, а также решает задачу деления двух целых чисел с учетом возможного переполнения результатом.