Задача: №16. 3Sum Closest #medium
Условие:
Решение:
Пояснение:
Задача требует нахождения суммы трёх чисел в массиве 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), так как используется постоянное количество дополнительной памяти.
Условие:
Учитывая целочисленный массив 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), так как используется постоянное количество дополнительной памяти.
👍9
Задача: №17. Letter Combinations of a Phone Number #medium
Условие:
Решение:
Пояснение:
Задача заключается в том, чтобы сгенерировать все возможные комбинации букв для заданной строки цифр, используя телефонную клавиатуру. Рассмотрим алгоритм подробнее.
Алгоритм:Проверка пустой строки:Если входная строка 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.
Условие:
Учитывая строку, содержащую цифры от 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.
👍5
Задача: №18. 4Sum #medium
Условие:
Решение:
Пояснение:
Задача заключается в том, чтобы найти все уникальные комбинации четырех чисел в массиве 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.
Условие:
Учитывая массив 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-го узла с конца связанного списка. Рассмотрим этот алгоритм более подробно.
Инициализация:
Создаем фиктивный узел dummy, который указывает на голову списка. Это позволяет упростить обработку граничных случаев, таких как удаление головного узла.
Инициализируем два указателя, fast и slow, которые оба начинают с фиктивного узла.
Сдвиг fast указателя на n шагов вперед:
Перемещаем указатель fast на n шагов вперед, чтобы между fast и slow был разрыв в n узлов.
Перемещение обоих указателей:
Перемещаем оба указателя вперед, пока fast не достигнет конца списка. На этом этапе slow будет указывать на узел перед тем, который нужно удалить.
Удаление узла:
Изменяем указатель next узла slow, чтобы пропустить n-й узел с конца списка.
Возврат нового заголовка списка:
Возвращаем dummy.next, который является новой головой списка после удаления нужного узла.
Временная и пространственная сложность:
Временная сложность: O(n), где n — длина связанного списка. Мы проходим список дважды: один раз для сдвига fast указателя и один раз для перемещения обоих указателей.
Пространственная сложность: O(1), поскольку используется только постоянное количество дополнительной памяти для указателей и фиктивного узла.
Условие:
Учитывая заголовок связанного списка, удалите 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), поскольку используется только постоянное количество дополнительной памяти для указателей и фиктивного узла.
👍1
Задача: №20. Valid Parentheses #easy
Условие:
Решение:
Пояснение:
Алгоритм использует стек для отслеживания открывающих скобок и проверки соответствия закрывающих скобок. Рассмотрим основные шаги этого алгоритма:
Инициализация стека:
Создаем пустой стек для хранения закрывающих скобок.
Проход по строке:
Проходим по каждому символу строки s.
Если символ является одной из открывающих скобок '(', '{' или '[', помещаем соответствующую закрывающую скобку в стек. Это позволяет нам отслеживать, какую закрывающую скобку мы ожидаем для данной открывающей скобки.
Проверка закрывающих скобок:
Если символ является закрывающей скобкой, проверяем, совпадает ли она с верхним элементом стека:
Если стек пуст, это означает, что нет соответствующей открывающей скобки, и строка недопустима.
Если верхний элемент стека не соответствует текущей закрывающей скобке, строка также недопустима.
Финальная проверка:
Если после обработки всех символов в строке стек пуст, это означает, что все открывающие скобки были успешно сопоставлены с закрывающими, и строка допустима.
Если стек не пуст, это означает, что имеются несоответствующие открывающие скобки, и строка недопустима.
Временная и пространственная сложность:
Временная сложность: O(n), где n — длина строки. Мы проходим по строке один раз.
Пространственная сложность: O(n) в худшем случае, если все символы строки являются открывающими скобками и помещаются в стек.
Условие:
Учитывая строку 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) в худшем случае, если все символы строки являются открывающими скобками и помещаются в стек.
👍4🤔2
Задача: 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;
}
}
Пояснение:
Эта функция находит минимальное количество прыжков, которые нужно сделать, чтобы достичь последнего элемента в массиве. Она проходит по массиву и для каждого элемента находит наибольшую дальность, на которую можно прыгнуть. Затем обновляет границы прыжков и увеличивает счетчик прыжков. На выходе возвращает количество совершенных прыжков.
👍2
Задача: 44. Wildcard Matching #hard
Условие:
Решение:
Пояснение:
Данная задача решается с помощью динамического программирования. Метод 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.
Условие:
Учитывая входную строку (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.
👍2❤1🤔1
Задача: 43. Multiply Strings #medium
Условие:
Решение:
Пояснение:
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"
Преимущества:
- Решение работает с большими числами, которые не могут быть представлены стандартными типами данных.
- Решение использует простую логику для вычисления произведения цифр и переноса в старшие разряды.
- Решение не требует дополнительных библиотек или функций.
Недостатки:
- Решение может быть менее эффективным, чем решения с использованием более сложных алгоритмов умножения.
- Решение работает с строками, что может быть менее эффективно, чем работа с массивами чисел.
Примечание:
Этот код демонстрирует простой и понятный способ умножения больших чисел. Существуют более эффективные алгоритмы для выполнения этой операции, например, алгоритм Карацубы.
Условие:
Учитывая два неотрицательных целых числа 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"
Преимущества:
- Решение работает с большими числами, которые не могут быть представлены стандартными типами данных.
- Решение использует простую логику для вычисления произведения цифр и переноса в старшие разряды.
- Решение не требует дополнительных библиотек или функций.
Недостатки:
- Решение может быть менее эффективным, чем решения с использованием более сложных алгоритмов умножения.
- Решение работает с строками, что может быть менее эффективно, чем работа с массивами чисел.
Примечание:
Этот код демонстрирует простой и понятный способ умножения больших чисел. Существуют более эффективные алгоритмы для выполнения этой операции, например, алгоритм Карацубы.
👍7🤯1
Задача: №21. Merge Two Sorted Lists #easy
Условие:
Решение:
Пояснение:
Рассмотрим, как работает предложенное решение для объединения двух отсортированных связанных списков.
Рекурсивное слияние:
Функция 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) из-за рекурсивных вызовов, которые могут занимать стековую память, пропорциональную сумме длин обоих списков.
Условие:
Вам даны заголовки двух отсортированных связанных списков 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) из-за рекурсивных вызовов, которые могут занимать стековую память, пропорциональную сумме длин обоих списков.
👍7💊2❤1
Задача: 22. Generate Parentheses #medium
Условие:
Решение:
Пояснение:
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. Рекурсивный подход позволяет итеративно строить комбинации, добавляя "()" в различные позиции.
Условие:
Учитывая 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. Рекурсивный подход позволяет итеративно строить комбинации, добавляя "()" в различные позиции.
👍6
Задача: 23. Merge k Sorted Lists #hard
Условие:
Решение:
Пояснение:
Этот код представляет собой решение задачи слияния k отсортированных связанных списков в один отсортированный связанный список.
Подход к решению задачи заключается в использовании приоритетной очереди (PriorityQueue) для хранения узлов всех списков. При этом элементы будут храниться в очереди с учетом их значений, чтобы мы могли получать самый минимальный узел каждый раз.
Мы начинаем с создания minHeap, который представляет собой приоритетную очередь, отсортированную по значениям узлов. Мы добавляем все узлы начальных списков в эту очередь.
Затем мы начинаем извлекать и обрабатывать узлы из очереди. Мы извлекаем минимальный узел из очереди и добавляем его значение в новый связанный список. Затем мы проверяем, есть ли следующий узел этого списка, и если есть, добавляем его в очередь.
Мы продолжаем этот процесс до тех пор, пока очередь не опустеет. В конце, когда все узлы из очереди обработаны, мы возвращаем голову нового слияния отсортированного списка.
Таким образом, данный код эффективно объединяет k отсортированных списков в один отсортированный список, используя приоритетную очередь для поддержания правильного порядка узлов.
Условие:
Вам дан массив из 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 отсортированных списков в один отсортированный список, используя приоритетную очередь для поддержания правильного порядка узлов.
❤3👍3
Задача: 24. Swap Nodes in Pairs #medium
Условие:
Решение:
Пояснение:
Этот код реализует функцию swapPairs, которая меняет местами каждую пару соседних узлов в связанном списке. Если в списке нечетное количество узлов, последний узел остается на своем месте.
Функция начинает с проверки базовых случаев: если список пуст или содержит только один узел, то возвращается исходный список, так как в нем нет пар для обмена.
Затем функция продолжает рекурсивно вызывать саму себя для оставшейся части списка (начиная со второго узла) и последующих узлов, после того как пара была обменена.
Далее мы меняем местами текущую пару узлов: второй узел становится головой, а первый узел становится его следующим узлом. Затем мы связываем второй узел со следующей после него парой, которая возвращается из рекурсивного вызова.
Наконец, после прохода по всем парам узлов, функция возвращает новую голову списка, которая была получена после всех обменов.
Таким образом, данный код эффективно меняет местами каждую пару соседних узлов в связанном списке, используя рекурсию для обработки всех пар узлов.
Условие:
Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы).
Решение:
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, которая меняет местами каждую пару соседних узлов в связанном списке. Если в списке нечетное количество узлов, последний узел остается на своем месте.
Функция начинает с проверки базовых случаев: если список пуст или содержит только один узел, то возвращается исходный список, так как в нем нет пар для обмена.
Затем функция продолжает рекурсивно вызывать саму себя для оставшейся части списка (начиная со второго узла) и последующих узлов, после того как пара была обменена.
Далее мы меняем местами текущую пару узлов: второй узел становится головой, а первый узел становится его следующим узлом. Затем мы связываем второй узел со следующей после него парой, которая возвращается из рекурсивного вызова.
Наконец, после прохода по всем парам узлов, функция возвращает новую голову списка, которая была получена после всех обменов.
Таким образом, данный код эффективно меняет местами каждую пару соседних узлов в связанном списке, используя рекурсию для обработки всех пар узлов.
👍3❤1