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 0
left, right = 0, len(height) - 1
max_left, max_right = height[left], height[right]
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
a = 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 = val
self.left = left
self.right = right
def list_to_tree(lst):
if not lst:
return None
root = TreeNode(lst[0])
queue = [root]
i = 1
while 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 += 1
if i < len(lst) and lst[i] is not None:
current.right = TreeNode(lst[i])
queue.append(current.right)
i += 1
return root
def isBalanced(root):
def check_balance(node):
if not node:
return 0, True
left_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) <= 1
height = max(left_height, right_height) + 1
return 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 heapq
def 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 = 0
visited = [False] * n
while heap:
# 从堆中取出距离最小的点
cost, idx = heapq.heappop(heap)
if visited[idx]:
continue
# 将这个点加入最小生成树
visited[idx] = True
total_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] = dist
heapq.heappush(heap, (dist, i))
return total_cost
