LeetCode 1184. Distance Between Bus Stops
1719 ワード
A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.
The bus goes along both directions i.e. clockwise and counterclockwise.
Return the shortest distance between the given start and destination stops.
経路が丸いので、出発地と到着地まで2つの道が存在します.左側から、右側から、簡単に道を求めて、残りの道は全体-求めたばかりの道だと思います.
考えを変えて,始点->終点の長さと終点->始点の長さをそれぞれ求める.
The bus goes along both directions i.e. clockwise and counterclockwise.
Return the shortest distance between the given start and destination stops.
経路が丸いので、出発地と到着地まで2つの道が存在します.左側から、右側から、簡単に道を求めて、残りの道は全体-求めたばかりの道だと思います.
class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
int distanceOne = 0;
for (int i=start; i<destination; i++){
distanceOne += distance[i];
}
int totalDistance = 0;
for (int i=0; i<distance.length; i++){
totalDistance += i;
}
return Math.min(distanceOne, totalDistance);
}
}
しかし,始点が0−index,終点がlast−indexの反例が発生した.考えを変えて,始点->終点の長さと終点->始点の長さをそれぞれ求める.
class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
int n = distance.length;
// 1st path : start to destination
int firstPath = 0;
for (int i=start; i%n != destination; i++) {
firstPath += distance[i%n];
}
// 2nd path : destination to start
int secondPath = 0;
for (int i=destination; i%n != start; i++) {
secondPath += distance[i%n];
}
return Math.min(firstPath, secondPath);
}
}
ポイント->開始ポイントに達すると、インデックスはboundから離れ、最後のインデックスの後に最初のインデックスで再開されます(インデックス%全長).Reference
この問題について(LeetCode 1184. Distance Between Bus Stops), 我々は、より多くの情報をここで見つけました https://velog.io/@strawberry/LeetCode-1184.-Distance-Between-Bus-Stopsテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol