README.md

1033. 移动石子直到连续

English Version

题目描述

三枚石子放置在数轴上，位置分别为 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

解法

方法一：脑筋急转弯

• 若 $3$ 个数已经相邻，则不用移动，直接返回结果 $[0,0]$；
• 若 $3$ 个数中存在两数之差小于 $3$，最小只需移动 $1$ 次；
• 其他情况最小只需移动 $2$ 次；
• 两边逐个往中间靠，就是最大移动次数 $c - a - 2$。

Python3

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        a, b, c = sorted([a, b, c])
        ans = [0] * 2
        if c - a == 2:
            return ans
        if b - a < 3 or c - b < 3:
            ans[0] = 1
        else:
            ans[0] = 2
        ans[1] = c - a - 2
        return ans

Java

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int x = Math.min(a, Math.min(b, c));
        int z = Math.max(a, Math.max(b, c));
        int y = a + b + c - x - z;
        int max = z - x - 2;
        int min = y - x == 1 && z - y == 1 ? 0 : y - x <= 2 || z - y <= 2 ? 1 : 2;
        return new int[]{min, max};
    }
}

C++

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        int x = min(min(a, b), c);
        int z = max(max(a, b), c);
        int y = a + b + c - x - z;
        if (z - x == 2) return {0, 0};
        int mx = z - x - 2;
        int mi = y - x < 3 || z - y < 3 ? 1 : 2;
        return {mi, mx};
    }
};

Go

func numMovesStones(a int, b int, c int) []int {
	x := min(min(a, b), c)
	z := max(max(a, b), c)
	y := a + b + c - x - z
	if z-x == 2 {
		return []int{0, 0}
	}
	mx := z - x - 2
	mi := 2
	if y-x < 3 || z-y < 3 {
		mi = 1
	}
	return []int{mi, mx}
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

...