Dijkstra算法，动态规划和滑动窗口
一：最小花费
题目链接：1928. 规定时间内到达终点的最小花费 - 力扣（LeetCode）
（1）Dijkstra算法
理解问题：首先，我们需要理解问题的核心是找到一条从城市 0 到城市 n-1 的路径，这条路径在不超过给定时间
maxTime的前提下，通行费之和最小。图的表示：由于城市之间是通过双向道路连接的，我们可以将这个问题抽象为一个图问题，其中城市是节点，道路是边。边的权重是通行时间。
算法选择：由于我们需要找到最小费用的路径，这看起来像是一个最短路径问题。但是，这里的最短路径是在时间限制下的费用最小，所以我们需要一个能够同时考虑时间和费用的算法。Dijkstra算法是一个很好的选择，但我们需要对其进行修改以考虑时间限制。
优先队列的使用：为了高效地找到当前费用最小的路径，我们使用优先队列（最小堆）。这样我们可以始终从当前费用最小的路径开始扩展。
状态记录：由于我们可能多次经过同一个城市，但时间不同，我们需要记录每个城市在不同时间点的访问状态。这通过
visited数组实现，它是一个二维数组，其中visited[i][t]表示在城市i在时间t是否已经访问过。算法流程：
- 初始化：将起点城市 0 加入优先队列，费用为
passingFees[0]，时间为 0。- 循环：从优先队列中取出当前费用最小的路径，检查是否到达终点城市。如果是，返回当前费用。
- 扩展：对于当前城市的每个邻接城市，计算到达邻接城市的新时间和新费用。如果新时间不超过
maxTime且该状态未被访问过，则将其加入优先队列，并标记为已访问。结束条件：如果优先队列为空，说明在给定时间内无法到达终点城市，返回 -1。
返回结果：如果在循环中找到了到达终点城市的路径，返回该路径的费用。如果循环结束仍未找到，返回 -1。
import heapq
def minCost(maxTime, edges, passingFees):
n = len(passingFees)
graph = [[] for _ in range(n)]
for u, v, time in edges:
graph[u].append((v, time))
graph[v].append((u, time))
pq = [(passingFees[0], 0, 0)]
visited = [False] * n
min_cost = [float('inf')] * n
min_cost[0] = passingFees[0]
while pq:
cost, u, time_used = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
if u == n - 1:
return cost
for v, time in graph[u]:
new_time = time_used + time
if new_time <= maxTime and cost + passingFees[v] < min_cost[v]:
min_cost[v] = cost + passingFees[v]
heapq.heappush(pq, (min_cost[v], v, new_time))
return -1
# 解析输入
def parse_input(input_str):
parts = input_str.split(', ')
maxTime = int(parts[0].split(' = ')[1])
edges_start = parts[1].find('[[')
edges_end = parts[1].find(']]') + 2
edges_str = parts[1][edges_start:edges_end]
edges = eval(edges_str)
passingFees_start = parts[2].find('[')
passingFees = eval(parts[2][passingFees_start:])
return maxTime, edges, passingFees
input_str = input()
maxTime, edges, passingFees = parse_input(input_str)
# 计算并输出结果
result = minCost(maxTime, edges, passingFees)
print(result)（2）动态规划
定义状态：在这个问题中，我们定义
dp[i][t]为到达城市i并且花费时间为t时的最小通行费总和。状态初始化：由于我们一开始在城市 0，所以
dp[0][0]初始化为passingFees[0]，即经过城市 0 的通行费。其他状态初始化为无穷大（float('inf')），表示在初始状态下无法到达。状态转移：对于每个城市
i和每个时间t，我们需要考虑所有从城市i出发的边(i, j, timeij)。如果从城市i到城市j需要的时间timeij加上当前时间t不超过maxTime，并且新的费用dp[i][t] + passingFees[j]小于dp[j][t + timeij]，则更新dp[j][t + timeij]。使用优先队列优化：由于我们希望在给定的时间内找到最小费用，可以使用优先队列（最小堆）来优化搜索过程。我们每次从优先队列中取出当前费用最小的状态，并尝试从这个状态转移到其他状态。
结果提取：在完成所有状态转移后，我们需要在
dp[n-1]（即到达城市 n-1 的所有可能时间）中找到最小的费用。如果这个最小费用仍然是无穷大，则说明无法在maxTime时间内到达城市 n-1，返回 -1。具体步骤如下：
- 初始化
dp表和优先队列。- 将起点（城市 0，费用
passingFees[0]，时间 0）加入优先队列。- 当优先队列不为空时，取出当前费用最小的状态，并尝试从这个状态转移到其他状态。
- 更新
dp表和优先队列。- 最后在
dp[n-1]中找到最小费用并返回。这个动态规划的方法实际上是一个基于优先队列的 Dijkstra 算法的变种，用于在给定时间限制内找到最小费用的路径。
from collections import defaultdict
import heapq
def minCost(maxTime, edges, passingFees):
n = len(passingFees)
graph = defaultdict(list)
for u, v, time in edges:
graph[u].append((v, time))
graph[v].append((u, time))
dp = [[float('inf')] * (maxTime + 1) for _ in range(n)]
dp[0][0] = passingFees[0]
pq = [(passingFees[0], 0, 0)] # (cost, node, time)
while pq:
cost, node, time = heapq.heappop(pq)
if node == n - 1:
return cost
for neighbor, travel_time in graph[node]:
new_time = time + travel_time
new_cost = cost + passingFees[neighbor]
if new_time <= maxTime and new_cost < dp[neighbor][new_time]:
dp[neighbor][new_time] = new_cost
heapq.heappush(pq, (new_cost, neighbor, new_time))
min_cost = min(dp[n-1][:maxTime+1])
return min_cost if min_cost != float('inf') else -1
# 获取用户输入
points_input = input()
angle_input = int(input())
location_input = input()
# 将输入字符串转换为相应的数据类型
points = eval(points_input)
angle = angle_input
location = eval(location_input)
# 调用函数并打印结果
print(visible_points(points, angle, location))
二：可见点的最大数目
题目链接：1610. 可见点的最大数目 - 力扣（LeetCode）
滑动窗口
为了解决这个问题，我们可以采用以下步骤：
- 计算每个点相对于你的位置的角度。
- 将这些角度按照从小到大的顺序排序。
- 使用滑动窗口的方法来找到在给定角度范围内可以看到的最多点数。
import math
def visible_points(points, angle, location):
# 计算每个点相对于location的角度
angles = []
same_pos_count = 0
for point in points:
dx, dy = point[0] - location[0], point[1] - location[1]
if dx == 0 and dy == 0:
same_pos_count += 1
continue
angle = math.degrees(math.atan2(dy, dx))
angles.append(angle)
# 将角度排序
angles.sort()
# 将角度列表扩展，以处理跨越0度线的情况
angles += [a + 360 for a in angles]
# 使用滑动窗口找到最大的可见点数
max_visible = 0
left = 0
for right in range(len(angles)):
while angles[right] - angles[left] > angle:
left += 1
max_visible = max(max_visible, right - left + 1)
return max_visible + same_pos_count
# 获取用户输入
points_input = input()
angle_input = int(input()
location_input = input()
# 将输入字符串转换为相应的数据类型
points = eval(points_input)
angle = angle_input
location = eval(location_input)
# 调用函数并打印结果
print(visible_points(points, angle, location))这段代码的目的是计算在给定的角度范围内，从特定位置出发可以看到的最大点数。以下是代码的思路和步骤：
初始化变量:
angles: 用于存储每个点相对于观察位置的角度。same_pos_count: 用于计数与观察位置重合的点的数量。计算每个点的角度:
- 遍历点数组
points。- 对于每个点，计算它与观察位置
location在 x 和 y 轴上的差值dx和dy。- 如果一个点与观察位置重合（即
dx == 0且dy == 0），则增加same_pos_count并跳过后续计算。- 使用
math.atan2(dy, dx)计算该点的角度（以弧度为单位），然后使用math.degrees()将其转换为度数。- 将计算出的角度添加到
angles列表中。处理角度列表:
- 对
angles列表进行排序，以便我们可以使用滑动窗口方法来找到给定角度范围内的最大点数。- 为了处理跨越0度线的情况（例如从350度到10度），将
angles列表中的每个角度加上360度后追加到列表的末尾。这样，我们就可以在0度线周围无缝地滑动窗口。滑动窗口查找最大可见点数:
- 初始化
max_visible为0，这是我们将要返回的最大可见点数。- 使用两个指针
left和right来表示滑动窗口的左右边界。- 遍历
angles列表，对于每个right指针的位置，检查窗口内的角度范围是否超过了给定的angle。- 如果超过了，移动
left指针，缩小窗口范围，直到窗口内的角度范围小于或等于给定的angle。- 更新
max_visible为当前窗口内点的数量和之前记录的最大数量的较大值。返回结果:
- 将
max_visible（滑动窗口中可见点的最大数量）与same_pos_count（与观察位置重合的点的数量）相加，得到最终结果。- 返回这个值，它表示在给定角度范围内从观察位置可以看到的最大点数。
这段代码有效地处理了观察角度范围内点的可见性问题，并且能够处理包括观察位置在内的点的特殊情况。
原文地址：https://blog.csdn.net/2301_80651329/article/details/142690901
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！