企业外贸网站建设方案,一个电信ip做网站卡不卡,网站排名搜索,如何编辑微信小程序1184. 公交站间的距离
today 1184 公交站间的距离
题目描述
环形公交路线上有 n 个站#xff0c;按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离#xff0c;distance[i] 表示编号为 i 的车站和编号为 (i 1) % n 的车站之间的距离。
环线上的公交车都…1184. 公交站间的距离
today 1184 公交站间的距离
题目描述
环形公交路线上有 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示例 2
输入distance [1,2,3,4], start 0, destination 2
输出3
解释公交站 0 和 2 之间的距离是 3示例 3
输入distance [1,2,3,4], start 0, destination 3
输出4
解释公交站 0 和 3 之间的距离是 4提示
1 n 10^4distance.length n0 start, destination n0 distance[i] 10^4
题目解析
这道题目是一道关于环形公交路线的题目。
首先我们可以将环形公交路线看作是一个环然后我们可以从 start 出发沿着顺时针方向行驶直到到达 destination这样得到的距离为sum1。 我们再从 destination 出发沿着逆时针方向行驶直到到达 start这样得到的距离为sum2最后我们返回 min(sum1, sum2)。 值得注意的是sum1和sum2的和为整个环路的距离。因此我们可以通过一次遍历解决问题。
复杂度分析
时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
代码实现
Python版本
class Solution(object):def distanceBetweenBusStops(self, distance, start, destination):if startdestination:start,destinationdestination,startsum1sum(distance[start:destination])sum2sum(distance[:])-sum1return min(sum1,sum2)C版本
class Solution {
public:int distanceBetweenBusStops(vectorint distance, int start, int destination) {if (start destination) {swap(start, destination);}int sum10,sum20;for(int i0;idistance.size();i){if(istartidestination)sum1distance[i];elsesum2distance[i];}return min(sum1,sum2);}
};Go版本
func distanceBetweenBusStops(distance []int, start, destination int) int {if start destination {start, destination destination, start}sum1, sum2 : 0, 0for i, j : range distance {if start i i destination {sum1 j} else {sum2 j}}return min(sum1, sum2)
}
