每日一问 - PAT A 级 1046 最短距离的 Python 实现（示例 + 思路解读 + 逐步优化）

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-****博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

目录

我的写法

专业点评

优点

改进建议

时间复杂度分析

空间复杂度分析

总结

我要更强

方法一：优化空间复杂度（保留前缀和）

方法二：直接使用距离数组进行查询

代码优化解释

时间和空间复杂度分析

总结

哲学和编程思想

编程思想和哲学

总结

举一反三

1. 空间换时间

2. 时间换空间

3. 贪心思想

4. 分治思想

5. 动态规划

举一反三的技巧

---

https://pintia.cn/problem-sets/994805342720868352/exam/problems/type/7?problemSetProblemId=994805435700199424&page=0

我的写法

# 从输入中读取一行，将其拆分为整数，并存储在 distances 列表中
distances = list(map(int, input().split()))

# 第一个元素是 N，表示接下来行程的数目
N = distances[0]

# 剩下的元素是各段行程的距离
distances = distances[1:]

# 从输入中读取 M，表示要处理的查询次数
M = int(input())

# 创建一个前缀和数组，用于存储从起点到各位置的累计距离
prefix_sum = [0] * (N + 1)

# 计算前缀和数组
for i in range(1, N + 1):
    # prefix_sum[i] 表示从起点到第 i 段行程结束的累计距离
    prefix_sum[i] = prefix_sum[i - 1] + distances[i - 1]

# 总的环形路径的距离
total_distance = prefix_sum[N]

# 处理每个查询
for i in range(M):
    # 读取查询的两个点 a 和 b
    a, b = map(int, input().split())
    
    # 确保 a 小于 b，如果不是则交换 a 和 b
    if a > b:
        a, b = b, a
    
    # 计算从 a 到 b 的路径距离
    distance1 = prefix_sum[b - 1] - prefix_sum[a - 1]
    
    # 计算从 b 到 a（绕过环的另一边）的路径距离
    distance2 = total_distance - distance1
    
    # 输出较短的路径距离
    print(min(distance1, distance2))

这段代码的功能是处理一个环形路径的查询问题，计算两个节点之间的最短距离。以下是对这段代码的点评，以及时间复杂度和空间复杂度的分析。

专业点评

优点

1. 前缀和的使用：
   • 通过前缀和数组 prefix_sum，可以在常数时间内计算任意两点之间的路径距离。这种方法有效地将路径长度查询的时间复杂度从线性降到常数。
2. 处理环形路径：
   • 计算两种可能的路径（顺时针和逆时针）并取最小值的方式，确保了找到两点间的最短路径。
3. 输入处理：

• 代码通过 map 和 split 组合高效地读取并转换输入，符合常见的Python代码风格。

改进建议

1. 输入验证：
   • 没有对输入进行验证假设输入是正确的。可以增加对输入数据的合法性检查，确保输入值在合理范围内。
2. 变量命名：

• 可以通过更具描述性的变量名（如 distance_clockwise 和 distance_counterclockwise）来提高代码的可读性。

时间复杂度分析

1. 前缀和计算：
   • 构建前缀和数组的时间复杂度为 O(N)，因为需要遍历距离数组一次。
2. 查询处理：
   • 每次查询的时间复杂度为 O(1)，因为计算路径距离和比较最小值的操作都是常数时间内完成的。
3. 总体时间复杂度：

• 总体时间复杂度为 O(N+M)，其中 N 是距离数组的大小，M 是查询次数。

空间复杂度分析

1. 前缀和数组：
   • 需要一个大小为 N+1 的前缀和数组 prefix_sum，空间复杂度为 O(N)。
2. 输入存储：
   • distances 数组存储每段行程的距离，空间复杂度为 O(N)。
3. 总体空间复杂度：

• 总的空间复杂度为 O(N)，因为额外使用的主要是 distances 和 prefix_sum 数组。

总结

这段代码使用前缀和技巧有效地解决了环形路径的最短距离查询问题，时间复杂度为 O(N+M)，空间复杂度为O(N)。整体实现高效、简洁，但可以通过增加输入验证和更清晰的变量命名进一步提高代码质量。

---

我要更强

在这个问题中，由于我们需要进行多次查询，而每次查询都需要计算两点之间的最短距离，前缀和的使用已经是一种非常高效的方案。进一步优化时间复杂度已经较为困难，因为查询已经是 O(1) 的时间复杂度。

