这是小川的第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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!