1：直方图的水量
题目链接：面试题 17.21. 直方图的水量 - 力扣（LeetCode）
双指针
初始化：我们使用两个指针
left和right分别指向数组的开始和结束。同时，我们记录下这两个位置的高度，即max_left和max_right。遍历数组：我们使用一个 while 循环来遍历整个数组，直到
left和right相遇。在每次循环中，我们比较left和right位置的柱子高度。处理较矮的柱子：
- 如果
left位置的柱子高度小于right位置的柱子高度，我们检查left位置的柱子高度是否大于或等于max_left。如果是，我们更新max_left；如果不是，那么left位置的柱子与max_left之间的差距就是可以存储的水量。然后，我们将left指针向右移动一位。- 如果
right位置的柱子高度小于或等于left位置的柱子高度，我们执行类似的操作，但针对right位置的柱子。计算水量：在每次循环中，我们计算较矮柱子与它对应的最大高度之间的差距，并将这个差距累加到
water变量中。结束条件：当
left和right相遇时，循环结束。
这个算法的关键在于，我们总是从两边向中间遍历，并确保在每次比较中，我们都有当前方向上的最大高度。这样，我们就可以确保在移动指针时正确地计算水量。因为我们是从两边向中间移动，所以每个位置只被访问一次，这使得算法的时间复杂度为 O(n)。
python">def trap(height):if not height:return 0left, right = 0, len(height) - 1max_left, max_right = height[left], height[right]water = 0while left < right:if height[left] < height[right]:if height[left] >= max_left:max_left = height[left]else:water += max_left - height[left]left += 1else:if height[right] >= max_right:max_right = height[right]else:water += max_right - height[right]right -= 1return watera = list(map(int, input().split()))
print(trap(a))
2：平衡二叉树
题目链接：LCR 176. 判断是否为平衡二叉树 - 力扣（LeetCode）
平衡二叉树的定义是：对于树中的任意一个节点，其左右子树的高度差不超过1。以下是一个判断二叉树是否为平衡二叉树的Python代码实现：
python">class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef list_to_tree(lst):if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while queue and i < len(lst):current = queue.pop(0)if i < len(lst) and lst[i] is not None:current.left = TreeNode(lst[i])queue.append(current.left)i += 1if i < len(lst) and lst[i] is not None:current.right = TreeNode(lst[i])queue.append(current.right)i += 1return rootdef isBalanced(root):def check_balance(node):if not node:return 0, Trueleft_height, left_balanced = check_balance(node.left)right_height, right_balanced = check_balance(node.right)balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1height = max(left_height, right_height) + 1return height, balanced_, is_tree_balanced = check_balance(root)return is_tree_balanced# 用户输入处理
user_input = input()
root = list_to_tree(input_tree)
print(isBalanced(root))这段代码中的 list_to_tree 函数负责将列表转换为二叉树结构。它使用广度优先搜索（BFS）的方法来遍历列表，并构建相应的树节点。然后，isBalanced 函数会检查这个树是否是平衡的。
3：最小生成树（Prim算法）
题目链接：1584. 连接所有点的最小费用 - 力扣（LeetCode）
这个问题可以通过使用Prim算法或者Kruskal算法来解决，这两种算法都是用来寻找最小生成树的经典算法。最小生成树是指在一个加权无向图中，包含图中全部顶点的、权值之和最小的树形结构。
对于这个问题，我们可以按以下步骤实现Prim算法：
- 创建一个数组，用来记录每个点到最小生成树的最短距离。
- 初始化这个数组，将除了起点外的所有点的距离设置为无穷大。
- 创建一个最小堆（优先队列），将所有点按照到最小生成树的距离排序。
- 依次从堆中取出距离最小的点，并将其连接到最小生成树中，同时更新其他点到最小生成树的距离。
现在，我将用Python代码来实现这个算法。
python">import heapqdef minCostConnectPoints(points):# 计算两个点之间的曼哈顿距离def manhattan_distance(p1, p2):return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])n = len(points)# 初始化最小生成树距离数组，全部设置为无穷大min_span_tree = [float('inf')] * n# 从第一个点开始构建最小生成树min_span_tree[0] = 0# 创建一个最小堆，存储(距离, 点的索引)heap = [(0, 0)]total_cost = 0visited = [False] * nwhile heap:# 从堆中取出距离最小的点cost, idx = heapq.heappop(heap)if visited[idx]:continue# 将这个点加入最小生成树visited[idx] = Truetotal_cost += cost# 更新其他点到最小生成树的距离for i in range(n):if not visited[i]:dist = manhattan_distance(points[idx], points[i])if dist < min_span_tree[i]:min_span_tree[i] = distheapq.heappush(heap, (dist, i))return total_cost
