前往
大廳
主題

LeetCode - 1629. Slowest Key 解題心得

Not In My Back Yard | 2022-02-25 00:00:10 | 巴幣 0 | 人氣 111

題目連結:


題目意譯:
一個新款設計的鍵盤將被測試,其中測試者會照一序列按下 n 個鍵,一次按一個。

你被給定一長度為 n 的字串 keysPressed,其中 keysPressed[i] 為測試序列中第 i 個按下的按鍵,以及一個排序後的列表 releaseTimes,其中 releaseTimes[i] 為第 i 個按鍵被釋放的時間。兩個陣列索引值皆從 0 開始。第 0 個按鍵於時間 0 按下,且接著每個按鍵將於前一個按鍵釋放的那一瞬間按下。

測試者想知道有著最長一次按壓時間的按鍵為何。第 i 次按壓有著時長 releaseTimes[i] - releaseTimes[i - 1],而第 0 個按壓有著時長 releaseTimes[0]。

注意,同一個按鍵可能會在測試中被重複按壓,且這些同一個按鍵的每次重複按壓不一定有著相同的時長。

回傳最長一次按壓時間的按鍵。如果有多個這樣子的按壓,回傳當中字典序最大的按鍵。

限制:
releaseTimes.length == n
keysPressed.length == n
2 ≦ n ≦ 1000
1 ≦ releaseTimes[i] ≦ 10 ^ 9
releaseTimes[i] < releaseTimes[i+1]
keysPressed 只包含小寫英文字母。



範例測資:
範例 1:
輸入: releaseTimes = [9,29,49,50], keysPressed = "cbcd"
輸出: "c"
解釋: 按壓順序如下:
按下 'c' 並有著時長 9(於時間 0 按下並於時間 9 釋放)。
按下 'b' 並有著時長 29 - 9 = 20(於前一個按鍵釋放的時間 9 那一瞬間按下並於時間 29 釋放)。
按下 'c' 並有著時長 49 - 29 = 20(於時前一個按鍵釋放的時間 29 那一瞬間按下並於時間 49 釋放)。
按下 'd' 並有著時長 50 - 49 = 1(於前一個按鍵釋放的時間 49 那一瞬間按下並於時間 50 釋放)。
這些按壓事件中最長的為 'b' 和 'c',兩者時長皆為 20。
'c' 字典序大於 'b',所以答案為 'c'。

範例 2:
輸入: releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
輸出: "a"
解釋: 按壓順序如下:
按下 's' 並有著時長 12。
按下 'p' 並有著時長 23 - 12 = 11。
按下 'u' 並有著時長 36 - 23 = 13。
按下 'd' 並有著時長 46 - 36 = 10。
按下 'a' 並有著時長 62 - 46 = 16。
這些按壓事件中最長的為 'a',其時長為 16。


解題思維:
就是單純掃過 releaseTimes 這個陣列求出每次按壓的時長,然後更新時長最大值即可。若有按鍵時長與當前最大值相等,則比較兩次的按鍵之字典序,留下字典序較大者即可。




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

創作回應

更多創作