Leetcode 1033 Moving Stones Until Consecutive

发表于 |

三个石头在一条直线上，分别在位置a, b, c处

每轮你可以选择一个最左或最右处的石头，然后将其移动至原先最左最右处的中间某处位置（不能和另外两个点重合）。

你需要一直移动石头直至三个石头处在连续位置。
当游戏结束时，返回达成上述局面所需的最小移动次数和最大移动次数。

示例1：
输入：a = 1, b = 2, c = 5
输出：[1,2]
解释：最小是将5移动到3，最大是从5移动到4再移动到3

提示：

  1. 1 <= a, b, c <= 100
  2. a != b != c

思路分析
不妨设a < b < c，首先分析最小情况：
对于任意三个数，我们总可以在两步之内将其变成连续的三个数，如a,b,c
将a变成b-1，将c变成b+1。
如果a,b,c已经有序，那么最小移动次数是0次
如果a,b,c满足已经有两个数临近或间隔为2，也就是 1,2,x 或 1,3,x的情况，那么最小移动次数是1次
其余情况全为2次

分析最大情况：
因为每次移动之后三个数总要靠近，那么每一次只靠近一步就是最大次数
对于a,b,c，最大移动次数为 c-b+1 + b-a+1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        a, b, c = sorted([a, b, c])
        if a == b-1 and b == c-1: minv = 0
        elif b-a<=2 or c-b<=2: minv = 1
        else: minv = 2
        maxv = c - b - 1 + (b - a - 1)
        return [minv, maxv]

#187 / 187 test cases passed.
#Status: Accepted
#Runtime: 36 ms, beats 100%
#Memory Usage: 13.1 MB