這是小川的第414次更新，第447篇原創(chuàng)

看題和準備

今天介紹的是LeetCode算法題中Easy級別的第265題（順位題號是1184）。公交車有n個從0到n-1的車站，形成一個圓圈。我們知道所有相鄰車站對之間的距離，其中distance[i]是車站i與車站(i + 1)%n之間的距離。

公交車沿兩個方向運行，即順時針和逆時針。返回給定起點和終點之間的最短距離。

輸入：distance = [1,2,3,4], start = 0, destination = 1
輸出：1

image

image

image

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

第一種解法

題目的意思是求兩個車站之間的距離，而所有車站組合起來形成一個環(huán)，因此可以從順時針方向出發(fā)，也可以從逆時針方向出發(fā)。我們只需要做兩件事情即可，第一是保證出發(fā)點的坐標小于終點，第二是比較順時針出發(fā)的距離和逆時針出發(fā)的距離大小。

針對第一點，可以做個判斷，如果出發(fā)點坐標大于終點坐標，就交換兩元素的值，保證出發(fā)點的坐標值始終小于終點的值。

針對第二點，順時針方向出發(fā)的距離之和很好計算，那么逆時針方向出發(fā)的距離和呢？因為整個路徑是成環(huán)形，逆時針方向出發(fā)的距離和，就是用總長減去順時針方向出發(fā)的距離和的差值。

使用兩個循環(huán)，一個計算總長，一個計算從順時針方向出發(fā)的距離和，比較順時針出發(fā)的距離與總長減去順時針出發(fā)的距離的大小即可。

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);
}

第二種解法

針對第一種解法，我們可以優(yōu)化下，只使用一個循環(huán)，在循環(huán)內(nèi)部單獨做個判斷，計算順時針方向出發(fā)的距離和。

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+篇，公眾號對話框回復【數(shù)據(jù)結構與算法】、【算法】、【數(shù)據(jù)結構】中的任一關鍵詞，獲取系列文章合集。

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發(fā)就是對我最大的回報和支持！