[LeetCode] 1033. Moving Stones Until Consecutive

[grandyang]

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，每次可以取最大或最小的位置，将其放到中间某个没有石头的位置，当三个石头位置相连时游戏结束，问最小和最大的移动分别是多少。这道题的英文描述比较迷，好在有例子可以分析，从而理解题意。首先来分析最大移动次数，其实就是三个石头的中间空位的个数，可以直接计算得出。再来看最小移动次数，其只能是 0，1，2 这三个值中的一个，为啥呢？最好的情况就是三个已经相连了，不需要移动。最坏的情况就是三个都离得很远，但是可以用两次移动分别将最大和最小位置的石头移动到中间的石头的两边，从而使它们相邻。若某两个石头中间只有一个位置，那么可以直接把第三个石头移动到这个中间位置，直接就相连了，最小移动次数一定是1，否则就分别看最大最小值和中间位置的之间的差值情况了。下面来看代码，博主首先将三个数字放到一个数组中，给数组排序，然后分别求出最大值和中间值的差值 diff1，以及中间值和最小值的差值 diff2，若二者中有一个等于2，则最小移动次数一定是1，最大移动次数一定是最大值见最小值减2。否则看 diff1 和 diff2 是否分别大于1，将结果的布尔值累加起来就是最小移动次数了，而最大移动次数仍旧不变，参见代码如下：

解法一：

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        vector<int> nums{a, b, c};
        sort(nums.begin(), nums.end());
        int diff1 = nums[2] - nums[1], diff2 = nums[1] - nums[0];
        if (diff1 == 2 || diff2 == 2) return {1, nums[2] - nums[0] - 2};
        return {(diff1 > 1) + (diff2 > 1), nums[2] - nums[0] - 2};
    }
};

下面来看一种简洁的写法，两行搞定碉堡了。直接先求出三个数字的最大值 mx，和最小值 mn，中间值 mid 就用三个数字之和减去最大值和最小值。然后之间判断 mid-mn 或 mx-mid 横纵是否等于2，是的话最小移动就是1，否则还是差值和1比较的布尔值，最大移动还是 mx-mn-2，参见代码如下：

解法二：

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        int mx = max({a, b, c}), mn = min({a, b, c}), mid = a + b + c - mx - mn;
        return {mid - mn == 2 || mx - mid == 2 ? 1 : (mid - mn > 1) + (mx - mid > 1), mx - mn - 2};
    }
};

Github 同步地址:

#1033

参考资料：

https://leetcode.com/problems/moving-stones-until-consecutive/

https://leetcode.com/problems/moving-stones-until-consecutive/discuss/965583/C%2B%2B-2-lines

https://leetcode.com/problems/moving-stones-until-consecutive/discuss/282836/C%2B%2BJava-4-lines

LeetCode All in One 题目讲解汇总(持续更新中...)