[LeetCode]1033. 移动石子直到连续

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

算法思路：

我们不能保证a、b、c是有序的，因此我们可以创建数组排序重新赋值。

判断思路：

最大移动次数：a和c向b靠拢，每次只移动一个单位长度，答案就是c-a-2。

最小移动次数：

（1）如果c-a==2，说明已经连续，无需移动。

（2）如果b-α=1或者c-b=1，说明有两颗石子已经连续，那么只需移动1次另一颗石子。 如果b-α=2或者c-b=2，那么把一颗石子移到另外两颗石子之间，只需移动1次移动。即(c - b) <= 2 || (b - a) <= 2且不满足条件（1），则最小移动一次。

（3）都不满足，说明无连续，a移动到b-1，c移动到b+1，移动两次

C++:

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        int v[3] ={a,b,c};
        sort(v,v+3);
        a=v[0];
        b=v[1];
        c=v[2];
        if (c-a==2) {//无需移动 已连续
            return {0,0};
        } else if ((c - b) <= 2 || (b - a) <= 2) {//其中一个连续 则最小只需移动一次
            return {1,c-a-2};
        }//都不连续 最小移动两次 最多移动c-b-1+b-a-1次
        return {2,c-a-2};
    }
};

Java:

class Solution {
    public int[] numMovesStones(int a, int b, int c) {
        int[] v =new int[]{a,b,c};
        Arrays.sort(v);
        a=v[0];
        b=v[1];
        c=v[2];
        
        if (c-a==2) {//无需移动 已连续
            return new int[]{0,0};
        } else if ((c - b) <= 2 || (b - a) <= 2) {//其中一个连续 则最小只需移动一次
            return new int[]{1,c-a-2};
        }//都不连续 最小移动两次 最多移动c-b-1+b-a-1次
        return new int[]{2,c-a-2};
    }
}

 C:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define max(a, b, c) (a) > (b)? ((a) > (c)? (a) : (c)) : ((b) > (c)? (b):(c))
#define min(a, b, c) (a) < (b)? ((a) < (c)? (a) : (c)) : ((b) < (c)? (b):(c))

int* numMovesStones(int a, int b, int c, int* returnSize){
    int* res = (int*)malloc(sizeof(int)*2);
    int x = min(a,b,c);
    int z = max(a,b,c);
    int y = a+b+c-x-z;
     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;

}