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