Circular Tour Problem in Java

这是像Google、Amazon、TCS、Accenture、Flipkart等顶级 IT 公司面试中经常遇到的问题。通过解决这个问题，可以考察应聘者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将通过不同的方法和逻辑来解决圆形旅行问题。此外，我们还将为此创建 Java 程序。

圆形旅行问题是一个经典的算法问题，通常与队列和贪婪算法相关，它围绕着在一个加油站链上完成一个圆形旅程。该问题可以描述如下。

问题陈述

您有 n 个按圆形路径排列的加油站。每个加油站都有

1. 可用汽油：petrol[i] 单位。
2. 到下一个加油站的距离：distance[i] 单位。

任务是找到第一个加油站（如果有的话），卡车可以从那里开始旅程并完成旅程，而无需完全加满汽油。卡车每行驶一单位距离消耗 1 单位燃油。

关键约束

• 如果卡车从一个加油站出发，无法到达下一个加油站，则它不能从该加油站开始旅程。
• 解决方案必须以 O(n) 的时间复杂度高效运行。

解决问题的方法

该问题可以使用具有单次遍历的贪婪算法高效解决

1. 跟踪汽油余额：计算每个加油站的汽油和距离之差（petrol[i] - distance[i]）。这代表了该加油站的净汽油收益/损失。
2. 累积检查：如果在遍历期间的任何时候，总汽油余额变为负数，则表示旅程无法从当前起始点开始。将起始点重置为下一个加油站。
3. 全局余额：如果所有加油站的总可用汽油（sum(petrol)）小于所需的总距离（sum(distance)），则不存在有效的起始点。

让我们在一个 Java 程序中实现上述算法。

文件名：CircularTour.java

输出

 
The truck can start at petrol pump index: 1   

解释

该实现围绕着通过维护两个 变量：currentPetrol 和 deficit 来有效地识别起始点。currentPetrol 跟踪卡车在访问每个加油站时油箱中的汽油量，而 deficit 存储当 currentPetrol 变为负数时遇到的任何负余额。

如果 currentPetrol 变为负数，则意味着从当前加油站或之前的任何加油站出发都无法完成循环。因此，将起始点 (start) 移至下一个加油站。最后，currentPetrol 和 deficit 的总和决定了旅程是否可行。如果它非负，则可以从计算出的 start 索引开始完成旅程。

复杂度分析

时间复杂度分析

1. 单次通过加油站：算法只需遍历加油站列表一次，因此时间复杂度为 O(n)。
2. 空间复杂度：由于除了少数变量外，没有使用额外的 数据结构，因此使用的空间是恒定的 O(1)。

空间复杂度分析

所提供的 Java 解决方案中圆形旅行问题的空间复杂度为 O(1)。这是因为该算法仅使用固定数量的变量（start、currentPetrol 和 deficit）来跟踪解决方案的状态，并且不分配与输入大小成比例的任何额外空间。所有操作都在给定的汽油站 数组 上就地执行，因此空间使用是恒定的。

关键考虑因素和变化

1. 边缘情况
   
   • 所有加油站的汽油量都少于所需距离（对于所有 i，petrol[i] < distance[i]）：卡车无法完成旅行。
   • 总汽油量足够但没有可行的起始点（例如，开头有很大的赤字）：算法通过检查 currentPetrol + deficit 来处理这种情况。
2. 变化
   
   • 该问题还可以使用基于队列的方法来解决，其中根据可行性动态添加或删除索引。但是，这会将最坏情况下的复杂度增加到 O(n^2)。

结论

圆形旅行问题展示了贪婪算法和仔细的变量管理在实现高效解决方案方面的力量。提供的 Java 实现确保了该问题的清晰性、正确性和最佳性能。