1184. Distance Between Bus Stops (公交站間的距離)
閱讀時間約 1 分鐘
↑看個小廣告，支持好內容↑
要稍微注意一下 distance 的意義，[1, 2, 3, 4] 代表站點 0~1 距離為 1、站點 1~2 距離為 2、站點 2~3 距離為 3、站點 3~0 距離為 4 (路線是一個環形)。
❶ Greedy
公車的行駛是雙向的，可以順時針也能逆時針，但加總起來必定會等於總周長。
// distance=[1,2,3,4], start=1, destination=2
公車可以走 1→2，距離=2
或是可以走 2→3→0→1，距離=3+4+1=8
(加起來就是繞行一圈的總長)
所以任選一條來算就可以，另一條用周長相減就行了。
[注意] start 不一定比 destination 小，但這不會影響答案唷。
- 本題分類標籤：
Array - 本題正解率＝
53.8％
留言0
查看全部
你可能也想看
Google News 追蹤
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述:
給定一個二維陣列的高與寬，並且給定起點位置座標。
請從起點位置開始順時針拜訪陣列元素，並且把沿路走過的座標記錄下來。
以陣列的形式返回答案。
台北捷運最近推出了一個很瘋狂的集章全制霸活動，集滿5條捷運路線(不含環狀線)，總共109個車站，就可以抽大獎，本文將使用 Held Karp 算法來計算從台北車站出發，遍歷 109 個車站，並在最後回到台北車站所需花費的最短時間與路徑。
前言
不知道大家在搭大眾運輸時，更偏好哪一種選擇呢？
繞路但可以一班車抵達，還是直線前進但中間需要換車呢？
假如今天把「目的地」換成我們設定的「目標」，你會選擇前者還是後者呢？
題目敘述 Minimum Cost For Tickets
題目會給定兩個陣列。
第一個是日期陣列days，代表外出旅遊的是哪幾天。
第二個是成本陣列costs，代表火車一日票、七日票、30日的月票的票價。
請問火車旅行支出的最小費用是多少？
又搭錯公車。
上午從木柵回來，想著時間還早，天氣也好，不如搭公車慢慢悠晃回家。
此處有兩班直達住家附近的公車，但都是環狀線，一班去程近，一班回程近。但距上回搭公車已時日久遠，不記得該搭哪一班才對。
想著要先看清楚路線才上車，但走到街口，就看見公車停下來，連猶豫的時間都沒有，於是就上了車。
02/08/2011
花園夜市（2011/01/29/18:00）
火車站前的公車站，有著北站和南站，有著同樣的公車路線站牌。
一直到回台北，我都沒搞懂這兩個站牌究竟是怎麼回事。
不過，有什麼關係，坐公車是自助旅行的第一課。
我想就這樣，我們開始了一個自助旅行的課程。
出了火車站，
01/20/2010
公車司機
自助旅行不可或缺的交通工具是什麼？
當然就是公車了
看了地圖，原本威尼斯人就有公車可以搭到今日的第一站媽祖閣．
在威尼斯週圍“繞了一圈“都沒找到．
去過澳門威尼斯人酒店的人，應該了解我所說的繞了一圈是什麼意思．
基本上和跑了 三千公尺 或是健走 五公
清晨等公車，遇到一台公車很特別，停靠點不是在站牌前，而是至少十步的距離，所有乘客必須往後走十步以上才上得了車。
第一次碰到時，我猜是不是司機心情不好？上車一看，中年司機看來平和，也沒什麼不佳態度，許是特殊情況吧，我這樣想。
第二次又碰到，特意記了一下車號，也特意看了司機一眼，看看下次還有沒有。
題目會給定我們一個輸入陣列connections，和城市的總數目n。
輸入陣列裡面是以pair的方式儲存，(a, b) 分邊代表這條邊的起點和終點。
請問，我們需要改變多少條邊的方向，才能讓每條路徑都指向編號零號的城市( City #0)？
註:
題目還保證，在改變方向之後，一定可以讓每座城
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
題目敘述:
給定一個二維陣列的高與寬，並且給定起點位置座標。
請從起點位置開始順時針拜訪陣列元素，並且把沿路走過的座標記錄下來。
以陣列的形式返回答案。
台北捷運最近推出了一個很瘋狂的集章全制霸活動，集滿5條捷運路線(不含環狀線)，總共109個車站，就可以抽大獎，本文將使用 Held Karp 算法來計算從台北車站出發，遍歷 109 個車站，並在最後回到台北車站所需花費的最短時間與路徑。
前言
不知道大家在搭大眾運輸時，更偏好哪一種選擇呢？
繞路但可以一班車抵達，還是直線前進但中間需要換車呢？
假如今天把「目的地」換成我們設定的「目標」，你會選擇前者還是後者呢？
題目敘述 Minimum Cost For Tickets
題目會給定兩個陣列。
第一個是日期陣列days，代表外出旅遊的是哪幾天。
第二個是成本陣列costs，代表火車一日票、七日票、30日的月票的票價。
請問火車旅行支出的最小費用是多少？
又搭錯公車。
上午從木柵回來，想著時間還早，天氣也好，不如搭公車慢慢悠晃回家。
此處有兩班直達住家附近的公車，但都是環狀線，一班去程近，一班回程近。但距上回搭公車已時日久遠，不記得該搭哪一班才對。
想著要先看清楚路線才上車，但走到街口，就看見公車停下來，連猶豫的時間都沒有，於是就上了車。
02/08/2011
花園夜市（2011/01/29/18:00）
火車站前的公車站，有著北站和南站，有著同樣的公車路線站牌。
一直到回台北，我都沒搞懂這兩個站牌究竟是怎麼回事。
不過，有什麼關係，坐公車是自助旅行的第一課。
我想就這樣，我們開始了一個自助旅行的課程。
出了火車站，
01/20/2010
公車司機
自助旅行不可或缺的交通工具是什麼？
當然就是公車了
看了地圖，原本威尼斯人就有公車可以搭到今日的第一站媽祖閣．
在威尼斯週圍“繞了一圈“都沒找到．
去過澳門威尼斯人酒店的人，應該了解我所說的繞了一圈是什麼意思．
基本上和跑了 三千公尺 或是健走 五公
清晨等公車，遇到一台公車很特別，停靠點不是在站牌前，而是至少十步的距離，所有乘客必須往後走十步以上才上得了車。
第一次碰到時，我猜是不是司機心情不好？上車一看，中年司機看來平和，也沒什麼不佳態度，許是特殊情況吧，我這樣想。
第二次又碰到，特意記了一下車號，也特意看了司機一眼，看看下次還有沒有。
題目會給定我們一個輸入陣列connections，和城市的總數目n。
輸入陣列裡面是以pair的方式儲存，(a, b) 分邊代表這條邊的起點和終點。
請問，我們需要改變多少條邊的方向，才能讓每條路徑都指向編號零號的城市( City #0)？
註:
題目還保證，在改變方向之後，一定可以讓每座城