1184. 公交站间的距离（24.9.16）

题目

环形公交路线上有n个站，按次序从 0 到n - 1进行编号。已知每一对相邻公交站之间的距离，distance[i]表示编号为i的车站和编号为(i + 1) % n的车站之间的距离。环线上的公交车都可以按顺时针和逆时针的方向行驶。要求返回乘客从出发点start到目的地destination之间的最短距离。

示例 1：

输入：distance=[1,2,3,4], start=0, destination=1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。

示例 2：

输入：distance=[1,2,3,4], start=0, destination=2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。

示例 3：

输入：distance=[1,2,3,4], start=0, destination=3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。

提示：

1. 1 <= n < 10^4；
2. distance.length = n；
3. 0 <= start, destination < n；
4. 0 <= distance[i] <= 10^4。

解题思路

题目当中是一个环，走法只有两种，一种是顺时针走，一种是逆时针走。
顺时针走：顺时针则是从start直接走到destination，只需要一次遍历，每走一步就++，加上对应值即可。
逆时针走：
（1）对于逆时针而言，假设逆时针的起始点为i，由于本题当中逆时针的步数一定小于其圈的大小，与顺时针相反，我们每走一步就--，那么得出的答案就是与终点/起点的相对位置，我们只需要让其沿顺时针方向走一圈其实仍然在这个位置，对于小于0的位置而言我们将其转化为了对应的顺时针的下标，对于大于0的位置而言则是让它多走了一圈，我们需要使用%操作时期回到对应下标
（2）根据 （1）可以得到下方的式子(对应位置)：（假设所在位置于 i，圈的大小为 n ）
        对于i>0而言：(i+n)%n
        对于i<0而言：(i+n)
两个式子可以简化为：(i+n)%n，因为i<0转化为对应位置也为非负数，执行%n无任何影响
（3）对于逆时针的情况需要注意的是：其距离是前一个数字对应的值，因此我们任然需要在对应位置-1再次求对应位置
（4）优化：（2）（3）合并：((i-1)+n)%n

代码

优化前：

class Solution {
public:int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {int n=distance.size();int shun=0,ni=0;//顺for(int i=start;i%n!=destination;i++){shun+=distance[i%n];}//逆for(int i=start;(n+i%n)%n!=destination;i--){int k=(n+i%n)%n;//将当前坐标转化为对应的坐标k=(n+(k-1)%n)%n;//转化为下一个坐标，求出对应长度ni+=distance[k];}return min(shun,ni);}
};

优化后：

class Solution {
public:int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {int n=distance.size();int shun=0,ni=0;//顺for(int i=start;i%n!=destination;i++){shun+=distance[i%n];}//逆for(int i=start;(n+i)%n!=destination;i--){int k=(n+i-1)%n;//将当前坐标转化为对应的坐标ni+=distance[k];}return min(shun,ni);}
};