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