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

Условие:

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

Решение:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        
        int n = nums.length;
        int closest = 0;
        // int min = Integer.MAX_VALUE;
        int max = Integer.MAX_VALUE;
        Arrays.sort(nums);
        //target += 1;


        for(int i=0; i<n-2; i++){
            int j=i+1;
            int k  = n-1;
            // min = Math.min(min,max);

            while(j<k){
                int sum = nums[i] + nums[j] + nums[k];

                if(sum == target)
                    return sum;

                else if(sum < target)
                    j++;

                else
                    k--;
                    int diff = Math.abs(sum - target);
                    if(diff < max){
                        max = diff;
                        closest = sum;
                    }
                }
            }   
            
        return closest;
    }
}

Пояснение:
Задача требует нахождения суммы трёх чисел в массиве nums, которая наиболее близка к заданному значению target. Рассмотрим алгоритм подробнее.

Алгоритм:
Инициализация:

Переменная closest для хранения суммы трёх чисел, наиболее близкой к target.
Переменная max для хранения минимальной разницы между текущей суммой и target.
Сортировка массива:

Сначала сортируем массив nums для упрощения поиска трёх чисел.
Поиск тройки:

Используем цикл, чтобы пройти по массиву nums до третьего с конца элемента.
Для каждого элемента устанавливаем два указателя: j (следующий элемент) и k (последний элемент).
Вычисление суммы:
Внутри вложенного цикла вычисляем сумму текущих трёх чисел sum = nums[i] + nums[j] + nums[k].
Если сумма равна target, возвращаем sum как ответ.
Если сумма меньше target, увеличиваем j, чтобы увеличить сумму.
Если сумма больше target, уменьшаем k, чтобы уменьшить сумму.
Обновление ближайшей суммы:
Вычисляем разницу diff между текущей суммой и target.
Если эта разница меньше max, обновляем max и closest.
Возврат результата:
После завершения всех итераций возвращаем closest как сумму, наиболее близкую к target. Временная и пространственная сложность:
Временная сложность: O(n^2), где n - длина массива nums. Это связано с вложенным циклом и операцией сортировки (которая выполняется за O(n log n)).
Пространственная сложность: O(1), так как используется постоянное количество дополнительной памяти.

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

Условие:

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

Решение:

```java
class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return Collections.emptyList();

        String[] phone_map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> output = new ArrayList<>();
        backtrack("", digits, phone_map, output);
        return output;
    }

    private void backtrack(String combination, String next_digits, String[] phone_map, List<String> output) {
        if (next_digits.isEmpty()) {
            output.add(combination);
        } else {
            String letters = phone_map[next_digits.charAt(0) - '2'];
            for (char letter : letters.toCharArray()) {
                backtrack(combination + letter, next_digits.substring(1), phone_map, output);
            }
        }
    }
}
```

Пояснение:
Задача заключается в том, чтобы сгенерировать все возможные комбинации букв для заданной строки цифр, используя телефонную клавиатуру. Рассмотрим алгоритм подробнее.
Алгоритм:Проверка пустой строки:Если входная строка digits пуста, возвращаем пустой список.Инициализация маппинга букв:Создаём массив phone_map, где каждая строка соответствует набору букв, ассоциированных с цифрами от 2 до 9.Инициализация выходного списка:Создаём пустой список output для хранения всех возможных комбинаций.Вызов функции обратного поиска:Запускаем рекурсивную функцию backtrack, начиная с пустой строки для комбинации, исходных цифр, маппинга букв и пустого выходного списка.Рекурсивная функция backtrack:Если строка next_digits пуста, добавляем текущую комбинацию combination в список output.В противном случае, получаем набор букв, соответствующий первой цифре в next_digits.Для каждой буквы в этом наборе вызываем backtrack рекурсивно, добавляя эту букву к текущей комбинации и уменьшая строку next_digits на один символ. Временная и пространственная сложность:
Временная сложность: O(4^n), где n — длина входной строки. В худшем случае каждая цифра может соответствовать 4 буквам (например, цифра 7).
Пространственная сложность: O(4^n), так как храним все возможные комбинации в списке output.

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

