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