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つの道が存在します.左側から、右側から、簡単に道を求めて、残りの道は全体-求めたばかりの道だと思います.
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から離れ、最後のインデックスの後に最初のインデックスで再開されます(インデックス%全長).