Условие:

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:

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

Решение:

public class Solution {
    int len = 0;

    public List<List<Integer>> fourSum(int[] nums, int target) {
        len = nums.length;
        Arrays.sort(nums);
        return kSum(nums, target, 4, 0);
    }

    private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (index >= len) {
            return res;
        }

        if (k == 2) {
            int i = index, j = len - 1;
            while (i < j) {
                // Find a pair
                if (target - nums[i] == nums[j]) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(target - nums[i]);
                    res.add(temp);
                    // Skip duplicates
                    while (i < j && nums[i] == nums[i + 1]) i++;
                    while (i < j && nums[j - 1] == nums[j]) j--;
                    i++;
                    j--;
                } else if (target - nums[i] > nums[j]) {
                    i++;
                } else {
                    j--;
                }
            }
        } else {
            for (int i = index; i < len - k + 1; i++) {
                // Use current number to reduce kSum into k-1Sum
                ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
                if (temp != null) {
                    // Add previous results
                    for (List<Integer> t : temp) {
                        t.add(0, nums[i]);
                    }
                    res.addAll(temp);
                }
                // Skip duplicates
                while (i < len - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
        }
        return res;
    }
}

Пояснение:
Задача заключается в том, чтобы найти все уникальные комбинации четырех чисел в массиве nums, сумма которых равна заданному значению target. Для этого используем метод kSum, который является обобщением задачи на k чисел.

Алгоритм:
Инициализация:

Переменная len хранит длину массива nums.
Сортируем массив nums для упрощения поиска комбинаций.
Метод fourSum:

Вызов метода kSum с k = 4, начиная с индекса 0.
Метод kSum:

Базовый случай: если k == 2, решаем задачу двух сумм (двойной указатель).
Для k > 2, рекурсивно уменьшаем задачу до k-1 сумм, уменьшая цель на значение текущего элемента и начиная с следующего индекса.
Двойной указатель для двух сумм:

Используем два указателя i и j, чтобы найти пары чисел, сумма которых равна оставшейся цели.
Пропускаем дублирующиеся значения для избегания повторяющихся комбинаций.
Рекурсивное уменьшение задачи:

Для каждого элемента в nums, уменьшаем цель на значение текущего элемента и вызываем kSum для k-1 чисел.
Добавляем текущий элемент к каждой комбинации, полученной из рекурсивного вызова.
Пропуск дубликатов:

Пропускаем дублирующиеся значения, чтобы избежать повторяющихся комбинаций.
Временная и пространственная сложность:
Временная сложность: O(n^(k-1)), где n — длина массива, а k — количество чисел в комбинации. Для fourSum это O(n^3).
Пространственная сложность: O(k), так как используется стек вызовов глубиной k.

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

Условие:

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

Решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // Move fast pointer n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // Move both pointers until fast reaches the end
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // Remove the nth node from the end
        slow.next = slow.next.next;

        return dummy.next;
    }
}

Пояснение:
Данное решение использует метод двух указателей для удаления n-го узла с конца связанного списка. Рассмотрим этот алгоритм более подробно.

Инициализация:

Создаем фиктивный узел dummy, который указывает на голову списка. Это позволяет упростить обработку граничных случаев, таких как удаление головного узла.
Инициализируем два указателя, fast и slow, которые оба начинают с фиктивного узла.
Сдвиг fast указателя на n шагов вперед:

Перемещаем указатель fast на n шагов вперед, чтобы между fast и slow был разрыв в n узлов.
Перемещение обоих указателей:

Перемещаем оба указателя вперед, пока fast не достигнет конца списка. На этом этапе slow будет указывать на узел перед тем, который нужно удалить.
Удаление узла:

Изменяем указатель next узла slow, чтобы пропустить n-й узел с конца списка.
Возврат нового заголовка списка:

Возвращаем dummy.next, который является новой головой списка после удаления нужного узла.
Временная и пространственная сложность:
Временная сложность: O(n), где n — длина связанного списка. Мы проходим список дважды: один раз для сдвига fast указателя и один раз для перемещения обоих указателей.
Пространственная сложность: O(1), поскольку используется только постоянное количество дополнительной памяти для указателей и фиктивного узла.

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

