前往
大廳
主題

LeetCode - 1560. Most Visited Sector in a Circular Track 解題心得

Not In My Back Yard | 2023-05-16 12:00:01 | 巴幣 100 | 人氣 115

題目連結:


題目意譯:
給定一個整數 n 以及一個整數陣列 rounds。代表我們有著一個環狀賽道其由編號為 1 到 n 的 n 個區域組成。一場馬拉松將在此賽道上矩形,該馬拉松由 m 輪組成。第 i 輪從第 rounds[i - 1] 區域開始,並於第 rounds[i] 區域結束。例如第 1 輪開始於 rounds[0] 並結束於 rounds[1]。

回傳一個陣列,其由最常被探訪的區域之編號組成,並以升序順序排列。

注意到,你將以區域編號之升序順序逆時針環繞著賽道(參見第一個範例)。

限制:
2 ≦ n ≦ 100
1 ≦ m ≦ 100
rounds.length == m + 1
1 ≦ rounds[i] ≦ n
rounds[i] != rounds[i + 1] for 0 ≦ i < m



範例測資:
範例 1:
輸入: n = 4, rounds = [1,3,1,2]
輸出: [1,2]
解釋: 馬拉松從區域 1 開始。探訪的區域之順序為以下:
1 --> 2 --> 3 (第 1 輪之結尾)--> 4 --> 1 (第 2 輪之結尾) --> 2 (第 3 輪與馬拉松之結尾)
我們可以看到區域 1 和 2 都被探訪了兩次,而它們是最常被探訪的區域。區域 3 和 4 只有被探訪一次。

範例 2:
輸入: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
輸出: [2]

範例 3:
輸入: n = 7, rounds = [1,3,5,7]
輸出: [1,2,3,4,5,6,7]


解題思維:
直接模擬並統計是可行的(因為 n 和 m 都不大,所以最糟時間複雜度為 O(mn))。


不過仔細觀察可以得知,我們只需要 rounds[0](開頭區域,稱其為 X)和 rounds[m](結尾區域,稱其為 Y)便可以知道哪些區域最常被探訪。因為我們被強迫以逆時針順序繞著賽道,不能往回跑。

如果 X > Y,則代表區域 1 、 2 、……、Y 與區域 X 、 X + 1 、……、n 是最常被探訪的區域;而如果 X ≦ Y,則代表區域 X 、 X + 1 、……、Y 是最常被探訪的區域。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作