Related: LeetCode 1040 - Moving Stones Until Consecutive II
https://leetcode.com/problems/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.
三个石头在一条直线上，分别在位置a, b, c处
每轮你可以选择一个最左或最右处的石头，然后将其移动至原先最左最右处的中间某处位置（不能和另外两个点重合）。
示例1：
输入：a = 1, b = 2, c = 5
输出：[1,2]
解释：最小是将5移动到3，最大是从5移动到4再移动到3
提示：
- 1 <= a, b, c <= 100
- a != b != c
https://leetcode.com/problems/moving-stones-until-consecutive/discuss/282836/C%2B%2BJava-4-lines
Edge case 1: all three stones are next to each other (
z - x == 2). Return {0, 0}.
Edge case 2: two stones are next to each other, or there is only one space in between. Minimum moves is
1.
Otherwise; minimum moves are
2, maximum - z - x - 2.
So the position of the middle stone (
y) only matters for the minimum moves.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 };
} public int[] numMovesStones(int a, int b, int c) {
int[] nums = {a, b, c};
Arrays.sort(nums);
int maxCount = nums[2] - nums[0] - 2;
int minCount = 2;
if (nums[2] - nums[1] < 3 || nums[1] - nums[0] < 3) minCount = 1;
if (nums[2] - nums[1] == 1 && nums[1] - nums[0] == 1) minCount = 0;
return new int[] { minCount, maxCount };
}
不妨设a < b < c，首先分析最小情况：
对于任意三个数，我们总可以在
将a变成b-1，将c变成b+1。
如果a,b,c已经有序，那么最小移动次数是0次
如果a,b,c满足已经有两个数临近或间隔为2，也就是
其余情况全为2次
对于任意三个数，我们总可以在
两步之内将其变成连续的三个数，如a,b,c将a变成b-1，将c变成b+1。
如果a,b,c已经有序，那么最小移动次数是0次
如果a,b,c满足已经有两个数临近或间隔为2，也就是
1,2,x 或 1,3,x的情况，那么最小移动次数是1次其余情况全为2次
分析最大情况：
因为每次移动之后三个数总要靠近，那么每一次只靠近一步就是最大次数
对于a,b,c，最大移动次数为 c-b+1 + b-a+1
https://www.cnblogs.com/seyjs/p/10853821.html因为每次移动之后三个数总要靠近，那么每一次只靠近一步就是最大次数
对于a,b,c，最大移动次数为 c-b+1 + b-a+1
首先对a,b,c进行排序，使得a最小，b其次，c最大。最大的移动次数很好求，就是a与c分别往b移动，每次移动一步，很容易得到最大移动次数是abs(c-b-1) + abs(b-a-1)。最小移动次数似乎很直接，就是a与c直接一步移动到b的两侧，这种情况下值应该是2，但是有几种特殊场景：第一是a,b,c都相邻，那么值是0；第二种是a与b相邻或者b与c相邻，那么值为1；第三种是a与b的差值为2或者b与c的差值位2，这时可以直接那剩余那个元素一步移动到a与b或者b与c的直接的空位中。
https://blog.csdn.net/CSerwangjun/article/details/89643294
核心是对最小和最大step情况的判断
对于最小来说，步数范围是0～2，0的情况就是三个直接在一起，1的情况就是三个中有两个相邻，或者有两个之间的距离是1，可以把另一个直接插在中间。2的话就是不是上诉情况，要把两个石头分别移到中间石头的两边。
最大step就很简单了，固定的，因为石头只能在两个边界之间走，所以最大就是两个边界之间能走的都走完。因为就是一次一步步走嘛，并且边界的石头如果越过了中间那块石头，那他就从边界的石头变成了中间的石头，之后边界的石头还是得一步步走。意思就是不管什么走法，最大的走法他们都会把两个边界之间能走的地方走满，（想证明的直接用反证法，比这种情况的maxstep还大的意思就是有某个位置被走了1步以上，想想看有什么情况哪个位置才能走一步以上）。所以最大就是两个边界值相减减去2，减2是因为他们仨连在一起之后，移动的那俩还得占两个坑。