Условие:

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

Решение:

```class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>(); // create an empty stack
        for (char c : s.toCharArray()) { // loop through each character in the string
            if (c == '(') // if the character is an opening parenthesis
                stack.push(')'); // push the corresponding closing parenthesis onto the stack
            else if (c == '{') // if the character is an opening brace
                stack.push('}'); // push the corresponding closing brace onto the stack
            else if (c == '[') // if the character is an opening bracket
                stack.push(']'); // push the corresponding closing bracket onto the stack
            else if (stack.isEmpty() || stack.pop() != c) // if the character is a closing bracket
                // if the stack is empty (i.e., there is no matching opening bracket) or the top of the stack
                // does not match the closing bracket, the string is not valid, so return false
                return false;
        }
        // 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
        return stack.isEmpty();
    }
}
```

Пояснение:
Алгоритм использует стек для отслеживания открывающих скобок и проверки соответствия закрывающих скобок. Рассмотрим основные шаги этого алгоритма:

Инициализация стека:

Создаем пустой стек для хранения закрывающих скобок.
Проход по строке:

Проходим по каждому символу строки s.
Если символ является одной из открывающих скобок '(', '{' или '[', помещаем соответствующую закрывающую скобку в стек. Это позволяет нам отслеживать, какую закрывающую скобку мы ожидаем для данной открывающей скобки.
Проверка закрывающих скобок:

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

Если после обработки всех символов в строке стек пуст, это означает, что все открывающие скобки были успешно сопоставлены с закрывающими, и строка допустима.
Если стек не пуст, это означает, что имеются несоответствующие открывающие скобки, и строка недопустима.
Временная и пространственная сложность:
Временная сложность: O(n), где n — длина строки. Мы проходим по строке один раз.
Пространственная сложность: O(n) в худшем случае, если все символы строки являются открывающими скобками и помещаются в стек.

Задача: 45. Jump Game II #medium

Условие:

Вам дан массив целых чисел с нулевым индексом длины n. Изначально вы находитесь на позиции nums[0].

Каждый элемент nums[i] представляет максимальную длину прыжка вперед с индекса i. Другими словами, если вы находитесь на nums[i], вы можете перейти к любому nums[i + j], где:

0 <= j <= nums[i] и
я + j < п
Возвращает минимальное количество переходов для достижения nums[n - 1]. Тестовые примеры генерируются таким образом, что вы можете достичь nums[n - 1].

Решение:

class Solution {
    public int jump(int[] nums) {
        int near = 0, far = 0, jumps = 0;

        while (far < nums.length - 1) {
            int farthest = 0;
            for (int i = near; i <= far; i++) {
                farthest = Math.max(farthest, i + nums[i]);
            }
            near = far + 1;
            far = farthest;
            jumps++;
        }

        return jumps;        
    }
}

Пояснение:
Эта функция находит минимальное количество прыжков, которые нужно сделать, чтобы достичь последнего элемента в массиве. Она проходит по массиву и для каждого элемента находит наибольшую дальность, на которую можно прыгнуть. Затем обновляет границы прыжков и увеличивает счетчик прыжков. На выходе возвращает количество совершенных прыжков.

Задача: 44. Wildcard Matching #hard

Условие:

Учитывая входную строку (s) и шаблон (p), реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой '?' и где:

'?' Соответствует любому отдельному символу.
'*' Соответствует любой последовательности символов (включая пусту

ю последовательность).
Сопоставление должно охватывать всю входную строку (не частично).

Решение:

class Solution {
    public boolean isMatch(String s, String p) {
        int n=s.length();
        int m=p.length();
        boolean dp[][]=new boolean[n+1][m+1];
        dp[0][0]=true;
       for(int i=1;i<n+1;i++){
           dp[i][0]=false;
       }
       for(int i=1;i<m+1;i++){
           if(p.charAt(i-1)=='*')
           dp[0][i]=dp[0][i-1];
        }       for(int i=1;i<n+1;i++){
         for(int j=1;j<m+1;j++){ 
            if(s.charAt(i-1)==p.charAt(j-1)|| p.charAt(j-1)=='?'){
                dp[i][j]=dp[i-1][j-1];
                
            }else if(p.charAt(j-1)=='*'){
                dp[i][j]=dp[i-1][j]||dp[i][j-1];
            }else{
                dp[i][j]=false;
            }
                
         }
       }
       return dp[n][m]; 
    }
}

