1033-移动石子直到连续

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

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

方法一：贪心

思路与算法

我们可以假设 x, y, z 分别为从小到大排序后的 a, b, c，来讨论最小和最大移动次数。

  1. 当三枚石子连续放置时，即 (y - x) = 1 并且 (z - y) = 1，不需要额外移动，最小移动次数为 0。
  2. 当三枚石子中有两枚是连续放置，或者间隔为 1 时，我们只需对另外一枚石子移动一次，最小移动次数为 1。
  3. 对于其他情况，我们最小需要移动 2 次。

对于最多移动次数，我们可以考虑将 x 向右（增加 1），或者将 z 向左（减小 1），每次移动都会使得两侧的距离减小 1，所以最多可以移动 z - x - 2 次。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        int x = min({a, b, c});
        int z = max({a, b, c});
        int y = a + b + c - x - z;

        vector<int> res(2);
        res[0] = 2;
        if ((z - y) == 1 && (y - x) == 1) {
            res[0] = 0;
        } else if ((z - y) <= 2 || (y - x) <= 2) {
            res[0] = 1;
        }
        res[1] = (z - x - 2);
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int x = Math.min(Math.min(a, b), c);
        int z = Math.max(Math.max(a, b), c);
        int y = a + b + c - x - z;

        int[] res = new int[2];
        res[0] = 2;
        if (z - y == 1 && y - x == 1) {
            res[0] = 0;
        } else if (z - y <= 2 || y - x <= 2) {
            res[0] = 1;
        }
        res[1] = z - x - 2;
        return res;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        x, y, z = sorted([a, b, c])
        res = [2, z - x - 2]
        if ((z - y) == 1 and (y - x) == 1):
            res[0] = 0
        elif ((z - y) <= 2 or (y - x) <= 2):
            res[0] = 1
        return res
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
    res := []int{2, z - x - 2}
    if ((z - y) == 1 && (y - x) == 1) {
        res[0] = 0;
    } else if ((z - y) <= 2 || (y - x) <= 2) {
        res[0] = 1;
    }
    return res
}

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var numMovesStones = function(a, b, c) {
    let x = Math.min(Math.min(a, b), c);
    let z = Math.max(Math.max(a, b), c);
    let y = a + b + c - x - z;
    let res = [2, z - x - 2];
    if (z - y == 1 && y - x == 1) {
        res[0] = 0;
    } else if (z - y <= 2 || y - x <= 2) {
        res[0] = 1;
    }
    return res;
};
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int[] NumMovesStones(int a, int b, int c) {
        int x = Math.Min(Math.Min(a, b), c);
        int z = Math.Max(Math.Max(a, b), c);
        int y = a + b + c - x - z;

        int[] res = new int[2];
        res[0] = 2;
        if (z - y == 1 && y - x == 1) {
            res[0] = 0;
        } else if (z - y <= 2 || y - x <= 2) {
            res[0] = 1;
        }
        res[1] = z - x - 2;
        return res;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int* numMovesStones(int a, int b, int c, int* returnSize) {
    int x = MIN(a, b);
    int z = MAX(a, b);
    x = MIN(x, c);
    z = MAX(z, c);
    int y = a + b + c - x - z;

    int *res = (int *)malloc(sizeof(int) * 2);
    res[0] = 2;
    if ((z - y) == 1 && (y - x) == 1) {
        res[0] = 0;
    } else if ((z - y) <= 2 || (y - x) <= 2) {
        res[0] = 1;
    }
    res[1] = (z - x - 2);
    *returnSize = 2;
    return res;
}

复杂度分析

  • 时间复杂度：O(1)。

  • 空间复杂度：O(1)。

 Comments
On this page
1033-移动石子直到连续