Illustration leetcode - 1184. Distance between bus stops (difficulty: simple)

One 、 subject

There are... On the circular bus route  n  Individual station , From  0  To  n - 1  Number . We know the distance between each pair of adjacent bus stops ,distance[i]  Indicates that the number is  i  The station and number are  (i + 1) % n  The distance between the stations .

All buses on the loop line can press Clockwise and Anti-clockwise Driving in the same direction .

Return passengers from the starting point  start  Destination  destination  The shortest distance between .

Two 、 Example

2.1> Example 1

【 Input 】distance = [1,2,3,4], start = 0, destination = 1
【 Output 】1
【 explain 】 Bus stop 0 and 1 The distance between them is 1 or 9, The minimum is 1.

2.2> Example 2

【 Input 】distance = [1,2,3,4], start = 0, destination = 2
【 Output 】3
【 explain 】 Bus stop 0 and 2 The distance between them is 3 or 7, The minimum is 3.

2.3> Example 3

【 Input 】distance = [1,2,3,4], start = 0, destination = 3
【 Output 】4
【 explain 】 Bus stop 0 and 3 The distance between them is 6 or 4, The minimum is 4.

Tips ：

• 1 <= n <= 10^4
• distance.length == n
• 0 <= start, destination < n
• 0 <= distance[i] <= 10^4

3、 ... and 、 Their thinking

3.1> Ideas 1： Forward and reverse double pointers

Since all the buses on the loop line are ok Drive clockwise and counterclockwise . Then we pass two pointers respectively , Start from the beginning and start from the end , Drive , Although the calculation route from the end point to the starting point is also positive , But according to the meaning of the question, it is actually from the beginning to the end , And experience the same distance , therefore , We call counting from the end to the start “ reverse ”. that , At first , Forward count ：forwardCount=0, Reverse counting ：reverseCount=0, Whether the forward driving is over ：forwardDriveFinished=false, Whether the reverse driving is over ：reverseDriveFinished=false. As shown in the figure below ：

Then when the first run is over , We found that , The reverse form is over （ namely ： from index(3) To index(0)）, Reverse counting ：reverseCount=2. And the positive form is still in progress , Where the positive count ：forwardCount=1. because reverseCount > forwardCount, So drive forward and continue .

 

Then the reverse form has ended in the last cycle , So this wheel can only be driven in a positive direction , Drive to index(2) The nodes of , Forward count ：forwardCount=3, because reverseCount < forwardCount, therefore , We can conclude that , The reverse form is shorter （ Although the forward drive continues ...）, Now that the result has been determined , Then we can end the forward drive at this time . return reverseCount Value as the result .

3.2> Ideas 2： Compare the results after complete traversal

The advantage of idea one is , When there is a small number of steps in the forward or reverse direction , We don't have to wait for the party with a longer number of steps to complete , As long as the end is completed, the shortest distance can be confirmed , You can end the traversal . But there is more code to implement . and If we want a simple code implementation , We can actually go through a complete loop , Then pass the final result , To judge .

Why can it be determined by a complete traversal ？ Suppose the total array is [1, 2, 3, 4, 5, 6, 7, 8], If we start=2,destination=7, that stay [2, 7) Count in the range of , It's the distance in the forward direction . And because the whole journey is a ring road , namely ： It's a circle , therefore Out of scope , Is the range of reverse driving . And if the destination=2,start=7 What shall I do? ？ Actually sum start=2,destination=7 The calculation is the same , For convenience , We just need to put destination=2,start=7 Transformation for start=2,destination=7, You can count . This way, , The implementation code will be more convenient and tidy . As shown in the figure below ：

Four 、 Code implementation

4.1> Realization 1： Forward and reverse double pointers

public int distanceBetweenBusStops1(int[] distance, int start, int destination) {
    int forwardCount = 0, reverseCount = 0, startNum = start, destinationNum = destination;
    boolean forwardDriveFinished = false, reverseDriveFinished = false;
    while (!forwardDriveFinished || !reverseDriveFinished) {
        //  Take a step forward 
        if (!forwardDriveFinished) {
            forwardCount += distance[startNum];
            startNum = (startNum + 1) % distance.length;
            if (startNum == destination) {
                forwardDriveFinished = true;
            }
        } else if (forwardCount <= reverseCount) {
            return forwardCount;
        }

        //  Take a step backwards 
        if (!reverseDriveFinished) {
            reverseCount += distance[destinationNum];
            destinationNum = (destinationNum + 1) % distance.length;
            if (start == destinationNum) {
                reverseDriveFinished = true;
            }
        } else if (reverseCount <= forwardCount) {
            return reverseCount;
        }
    }
    return Math.min(forwardCount, reverseCount);
}

4.2> Realization 2： Compare the results after complete traversal

public int distanceBetweenBusStops2(int[] distance, int start, int destination) {
    int forwardCount = 0, reverseCount = 0;
    if (start > destination) {
        int temp = destination;
        destination = start;
        start = temp;
    }

    for (int i = 0; i < distance.length; i++) {
        if (i >= start && i < destination) {
            forwardCount += distance[i];
        } else {
            reverseCount += distance[i];
        }
    }
    return Math.min(forwardCount, reverseCount);
}

That's all for today's article ：

Writing is not easy to , An article completed by the author in hours or even days , I only want to exchange you for a few seconds give the thumbs-up & Share .

More technical dry goods , Welcome everyone to follow the official account @ Java Muse 「 Dry cargo sharing , Update daily 」

Previous recommendation

The illustration LeetCode——731. My schedule II（ difficulty ： secondary ）https://mp.csdn.net/mp_blog/creation/editor/125884328 The illustration LeetCode——3. Longest substring without repeating characters （ difficulty ： secondary ）https://mp.csdn.net/mp_blog/creation/editor/125857066LeetCode Work: ——21. Merge two ordered lists （ difficulty ： Simple ）https://mp.csdn.net/mp_blog/creation/editor/125840103LeetCode Work: ——565. Array nesting （ difficulty ： secondary ）https://mp.csdn.net/mp_blog/creation/editor/125831251

Title source ： Power button （LeetCode）