Пояснение:

Данная задача решается с помощью динамического программирования. Метод ismatch принимает две строки s и p и возвращает true, если строка s соответствует шаблону p, в котором '*' может заменить любую последовательность символов, а '?' может заменить любой один символ.


Алгоритм создает двумерный массив dp размером (n+1) x (m+1), где n и m - длины строк s и p соответственно. Элемент dp[i][j] будет хранить true, если подстрока s[0..i-1] соответствует подстроке p[0..j-1].


Сначала заполняются базовые случаи: dp[0][0] устанавливается в true, dp[i][0] устанавливаются в false для i от 1 до n и dp[0][i] вычисляются, если символ в p равен '*'.


Затем выполняется двойной цикл по строкам s и столбцам p. Если символы в s и p совпадают или символ в p равен '?', то для текущего элемента dp[i][j] присваивается значение dp[i-1][j-1]. Если символ в p равен '*', то dp[i][j] вычисляется как логическое ИЛИ между dp[i-1][j] и dp[i][j-1]. В противном случае dp[i][j] устанавливается в false.


В конце метод возвращает значение dp[n][m], которое показывает, соответствует ли строка s шаблону p.

Задача: 43. Multiply Strings #medium

Условие:

Учитывая два неотрицательных целых числа num1 и num2, представленных в виде строк, верните произведение num1 и num2, также представленное в виде строки.

Примечание. Вы не должны использовать встроенную библиотеку BigInteger или напрямую преобразовывать входные данные в целое число.

Решение:

public String multiply(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    int[] pos = new int[m + n];
   
    for(int i = m - 1; i >= 0; i--) {
        for(int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + pos[p2];

            pos[p1] += sum / 10;
            pos[p2] = (sum) % 10;
        }
    }  
    
    StringBuilder sb = new StringBuilder();
    for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
    return sb.length() == 0 ? "0" : sb.toString();
}

Пояснение:

1. Инициализация:
- `m` и `n` хранят длины строк `num1` и `num2` соответственно.
- Создается массив `pos` размером `m + n`, который будет хранить результат умножения. Каждый элемент массива `pos` будет представлять цифру в результате.

2. Умножение:
- Используется два вложенных цикла для перебора всех пар цифр из `num1` и `num2`.
- В каждом шаге:
- `mul` вычисляет произведение текущих цифр, преобразованных из символов в числа (отнимая '0' от ASCII-кода символа).
- `p1` и `p2` определяют индексы в массиве `pos`, куда нужно записать результат умножения. `p1` соответствует разряду, в который попадает старшая цифра произведения, а `p2` - разряду младшей цифры.
- `sum` вычисляет сумму произведения и предыдущего значения в `pos[p2]` (если оно было).
- В `pos[p1]` записывается десяток от `sum` (деление на 10 с округлением вниз), а в `pos[p2]` - единица от `sum` (остаток от деления на 10).

3. Формирование строки-результата:
- Создается объект `StringBuilder` для построения строки-результата.
- Проходит по массиву `pos` и добавляет каждую цифру в `StringBuilder`. При этом игнорируются ведущие нули.
- Если `StringBuilder` пуст, то возвращается строка "0".
- В противном случае возвращается строка, построенная с помощью `StringBuilder`.

Пример:

`num1 = "123"`, `num2 = "456"`
- `pos = [0, 0, 0, 0, 0, 0]` (начальное значение)
- После умножения: `pos = [0, 5, 6, 0, 8, 8]`
- Результат: "56088"

Преимущества:

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

Недостатки:

- Решение может быть менее эффективным, чем решения с использованием более сложных алгоритмов умножения.
- Решение работает с строками, что может быть менее эффективно, чем работа с массивами чисел.

