Python|移动石子直到连续

1 问题描述

三枚石子放置在数轴上，位置分别为 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 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。

2 问题分析

因为分别要求最大值和最小值，我们就分开进行分析。

想要移动次数最大，那就一步一步往中间挪。因为题目已经说明只能移动左边或者右边的石子，不能移动中间的石子，所以这是最大值唯一的一种情况，不用过分分析。因为z和x之间能移动的空间是z-x-1，再去掉一个y占的位置，所以最终移动的最多次数就是z-x-2。

接下来就分析最小值。和最大值不同，在不同情况下最小值有不同的规律。根据间隔的空位情况可以分成以下三种：（为便于观看，下面举例中用*代替间隔）

三个石子之间间隔都为零。例如：xyz；这种情况最小值就为0。

三个石子之间有两个石子间隔为一，或者三个石子之间有两个石子相邻。例如：x*y***z,xy***z；这种情况最小值就为1。

三个石子两两间隔为大于一。例如：x**y**z；这种情况最小值就为2。

3 题目代码

class Solution:

    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:

        # d_min:三石子间距最小值，d_max:最大值（也就是z-y），d_mid:中间值

        d_min, d_mid, d_max = sorted([abs(a-b), abs(b-c), abs(a-c)])

        # (d_min > 2) + 1:当d_min>2时，返回1+1；d_min<=2时，返回1

        return [0 if d_mid == 1 else (d_min > 2) + 1, d_max - 2]

4 题目总结

题目很有意思，理解题意之后要分清楚不同的情况对应的什么规律。之后再写代码。总体上看难度并不是很大。但要注意一些细节，特别是分析最小值时那几种情况。思考的时候要全面，但也不要过分思考，要对自己有信心。

END

主 编 | 王文星

责 编 | 周茂林

where2go 团队