這是小川的第386次更新，第414篇原創
01 看題和準備
今天介紹的是LeetCode算法題中Easy級别的第247題（順位題号是1033）。在
a
，
b
和
c
位置的數字線上有三塊石頭。每次，你在一個終點（即最低或最高位置的石頭）上拾取一塊石頭，然後将它移動到這些終點之間的空置位置。
形式上，假設石頭目前位于
x
y
z
位置，
x <y <z
。你在x位置或z位置拾取石頭，然後将石頭移動到整數位置
k
x <k <z
且
k！= y
。
當你不能做任何移動時，遊戲結束。例如，當石頭處于連續的位置時。
當遊戲結束時，你可以做出的最小和最大移動次數是多少？将答案作為長度為2的數組傳回：
answer = [minimum_moves，maximum_moves]
例如：
輸入：a = 1，b = 2，c = 5
輸出：[1,2]
說明：将石頭從5移動到3，或将石頭從5移動到4到3。
輸入：a = 4，b = 3，c = 2
輸出：[0,0]
說明：不能做任何移動。
輸入：a = 3，b = 5，c = 1
說明：将石頭從1移動到4;或将石頭從1移動到2到4。
注意：
- 1 <= a <= 100
- 1 <= b <= 100
- 1 <= c <= 100
- a != b，b != c，c != a
02 解題
先将三個數排序，找出最小值
min
，中間值
mid
，最大值
max
最小移動步數：既然要移動的步數最少，那就跳着移動，向中間值
mid
靠攏。
如果三個數都相鄰，那麼就不需要跳。
如果其中有兩個數相鄰，即最小值和中間值相鄰，或者中間值和最大值相鄰，那麼就隻需要跳一步即可。
如果三個數不相鄰，分兩種情況：
- 第一，如果最大值與中間值相差2，那麼隻需要跳一步，将最小值跳到最大值與中間值之間即可；如果中間值與最小值相差2，那麼隻需要跳一步，将最大值跳到中間值與最小值之間即可。
- 第二，任意兩數的內插補點大于2，那就往中間數左右兩邊相鄰的數字上跳，左右兩邊各跳一次即可。
最多移動步數：既然要移動的步數最多，那就一次隻移動一次，向中間值
mid
最大值
max
向左移動，移動到
mid+1
的位置，一共移動了
max-mid-1
步。
最小值
min
向右移動，移動到
mid-1
mid-min-1
是以，最多移動步數為
(max-mid-1)+(mid-min-1) = max - min - 2
public int[] numMovesStones(int a, int b, int c) {
int max = Math.max(a, Math.max(b, c));
int min = Math.min(a, Math.min(b, c));
int mid = a + b + c - max - min;
int min_moves = Math.min(1, mid-min-1) +
Math.min(1, max-mid-1);
if (mid-min == 2 || max-mid == 2) {
min_moves = 1;
}
int max_moves = max - min - 2;
return new int[]{min_moves, max_moves};
}
03 小結
算法專題目前已連續日更超過七個月，算法題文章253+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。
以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！