前往
大廳
主題

LeetCode - 1033. Moving Stones Until Consecutive 解題心得

Not In My Back Yard | 2021-03-15 00:00:04 | 巴幣 0 | 人氣 166

題目連結:


題目意譯:
有三顆石頭位於數線上的位置 a 、 b 以及 c。

每回合,你挑選一個端點上的石頭(即位置值最小或最大的石頭),然後將其移動至兩端點之間未被佔據的位置。更正式地,讓我們假設目前石頭位於位置 x 、 y 、 z 且 x < y < z。你挑在位置 x 或位置 z 的石頭,然後移動該石頭到位置 k ,其中 x < k < z 且 k != y。

此遊戲結束於你不能再做任何操作為止,即三顆石頭的位置是相鄰的。

當遊戲結束時,你能執行的最少以及最多操作數為何?回傳答案以一個長度為 2 之陣列:answer = [最少操作數, 最多操作數]

注:
1 ≦ a ≦ 100
1 ≦ b ≦ 100
1 ≦ c ≦ 100
a != b 、 b != c 、 c != a



範例測資:
範例 1:
輸入: a = 1, b = 2, c = 5
輸出: [1,2]
解釋: 將石頭從 5 移到 3;或將石頭從 5 移到 4 再到 3。

範例 2:
輸入: a = 4, b = 3, c = 2
輸出: [0,0]
解釋: 無法做任何操作。

範例 3:
輸入: a = 3, b = 5, c = 1
輸出: [1,2]
解釋: 將石頭從 1 移到 4;或將石頭從 1 移到 2 再到 4。


解題思維:
我們先將給定的 a 、 b 、 c 排序一下並定為 x 、 y 、 z 且 x < y < z。

最大步數比較直觀:每次端點的石頭只往中間的石頭移動一單位。所以最大步數會是 z - x - 2。

而最小步數比較麻煩一點(情況比較多):
首先當 x + 2 = y + 1 = z 時,因為石頭已經相鄰了所以動不了。因此最小步數為 0;

當 x + 2 = y 或是 y + 2 = z 時,因為其中有兩顆石頭只隔一單位的空格,所以我們可以把另一顆石頭移過來,便可以使所有石頭相鄰。因此最小步數為 1;

剩下的情況,石頭都分得比較開,所以我們最佳步數只能把端點兩顆石頭分別移動到中間的石頭之兩側,所以最少步數為 2。




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

創作回應

更多創作