Примечание:

Этот код демонстрирует простой и понятный способ умножения больших чисел. Существуют более эффективные алгоритмы для выполнения этой операции, например, алгоритм Карацубы.

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

Условие:

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

Решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1!=null && list2!=null){
        if(list1.val<list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
            }
            else{
                list2.next=mergeTwoLists(list1,list2.next);
                return list2;
        }
        }
        if(list1==null)
            return list2;
        return list1;
    }
}

Пояснение:
Рассмотрим, как работает предложенное решение для объединения двух отсортированных связанных списков.

Рекурсивное слияние:

Функция mergeTwoLists рекурсивно сливает два списка, list1 и list2.
Базовый случай:

Если list1 равен null, это означает, что первый список пуст, и нам просто нужно вернуть list2.
Аналогично, если list2 равен null, это означает, что второй список пуст, и нам нужно вернуть list1.
Сравнение значений узлов:

Если оба списка не пусты, мы сравниваем значения текущих узлов list1 и list2.
Если значение текущего узла list1 меньше значения текущего узла list2, мы рекурсивно вызываем mergeTwoLists для следующего узла list1 и текущего узла list2, и устанавливаем следующий узел для list1. Затем возвращаем list1.
Иначе, мы рекурсивно вызываем mergeTwoLists для текущего узла list1 и следующего узла list2, и устанавливаем следующий узел для list2. Затем возвращаем list2.
Соединение списков:

Процесс повторяется до тех пор, пока не будут обработаны все узлы обоих списков. В итоге, мы получаем отсортированный объединенный список.
Временная и пространственная сложность:
Временная сложность: O(m + n), где m и n — длины списков list1 и list2 соответственно. Мы проходим по каждому узлу обоих списков один раз.
Пространственная сложность: O(m + n) из-за рекурсивных вызовов, которые могут занимать стековую память, пропорциональную сумме длин обоих списков.

Задача: 22. Generate Parentheses #medium

Условие:

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

Решение:

 public List<String> generateParenthesis(int n) {
        Set<String> ans = new HashSet<>();
        ans = createParenthesis(n, ans);
        System.out.println("Ans: " + ans);
        return new ArrayList<>(ans);
    }

    private static Set<String> createParenthesis(int n, Set<String> currentList) {
        java.util.Set<String> temp = new HashSet<>();
        if (n <= 0) return new HashSet<>();
        if (n == 1) {
            temp.add("()");
            return temp;
        }
        currentList = createParenthesis(n - 1, currentList);
        System.out.println("At n-1 " + String.valueOf(n-1) + ": " + currentList);
        for (String parenthesis : currentList) {
            for (int i = 0; i <= parenthesis.length(); i++) {
                String newStr;
                if (i == 0) {
                    System.out.println("At 0 for " + parenthesis);
                    newStr = "()" + parenthesis;
                    System.out.println(newStr);
                } else if (i == parenthesis.length()) {
                    System.out.println("At last for " + parenthesis);
                    newStr = parenthesis + "()";
                    System.out.println(newStr);
                } else {
                    System.out.println("At " + i + " for " + parenthesis);
                    newStr = parenthesis.substring(0, i) + "()" + parenthesis.substring(i);
                    System.out.println(newStr);
                }
                temp.add(newStr);
            }
        }
        currentList = temp;

        return currentList;
    }

Пояснение:
1. Метод `generateParenthesis(int n)`:
- Создание множества HashSet ans для хранения уникальных комбинаций скобок.
- Вызов метода createParenthesis(n, ans), который будет заполнять множество ans всеми возможными комбинациями скобок.
- Вывод результата в консоль.
- Возврат списка (ArrayList) комбинаций скобок из множества ans.

2. Метод `createParenthesis(int n, Set<String> currentList)`:
- Создание временного множества temp для хранения временных комбинаций скобок.
- Проверка, если n <= 0, возвращается пустое множество.
- Если n == 1, добавляется базовая комбинация "()" во временное множество temp.
- Рекурсивный вызов createParenthesis(n - 1, currentList) для генерации комбинаций скобок с меньшим количеством пар.
- Для каждой комбинации в currentList:
- Перебор индексов в комбинации.
- Формирование новой комбинации путем вставки "()" в каждую позицию.
- Добавление полученной комбинации во временное множество temp.
- Обновление currentList на основе временного множества temp.
- Возврат текущего списка комбинаций.

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

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

