Задача: №16. 3Sum Closest #medium
Условие:
Решение:
Пояснение:
Сортировка массива:
Сначала мы сортируем массив num. Это позволит нам использовать два указателя для нахождения наиболее близкой суммы.
Инициализация результата:
Инициализируем переменную result суммой первых трех элементов отсортированного массива. Это будет нашей начальной ближайшей суммой.
Проход по массиву:
Используем цикл for, чтобы пройти по массиву. Для каждого элемента используем два указателя j и k:
j начинается сразу после текущего элемента i.
k начинается с конца массива.
Два указателя:
Внутри цикла while, пока j меньше k, вычисляем сумму sum элементов num[i], num[j] и num[k].
Если сумма sum равна target, то возвращаем sum, так как мы нашли точное соответствие.
Обновление результата:
Если текущая сумма sum ближе к target, чем предыдущая ближайшая сумма result, обновляем result.
Сдвиг указателей:
Если sum меньше target, сдвигаем указатель j вправо, чтобы увеличить сумму.
Если sum больше target, сдвигаем указатель k влево, чтобы уменьшить сумму.
Возврат результата:
После завершения всех итераций возвращаем result, которая будет содержать сумму трех чисел, ближайшую к target.
Временная и пространственная сложность:
Временная сложность: O(n^2), где n — длина массива. Сортировка занимает O(n log n), и основной алгоритм с двумя указателями выполняется за O(n^2).
Пространственная сложность: O(1), так как мы используем только несколько дополнительных переменных, и не используем дополнительную память, зависящую от размера входных данных.
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Решение:
```class Solution:
def threeSumClosest(self, num, target):
num.sort()
result = num[0] + num[1] + num[2]
for i in range(len(num) - 2):
j, k = i+1, len(num) - 1
while j < k:
sum = num[i] + num[j] + num[k]
if sum == target:
return sum
if abs(sum - target) < abs(result - target):
result = sum
if sum < target:
j += 1
elif sum > target:
k -= 1
else:
return result
return result
```
Пояснение:
Сортировка массива:
Сначала мы сортируем массив num. Это позволит нам использовать два указателя для нахождения наиболее близкой суммы.
Инициализация результата:
Инициализируем переменную result суммой первых трех элементов отсортированного массива. Это будет нашей начальной ближайшей суммой.
Проход по массиву:
Используем цикл for, чтобы пройти по массиву. Для каждого элемента используем два указателя j и k:
j начинается сразу после текущего элемента i.
k начинается с конца массива.
Два указателя:
Внутри цикла while, пока j меньше k, вычисляем сумму sum элементов num[i], num[j] и num[k].
Если сумма sum равна target, то возвращаем sum, так как мы нашли точное соответствие.
Обновление результата:
Если текущая сумма sum ближе к target, чем предыдущая ближайшая сумма result, обновляем result.
Сдвиг указателей:
Если sum меньше target, сдвигаем указатель j вправо, чтобы увеличить сумму.
Если sum больше target, сдвигаем указатель k влево, чтобы уменьшить сумму.
Возврат результата:
После завершения всех итераций возвращаем result, которая будет содержать сумму трех чисел, ближайшую к target.
Временная и пространственная сложность:
Временная сложность: O(n^2), где n — длина массива. Сортировка занимает O(n log n), и основной алгоритм с двумя указателями выполняется за O(n^2).
Пространственная сложность: O(1), так как мы используем только несколько дополнительных переменных, и не используем дополнительную память, зависящую от размера входных данных.
👍12❤2🔥1
Задача: №17. Letter Combinations of a Phone Number #medium
Условие:
Решение:
Пояснение:
Сортировка:
Сначала мы сортируем массив nums. Сортировка помогает легко обрабатывать дубликаты, так как одинаковые элементы будут расположены рядом.
Рекурсивный метод dfs:
Метод dfs используется для рекурсивного построения всех возможных подмножеств. В dfs, path представляет текущее подмножество, а res — список всех подмножеств.
Добавление подмножества в результат:
На каждом уровне рекурсии мы добавляем текущее подмножество path в результат res.
Обработка дубликатов:
Перед продолжением рекурсии проверяем, является ли текущий элемент nums[i] дубликатом предыдущего элемента. Если это так, пропускаем его, чтобы избежать повторного добавления одинаковых подмножеств в res.
Рекурсивное построение подмножеств:
Для каждого элемента в nums, начиная с текущего индекса, мы вызываем dfs для следующих элементов массива (nums[i+1:]). Это означает, что мы рассматриваем подмножества, включающие текущий элемент, и продолжаем строить подмножества без текущего элемента.
Путь (path) и отсек (nums):
Каждый раз при вызове dfs создается новое подмножество, добавляя текущий элемент к path. Затем этот новый список передается в следующий уровень рекурсии, что позволяет построить все возможные подмножества.
Временная и пространственная сложность:
Временная сложность: O(2^n), где n — количество элементов в nums. Это связано с тем, что существует 2^n подмножеств для массива из n элементов.
Пространственная сложность: O(2^n * n), так как для каждой из 2^n возможных подмножеств может потребоваться до n элементов для хранения.
Условие:
Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.
Решение:
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
res.append(path)
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
self.dfs(nums[i+1:], path + [nums[i]], res)
Пояснение:
Сортировка:
Сначала мы сортируем массив nums. Сортировка помогает легко обрабатывать дубликаты, так как одинаковые элементы будут расположены рядом.
Рекурсивный метод dfs:
Метод dfs используется для рекурсивного построения всех возможных подмножеств. В dfs, path представляет текущее подмножество, а res — список всех подмножеств.
Добавление подмножества в результат:
На каждом уровне рекурсии мы добавляем текущее подмножество path в результат res.
Обработка дубликатов:
Перед продолжением рекурсии проверяем, является ли текущий элемент nums[i] дубликатом предыдущего элемента. Если это так, пропускаем его, чтобы избежать повторного добавления одинаковых подмножеств в res.
Рекурсивное построение подмножеств:
Для каждого элемента в nums, начиная с текущего индекса, мы вызываем dfs для следующих элементов массива (nums[i+1:]). Это означает, что мы рассматриваем подмножества, включающие текущий элемент, и продолжаем строить подмножества без текущего элемента.
Путь (path) и отсек (nums):
Каждый раз при вызове dfs создается новое подмножество, добавляя текущий элемент к path. Затем этот новый список передается в следующий уровень рекурсии, что позволяет построить все возможные подмножества.
Временная и пространственная сложность:
Временная сложность: O(2^n), где n — количество элементов в nums. Это связано с тем, что существует 2^n подмножеств для массива из n элементов.
Пространственная сложность: O(2^n * n), так как для каждой из 2^n возможных подмножеств может потребоваться до n элементов для хранения.
👍3❤1