2134. minimum swaps to group all 1 together II
要趕在開學前把75刷完了
題目:給你一個array nums,它是circular的(也就是nums[0] nums[n-1]實際是相連的)
其中nums[i]只會是0或著1，每一次operation我們可以把任一位置的0和1互換，求出最少
的swap數使的circualr array nums中的1全部group成一連續數列
思路:
由於swap可以是任一位置間互換，所以一個subsequence中0的數目就是需求的swap數
而這樣一個subsequence的最大長度就是其中1的數量總和，為了要滿足circular性質
實際操作可以在nums後接一個nums的duplicate掃過去紀錄其中含最少0的subseq的
0的數目。
int minSwaps(vector<int>& nums) {
int n=nums.size();
int temp=0;
int tol=0;
for(int i=0;i<n;++i){
tol+=nums[i];
nums.push_back(nums[i]);
}
int new_n=nums.size();
for(int i=0;i<tol;++i){
temp+=nums[i];
}
//return temp;
int ans=tol-temp;
for(int i=0;i<new_n-tol;++i){
temp-=nums[i];
temp+=nums[tol+i];
if(tol-temp<ans){
ans=tol-temp;
}
}
return ans;