leetcode 1453. 圆形靶内的最大飞镖数量 376. 摆动序列 897. 递增顺序查找树 面试题 16.11. 跳水板 21. 合并两个有序链表

1453. 圆形靶内的最大飞镖数量

根据两点和r求圆心，判断在圆里面的个数。

class Solution: def numPoints(self, points: List[List[int]], r: int) -> int: def in_circle(x,y,zero_x,zero_y,r): return (x-zero_x)*(x-zero_x)+(y-zero_y)*(y-zero_y)<=r*r def get_zero_point(point1,point2,r): if point1==point2: return point1 p1_p2 = ((point1[0]-point2[0])**2+(point1[1]-point2[1])**2)**0.5 if p1_p2>2*r: return None middle = ((point1[0]+point2[0])/2,(point1[1]+point2[1])/2) verlen = (r**2-(point1[0]/2-point2[0]/2)**2-(point1[1]/2-point2[1]/2)**2)**0.5 return (middle[0]+(point2[1]-point1[1])/p1_p2*verlen,middle[1]-(point2[0]-point1[0])/p1_p2*verlen) result = 0 for p1 in points: for p2 in points: base_point = get_zero_point(p1,p2,r) if not base_point: continue count = 0 for x, y in points: if (x-base_point[0])**2+(y-base_point[1])**2<=r**2: count+=1 result = max(result,count) return result

376. 摆动序列

class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: if len(nums)==0: return 0 sign_list = [0]*(len(nums)-1) for i in range(1,len(nums)): sign_list[i-1]=1 if nums[i]-nums[i-1]>0 else -1 if nums[i]-nums[i-1]<0 else 0 index = 0 result = 0 last_index=0 while index<len(sign_list): if sign_list[index]!=last_index and sign_list[index]!=0: result+=1 last_index=sign_list[index] index+=1 return result+1

897. 递增顺序查找树

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def increasingBST(self, root: TreeNode) -> TreeNode: node_list = [] def search(root,node_list): if not root: return search(root.left,node_list) root.left = None node_list+=[root] search(root.right,node_list) root.right = None search(root,node_list) if len(node_list)==0: return None for i in range(len(node_list)-2,-1,-1): node_list[i].right = node_list[i+1] return node_list[0]

面试题 16.11. 跳水板

class Solution: def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]: if k==0: return [] result = [shorter*k] diff = longer-shorter if diff==0: return result for i in range(1,k+1): result.append(result[i-1]+diff) return result

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, l1: ListNode, l2: ListNode) -> ListNode: if not l1 and not l2: return None if not l1 or not l2: return l1 if not l2 else l2 result = l1 if l1.val<=l2.val else l2 p = result p1 = l1.next if l1.val<=l2.val else l1 p2 = l2.next if l1.val>l2.val else l2 while p1 or p2: if p1 and (not p2 or p1.val<=p2.val): p.next = p1 p1 = p1.next else: p.next = p2 p2 = p2.next p = p.next return result