【一天三道算法题】代码随想录——Day13

**一天三道算法题**

**Day13**

今天我们将解决三个有趣的算法问题。这些问题涉及到数组、链表和二叉树等数据结构。

###问题1：寻找两个数组的交集给定两个整数数组 `nums1` 和 `nums2`，返回它们的交集。输出结果中的每个元素一定是两数组中存在的，并且出现次数在两数组中均为最大。

**示例1:**

输入:`nums1 = [1,2,2,1]`, `nums2 = [2,2]`

输出:`[2]`

**示例2:**

输入:`nums1 = [4,9,5]`, `nums2 = [9,4,9,8,4]`

输出:`[4,9]`

def intersection(nums1, nums2):
 # 将两个数组转换为集合 set1 = set(nums1)
 set2 = set(nums2)

 # 找到两个集合的交集 intersection_set = set1 & set2 # 返回结果列表 return list(intersection_set)


# 测试用例nums1 = [1,2,2,1]
nums2 = [2,2]

print(intersection(nums1, nums2)) # 输出: [2]

nums1 = [4,9,5]
nums2 = [9,4,9,8,4]

print(intersection(nums1, nums2)) # 输出: [4,9]

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef mergeTwoLists(l1, l2):
 # 创建一个新的链表头节点 dummy = ListNode(0)
 current = dummy # 合并两个链表 while l1 and l2:
 if l1.val < l2.val:
 current.next = l1 l1 = l1.next else:
 current.next = l2 l2 = l2.next current = current.next # 将剩余的链表连接到结果中 if l1:
 current.next = l1 elif l2:
 current.next = l2 return dummy.next# 测试用例l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(3)

l2 = ListNode(4)
l2.next = ListNode(5)
l2.next.next = ListNode(6)

print(mergeTwoLists(l1, l2)) # 输出: [1,2,3,4,5,6]

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isBalanced(root):
 # 定义一个辅助函数来计算树的高度 def check(node):
 if not node:
 return0 left_height = check(node.left)
 right_height = check(node.right)

 # 如果子树不平衡，则返回-1 if left_height == -1 or right_height == -1 or abs(left_height - right_height) >1:
 return -1 # 返回当前树的高度 return max(left_height, right_height) +1 # 检查树是否平衡 return check(root) != -1# 测试用例root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(isBalanced(root)) # 输出: True