Задача: №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
Задача: №18. 4Sum #medium
Условие:
Решение:
Пояснение:
Сортировка:
Сначала массив nums сортируется. Сортировка упрощает обработку дубликатов и ускоряет выполнение с помощью двоичного поиска.
Рекурсивная функция findNsum:
Функция findNsum рекурсивно находит комбинации, сумма которых равна заданному target. В зависимости от значения N, она обрабатывает различные случаи:
Для N = 2: Это подзадача "Two Sum". Мы используем два указателя (l и r), чтобы найти пары чисел в массиве, которые суммируются до target.
Если текущая пара чисел nums[l] и nums[r] суммируется до target, добавляем эту пару к результатам.
Двигаем указатели влево и вправо, пропуская дубликаты, чтобы избежать повторных комбинаций.
Для N > 2: Функция рекурсивно вызывает себя, уменьшая N на 1 и продолжая искать комбинации среди оставшихся элементов массива. Мы также проверяем, находятся ли текущий элемент и его комбинации в допустимом диапазоне (для оптимизации).
Условия выхода из рекурсии:
Если длина массива меньше N или N меньше 2, функция завершает выполнение, так как это не имеет смысла для дальнейшего поиска комбинаций.
Мы используем условия, чтобы прекратить выполнение, если текущий элемент слишком велик или слишком мал для достижения целевого значения при данном числе элементов (N).
Уникальные комбинации:
Чтобы избежать дубликатов, проверяем, является ли текущий элемент уникальным по сравнению с предыдущими.
Сбор результатов:
Результаты для каждого вызова функции findNsum добавляются в общий список results.
Условие:
Учитывая массив 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] == цель
Вы можете вернуть ответ в любом порядке.
Решение:
def fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
Пояснение:
Сортировка:
Сначала массив nums сортируется. Сортировка упрощает обработку дубликатов и ускоряет выполнение с помощью двоичного поиска.
Рекурсивная функция findNsum:
Функция findNsum рекурсивно находит комбинации, сумма которых равна заданному target. В зависимости от значения N, она обрабатывает различные случаи:
Для N = 2: Это подзадача "Two Sum". Мы используем два указателя (l и r), чтобы найти пары чисел в массиве, которые суммируются до target.
Если текущая пара чисел nums[l] и nums[r] суммируется до target, добавляем эту пару к результатам.
Двигаем указатели влево и вправо, пропуская дубликаты, чтобы избежать повторных комбинаций.
Для N > 2: Функция рекурсивно вызывает себя, уменьшая N на 1 и продолжая искать комбинации среди оставшихся элементов массива. Мы также проверяем, находятся ли текущий элемент и его комбинации в допустимом диапазоне (для оптимизации).
Условия выхода из рекурсии:
Если длина массива меньше N или N меньше 2, функция завершает выполнение, так как это не имеет смысла для дальнейшего поиска комбинаций.
Мы используем условия, чтобы прекратить выполнение, если текущий элемент слишком велик или слишком мал для достижения целевого значения при данном числе элементов (N).
Уникальные комбинации:
Чтобы избежать дубликатов, проверяем, является ли текущий элемент уникальным по сравнению с предыдущими.
Сбор результатов:
Результаты для каждого вызова функции findNsum добавляются в общий список results.
🔥1