然而，我们可以考虑优化空间复杂度，特别是当 N 非常大时。以下是几种可能的优化方法：

方法一：优化空间复杂度（保留前缀和）

尽管前缀和数组的空间复杂度是 O(N)，但它已经是当前任务的较优解。如果我们希望进一步减少空间消耗，可以考虑在查询中实时计算部分前缀和，而不是存储整个前缀和数组。然而，由于查询次数 M 通常大于路径段数 N，这种方法可能并不会带来实际的性能提升。

方法二：直接使用距离数组进行查询

如果我们不使用前缀和数组，而是直接从距离数组中计算路径长度，虽然会增加每次查询的时间复杂度，但可以节省空间。

下面是直接使用距离数组进行查询的代码示例：

# 读取输入
distances = list(map(int, input().split()))
N = distances[0]
distances = distances[1:]
M = int(input())

# 计算总距离
total_distance = sum(distances)

# 处理每个查询
for _ in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    
    # 计算从 a 到 b 的路径距离
    distance1 = sum(distances[a-1:b-1])
    
    # 计算从 b 到 a（绕过环的另一边）的路径距离
    distance2 = total_distance - distance1
    
    # 输出较短的路径距离
    print(min(distance1, distance2))

代码优化解释

1. 输入读取和初始化：
   • 读取并解析输入，distances 包含各段行程的距离。
2. 总距离计算：
   • 计算环形路径的总距离。
3. 查询处理：

对每个查询，计算从 a 到 b 的两种路径距离，输出较小的值。

时间和空间复杂度分析

1. 时间复杂度：
   • 每次查询的时间复杂度为 O(N)，因为我们需要计算部分路径的距离。总的时间复杂度为 O(M⋅N)。
2. 空间复杂度：

• 这种方法的空间复杂度为 O(1)，除了输入数据外不需要额外的空间。

总结

直接使用距离数组进行查询可以显著减少空间消耗，但会增加查询的时间复杂度。如果路径段数 N 较小且查询次数 M 较多，这种方法可能不如使用前缀和的方案高效。选择何种方法需要根据具体的输入规模进行权衡。

---

哲学和编程思想

在上述解决问题的过程中，运用了多种编程思想和哲学，下面详细说明：

编程思想和哲学

1. 空间换时间（前缀和方法）：
   • 思想：通过增加额外的空间（前缀和数组）来换取时间上的优化。
   • 具体应用：在前缀和方法中，我们使用一个大小为 �+1N+1 的数组来存储从起点到各位置的累计距离。这使得每次查询的时间复杂度从可能的 �(�)O(N) 降至 �(1)O(1)。
   • 哲学：用更多的空间来预处理数据，以便在后续查询中能够快速得到结果。这种方法常用于需要多次查询的大数据集。
2. 时间换空间（直接计算路径距离）：
   • 思想：减少空间使用，通过增加计算时间来实现同样的功能。
   • 具体应用：在没有使用前缀和的情况下，我们直接在每次查询中计算部分路径的距离。这样做虽然节省了空间，但查询时间复杂度增加到了 �(�)O(N)。
   • 哲学：在空间资源紧张的情况下，可以通过增加计算时间来节省空间。这种方法适用于空间资源比时间资源更宝贵的场景。
3. 贪心思想：
   • 思想：在每一步选择中做出局部最优的选择，希望最终得到全局最优解。
   • 具体应用：在环形路径的查询中，我们计算了两种路径（顺时针和逆时针）的距离，并选择了最小的那个距离。这个过程实际上是一个贪心选择的过程。
   • 哲学：通过一系列局部最优的选择，可以达到全局最优的效果。这种方法适用于问题可以分解成一系列子问题，并且每个子问题的最优解能构成问题的最优解的情况。
4. 分治思想：
   • 思想：将问题分解成更小的子问题，分别解决这些子问题，然后合并结果。
   • 具体应用：虽然在上述代码中没有直接应用分治法，但前缀和的计算过程可以看作是一种分治思想的应用。我们先解决小范围内的求和问题，再通过累积的方式解决更大范围的求和问题。
   • 哲学：通过将复杂问题分解成更小、更易解决的子问题，可以有效地降低解决问题的复杂度。这种方法尤其适用于递归和动态规划。
