目录
103. 二叉树的锯齿形层序遍历
# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res=[]
queue=[root]
cnt=0
while queue:
level_node=[]
level_value=[]
for node in queue:
if node:
level_value.append(node.val)
if node.left:
level_node.append(node.left)
if node.right:
level_node.append(node.right)
if cnt%2==1:
level_value=level_value[::-1]
res.append(level_value)
cnt+=1
queue=level_node
return res
92. 反转链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
def reverse(head):
pre=None
cur=head
while cur:
temp=cur.next
cur.next=pre
pre=cur
cur=temp
dummy=ListNode(next=head)
pre=dummy
for i in range(left-1):
pre=pre.next
rightNode=pre
for i in range(right-left+1):
rightNode=rightNode.next
leftNode=pre.next
back=rightNode.next
pre.next=None
rightNode.next=None
reverse(leftNode)
pre.next=rightNode
leftNode.next=back
return dummy.next
54. 螺旋矩阵
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
visited = [[False] * n for _ in range(m)]
total = m * n
res = [0] * total
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
i, j = 0, 0
d = 0
for k in range(total):
res[k] = matrix[i][j]
visited[i][j] = True
ni, nj = i + dirs[d][0], j + dirs[d][1]
if not (0 <= ni < m and 0 <= nj < n) or visited[ni][nj]==True: # 拐弯的条件
d = (d + 1) % 4
i += dirs[d][0]
j += dirs[d][1]
return res
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 merge2Lists(list1,list2):
if not list1:
return list2
if not list2:
return list1
if list1.val<=list2.val:
list1.next=merge2Lists(list1.next,list2)
return list1
else:
list2.next=merge2Lists(list2.next,list1)
return list2
if not lists:
return None
n=len(lists)
if n==1:
return lists[0]
mid=n//2
left=self.mergeKLists(lists[:mid])
right=self.mergeKLists(lists[mid:])
return merge2Lists(left,right)
160. 相交链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
a,b=headA,headB
while a!=b:
a=a.next if a else headB
b=b.next if b else headA
return a
300. 最长递增子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp=[1 for _ in range(len(nums))]
res=1
for i in range(1,len(nums)):
for j in range(i):
if nums[j]<nums[i]:
# 用j去遍历i之前的每一个元素
dp[i]=max(dp[i],dp[j]+1)
res=max(res,dp[i])
return res
415. 字符串相加
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
# 不能直接将输入的字符串转为整数
res=""
i,j,carry=len(num1)-1,len(num2)-1,0
while i>=0 or j>=0:
n1=int(num1[i]) if i>=0 else 0
n2=int(num2[j]) if j>=0 else 0
tmp=n1+n2+carry
carry=tmp//10
res=str(tmp%10)+res # 不能写成res+=str(tmp%10),字符串的加法还是讲究顺序的
i=i-1
j=j-1
return "1"+res if carry else res
143. 重排链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# 链表的中间结点（偶数时就获取左边结点，即左半部分最后一个节点）
def middle(head):
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
# 反转链表
def reverse(head):
pre=None
cur=head
while cur:
temp=cur.next
cur.next=pre
pre=cur
cur=temp
return pre
# 合并链表（端点合并）
def merge(l1,l2):
while l1 and l2:
l1_temp=l1.next
l2_temp=l2.next
l1.next=l2
l1=l1_temp
l2.next=l1
l2=l2_temp
mid=middle(head)
l1=head
l2=reverse(mid) # 注意此时l1与l2断开
merge(l1,l2)
42. 接雨水
Python
class Solution:
def trap(self, height: List[int]) -> int:
stack=[0]
res=0
for i in range(1,len(height)):
if height[i]<=height[stack[-1]]:
stack.append(i)
else:
while stack and height[i]>height[stack[-1]]:
mid=height[stack[-1]]
right=height[i]
stack.pop()
if stack:
left=height[stack[-1]]
h=min(left,right)-mid
w=i-stack[-1]-1
res+=h*w
stack.append(i)
return res
142. 环形链表 II
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow,fast=head,head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if slow==fast:
slow=head
while slow!=fast:
slow=slow.next
fast=fast.next
return slow
return None
Java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if (slow==fast){
slow=head;
while (slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
}
return null;
}
}