移动石子直到连续

标签: 脑筋急转弯 数学

难度: Medium

三枚石子放置在数轴上，位置分别为 a，b，c。

每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

 

示例 1：

输入：a = 1, b = 2, c = 5
输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。

示例 2：

输入：a = 4, b = 3, c = 2
输出：[0, 0]
解释：我们无法进行任何移动。

 

提示：

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

Submission

运行时间: 24 ms

内存: 16.0 MB

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        a, b, c = sorted([a, b, c])
        mx = c - a - 2
        if b-a==1 and c-b==1:
            mn = 0
        elif b-a==1 or c-b==1:
            mn = 1
        elif b-a==2 or c-b==2:
            mn = 1
        else:
            mn = 2
        return [mn, mx]

Explain

首先将输入的三个石子位置进行排序，确保它们的顺序为 a < b < c。最大移动次数计算方法是将两端的石子移动到中间的空位，即距离减去已占用的两个位置（c-a-2）。最小移动次数的计算则需要考虑几种情况：1) 如果三个石子已连续，即 b-a=1 且 c-b=1，则无需移动；2) 如果有两个石子已连续，无论是 a 和 b 还是 b 和 c，只需一次移动即可；3) 如果两个石子之间的距离为 2，即 b-a=2 或 c-b=2，也只需一次移动；4) 其他情况需要至少两次移动，即将最远的石子移至中间的某个位置，然后再进行调整。

时间复杂度: O(1)

空间复杂度: O(1)

# Solution class to determine the number of moves to make stones consecutive
class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        # Sort the stones to get the correct order
        a, b, c = sorted([a, b, c])
        # Calculate the maximum moves by assuming moving both ends to the middle
        mx = c - a - 2
        # Calculate the minimum moves based on the gaps between the stones
        if b-a==1 and c-b==1:
            mn = 0  # Already consecutive
        elif b-a==1 or c-b==1:
            mn = 1  # One move if one pair is already consecutive
        elif b-a==2 or c-b==2:
            mn = 1  # One move if the gap between any two stones is 2
        else:
            mn = 2  # Otherwise, two moves are required
        return [mn, mx]  # Return the result as a list of minimum and maximum moves

Explore

当b-a=2或c-b=2时，表示两个石子之间只隔了一个位置。例如，如果b-a=2，石子的位置可能是a, a+2, c，只需将c移动到a+1的位置，即可使得石子连续（a, a+1, a+2）。同样地，如果c-b=2，石子的位置可能是a, c-2, c，在这种情况下，只需将a移动到c-1的位置，使得石子连续（c-2, c-1, c）。这样，只需要一次移动就可以使石子排列连续。

是的，最小移动次数确实依赖于具体的间隔值。例如，如果间隔值很小（如b-a=1或c-b=1），则最小移动次数可能为0或1。如果石子位置是a, a+1, c且c-a>2，则只需要一次移动，将c移动到a+2的位置。如果间隔值更大，如a, a+3, a+5，这时虽然最小移动次数为2（首先将a+5移动到a+2，然后将a+3移动到a+1或a+4），因此间隔值越大，可能需要更多的移动次数来使石子连续。

最大移动次数的计算基于最保守的移动策略，即将两端的石子移至中间空位。这种情况下的移动次数被认为是最大的，因为它假设了在移动过程中未使用任何可用的短距离移动。实际上，这通常是最不效率的移动方式，因为它没有利用已经相对较近的石子。在绝大多数实际情况下，通过优化移动策略，可以减少移动次数。但从理论上讲，如果移动策略不佳，确实可能存在更多的移动步骤，尤其是在没有优化移动顺序和选择的情况下。