leetcode 21-30（2024.08.16）

立个flag，1-100题每天分配10题，不会就先空着（5，9）。

1. 21：合并两个有序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:dummy = res = ListNode()while list1 and list2:if list1.val < list2.val:res.next = list1list1 = list1.nextelse:res.next = list2list2 = list2.nextres = res.nextif list1:res.next = list1if list2:res.next = list2return dummy.next

2. 22：括号生成

class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtracking(left, right, n, path, res):if left > n or right > n or right > left:returnif len(path) == 2 * n:valid = "".join(path.copy())res.append(valid)path.append('(')backtracking(left + 1, right, n, path, res)path.pop()path.append(')')backtracking(left, right + 1, n, path, res)path.pop()res = []path = []left = 0right = 0backtracking(left, right, n, path, res)return res

3. 23：合并K个升序链表

# Definition for singly-linked list.
# 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]:def mergeTwoLists(l1, l2):dummy = res = ListNode()while l1 and l2:if l1.val < l2.val:res.next = l1l1 = l1.nextelse:res.next = l2l2 = l2.nextres = res.nextif l1:res.next = l1if l2:res.next = l2return dummy.nextres = Nonefor i in lists:res = mergeTwoLists(res, i)return res

 4. 24：两两交换链表中的节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:dummy = res = ListNode()res.next = headwhile head and head.next:temp = head.nexthead.next = head.next.nexttemp.next = headres.next = temphead = head.nextres = res.next.nextreturn dummy.next

 5. 25：K个一组翻转链表 

 6. 26：删除有序数组中的重复项 

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slow = 0fast = 0while fast < len(nums):if nums[slow] != nums[fast]:slow = slow + 1nums[slow] = nums[fast]fast = fast + 1return slow + 1

 7. 27：移除元素

class Solution:def removeElement(self, nums: List[int], val: int) -> int:slow = 0fast = 0while fast < len(nums):if nums[fast] != val:nums[slow] = nums[fast]slow = slow + 1fast = fast + 1return slow

 8. 28：找出字符串中第一个匹配项的下标

class Solution:def strStr(self, haystack: str, needle: str) -> int:lis = []for i in range(len(haystack)):if haystack[i] == needle[0]:lis.append(i)res = -1for i in lis:if haystack[i : i + len(needle)] == needle:res = ibreakreturn res

 9. 29：两数相除 

 10. 30：串联所有单词的子串

class Solution:def findSubstring(self, s: str, words: List[str]) -> List[int]:def pair(st, haxi, leng):begin = 0while begin + leng <= len(st):word = st[begin : begin + leng]if word in haxi and haxi[word] > 0:haxi[word] = haxi[word] - 1begin = begin + lengelse:return Falsereturn Truehaxi = {}for word in words:if word in haxi:haxi[word] = haxi[word] + 1else:haxi[word] = 1res = []num = len(words)leng = len(words[0])length = num * lengleft = 0right = left + lengthwhile right <= len(s):st = s[left:right]output = pair(st, haxi.copy(), leng)if output:res.append(left)left = left + 1right = left + lengthreturn res