Задача: №16. 3Sum Closest #medium

Условие:

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

Решение:

class Solution { 
public: 
    int threeSumClosest(vector<int>& nums, int target) { 
        sort(nums.begin(),nums.end()); 
        int front; 
        int sum=nums[0]+nums[1]+nums[2],sum1=0; 
        for(int i=0;i<nums.size();i++){ 
            front=i+1; 
            int back=nums.size()-1; 
            while(front<back){ 
            sum1=nums[front]+nums[back]+nums[i]; 
            if(abs(sum1-target)<=abs(sum-target)){ 
                sum=sum1; 
            } 
            if(sum1>target)  
                back--; 
            else if(sum1<target)  
               front++; 
            else return sum1; 
            } 
        } 
        return sum; 
    } 
};

Пояснение:
1: Сортировка и начальная инициализацияsort(nums.begin(), nums.end()); // Сортировка массива nums
int front;int sum = nums[0] + nums[1] + nums[2]; // Инициализация переменной для хранения наиболее близкой суммы
int sum1 = 0; // Переменная для текущей суммы трех чисел
1. Массив nums сортируется для удобства работы с двумя указателями (front и back) в последующих шагах.2. sum инициализируется суммой первых трех элементов массива (предполагается, что массив содержит как минимум 3 элемента).
3. sum1 будет использоваться для хранения текущей суммы трех чисел.
2: Основной цикл по каждому элементу
1. Инициализация указателей:
front = i + 1; int back = nums.size() - 1;
front и back - это указатели на элементы после текущего и последний элемент массива соответственно.
2. Цикл с двумя указателями:
while(front < back) {
sum1 = nums[front] + nums[back] + nums[i];
Цикл продолжается, пока front меньше back. Внутри цикла вычисляется текущая сумма трех элементов.
- Обновление sum, если текущая сумма ближе к целевому значению:
if (abs(sum1 - target) <= abs(sum - target)) { sum = sum1;
}
Если абсолютная разница между sum1 и target меньше или равна разнице между sum и target, обновляем sum.
- Движение указателей:
;
Если текущая сумма больше целевого значения (target), смещаем указатель back влево, чтобы уменьшить сумму.
Если текущая сумма меньше целевого значения, смещаем указатель front вправо, чтобы увеличить сумму. Если текущая сумма равна целевому значению (target), возвращаем текущую сумму, так как это наилучший возможный результат.
3: Возвращение результата
return sum;
Метод возвращает наиболее близкую сумму трех чисел к заданному значению target.
### Временная сложность- Сложность сортировки массива O(n log n).
- Внешний цикл O(n) с внутренним циклом O(n), что в сумме даёт O(n^2).Итого, временная сложность этого алгоритма в худшем случае составляет O(n^2).

Задача: №17. Letter Combinations of a Phone Number #medium

Условие:

Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.

Решение:

class Solution { 
public: 
    void find(string digits,vector<string>v,vector<string>&res,string s,int k){ 
        if(k>=digits.size()){ 
            res.push_back(s); 
            return; 
        } 
        int a = digits[k] - '0'; 
        for(int i=0;i<v[a].size();i++){ 
            s+=v[a][i]; 
            find(digits,v,res,s,k+1); 
            s.pop_back(); 
        } 
    } 
    vector<string> letterCombinations(string digits) { 
        vector<string>res; 
        if(digits.size()==0) return res; 
        vector<string>v={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 
        int k=0; 
        string s=""; 
        find(digits,v,res,s,k); 
        return res; 
    } 
};

Пояснение:
1. void find(string digits, vector<string> v, vector<string>& res, string s, int k):
- Эта функция является рекурсивной.
- Она принимает следующие параметры:
- digits: входная цифровая строка.
- v: вектор строк, где каждая строка содержит буквы, соответствующие цифрам от 0 до 9.
- res: вектор, в который будут добавляться результирующие строки.
- s: текущая строка, которая формируется в процессе рекурсии.
- k: индекс текущей цифры в digits.
- Если k равен размеру digits, это означает, что мы нашли полную комбинацию букв, поэтому добавляем s в res.
- Иначе, для текущей цифры digits[k] мы итерируемся по соответствующим буквам в v[digits[k] - '0'] и добавляем их к s. Затем рекурсивно вызываем find() с увеличенным k, чтобы найти следующую часть комбинации.
- После рекурсивного вызова, мы удаляем последний символ из s, чтобы вернуться к предыдущей части комбинации.

2. vector<string> letterCombinations(string digits):
- Эта функция является главной, которая вызывает find().
- Если digits пуст, возвращаем пустой вектор.
- Создаем вектор v, где каждая строка содержит буквы, соответствующие цифрам от 0 до 9.
- Инициализируем k = 0 и пустую строку s.
- Вызываем find() с параметрами digits, v, res, s и k.
- Возвращаем res, содержащий все найденные комбинации букв.

Задача: №18. 4Sum #medium

Условие:

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
0 <= a, b, c, d < na, b, c и d различны.
nums[a] + nums[b] + nums[c] + nums[d] == цельВы можете вернуть ответ в любом порядке.

Решение:

class Solution { 
public: 
    vector<vector<int>> fourSum(vector<int>& nums, int target) { 
        int n=nums.size(); 
        vector<vector<int>>ans; 
        sort(nums.begin(),nums.end()); 
 
        for(int a=0;a<n;a++) 
        { 
            for(int b=a+1;b<n;b++) 
            { 
                int c=b+1; 
                int d=n-1; 
                while(c<d) 
                { 
                    long long sum=nums[a]; 
                    sum+=nums[b]; 
                    sum+=nums[c]; 
                    sum+=nums[d]; 
                    if(sum<target) 
                    { 
                        c++; 
                    } 
                    else if(sum>target) 
                    { 
                        d--; 
                    } 
                    else 
                    { 
                        vector<int>v={nums[a],nums[b],nums[c],nums[d]}; 
                        //if new quads then push to main vector 
                        if(find(ans.begin(),ans.end(),v)==ans.end())  
                        { 
                            ans.push_back(v); 
                        } 
                        c++; 
                        d--; 
                    } 
                } 
            } 
        } 
        return ans; 
    } 
};

Пояснение:
1. vector<vector<int>> fourSum(vector<int>& nums, int target):
- Это основная функция, которая принимает вектор nums и целевое значение target.
- Она возвращает вектор всех найденных четверок элементов.

2. Инициализация:
- Получаем размер вектора nums и сохраняем его в n.
- Создаем вектор ans, который будет хранить все найденные четверки.
- Сортируем вектор nums в порядке возрастания.

3. Основной цикл:
- Внешний цикл for перебирает все возможные значения a (от 0 до n-1).
- Внутренний цикл for перебирает все возможные значения b (от a+1 до n-1).
- Затем в цикле while мы используем два указателя c и d, которые двигаются навстречу друг другу.

4. Логика поиска:
- Вычисляем сумму текущей четверки (a, b, c, d) и сравниваем ее с target.
- Если сумма меньше target, увеличиваем c, чтобы увеличить сумму.
- Если сумма больше target, уменьшаем d, чтобы уменьшить сумму.
- Если сумма равна target, добавляем текущую четверку в ans, но только если она еще не была добавлена. Для этого мы используем стандартную функцию find() для проверки, есть ли такая четверка в ans.
- После этого увеличиваем c и уменьшаем d, чтобы найти следующую четверку.

5. Возвращаем ans:
- После завершения всех циклов возвращаем вектор ans, содержащий все найденные четверки.

Задача: №19. Remove Nth Node From End of List #medium

Условие:

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

Решение:

/** 
 * 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: 
    ListNode* removeNthFromEnd(ListNode* head, int n) { 
        ListNode *slow, *fast; 
        slow=head; 
        fast=head; 
        ListNode *prev=new ListNode(0,head); 
        ListNode *answer=prev; 
        while(n>1){ 
            fast=fast->next; 
            n--; 
        } 
        while(fast->next){ 
            fast=fast->next; 
            slow=slow->next; 
            prev=prev->next; 
        } 
        prev->next=slow->next; 
        return answer->next; 
    } 
};

Пояснение:
1: Инициализация
* Создаем два указателя, slow и fast, оба указывающие на первый узел списка.* Создаем фиктивный узел prev и указываем его на первый узел списка. Это упрощает обработку краевых случаев.
* Указатель answer указывает на фиктивный узел prev.
2: Перемещение указателя fast
* Цикл while перемещает указатель fast на n позиций вперед. Это устанавливает fast на n-й узел от начала списка.
3: Перемещение указателей slow и prev
* Другой цикл while перемещает указатели slow и prev вперед, пока fast не достигнет конца списка. На этом этапе slow будет указывать на узел, предшествующий узлу, который нужно удалить, а prev - на узел перед ним. 4: Удаление узла
* Обновляем prev->next, чтобы пропустить узел, на который указывает slow. Это эффективно удаляет узел из списка.
* Возвращаем answer->next, который указывает на первый узел обновленного списка. Фиктивный узел был добавлен в начале для упрощения обработки.

Задача: №20. Valid Parentheses #easy

Условие:

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа.
Открытые скобки должны закрываться в правильном порядке.Каждой закрывающей скобке соответствует открытая скобка того же типа.

Решение:

class Solution { 
public: 
    bool isValid(string s) { 
        stack<char> st; // create an empty stack to store opening brackets 
        for (char c : s) { // loop through each character in the string 
            if (c == '('  c == '{'  c == '[') { // if the character is an opening bracket 
                st.push(c); // push it onto the stack 
            } else { // if the character is a closing bracket 
                if (st.empty()  // if the stack is empty or  
                    (c == ')' && st.top() != '(')  // the closing bracket doesn't match the corresponding opening bracket at the top of the stack 
                    (c == '}' && st.top() != '{') || 
                    (c == ']' && st.top() != '[')) { 
                    return false; // the string is not valid, so return false 
                } 
                st.pop(); // otherwise, pop the opening bracket from the stack 
            } 
        } 
        return st.empty(); // if the stack is empty, all opening brackets have been matched with their corresponding closing brackets, 
                           // so the string is valid, otherwise, there are unmatched opening brackets, so return false 
    } 
};

Пояснение:

1: Инициализация
* Создаем пустой стек st для хранения открывающих скобок.
2: Итерация по строке
* Перебираем каждый символ c в строке s.
3: Обработка открывающих скобок
* Если символ c является открывающей скобкой (', {' или [', мы помещаем его в стек.
4: Обработка закрывающих скобок
* Если символ c является закрывающей скобкой ')', }' или ], мы проверяем: * Если стек пуст (нет открывающей скобки для пары), или
* Закрывающая скобка не соответствует ожидаемой открывающей скобке в верхней части стека, то * Возвращаем false, поскольку строка не является допустимой.
* Если все проверки пройдены, мы извлекаем соответствующую открывающую скобку из стека.
5: Проверка пустого стека
* После обработки всех символов в строке, если стек пуст, это означает, что все открывающие скобки были сопоставлены с соответствующими закрывающими скобками. В этом случае возвращаем true.
* Если стек не пуст, это означает, что остались несопоставленные открывающие скобки, поэтому возвращаем false.

Задача: №21. Merge Two Sorted Lists #easy

Условие:

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.

Решение:

class Solution { 
public: 
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { 
        ListNode* dummy = new ListNode(0); 
        ListNode* cur = dummy; 
 
        while (list1 && list2) { 
            if (list1->val > list2->val) { 
                cur->next = list2; 
                list2 = list2->next; 
            } else { 
                cur->next = list1; 
                list1 = list1->next; 
            } 
            cur = cur->next; 
        } 
 
        cur->next = list1 ? list1 : list2; 
 
        return dummy->next;         
    } 
};

Пояснение:
1: Инициализация
* Создаем фиктивный узел dummy со значением 0. Он будет служить началом результирующего упорядоченного списка.* Создаем указатель cur, который будет указывать на текущую позицию в результирующем списке, изначально он указывает на фиктивный узел.
2: Слияние списков
* Пока оба списка list1 и list2 не пусты, выполняем следующие действия:
* Сравниваем значения узлов, на которые указывают list1 и list2. * Если значение узла в list1 больше, то добавляем узел из list2 в результирующий список и перемещаем list2 на следующий узел.
* В противном случае добавляем узел из list1 в результирующий список и перемещаем list1 на следующий узел. * Перемещаем указатель cur на следующий узел в результирующем списке.
3: Обработка оставшихся узлов
* После того, как один из списков станет пустым, добавляем оставшиеся узлы из другого списка в конец результирующего списка.
4: Возврат результата
* Возвращаем указатель на первый узел результирующего списка, который является следующим узлом после фиктивного узла.

Задача:22. Generate Parentheses #Medium
Условие:

Учитывая n пар круглых скобок, напишите функцию для генерации всех комбинаций правильно сформированных круглых скобок.

Решение:

class Solution { 
public: 
    vector<string> res; 
 
    void dfs(string cur, int open, int close, int n) 
    { 
        if (cur.length() == 2 * n) 
        { 
            if (open == close) res.push_back(cur); 
            return; 
        } 
 
        if (open < n) dfs(cur + "(", open + 1, close, n); 
        if (open > close) dfs(cur + ")", open, close + 1, n); 
    } 
 
    vector<string> generateParenthesis(int n) { 
        dfs("", 0, 0, n); 
        return res; 
    } 
};

Пояснение:
1

. vector<string> res;: Это вектор, который будет хранить все сгенерированные правильные последовательности скобок.

2. void dfs(string cur, int open, int close, int n):
- Эта функция использует глубинный поиск (DFS) для генерации правильных последовательностей скобок.
- Параметры:
- cur: текущая строка с частично сформированной последовательностью скобок.
- open: количество открывающих скобок в cur.
- close: количество закрывающих скобок в cur.
- n: заданное число, которое определяет, сколько пар скобок нужно сгенерировать.
- Если длина cur равна 2 * n (то есть количество открывающих скобок равно количеству закрывающих скобок), проверяем, что open равно close, и если так, добавляем cur в res.
- Если количество открывающих скобок меньше n, рекурсивно вызываем dfs() с добавлением открывающей скобки.
- Если количество открывающих скобок больше количества закрывающих скобок, рекурсивно вызываем dfs() с добавлением закрывающей скобки.

3. vector<string> generateParenthesis(int n):
- Это основная функция, которая вызывает dfs() с начальными параметрами.
- Она инициализирует пустую строку cur, а также open и close равные 0.
- Затем вызывает dfs() и возвращает res, содержащий все сгенерированные правильные последовательности скобок.

Задача: 23. Merge k Sorted Lists #medium

Условие:

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.Объедините все связанные списки в один отсортированный связанный список и верните его.

Решение:

/** 
 * 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 compare{ 
    public: 
    bool operator()(ListNode* a, ListNode* b){ 
    return a->val > b->val; 
 
    } 
 }; 
class Solution { 
public: 
    ListNode* mergeKLists(vector<ListNode*>& lists) { 
        if(lists.empty()){ 
            return NULL; 
        } 
 
         
     priority_queue<ListNode*, vector<ListNode*>, compare> minheap; 
    for(int i=0;i<lists.size();i++){ 
        if(lists[i]!=NULL) 
    minheap.push(lists[i]); 
    }   
     
    ListNode* head=NULL; 
    ListNode* temp1; 
    while(!minheap.empty()){ 
    ListNode* temp= minheap.top(); 
    
    if(head==NULL){ 
    head=temp; 
     temp1=temp;} 
     else{ 
     temp1->next=temp; 
     temp1=temp;} 
 
    minheap.pop(); 
    if(temp->next!=NULL){ 
        minheap.push(temp->next); 
    } 
 
 
  
    } 
    if(temp1!=NULL) 
    temp1->next=NULL; 
    return head;  
         
    } 
};
 

Пояснение:
Шаг 1: Создание функции compare для сравнения узлов в куче.
* Функция compare используется для определения порядка узлов в куче с приоритетом.* Она принимает два узла, a и b, и возвращает true, если значение a больше значения b. Это означает, что узлы с меньшими значениями будут иметь более высокий приоритет в куче.
Шаг 2: Инициализация кучи с приоритетом.
* Создается куча с приоритетом minheap с помощью функции compare.
* Для каждого непустого узла lists[i] в исходном списке узлов этот узел добавляется в кучу.
Шаг 3: Инициализация новой головы и временной ссылки.
* Начальное значение новой головы списка head устанавливается как NULL.* Создается временная ссылка temp1 для отслеживания текущего последнего узла в новом списке.
Шаг 4: Итеративное удаление узлов из минимальной кучи и добавление их в новый список.
* Пока куча с приоритетом не будет пуста, выполняется следующий цикл:
* Извлекается верхний узел с минимальным значением из кучи с приоритетом. * Если это первый узел, то он устанавливается как голова нового списка (head).
* Иначе он добавляется в конец нового списка через ссылку temp1. * Узел с минимальным значением удаляется из кучи.
* Если узел, извлеченный из кучи, имеет следующий узел, то этот следующий узел добавляется в кучу.
Шаг 5: Завершение нового списка.
* После выхода из цикла последним узлом нового списка является temp1, который был обновлен во время итерации.* Устанавливается temp1->next = NULL для завершения нового списка.
Шаг 6: Возврат новой головы списка.
* Функция возвращает голову нового отсортированного связного списка, head.

Задача: 24. Swap Nodes in Pairs #medium

Условие:

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

Решение:

class Solution { 
public: 
    ListNode* swapPairs(ListNode* head) { 
        ListNode *temp = (ListNode*)malloc(sizeof(ListNode)); //dummy node 
        temp->next = head; 
 
        ListNode *ptr = temp,*swap1,*swap2; // pointers  
 
        while(ptr->next && ptr->next->next){  //atleast 2 nodes shold be present for swapping 
 
            swap1 = ptr->next; // node1  
            swap2 = ptr->next->next; // node2 
 
            swap1->next = swap2->next; // swapping nodes link just like variables 
            swap2->next = swap1; 
 
            ptr->next = swap2; // updation of ptr's next   
            ptr = swap1;  // updation of ptr 
        } 
        return temp->next; 
    } 
}; 
 

Пояснение:

1. Инициализация Dummy-узла:
* Создаем фиктивный узел temp типа ListNode* и устанавливаем его next на head (начальный узел списка). Это позволяет нам обрабатывать случай, когда список пуст или содержит только один узел.
2. Инициализация Указателей:
* Устанавливаем указатель ptr на temp (фиктивный узел).* Устанавливаем указатели swap1 и swap2 на nullptr.
3. Итерация по списку:
* Заходим в цикл while, если ptr->next и ptr->next->next не равны nullptr. Это означает, что в списке есть по крайней мере два узла для обмена.
4. Обмен узлов:
* Устанавливаем swap1 на ptr->next (первый узел для обмена).
* Устанавливаем swap2 на ptr->next->next (второй узел для обмена).* Меняем ссылки next для swap1 и swap2. Это по существу обменивает два узла.
* Устанавливаем ptr->next на swap2. Это обновляет ссылку next для ptr.* Обновляем ptr на swap1. Это перемещает указатель вперед к следующему узлу первого обмена.
5. Возврат результата:
* После завершения обработки всех пар узлов возвращаем temp->next (фиктивный узел temp был добавлен в начале, поэтому его нужно пропустить)

Задача: 25. Reverse Nodes in k-Group #hard

Условие:

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

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

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Решение:

/** 
 * 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) { 
 
          // bc 
          int num=count(head);                                       
          if(num<k){ 
              return head; 
          } 
          int x=k; 
          ListNode *next, *prev=NULL; 
          ListNode *curr=head; 
          while(x--){ 
              next=curr->next; 
              curr->next=prev; 
              prev=curr; 
              curr=next; 
          } 
          // 1->2->3->4.... 
          head->next= reverseKGroup(next,k); 
          return prev; 
    } 
};

Пояснение:

1. Начинаем с определения структуры listnode, представляющей узел списка с одним целочисленным значением val и указателем на следующий узел next.

2.В классе solution определяем метод count для подсчета количества узлов в списке.

3.В методе reversekgroup определяем базовый случай: если количество узлов в списке меньше k, то просто возвращаем исходный список.

4.Затем определяем переменные num (количество узлов в списке), x (количество элементов, которые нужно развернуть в группе), указатели next (следующий узел), prev (предыдущий узел) и curr (текущий узел).

5.Затем в цикле с помощью x устанавливаем указатели и переворачиваем каждую группу по k элементов, меняя указатели на следующий и предыдущий узлы.

6.После переворота текущей группы устанавливаем указатель на следующий узел (next) равным результату рекурсивного вызова функции для следующей группы с параметром k.

7.Наконец, возвращаем указатель на первый узел в перевернутой группе (prev).

Задача: 26. Remove Duplicates from Sorted Array #easy

Условие:

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

Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

class Solution { 
public: 
    int removeDuplicates(vector<int>& nums) { 
        if (nums.empty()) { 
            return 0; 
        } 
 
        int k = 1; // Initialize the count of unique elements to 1 
        for (int i = 1; i < nums.size(); i++) { 
            if (nums[i] != nums[i - 1]) { 
                nums[k] = nums[i]; // Overwrite the next unique element 
                k++; 
            } 
        } 
         
        return k; 
    } 
};

Пояснение:
Шаг 1: Проверка пустого массива
Если массив nums пуст, он не содержит повторяющихся элементов, и функция возвращает 0.
Шаг 2: Инициализация индекса уникальных элементов
Создается переменная k и инициализируется значением 1. k будет отслеживать количество уникальных элементов в массиве.
Шаг 3: Итерация по элементам массива
Цикл for перебирает элементы массива, начиная со второго элемента (i = 1) до последнего элемента.
Шаг 4: Сравнение с предыдущим элементом
Для каждого элемента i сравнивается со значением предыдущего элемента nums[i - 1].
Шаг 5: Обновление массива и индекса уникальных элементов
* Если nums[i] не равно nums[i - 1], это означает, что это уникальный элемент.* В этом случае значение nums[k] перезаписывается значением nums[i] для сохранения уникального элемента.
* Переменная k увеличивается на 1, отслеживая общее количество уникальных элементов.
Шаг 6: Возврат индекса уникальных элементов
После завершения цикла переменная k содержит индекс последнего уникального элемента в массиве. Функция возвращает k, которое представляет количество уникальных элементов в массиве.

Задача: 27. Remove Element #easy
Условие:

Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val.

Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int cnt=0, sz=nums.size();
        for(int i=0; i<nums.size(); i++){
            if(nums[i]==val){
                cnt++;
                nums.erase(nums.begin()+i);
                i--;
            }
        }
        return sz-cnt;
    }
};

Пояснение:
Данный код реализует функцию removeElement для удаления всех вхождений числа val из вектора nums. Вот краткое объяснение кода:

1. Переменные и цикл: Создается счетчик cnt и переменная sz для хранения исходного размера вектора nums. Происходит цикл прохода по вектору nums с использованием индекса i.

2. Удаление элементов: Если текущий элемент nums[i] равен значению val, то увеличивается счетчик cnt, происходит удаление элемента из вектора nums с помощью метода erase и сдвигается индекс i на 1 назад, чтобы избежать пропуска элементов после удаления.

3. Возвращение результата: После завершения цикла возвращается разница между исходным размером вектора (sz) и количеством удаленных элементов (cnt). Это представляет количество оставшихся элементов в векторе после удаления всех вхождений числа val.

Хотя данный код удаляет элементы вектора, но имеет недостаток, что при повторном итерировании по вектору после удаления элемента индекс i остается на том же месте. Это может вызвать пропуск некоторых элементов для проверки на равенство val. Чтобы это исправить, следует использовать другой подход, например, два указателя (или индекса), один указывающий на текущий элемент, а другой на позицию для вставки (непосредственно перед текущим элементом, который нужно удалить).

Задача: 28. Find the Index of the First Occurrence in a String #easy
Условие:

Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена.

Решение:

class Solution {
public:
  int strStr(string haystack, string needle) {
    if(haystack.size()<needle.size()){return -1;}
    if(haystack.size()==needle.size()){if(haystack==needle){return 0;}else{return -1;}}
    for(int i=0; i<haystack.size()-needle.size()+1; i++){
      string s=haystack.substr(i, needle.size());
      //cout<<s<<endl;
      if(s==needle){
        return i;
      }
    }
    return -1;
  }
};

Пояснение:
Данный код реализует функцию strStr для поиска подстроки needle в строке haystack. Вот краткое объяснение кода:

1. Проверки базовых случаев: Сначала проверяется особый случай, когда размер строки haystack меньше размера подстроки needle. В таком случае функция возвращает -1, что означает, что подстрока не может быть найдена в строке. Затем проверяется случай, когда размер haystack равен размеру needle. Если содержимое haystack полностью совпадает с needle, то функция возвращает 0, иначе -1.

2. Проход по строке: Затем выполняется цикл прохода по строке haystack от 0 до haystack.size() - needle.size() + 1. Внутри цикла на каждой итерации создается подстрока s из haystack, начиная с индекса i и длиной needle.size(). Затем проверяется, совпадает ли подстрока s с needle. Если совпадение найдено, функция возвращает индекс i, где начинается найденная подстрока.

3. Возврат результатов: Если ни одно совпадение не найдено в цикле, функция возвращает -1, что указывает на отсутствие подстроки needle в строке haystack.

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

Задача: 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, а также решает задачу деления двух целых чисел с учетом возможного переполнения результатом.

Задача: 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`, так как он проходит по строке только один раз.

Задача: 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` на следующую перестановку в лексикографическом порядке.

Задача: 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`.

Задача: 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`.

Задача: 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` используют бинарный поиск для нахождения элементов.