Задача: №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), поскольку используется только постоянное количество дополнительной памяти для указателей и фиктивного узла.