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