Задача: №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;        
    }
}

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