Условие:

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

Решение:

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        Queue<ListNode> minHeap = new PriorityQueue<>((head1,head2)->head1.val-head2.val);
        for(ListNode listNode: lists){
            if(listNode!=null) minHeap.offer(listNode);
        }
        ListNode head=null,cur=null;
        while(!minHeap.isEmpty()){
            ListNode curNode = minHeap.poll();
            if(curNode.next!=null) minHeap.offer(curNode.next);
            if(head==null){
                head = new ListNode(curNode.val);
                cur = head;
            }
            else{
                cur.next = new ListNode(curNode.val);
                cur = cur.next;
            }
        }
        return head;
    }
}

Пояснение:
Этот код представляет собой решение задачи слияния k отсортированных связанных списков в один отсортированный связанный список.

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

Мы начинаем с создания minHeap, который представляет собой приоритетную очередь, отсортированную по значениям узлов. Мы добавляем все узлы начальных списков в эту очередь.

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

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

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

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

Условие:

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

Решение:

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next==null) return head;
        ListNode second = head.next;
        ListNode pr = swapPairs(second.next);
        second.next = head;
        head.next = pr;
        return second;
    }
}

Пояснение:
Этот код реализует функцию swapPairs, которая меняет местами каждую пару соседних узлов в связанном списке. Если в списке нечетное количество узлов, последний узел остается на своем месте.

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

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

Далее мы меняем местами текущую пару узлов: второй узел становится головой, а первый узел становится его следующим узлом. Затем мы связываем второй узел со следующей после него парой, которая возвращается из рекурсивного вызова.

Наконец, после прохода по всем парам узлов, функция возвращает новую голову списка, которая была получена после всех обменов.

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

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

Условие:

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

Решение:

 public ListNode reverseKGroup(ListNode head, int k) {
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pointer = dummy;
        
        while (pointer != null) {
            ListNode node = pointer;
            for (int i = 0; i < k && node != null; i++) node = node.next;
            if (node == null) break;
            
            // reverse the k nodes
            ListNode prev = null, curr = pointer.next;
            for (int i = 0; i < k; i++) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            
            ListNode tail = pointer.next;
            tail.next = curr;
            pointer.next = prev;
            pointer = tail;
        }
        
        return dummy.next;
    }

Пояснение:
Данный код реализует функцию reverseKGroup, которая разворачивает узлы связанного списка попарно с шагом k, начиная с головы списка. Если в конце списка остается менее чем k элементов, то они остаются на своих местах.

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

Далее функция начинает цикл, который продолжается до тех пор, пока указатель pointer не достигнет конца списка. Внутри цикла устанавливается node на текущий узел, после чего происходит обход k элементов или до конца списка. Если достигнут конец списка, то цикл прерывается.

Затем происходит разворот k узлов. Для каждой пары узлов происходит их обмен местами. Затем устанавливается связь между предыдущим и следующим блоками узлов.

Наконец, после всех обменов и перестановок блоков узлов, функция возвращает новую голову списка (которая была установлена в начале), пропуская фиктивный узел dummy.

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

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

Условие:

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

Решение:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n<=1){return n;}
        
        int left = 0; //everything to the left of left(inclusive) is good
        int right = 1;//the current element we are processing
        
        while(right<=n-1){
            if(nums[right] == nums[left]){
                right++;
            }
            else{
                nums[left+1] = nums[right];
                left++;
                right++;
            }
        }
        
        return left+1;
    }
}

Пояснение:
Данный код представляет собой решение задачи удаления дубликатов из отсортированного массива nums. Подход к решению задачи основан на использовании двух указателей - left и right, которые будут указывать на элементы массива для обработки.

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

В конце функция возвращает left + 1, что представляет собой индекс последнего уникального элемента в массиве, увеличенный на 1 для получения общего количества уникальных элементов в массиве.

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