5. 动态规划思想：

• 思想：通过记录子问题的解，避免重复计算，逐步解决更大的问题。
• 具体应用：前缀和数组的构建和使用实际上是一种动态规划思想的体现。我们通过记录每个位置的累计和，避免了在每次查询时重复计算相同的子区间和。
• 哲学：通过存储和利用子问题的解，可以大大提高解决问题的效率。这种方法适用于具有重叠子问题的场景。

总结

通过分析和解释，可以看到编程思想和哲学在解决实际问题中的应用。这些思想帮助我们在不同的约束条件下（如时间复杂度和空间复杂度）找到适合的解决方案。理解并灵活应用这些思想，可以使我们在编程中更加从容地应对各种挑战。

---

举一反三

理解和灵活应用编程思想和哲学是提升编程能力的关键。下面是一些技巧，结合这些思想，能更好地举一反三，解决类似的问题：

1. 空间换时间

• 技巧：预处理和缓存
  • 应用：当你需要频繁查询某些数据时，考虑是否可以通过预处理将结果存储在数组或表中，从而减少每次查询的计算量。
  • 示例：前缀和、动态规划中的状态转移表、缓存最近查询结果的LRU缓存。
• 延伸：存储中间结果

• 应用：在递归问题中，存储已经计算过的结果，避免重复计算。
• 示例：斐波那契数列的动态规划实现。

2. 时间换空间

• 技巧：实时计算
  • 应用：当空间有限时，考虑是否可以在每次需要时实时计算所需的数据，而不是提前存储所有可能的结果。
  • 示例：对每次查询实时计算路径距离，而不是使用前缀和数组。
• 延伸：按需加载

• 应用：在处理大数据时，可以考虑按需加载需要的数据，而不是一次性加载所有数据。
• 示例：分页加载数据、流式处理大文件。

3. 贪心思想

• 技巧：每次选择局部最优解
  • 应用：当问题可以分解成一系列子问题，并且每个子问题的最优解能构成问题的最优解时，考虑使用贪心算法。
  • 示例：找零钱问题、活动选择问题、最小生成树（Prim和Kruskal算法）。
• 延伸：构建贪心策略

• 应用：在实际问题中，尝试构建一个简单的贪心策略，验证其是否能得到全局最优解。
• 示例：为旅行商问题构建最近邻居贪心策略。

4. 分治思想

• 技巧：将问题分解成更小的子问题
  • 应用：当问题可以递归地分解成更小的问题，并且这些子问题独立求解后可以合并成最终结果时，考虑使用分治算法。
  • 示例：二分搜索、归并排序、快速排序。
• 延伸：寻找合适的分解点

• 应用：在实际问题中，尝试找到合适的分解点，以便将问题分解成更小的、易于解决的子问题。
• 示例：在图算法中，将图分解成子图进行处理。

5. 动态规划

• 技巧：记录子问题的解
  • 应用：当问题具有重叠子问题结构时，通过记录子问题的解，避免重复计算。
  • 示例：背包问题、最长公共子序列、最长递增子序列。
• 延伸：自底向上和自顶向下

• 应用：理解动态规划的两种实现方式：自顶向下的记忆化搜索和自底向上的递推。
• 示例：斐波那契数列的两种动态规划实现。

举一反三的技巧

1. 类比法：将当前问题与已知问题进行类比，寻找相似之处，应用相同或类似的解决方法。
   • 实践：在面对新问题时，问自己：“这是否类似于我之前解决过的某个问题？”
2. 分解法：将复杂问题分解成更小的子问题，分别解决这些子问题，再将其组合成最终解决方案。
   • 实践：在解决复杂问题时，尝试运用分治思想，将问题逐步细化。
3. 验证法：假设某种策略是可行的，先尝试解决子问题，验证其可行性，再逐步扩展到更大的问题。
   • 实践：在尝试贪心算法或其他策略时，先在小规模问题上验证，再扩展到全局。
4. 优化法：在已有解决方案的基础上，思考是否有可以优化的部分，特别是时间复杂度和空间复杂度。

• 实践：在已有的解决方案上，问自己：“是否有更快（时间）或更省空间的方法？”

通过运用这些技巧和思想，可以更好地理解和解决问题，提升编程能力。理解背后的哲学和原理，能够在面对新的或复杂的问题时，迅速找到有效的解决方案。

---