[Leetcode 1033] Moving Stones Until Consecutive

原题说明

Three stones are on a number line at positions a, b, and c.

Each turn, you pick up a stone at an endpoint (ie., either the lowest or highest position stone), and move it to an unoccupied position between those endpoints.  Formally, let’s say the stones are currently at positions x, y, z with x < y < z.  You pick up the stone at either position x or position z, and move that stone to an integer position k, with x < k < z and k != y.

The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.

When the game ends, what is the minimum and maximum number of moves that you could have made?  Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

 

Example 1:

Input: a = 1, b = 2, c = 5
Output: [1,2]
Explanation: Move the stone from 5 to 3, or move the stone from 5 to 4 to 3.

Example 2:

Input: a = 4, b = 3, c = 2
Output: [0,0]
Explanation: We cannot make any moves.

Example 3:

Input: a = 3, b = 5, c = 1
Output: [1,2]
Explanation: Move the stone from 1 to 4; or move the stone from 1 to 2 to 4.

 

Note:

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

解题思路

首先将a, b, c排序，最多的步数是将两边的石头每次移动一格，因此最多移动c - a - 2格，-2是因为要跳过中间的石头。
最少的步数要根据情况判断：
1）如果说没有任何两块石头靠在一起（即min(stones[2] - stones[1], stones[1] - stones[0]) > 2）那么要移动两步让三块石头都靠一起
2）反之，如果有一边石头已经靠在一起了，那么只需要移动另一边石头一次
3）如果两边石头都是靠在一起的（即stones[2] - stones[0] == 2）那么一次都不用移动。

示例代码 (cpp)

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        vector<int> stones = {a, b, c};
        sort(stones.begin(), stones.end());
        if (stones[2] - stones[0] == 2) {
            return {0, 0};
        }
        return {min(stones[2] - stones[1], stones[1] - stones[0]) <= 2 ? 1 : 2, stones[2] - stones[0] - 2};
    }
};

示例代码 (java)

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
      int[] s = { a, b, c };
      Arrays.sort(s);
      if (s[2] - s[0] == 2) return new int[] { 0, 0 };
      return new int[] { Math.min(s[1] - s[0], s[2] - s[1]) <= 2 ? 1 : 2, s[2] - s[0] - 2 };
    }
}

示例代码 (python)

class Solution:
    def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
        x, y, z = sorted([a, b, c])
        if x + 1 == y == z - 1:
            min_steps = 0
        elif y - x > 2 and z - y > 2:
            min_steps = 2
        else:
            min_steps = 1
        max_steps = z - x - 2
        return [min_steps, max_steps]

复杂度分析

时间复杂度: O(1)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！