ETH官方钱包

前往
大廳
主題

LeetCode - 1974. Minimum Time to Type Word Using Special Typewriter 解題心得

Not In My Back Yard | 2022-01-27 00:00:01 | 巴幣 0 | 人氣 250

題目連結:


題目意譯:
現有一個特殊的打字機其有著小寫字母 'a' 到 'z' 排成一圈並有著一個指標。一個字元只可以在指標有指到該字元時才能被打出。指標一開始指向於 'a'。

每一秒,你可以執行以下操作之一:
將指標逆時針或順時針移動一個字元。
打出當前指標指到的字元。

給定一個字串 word,回傳依序打出 word 中每個字元的最少所需秒數。

限制:
1 ≦ word.length ≦ 100
word 由小寫英文字母組成。



範例測資:
範例 1:
輸入: word = "abc"
輸出: 5
解釋:
字元由以下方式印出:
- 花一秒打出字元 'a',因為一開始指標指在 'a' 上。
- 花一秒將指標順時針移動到 'b'。
- 花一秒打出字元 'b'。
- 花一秒將指標順時針移動到 'c'。
- 花一秒打出字元 'c'。

範例 2:
輸入: word = "bza"
輸出: 7
解釋:
字元由以下方式印出:
- 花一秒將指標順時針移動到 'b'。
- 花一秒打出字元 'b'。
- 花兩秒將指標逆時針移動到 'z'。
- 花一秒打出字元 'z'。
- 花一秒將指標順時針移動到 'a'。
- 花一秒打出字元 'a'。

範例 3:
輸入: word = "zjpc"
輸出: 34
解釋:
字元由以下方式印出:
- 花一秒將指標逆時針移動到 'z'。
- 花一秒打出字元 'z'。
- 花十秒將指標順時針移動到 'j'。
- 花一秒打出字元 'j'。
- 花六秒將指標順時針移動到 'p'。
- 花一秒打出字元 'p'。
- 花十三秒將指標逆時針移動到 'c'。
- 花一秒打出字元 'c'。


解題思維:
因為指標一定要指到目標字元,才能打出該字元,又因為要按照的順序打出所有字元。

因此我們可以假設每次打出字元前,我們都需要做若干次移動(只是可能移動字元數為 0,也就是沒動)。

假設現在指標在字元 X(這邊使用數字代表字母,方便計算距離。例 'a' 為 1 、 'b' 為 2 等等),而我們要移動到字元 Y。

一輪的移動中,我們可以順時針或逆時針移動指標,而我們只需看順時針移動的距離
|Y - X|
以及逆時針移動的距離
26 - |Y - X|
哪個最小即可。

每一輪移動都選最小移動距離,而打出字元的秒數故固定為一秒,因此便可以得到最少所需秒數。將過程中總移動距離加上字元總數即是所求。




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

創作回應

更多創作