1. 移动石子直到连续(三个石子)
class Solution {
public:
vector<int> numMovesStones(int a, int b, int c) {
int x = min({a, b, c});
int z = max({a, b, c});
int y = a + b + c - x - z;
vector<int> res(2);
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);
return res;
}
};
2. 移动石子直到连续II(无数石子)
模拟找数学规律
class Solution {
public:
vector<int> numMovesStonesII(vector<int>& stones) {
sort(stones.begin(),stones.end());
int n = stones.size();
int mi = n;
int ma = INT_MIN;
if (stones.back() - stones[0] + 1 == n) //n个连续石头
return {0, 0};
//任取一端进行初始移动的最大值，直接用max，不必讨论
ma = max(stones[n - 2] - stones[0] + 1, stones[n - 1] - stones[1] + 1) - (n - 1);
//最小值需要讨论，双指针
for(int i = 0, j = 0; i < n && j + 1 < n; ++i) {
//移动后面指针，保证两指针距离在n之间
while (j + 1 < n && stones[j + 1] - stones[i] + 1 <= n)
++j;
if (j - i + 1 == n - 1 && stones[j] - stones[i] + 1 == n - 1)
mi = min(mi, 2);
else mi = min(mi, n - (j - i + 1));
}
return {mi, ma};
}
};