这是小川的第414次更新，第447篇原创
看题和准备
今天介绍的是LeetCode算法题中Easy级别的第265题（顺位题号是1184）。公交车有n个从0到n-1的车站，形成一个圆圈。我们知道所有相邻车站对之间的距离，其中distance[i]是车站i与车站(i + 1)%n之间的距离。
公交车沿两个方向运行，即顺时针和逆时针。返回给定起点和终点之间的最短距离。
输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
说明：0与1之间的距离为1或9，最小为1。
输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
说明：0和2之间的距离为3或7，最小为3。
输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
说明：0与3之间的距离为6或4，最小为4。
约束：
- 1 <= n <= 10^4
- distance.length == n
- 0 <= start, destination < n
- 0 <= distance[i] <= 10^4
第一种解法
题目的意思是求两个车站之间的距离，而所有车站组合起来形成一个环，因此可以从顺时针方向出发，也可以从逆时针方向出发。我们只需要做两件事情即可，第一是保证出发点的坐标小于终点，第二是比较顺时针出发的距离和逆时针出发的距离大小。
针对第一点，可以做个判断，如果出发点坐标大于终点坐标，就交换两元素的值，保证出发点的坐标值始终小于终点的值。
针对第二点，顺时针方向出发的距离之和很好计算，那么逆时针方向出发的距离和呢？因为整个路径是成环形，逆时针方向出发的距离和，就是用总长减去顺时针方向出发的距离和的差值。
使用两个循环，一个计算总长，一个计算从顺时针方向出发的距离和，比较顺时针出发的距离与总长减去顺时针出发的距离的大小即可。
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
int sum = 0;
for (int dis : distance) {
sum += dis;
}
int part = 0;
for (int i=start; i<destination; i++) {
part += distance[i];
}
return Math.min(part, sum-part);
}第二种解法
针对第一种解法，我们可以优化下，只使用一个循环，在循环内部单独做个判断，计算顺时针方向出发的距离和。
public int distanceBetweenBusStops2(int[] distance, int start, int destination) {
if (start > destination) {
int temp = start;
start = destination;
destination = temp;
}
int sum = 0, part = 0;
for (int i=0; i<distance.length; i++) {
if (i >= start && i < destination) {
part += distance[i];
}
sum += distance[i];
}
return Math.min(part, sum-part);
}小结
算法专题目前已更新LeetCode算法题文章271+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
- 还没有人评论，欢迎说说您的想法！
客服
