数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的连续移动石头 II
假设我们正在考虑一条无限长的数轴，这里第 i 个石头的坐标由数组 stones 给出，stones[i] 表示第 i 个石头的坐标。如果一个石头是端点石头，则它具有最小或最大的坐标。现在，在每一轮中，我们拾取一个端点石头并将其移动到一个未占用的位置，以便它不再是端点石头。
如果石头位于例如 stones = [1,2,5]，我们不能移动坐标为 5 的端点石头，因为将其移动到任何位置（例如 0 或 3）都会使该石头保持为端点石头。
当我们无法再进行任何移动时，游戏将停止。因此，石头位于连续的位置。
这里我们必须找到游戏何时结束，那么我们可能进行的最小和最大移动次数是多少？将答案作为一对 [min_moves, max_moves] 返回。
例如，如果输入类似于 [7,3,9]，则结果将为 [1,3]
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为 2 的数组 ans
ans[0] := inf，ans[1] := -inf 且 n := a 的大小
对数组 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 执行以下操作：
curr := a[i]，lastPossible = a[i]
如果 lastPossible > a[n - 1]，则退出循环
spaceInBetween := false
如果 j <= i，则
j := i + 1
当 j < n 且 a[j] <= lastPossible，执行以下操作
如果 a[j] - a[j - 1]) > 1，则
spaceInBetween := true
如果 a[j] - a[j - 1]) > 1，则
将 j 加 1
idx := j - 1
如果 n - (idx - i + 1) > 1，则
spaceInBetween := true
ballLeft := i，ballRight := n - (idx + 1)
minVal := ballLeft + ballRight + (当 spaceInBetween 为 true 时为 0，否则为 1)
ans[0] := minVal 和 ans[0] 的最小值
ans[1] := a[n - 2] - a[0] 和 a[n - 1] - a[1]) - (n - 2) 的最大值，
返回 ans
从主方法调用 solve(stones)
示例
#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, ]
177 次浏览
