Re: [閒聊] 每日leetcode
看板Marginalman作者enmeitiryous (enmeitiryous)時間1年前 (2024/08/02 11:19)推噓3(3推 0噓 1→)留言4則, 4人參與討論串616/1554 (看更多)
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
推
08/02 11:19,
1年前
, 1F
08/02 11:19, 1F
推
08/02 11:20,
1年前
, 2F
08/02 11:20, 2F
推
08/02 14:56,
1年前
, 3F
08/02 14:56, 3F
→
08/02 23:26,
1年前
, 4F
08/02 23:26, 4F
討論串 (同標題文章)
完整討論串 (本文為第 616 之 1554 篇)：