1033 Moving Stones Until Consecutive 移動(dòng)石子直到連續(xù)
Description:
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:
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 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a
題目描述:
三枚石子放置在數(shù)軸上，位置分別為 a，b，c。
每一回合，我們假設(shè)這三枚石子當(dāng)前分別位于位置 x, y, z 且 x < y < z。從位置 x 或者是位置 z 拿起一枚石子，并將該石子移動(dòng)到某一整數(shù)位置 k 處，其中 x < k < z 且 k != y。
當(dāng)你無法進(jìn)行任何移動(dòng)時(shí)，即，這些石子的位置連續(xù)時(shí)，游戲結(jié)束。
要使游戲結(jié)束，你可以執(zhí)行的最小和最大移動(dòng)次數(shù)分別是多少？ 以長(zhǎng)度為 2 的數(shù)組形式返回答案：answer = [minimum_moves, maximum_moves]
示例 :
示例 1：
輸入：a = 1, b = 2, c = 5
輸出：[1, 2]
解釋：將石子從 5 移動(dòng)到 4 再移動(dòng)到 3，或者我們可以直接將石子移動(dòng)到 3。
示例 2：
輸入：a = 4, b = 3, c = 2
輸出：[0, 0]
解釋：我們無法進(jìn)行任何移動(dòng)。
提示：
1 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a
思路:
先按大小順序排序a, b, c, 如果三個(gè)數(shù)連續(xù), 不需要移動(dòng), 輸出{0, 0}; 如果相鄰兩個(gè)數(shù)相差為 1或者 2, 則將第三個(gè)數(shù)放在后面或者插入中間, 輸出{1, max - min + 2}; 否則輸出{2, max - min + 2}, max - min + 2表示最大和最小值中間的間隔值
時(shí)間復(fù)雜度O(1), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
vector<int> numMovesStones(int a, int b, int c)
{
int x = min(min(a, b), c), z = max(max(a, b), c);
int y = a + b + c - x - z;
if (y - x == 1 && z - y == 1) return {0, 0};
else if (y - x < 3 || z - y < 3) return {1, z - x - 2};
else return {2, z - x - 2};
}
};
Java:
class Solution {
public int[] numMovesStones(int a, int b, int c) {
int x = Math.min(Math.min(a, b), c), z = Math.max(Math.max(a, b), c);
int y = a + b + c - x - z;
if (y - x == 1 && z - y == 1) return new int[]{0, 0};
else if (y - x < 3 || z - y < 3) return new int[]{1, z - x - 2};
else return new int[]{2, z - x - 2};
}
}
Python:
class Solution:
def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
return [1 if ((a + b + c - max(a, b, c) - min(a, b, c) * 2 == 2) or (2 * max(a, b, c) - a - b - c + min(a, b, c) == 2)) else (a + b + c - max(a, b, c) - min(a, b, c) * 2 != 1) + (2 * max(a, b, c) - a - b - c + min(a, b, c) != 1), max(a, b, c) - min(a, b, c) - 2]
