What is the minimum number of moves required in "Moving Stones Until Consecutive"?

The minimum number of moves required is always at most two, by placing one stone adjacent to another, then moving the third stone next to the others.

What is the maximum number of moves in this problem?

The maximum number of moves is three, as you can move each stone one by one to make them consecutive.

How can GhostInterview help with "Moving Stones Until Consecutive"?

GhostInterview helps by offering detailed insights into how to approach the problem, highlighting optimal strategies, and addressing potential mistakes.

Can the stones start already in consecutive positions?

Yes, if the stones are already consecutive, no moves are required, and the answer would be [0,0].

How do I calculate the number of moves in "Moving Stones Until Consecutive"?

To calculate the number of moves, analyze the distance between the stones and determine how many steps are needed to place the stones consecutively, based on the game rules.

#1033

Medium

auto_awesome数学·结合·brainteaser

LeetCode 题解工作台

移动石子直到连续

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

数学脑筋急转弯

题目描述

三枚石子放置在数轴上，位置分别为 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 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a

lightbulb

解题思路

方法一：分类讨论

我们先将 $a, b, c$ 排序，记为 $x, y, z$ ，即 $x \lt y \lt z$ 。

接下来分情况讨论：

如果 $z - x \leq 2$ ，说明 $3$ 个数已经相邻，不用移动，结果为 $[0, 0]$ ；
否则，如果 $y - x \lt 3$ ，或者 $z - y \lt 3$ ，说明有两个数只间隔一个位置，我们只需要把另一个数移动到这两个数的中间，最小移动次数为 $1$ ；其他情况，最小移动次数为 $2$ ；
最大移动次数就是两边的数字逐个往中间靠，最多移动 $z - x - 2$ 次。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        x, z = min(a, b, c), max(a, b, c)
        y = a + b + c - x - z
        mi = mx = 0
        if z - x > 2:
            mi = 1 if y - x < 3 or z - y < 3 else 2
            mx = z - x - 2
        return [mi, mx]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates understanding of how to minimize the number of moves in the game.
question_mark
The candidate efficiently identifies the minimum and maximum number of moves required for the given input.
question_mark
The candidate discusses the strategy for choosing which stone to move in each step.

warning

常见陷阱

外企场景

error
Overcomplicating the calculation of moves when the solution is simple and requires minimal operations.
error
Failing to recognize that the minimum moves are always limited to a maximum of two steps.
error
Misunderstanding the maximum number of moves and assuming that more than three steps might be required.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider the case where the stones are placed in consecutive positions from the beginning.
arrow_right_alt
Explore how the problem changes if the stones can be moved to any integer position instead of being restricted to unoccupied spaces between the other stones.
arrow_right_alt
Examine how the problem would change if there were more than three stones, requiring a strategy for larger sets of stones.

help

常见问题

外企场景

继续练习

#1025 除数博弈 #1227 飞机座位分配概率 #810 黑板异或游戏