Medium

题目描述

在X轴上有三个不同位置的石子。给定三个整数 a、b 和 c，代表石子的位置。

在一次移动中，你可以选择一个端点的石子（即位置最低或最高的石子），并将其移动到端点之间的一个未被占用的位置。形式化地说，假设石子当前位于位置 x、y 和 z，其中 x < y < z。你可以选择位于位置 x 或 z 的石子，并将该石子移动到整数位置 k，其中 x < k < z 且 k != y。

当你无法进行更多移动时（即石子处于三个连续位置），游戏结束。

返回一个长度为 2 的整数数组 answer，其中：

  • answer[0] 是你能进行的最少移动次数
  • answer[1] 是你能进行的最大移动次数

示例 1：

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

示例 2：

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

示例 3：

输入：a = 3, b = 5, c = 1
输出：[1,2]
解释：将石子从 1 移动到 4；或者将石子从 1 移动到 2 再移动到 4。

约束：

  • 1 <= a, b, c <= 100
  • a, b, c 的值各不相同

解题思路

这是一个数学和脑筋急转弯问题，需要分别计算最少和最多移动次数。

首先对三个位置进行排序，设为 x < y < z。

最少移动次数分析：

  • 如果三个石子已经连续（z - x == 2），则需要 0 次移动
  • 如果有两个石子相邻或距离为 2（y - x <= 2 或 z - y <= 2），则只需要 1 次移动
  • 其他情况需要 2 次移动

最大移动次数分析： 每次移动只能移动端点的石子到中间的空位，每次移动最少减少 1 的总间距。最大移动次数就是总间距减去已占用的位置数。

具体计算：总共有 z - x + 1 个位置，其中 3 个被占用，所以空位有 z - x - 2 个。

由于每次只能填充一个空位，所以最大移动次数为 z - x - 2。

代码实现

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        vector<int> stones = {a, b, c};
        sort(stones.begin(), stones.end());
        int x = stones[0], y = stones[1], z = stones[2];
        
        int minMoves, maxMoves;
        
        // 计算最少移动次数
        if (z - x == 2) {
            minMoves = 0;  // 已经连续
        } else if (y - x <= 2 || z - y <= 2) {
            minMoves = 1;  // 只需要一次移动
        } else {
            minMoves = 2;  // 需要两次移动
        }
        
        // 计算最大移动次数
        maxMoves = z - x - 2;
        
        return {minMoves, maxMoves};
    }
};

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        stones = sorted([a, b, c])
        x, y, z = stones
        
        # 计算最少移动次数
        if z - x == 2:
            min_moves = 0  # 已经连续
        elif y - x <= 2 or z - y <= 2:
            min_moves = 1  # 只需要一次移动
        else:
            min_moves = 2  # 需要两次移动
        
        # 计算最大移动次数
        max_moves = z - x - 2
        
        return [min_moves, max_moves]

public class Solution {
    public int[] NumMovesStones(int a, int b, int c) {
        int[] stones = {a, b, c};
        Array.Sort(stones);
        int x = stones[0], y = stones[1], z = stones[2];
        
        int minMoves, maxMoves;
        
        // 计算最少移动次数
        if (z - x == 2) {
            minMoves = 0;  // 已经连续
        } else if (y - x <= 2 || z - y <= 2) {
            minMoves = 1;  // 只需要一次移动
        } else {
            minMoves = 2;  // 需要两次移动
        }
        
        // 计算最大移动次数
        maxMoves = z - x - 2;
        
        return new int[] {minMoves, maxMoves};
    }
}

/**
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number[]}
 */
var numMovesStones = function(a, b, c) {
    let stones = [a, b, c].sort((x, y) => x - y);
    let x = stones[0], y = stones[1], z = stones[2];
    
    // If already consecutive
    if (z - x === 2) {
        return [0, 0];
    }
    
    // Minimum moves
    let minMoves;
    if (y - x <= 2 || z - y <= 2) {
        minMoves = 1;
    } else {
        minMoves = 2;
    }
    
    // Maximum moves
    let maxMoves = Math.max(y - x - 1, z - y - 1);
    
    return [minMoves, maxMoves];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(1)
空间复杂度O(1)