查找访问所有加油站的第一个循环行程

给定一个加油站数组，其中数组的每个元素代表一个加油站。每个加油站有两个属性：

汽油：加油站可以提供的汽油量。

距离：到下一个加油站的距离。

任务是找到一个加油站，从那里开始可以进行一个环形旅程，并能完成整个旅程，以便你可以穿过每个加油站并返回起点。每个加油站提供一定量的汽油，而连续加油站之间的距离会消耗一些汽油。

让我们来实现它的代码

代码

输出

说明

结构定义

该代码定义了一个 PetrolPump 结构，包含两个属性：petrol 和 distance。数组中的每个元素都代表一个具有这些属性的加油站。

函数 findStartingPoint

该函数接受加油站数组 (arr) 和加油站数量 (n) 作为输入参数。

它实现了查找环形旅程起点的算法。

初始化

start 和 end 初始化为 0 和 1，分别表示旅程中当前的起始加油站和结束加油站。

curr_petrol 初始化为起始加油站的汽油量减去距离。

主循环

代码使用一个 while 循环，该循环一直持续到找到合适的起点（当 end 等于 start 且 curr_petrol 非负时）。

检查并更新当前汽油量

如果 curr_petrol 变为负数，则表示当前的起点不合适。

代码进入一个嵌套的 while 循环以查找新的起点 (start)。

它减去从移除的加油站到下一个加油站所消耗的汽油，并递增 start。

此循环一直持续到找到一个有效的起点或检查完所有加油站。

移动到下一个加油站

代码以循环方式将 end 更新到下一个加油站。

更新当前汽油量

通过添加当前加油站提供的汽油量并减去到下一个加油站的距离来更新 curr_petrol。

返回起点

如果找到合适的起点，则函数返回该加油站的索引作为起点。

如果在遍历所有加油站后仍未找到合适的起点，则返回 -1。

主函数

main 函数用于创建演示用的加油站数组 (arr)。

使用此数组调用 findStartingPoint 函数，并将结果存储在 start 变量中。

输出

如果找到了起点 (start != -1)，则打印出可以开始环形旅程的加油站的索引。

如果没有解决方案（start == -1），则打印一条消息，表明没有找到合适的起点。

让我们讨论时间和空间复杂度

时间复杂度

代码的时间复杂度为 O(N)，其中 N 是加油站的数量。

说明

主循环一直运行直到找到合适的起点，最多迭代每个加油站两次（一次用于 start，一次用于 end）。

每次循环迭代都涉及常数时间的操作（算术、比较和更新）。

嵌套的 while 循环在最坏情况下会迭代所有加油站一次，这为时间复杂度贡献了 O(N)。

因此，总时间复杂度为 O(N)。

空间复杂度

代码的空间复杂度为 O(1)，即常数空间。

解释：代码使用的额外空间量是恒定的，与输入大小无关。

使用的变量只有 start、end、curr_petrol 和循环控制变量。

没有创建任何依赖于输入大小的额外数据结构或数组。

因此，总空间复杂度为 O(1)。