Задача: 27. Remove Element #easy

Условие:

Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val.
Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее:
Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

class Solution {
    public int removeElement(int[] nums, int val) {
        
        int left_most_index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[left_most_index++] = nums[i];
            }
        }
        return left_most_index;        
    }
}

Пояснение:
Данный код решает задачу удаления всех вхождений указанного значения val из массива nums. Подход к решению основан на использовании переменной left_most_index, которая указывает на индекс, куда должны быть помещены уникальные элементы массива.

В начале работы функции removeElement переменная left_most_index инициализируется значением 0. Затем происходит итерация по массиву nums, где для каждого элемента проверяется, не равен ли он значению val. Если элемент отличается от val, он считается уникальным и помещается на позицию с индексом left_most_index, после чего значение left_most_index увеличивается на 1.

По завершении итерации left_most_index содержит количество уникальных элементов, находящихся в массиве после удаления всех вхождений val. Функция возвращает left_most_index, который является размером нового массива, содержащего только уникальные элементы.

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

Задача: 28. Find the Index of the First Occurrence in a String #easy

Условие:

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

Решение:

public class Solution {
    
    private int[] failureFunction(char[] str) {
        int[] f = new int[str.length+1];
        for (int i = 2; i < f.length; i++) {
            int j = f[i-1];
            while (j > 0 && str[j] != str[i-1]) j = f[j];
            if (j > 0 || str[j] == str[i-1]) f[i] = j+1;
        }
        return f;
    }

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        if (needle.length() <= haystack.length()) {
            int[] f = failureFunction(needle.toCharArray());
            int i = 0, j = 0;
            while (i < haystack.length()) {
                if (haystack.charAt(i) == needle.charAt(j)) {
                    i++; j++;
                    if (j == needle.length()) return i-j;
                } else if (j > 0) j = f[j];
                else i++;
            }
        }
        return -1;
    }
}

Пояснение:
В классе Solution содержатся два метода: failureFunction и strStr. Метод failureFunction является закрытым и используется для построения функции сбоев для заданного символьного массива str. Он возвращает массив целых чисел f, длина которого на 1 больше длины входного массива. Алгоритм метода основан на построении функции сбоев с помощью цикла с условиями проверки и корректировкой значений в массиве f.

Метод strStr является публичным и решает задачу поиска подстроки needle в строке haystack. Если длина подстроки needle равна 0, метод возвращает 0. После проверки условия на длину подстроки, метод вызывает failureFunction для подстроки needle и сохраняет значения функции сбоев в массив f. Затем происходит итерация по строке haystack, сравнение символов с подстрокой needle, и в случае несовпадения использование значений из массива f для правильного сдвига.

Когда метод найдет подстроку needle в строке haystack, он вернет индекс начала найденной подстроки. Если ничего не будет найдено, метод вернет -1. Таким образом, эти методы вместе представляют реализацию алгоритма поиска подстроки с использованием функции сбоев, основанной на алгоритме Кнута-Морриса-Пратта.

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

Решение:

public int divide(int dividend, int divisor) {
  long result = divideLong(dividend, divisor);
  return result > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)result;
}

// It's easy to handle edge cases when
// operate with long numbers rather than int
public long divideLong(long dividend, long divisor) {
  
  // Remember the sign
  boolean negative = dividend < 0 != divisor < 0;
  
  // Make dividend and divisor unsign
  if (dividend < 0) dividend = -dividend;
  if (divisor < 0) divisor = -divisor;
  
  // Return if nothing to divide
  if (dividend < divisor) return 0;
  
  // Sum divisor 2, 4, 8, 16, 32 .... times
    long sum = divisor;
    long divide = 1;
    while ((sum+sum) <= dividend) {
      sum += sum;
      divide += divide;
    }
    
    // Make a recursive call for (devided-sum) and add it to the result
    return negative ? -(divide + divideLong((dividend-sum), divisor)) :
      (divide + divideLong((dividend-sum), divisor));
}

