Python | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:9 118
Subscribers
-124 hours
-297 days
-9330 days
Posts Archive
9 118
Задача: 24. Swap Nodes in Pairs #medium
Условие:
Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы).Решение:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not (head and head.next):
return head
head, head.next, head.next.next = head.next, head, self.swapPairs(head.next.next)
return head1. Функция swapPairs принимает на вход головной узел связного списка head и возвращает новую голову списка после перестановки пар узлов. 2. Сначала проверяется, есть ли головной узел head и есть ли следующий за ним узел head.next. Если нет, то возвращается исходный head, так как нечего менять. 3. Если есть как минимум два узла, то происходит перестановка: - Временная переменная temp сохраняет второй узел head.next. - Головной узел head становится третьим узлом, а его следующий узел head.next становится первым узлом. - Следующий за вторым узлом указатель head.next.next обновляется рекурсивным вызовом self.swapPairs(head.next.next), чтобы перестроить оставшуюся часть списка. - Головной узел head возвращается в качестве новой головы списка. 4. Рекурсивный вызов self.swapPairs(head.next.next) будет происходить, пока не останется меньше двух узлов в списке. Это обеспечивает перестановку всех пар узлов.
9 118
📌 Составили список лучших каналов от действующих разработчиков:
Python Developer — советы и практики от действующего Senior-разработчика
Java Developer — секреты и тонкости программирования на Java
Frontend Developer — готовый код и полезные ресурсы для любого фронтендера
9 118
😮 Добавлена новая база слитых курсов на 800ГБ:
Python:
https://t.me/+-3O1svHQCGUxNWYy
Программирование:
https://t.me/+1VPcMAgJ7oliYmQy
Frontend и Web:
https://t.me/+viU1cwWNrNE2YWIy
Графика и дизайн:
https://t.me/+28fE7chaCHRhZTYy
9 118
Задача: 23. Merge k Sorted Lists #medium
Условие:
Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.Объедините все связанные списки в один отсортированный связанный список и верните его.Решение:
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
n = len(lists)
newList = ListNode()
new = newList
while n:
# Find list with smallest value:
smallestNode = ListNode(float('inf'))
smallestIndex = -1
for i in range(n):
listNode = lists[i]
if listNode and listNode.val < smallestNode.val:
smallestNode = listNode
smallestIndex = i
if smallestIndex == -1:
break
new.next = ListNode(smallestNode.val)
new = new.next
if smallestNode.next:
lists[smallestIndex] = smallestNode.next
else:
lists.pop(smallestIndex)
n-=1
return newList.next 1. Определяется класс ListNode, который представляет узел связного списка. У него есть два атрибута: val (значение узла) и next (ссылка на следующий узел). 2. Определяется класс Solution, который содержит метод mergeKLists. 3. Метод mergeKLists принимает на вход список lists, который является списком связных списков. Каждый список в lists является необязательным (Optional[ListNode]). 4. Вначале определяется длина списка lists и сохраняется в переменной n. 5. Создается новый связный список newList и переменная new, которая будет указывать на последний добавленный узел в newList. 6. Запускается цикл, который продолжается, пока n (количество списков в lists) не станет равным 0. 7. Внутри цикла производится поиск списка с наименьшим значением в первом узле. Для этого: - Создается переменная smallestNode со значением бесконечности. - Создается переменная smallestIndex со значением -1. - Перебираются все списки в lists. - Если текущий список не пуст и значение в его первом узле меньше, чем в smallestNode, то smallestNode и smallestIndex обновляются. 8. Если smallestIndex равен -1, это означает, что все списки в lists пусты, поэтому цикл завершается. 9. Иначе создается новый узел с значением, взятым из smallestNode, и добавляется в конец newList. 10. Если у smallestNode есть следующий узел, то соответствующий список в lists обновляется, чтобы указывать на этот следующий узел. Если у smallestNode нет следующего узла, то этот список удаляется из lists, и n уменьшается на 1. 11. После завершения цикла возвращается newList.next, так как первый узел newList был пустым вспомогательным узлом.
9 118
Задача: 22. Generate Parentheses #medium
Условие:
Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.Решение:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(left, right, s):
if len(s) == n * 2:
res.append(s)
return
if left < n:
dfs(left + 1, right, s + '(')
if right < left:
dfs(left, right + 1, s + ')')
res = []
dfs(0, 0, '')
return res1. Функция generateParenthesis принимает на вход целое число n, которое представляет количество пар скобок, которые нужно сгенерировать. 2. Внутри функции есть вспомогательная функция, называемая dfs (Depth-First Search). Эта функция выполняет фактическую генерацию скобок. 3. Функция dfs принимает три параметра: - left: количество открывающих скобок в текущей строке. - right: количество закрывающих скобок в текущей строке. - s: текущая строка скобок. 4. Базовый случай рекурсии - когда длина строки s равна n * 2, что означает, что мы сгенерировали полную строку скобок. В этом случае мы добавляем текущую строку s в список res и выходим из функции. 5. Первый рекурсивный случай - когда left меньше n. Это значит, что мы можем добавить открывающую скобку к строке. Поэтому мы вызываем dfs с left + 1, right без изменений и s + '('. 6. Второй рекурсивный случай - когда right меньше left. Это означает, что мы можем добавить закрывающую скобку к строке, так как количество закрывающих скобок меньше количества открывающих. Поэтому мы вызываем dfs с left без изменений, right + 1 и s + ')'. 7. Функция dfs первоначально вызывается с left = 0, right = 0 и пустой строкой ''. 8. Рекурсивные вызовы продолжаются, пока не будет достигнут базовый случай, и все допустимые сочетания скобок будут добавлены в список res. 9. Наконец, функция generateParenthesis возвращает список res, содержащий все допустимые строки скобок длины n * 2.
9 118
Задача: №21. Merge Two Sorted Lists #easy
Условие:
Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.Решение:
class Solution(object):
def mergeTwoLists(self, l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next 9 118
Задача: 44. Wildcard Matching #Hard
Условие:
При наличии входных строк и шаблона (p) реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой "?" и "*", где: "?" Соответствует любому отдельному символу."*" Соответствует любой последовательности символов (включая пустую последовательность). Соответствие должно охватывать всю входную строку (не частичное).Решение:
class Solution:
def isMatch(self, s: str, p: str) -> bool:
memo = [[None] * (len(p) + 1) for _ in range(len(s) + 1)]
return self.f(s, 0, p, 0, memo)
def f(self, s, i, p, j, memo):
if i == len(s) and j == len(p): //both strings end : match successfull
return True
//Pattern is over but string is left: match unsuccessful.
//Point to note : if String is over and pattern is left,
//it 'might' still be possible to match the string.
//Take for eg. s = "" and p = "*******".
if j == len(p):
return False
if memo[i][j] is None: //subproblem not solved earlier.
flag = False
//match single character, but string s should be left,
//else we get IndexError
if i < len(s) and (s[i] == p[j] or p[j] == '?'):
flag = self.f(s, i + 1, p, j + 1, memo)
elif p[j] == '*': // can match variable no. of characters, so loop over them and see when it matches.
for t in range(i, len(s) + 1):
if self.f(s, t, p, j + 1, memo):
flag = True
break
//if it doesn't ever match, the flag will be False by default.
memo[i][j] = flag
return memo[i][j]
9 118
Задача: 45. Jump Game II #Medium
Условие:
Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0]. Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i. Другими словами, если вы находитесь в nums[i], вы можете перейти к любому nums[i + j], где: 0 <= j <= nums[i] иi + j < n Возвращает минимальное количество переходов для достижения nums[n - 1]. Тестовые примеры генерируются таким образом, чтобы вы могли достичь nums[n - 1].Решение:
class Solution:
def jump(self, nums: List[int]) -> int:
ans = 0
end = 0
farthest = 0
# Implicit BFS
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if farthest >= len(nums) - 1:
ans += 1
break
if i == end: # Visited all the items on the current level
ans += 1 # Increment the level
end = farthest # Make the queue size for the next level
return ans9 118
Задача: 46. Permutations #Medium
Условие:
Учитывая массив nums, состоящий из различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке.Решение:
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
def permute_rec(nums, current_index, result):
if current_index == len(nums) - 1:
result.append(nums.copy())
return
for index in range(current_index, len(nums)):
nums[current_index], nums[index] = nums[index], nums[current_index]
permute_rec(nums, current_index + 1, result)
nums[current_index], nums[index] = nums[index], nums[current_index]
permute_rec(nums, 0, result)
return result9 118
Задача: №20. Valid Parentheses #easy
Условие:
Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа. Открытые скобки должны закрываться в правильном порядке. Каждой закрывающей скобке соответствует открытая скобка того же типа.Решение:
def isValid(self, s: str) -> bool:
dic = {'(':1 , ')':2 , '[':3 , ']':6 , '{':5 , '}':10}
res = []
for one in s:
temp = dic[one]
if(temp %2 ):
res.append(temp)
else:
if(len(res) and res[-1]==temp//2):
del res[-1]
else:
return False
return res==[]9 118
Задача: №19. Remove Nth Node From End of List #medium
Условие:
Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.Решение:
# class ListNode:
# def init(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if head.next == None:
return None
tmp = head
size = 0
# find the size of the linked list
while tmp:
size += 1
tmp = tmp.next
tmp = head
#if we have to remove the first node:
if n == size:
return head.next
for i in range(size-n-1):
tmp = tmp.next
tmp.next = tmp.next.next
return head9 118
Задача: №18. 4Sum #medium
Условие:
Учитывая массив 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
```
9 118
Задача: №17. Letter Combinations of a Phone Number #medium
Условие:
Учитывая строку, содержащую цифры от 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)9 118
Задача: №16. 3Sum Closest #medium
Условие:
Учитывая целочисленный массив 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
```
