用C ++移动石头直到连续II
假设我们正在考虑一个无限数线，则第i个石头的位置由数组石头给出，而结石[i]表示第i个石头的位置。如果石头的位置最小或最大，则它是终点石头。现在，在每个回合中，我们拾起终点石并将其移至空位，以使其不再是终点石。
如果结石在说，结石=[1,2,5]，则我们无法将终点结石移动到位置5，因为将其移动到任何位置（例如0或3）仍将其作为终点结石。
当我们无法再移动时，该游戏将停止。因此，宝石处于连续位置。
在这里我们必须找到游戏何时结束，那么我们本可以进行的最小和最大移动次数是多少？成对找到答案[min_moves，max_moves]
例如，如果输入类似于[7,3,9]，则结果将为[1,3]
为了解决这个问题，我们将遵循以下步骤-
定义大小为2的数组
ans[0]：=inf，ans[1]：=-inf和n：=a的大小
对数组进行排序
x：=1
而x<n且a[x]＆a[x−1]与1相同，则-
x增加1
如果x与n相同，则
返回一对{0,0}
minVal：=0，j：=1
用于初始化i：=0，当i<a.size（时，将i增加1做-
spaceInBetween：=true
如果a[j]-a[j-1]）>1，则，
如果a[j]-a[j-1]）>1，则，
将j增加1
spaceInBetween：=true
j：=i+1
curr：=a[i]，lastPossible=a[i]
如果lastPossible>a[n-1]，则从循环中出来
spaceInBetween：=假
如果j<=i，那么，
当j<n和a[j]<=lastPossible时，执行以下操作：
idx：=j-1
如果n-（idx-i+1）>1，则，
ballLeft：=i，ballRight：=n-（idx+1）
minVal：=ballLeft+ballRight+（当spaceInBetween为true时为0，否则为1）
ans[0]：=minValansans[0]的最小值
ans[1]：=a[n-2]-a[0]和a[n-1]-a[1]）-(n-2)的最大值，
返回ans
从主要方法调用solve（石头）
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> solve(vector<int> a) {
vector <int> ans(2);
ans[0] = INT_MAX;
ans[1] = INT_MIN;
int n = a.size();
sort(a.begin(), a.end());
int x = 1;
while(x < n && a[x] - a[x - 1] == 1)
x ++;
if(x == n){
return {0,0};
}
int minVal = 0;
int j = 1;
for(int i = 0; i < a.size(); i++){
int curr = a[i];
int lastPossible = a[i] + n - 1;
if(lastPossible > a[n - 1])
break;
bool spaceInBetween = false;
if(j <= i)
j = i + 1;
while(j < n && a[j] <= lastPossible){
if((a[j] - a[j - 1]) > 1) {
spaceInBetween = true;
}
j++;
}
int idx = j - 1;
if(n - (idx - i + 1) > 1)
spaceInBetween = true;
int ballLeft = i;
int ballRight = n - (idx + 1);
minVal = ballLeft + ballRight + (spaceInBetween? 0 : 1);
ans[0] = min(minVal, ans[0]);
}
ans[1] = max(a[n - 2] - a[0], a[n - 1] - a[1]) - (n -2);
return ans;
}
vector<int> numMovesStonesII(vector<int>& stones) {
return solve(stones);
}
};
main(){
Solution ob;
vector<int> v1 = {7,3,9};
print_vector(ob.numMovesStonesII(v1));
}输入值
[7,3,9]
输出结果
[1, 3, ]