資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