Пояснение:
Метод divide принимает два целых числа dividend и divisor и возвращает результат их деления. Внутри метода вызывается вспомогательный метод divideLong, который работает с длинными числами типа long. Результат деления сохраняется в переменной result, а затем проверяется на превышение максимального значения типа int. Если результат больше Integer.MAX_VALUE, то возвращается Integer.MAX_VALUE, иначе результат приводится к типу int и возвращается.

Метод divideLong используется для обработки деления на длинных числах, что позволяет более удобно работать с граничными случаями. Сначала определяется знак результата деления путем сравнения знаков делимого и делителя. Затем делимое и делитель приводятся к неотрицательным значениям, чтобы избежать проблем с делением отрицательных чисел.

Если делимое меньше делителя, то возвращается 0. Далее происходит итерация в цикле, в котором значение делителя удваивается до тех пор, пока не будет превышено делимое. При этом также увеличивается счётчик divide. После завершения итераций рекурсивно вызывается divideLong для разности делимого и текущей суммы, и результату добавляется текущее значение счётчика divide. При отрицательном результате деления результат умножается на -1. Таким образом, данный метод реализует деление чисел с использованием итераций и основывается на принципе удвоения значения делителя для нахождения результата.

Задача: 30. Substring with Concatenation of All Words #hard

Условие:

Вам дана строка s и массив строк-слов. Все строки слов имеют одинаковую длину.

Объединенная строка — это строка, которая в точности содержит все строки любой перестановки объединенных слов.

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

Решение:

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> answer = new ArrayList<>();
        HashMap<String,Integer> mapOfWords = new HashMap<>();
        for(String word: words) mapOfWords.put(word,mapOfWords.getOrDefault(word,0)+1);
        int k = words[0].length();
        int n = words.length*k;
        int sLen = s.length();
        if(sLen<n) return answer;
        int[] arr = new int[26];
        for(String word: words){
            for(int i=0;i<k;i++){
                arr[word.charAt(i)-'a']++;
            }
        }
        int start=0,end=n-1;
        for(int i=0;i<=end;i++) arr[s.charAt(i)-'a']--;
        while(end<s.length()-1){
            if(allZeros(arr)&&validWords(s.substring(start,end+1),new HashMap<>(mapOfWords),k)) answer.add(start);
            arr[s.charAt(start)-'a']++;
            start++;end++;
            arr[s.charAt(end)-'a']--;
        }
        if(allZeros(arr)&&validWords(s.substring(start,end+1),new HashMap<>(mapOfWords),k)) answer.add(start);
        return answer;
    }
    public boolean allZeros(int[] arr){
        return Arrays.stream(arr).allMatch(i->i==0);
    }
    public boolean validWords(String s, HashMap<String,Integer> mapOfWords, int k){
        for(int i=0;i*k<s.length();i++){
            String currentString = s.substring(i*k,(i+1)*k);
            if(mapOfWords.containsKey(currentString)){
                mapOfWords.put(currentString,mapOfWords.get(currentString)-1);
                if(mapOfWords.get(currentString)<0) return false;
            }
            else return false;
        }
        return true;
    }
}

Пояснение:
Класс Solution содержит метод findSubstring, который принимает строку s и массив слов words и возвращает список целых чисел. Алгоритм findSubstring осуществляет поиск всех начальных индексов в строке s, где все слова из массива words встречаются последовательно. Внутри метода используются различные структуры данных, такие как HashMap и массивы для эффективного хранения данных и проверки условий.

На первом этапе метод формирует HashMap с подсчетом количества каждого слова из массива words и вычисляет длины слов и общую длину массива слов. Далее инициализируется массив arr, который используется для подсчета количества символов в каждом слове. Затем происходит последовательное сравнение слов в строке s с массивом words, с учётом совпадения и корректности слов и их количества. Если все условия соблюдаются, то добавляется индекс начала найденной подстроки в список ответа answer.

Основные вспомогательные методы allZeros и validWords используются для проверки, все ли элементы массива равны нулю и соответствуют ли найденные слова ожидаемым словам из массива words. В результате успешного анализа строки метод findSubstring возвращает список индексов начала каждой найденной подстроки.