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

看題和準(zhǔn)備

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

公交車(chē)沿兩個(gè)方向運(yùn)行，即順時(shí)針和逆時(shí)針。返回給定起點(diǎn)和終點(diǎ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
  
  

第一種解法

題目的意思是求兩個(gè)車(chē)站之間的距離，而所有車(chē)站組合起來(lái)形成一個(gè)環(huán)，因此可以從順時(shí)針?lè)较虺霭l(fā)，也可以從逆時(shí)針?lè)较虺霭l(fā)。我們只需要做兩件事情即可，第一是保證出發(fā)點(diǎn)的坐標(biāo)小于終點(diǎn)，第二是比較順時(shí)針出發(fā)的距離和逆時(shí)針出發(fā)的距離大小。

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

針對(duì)第二點(diǎn)，順時(shí)針?lè)较虺霭l(fā)的距離之和很好計(jì)算，那么逆時(shí)針?lè)较虺霭l(fā)的距離和呢？因?yàn)檎麄€(gè)路徑是成環(huán)形，逆時(shí)針?lè)较虺霭l(fā)的距離和，就是用總長(zhǎng)減去順時(shí)針?lè)较虺霭l(fā)的距離和的差值。

使用兩個(gè)循環(huán)，一個(gè)計(jì)算總長(zhǎng)，一個(gè)計(jì)算從順時(shí)針?lè)较虺霭l(fā)的距離和，比較順時(shí)針出發(fā)的距離與總長(zhǎng)減去順時(shí)針出發(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);
}

第二種解法

針對(duì)第一種解法，我們可以?xún)?yōu)化下，只使用一個(gè)循環(huán)，在循環(huán)內(nèi)部單獨(dú)做個(gè)判斷，計(jì)算順時(shí)針?lè)较虺霭l(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);
}

小結(jié)

算法專(zhuān)題目前已更新LeetCode算法題文章271+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

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