Dijkstra算法，动态规划和滑动窗口

一：最小花费

题目链接：1928. 规定时间内到达终点的最小花费 - 力扣（LeetCode）

（1）Dijkstra算法

1. 理解问题：首先，我们需要理解问题的核心是找到一条从城市 0 到城市 n-1 的路径，这条路径在不超过给定时间 maxTime 的前提下，通行费之和最小。

2. 图的表示：由于城市之间是通过双向道路连接的，我们可以将这个问题抽象为一个图问题，其中城市是节点，道路是边。边的权重是通行时间。

3. 算法选择：由于我们需要找到最小费用的路径，这看起来像是一个最短路径问题。但是，这里的最短路径是在时间限制下的费用最小，所以我们需要一个能够同时考虑时间和费用的算法。Dijkstra算法是一个很好的选择，但我们需要对其进行修改以考虑时间限制。

4. 优先队列的使用：为了高效地找到当前费用最小的路径，我们使用优先队列（最小堆）。这样我们可以始终从当前费用最小的路径开始扩展。

5. 状态记录：由于我们可能多次经过同一个城市，但时间不同，我们需要记录每个城市在不同时间点的访问状态。这通过 visited 数组实现，它是一个二维数组，其中 visited[i][t] 表示在城市 i 在时间 t 是否已经访问过。

6. 算法流程：

   • 初始化：将起点城市 0 加入优先队列，费用为 passingFees[0]，时间为 0。
   • 循环：从优先队列中取出当前费用最小的路径，检查是否到达终点城市。如果是，返回当前费用。
   • 扩展：对于当前城市的每个邻接城市，计算到达邻接城市的新时间和新费用。如果新时间不超过 maxTime 且该状态未被访问过，则将其加入优先队列，并标记为已访问。

7. 结束条件：如果优先队列为空，说明在给定时间内无法到达终点城市，返回 -1。

8. 返回结果：如果在循环中找到了到达终点城市的路径，返回该路径的费用。如果循环结束仍未找到，返回 -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）动态规划

1. 定义状态：在这个问题中，我们定义 dp[i][t] 为到达城市 i 并且花费时间为 t 时的最小通行费总和。

2. 状态初始化：由于我们一开始在城市 0，所以 dp[0][0] 初始化为 passingFees[0]，即经过城市 0 的通行费。其他状态初始化为无穷大（float('inf')），表示在初始状态下无法到达。

3. 状态转移：对于每个城市 i 和每个时间 t，我们需要考虑所有从城市 i 出发的边 (i, j, timeij)。如果从城市 i 到城市 j 需要的时间 timeij 加上当前时间 t 不超过 maxTime，并且新的费用 dp[i][t] + passingFees[j] 小于 dp[j][t + timeij]，则更新 dp[j][t + timeij]。

4. 使用优先队列优化：由于我们希望在给定的时间内找到最小费用，可以使用优先队列（最小堆）来优化搜索过程。我们每次从优先队列中取出当前费用最小的状态，并尝试从这个状态转移到其他状态。

5. 结果提取：在完成所有状态转移后，我们需要在 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）

滑动窗口

为了解决这个问题，我们可以采用以下步骤：

1. 计算每个点相对于你的位置的角度。
2. 将这些角度按照从小到大的顺序排序。
3. 使用滑动窗口的方法来找到在给定角度范围内可以看到的最多点数。

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))

这段代码的目的是计算在给定的角度范围内，从特定位置出发可以看到的最大点数。以下是代码的思路和步骤：

1. 初始化变量:

   • angles: 用于存储每个点相对于观察位置的角度。
   • same_pos_count: 用于计数与观察位置重合的点的数量。

2. 计算每个点的角度:

   • 遍历点数组 points。
   • 对于每个点，计算它与观察位置 location 在 x 和 y 轴上的差值 dx 和 dy。
   • 如果一个点与观察位置重合（即 dx == 0 且 dy == 0），则增加 same_pos_count 并跳过后续计算。
   • 使用 math.atan2(dy, dx) 计算该点的角度（以弧度为单位），然后使用 math.degrees() 将其转换为度数。
   • 将计算出的角度添加到 angles 列表中。

3. 处理角度列表:

   • 对 angles 列表进行排序，以便我们可以使用滑动窗口方法来找到给定角度范围内的最大点数。
   • 为了处理跨越0度线的情况（例如从350度到10度），将 angles 列表中的每个角度加上360度后追加到列表的末尾。这样，我们就可以在0度线周围无缝地滑动窗口。

4. 滑动窗口查找最大可见点数:

   • 初始化 max_visible 为0，这是我们将要返回的最大可见点数。
   • 使用两个指针 left 和 right 来表示滑动窗口的左右边界。
   • 遍历 angles 列表，对于每个 right 指针的位置，检查窗口内的角度范围是否超过了给定的 angle。
   • 如果超过了，移动 left 指针，缩小窗口范围，直到窗口内的角度范围小于或等于给定的 angle。
   • 更新 max_visible 为当前窗口内点的数量和之前记录的最大数量的较大值。

5. 返回结果:

   • 将 max_visible（滑动窗口中可见点的最大数量）与 same_pos_count（与观察位置重合的点的数量）相加，得到最终结果。
   • 返回这个值，它表示在给定角度范围内从观察位置可以看到的最大点数。

这段代码有效地处理了观察角度范围内点的可见性问题，并且能够处理包括观察位置在内的点的特殊情况。