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 团队