热题系列章节20

embedded/2024/9/23 9:15:56/

25. K 个一组翻转链表

python"># Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from queue import PriorityQueue
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:nums = []for l in lists:while l:nums.append(l.val)l = l.nextnums.sort()cur = head = ListNode(0)for i in nums:cur.next = ListNode(val=i)cur= cur.nextreturn head.next

5. 最长回文子串

33. 搜索旋转排序数组

200. 岛屿数量

92. 反转链表 II

python"># 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]:head=ListNode(0)# 创建一个指针用于遍历合并链表current=head# 当两个链表同时都有节点时while list1 and list2:# 如果链表l1节点的值>=l2节点的值,将l2当前节点赋予current的下一个节点# 将l2指向其下一个节点if list1.val>=list2.val:current.next=list2list2=list2.nextelse:current.next=list1list1=list1.nextcurrent=current.next# 将剩余部分连接到合并链表的末尾current.next= list1 if list1 else list2return head.next

23. 合并K个排序链表

python"># Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from queue import PriorityQueue
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:nums = []for l in lists:while l:nums.append(l.val)l = l.nextnums.sort()cur = head = ListNode(0)for i in nums:cur.next = ListNode(val=i)cur= cur.nextreturn head.next

143. 重排链表

python">class Solution(object):def reorderList(self, head):""":type head: ListNode:rtype: None Do not return anything, modify head in-place instead."""if not head or not head.next: return head# 1 2 3 4 5fast = headpre_mid = head# 找到中点, 偶数个找到时上界那个while fast.next and fast.next.next:pre_mid = pre_mid.nextfast = fast.next.next# 翻转中点之后的链表,采用是pre, cur双指针方法pre = Nonecur = pre_mid.next# 1 2 5 4 3while cur:tmp = cur.nextcur.next = prepre = curcur = tmp# 翻转链表和前面链表拼接pre_mid.next = pre# 1 5 2 4 3# 链表头p1 = head# 翻转头p2 = pre_mid.next#print(p1.val, p2.val)while p1 != pre_mid:# 建议大家这部分画图, 很容易理解pre_mid.next = p2.nextp2.next = p1.nextp1.next = p2p1 = p2.nextp2 = pre_mid.next

124. 二叉树中的最大路径和

python"># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:self.ans = float("-inf")def maxGain(r):if not r:return 0 left = max(maxGain(r.left), 0) # 注意：这里的需要保存大于0 的根right = max(maxGain(r.right), 0)self.ans = max(self.ans, r.val+left+right) # 不然遇到[2,-1]的情况会出错return r.val+max(left, right)maxGain(root)return self.ans