作者enmeitiryous (enmeitiryous)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Fri Aug 2 11:19:25 2024
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;
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.238.8 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722568767.A.F5C.html
推 Smallsh: 大師 08/02 11:19
推 sustainer123: 大師 08/02 11:20