【GiantPandaCV導(dǎo)語(yǔ)】這是LeetCode的第42場(chǎng)雙周賽的題解，公眾號(hào)后面每周周末會(huì)以主條推文的方式更新當(dāng)前周的Leetcode比賽的解題報(bào)告，并整理成一個(gè)面試刷題專欄，有需要的讀者可以關(guān)注一下。另外，以前的比賽的解題報(bào)告我也會(huì)從當(dāng)前這個(gè)時(shí)間點(diǎn)往前補(bǔ)，原創(chuàng)的解題報(bào)告會(huì)盡量以次條的方式放在CV相關(guān)的推文下方，不影響目前公眾號(hào)的布局。本次周賽考察的知識(shí)點(diǎn)有：c++ stl，隊(duì)列，堆棧，模擬，找規(guī)律，數(shù)論，前綴和等。如果你只是關(guān)心面試，看前面三題就好，最后一題有億點(diǎn)難。

比賽鏈接

• https://leetcode-cn.com/contest/biweekly-contest-42/

題目一：無(wú)法吃午餐的學(xué)生數(shù)量

解題思路：數(shù)據(jù)范圍比較小，按照題意直接用c++ stl的deque和stack進(jìn)行模擬即可，當(dāng)隊(duì)列里面所有元素都和棧頂元素不存在喜歡關(guān)系就退出模擬過(guò)程。

時(shí)間復(fù)雜度：O(n)

解題代碼如下：

class?Solution?{
public:
????int?countStudents(vector<int>&?students,?vector<int>&?sandwiches)?{
????????deque?<int>?q;
????????stack?<int>?s;
????????int?len?=?students.size();
????????for(int?i=0;?i????????????q.push_back(students[i]);
????????}
????????for(int?i=len-1;?i>=0;?i--){
????????????s.push(sandwiches[i]);
????????}
????????int?ans?=?len;
????????int?cnt?=?0;
????????while(q.size()){
????????????int?x?=?q.front();
????????????q.pop_front();
????????????if(x?==?s.top()){
????????????????ans--;
????????????????s.pop();
????????????????cnt?=?0;
????????????}
????????????else{
????????????????q.push_back(x);
????????????????cnt++;
????????????????if(cnt>100)?break;
????????????}
????????}
????????return?ans;
????}
};

題目2：平均等待時(shí)間

解題思路：由于做菜順序是固定的，按照題意模擬即可，動(dòng)態(tài)維護(hù)一下做完上一道菜的截至?xí)r間。

時(shí)間復(fù)雜度：O(n)

解題代碼如下：

class?Solution?{
public:
????double?averageWaitingTime(vector<vector<int>>&?customers)?{
????????double?ans?=?0;
????????double?now?=?0;
????????for(int?i=0;?i????????????now?=?max(now,?(double)customers[i][0]);
????????????ans?=?ans?+?(now?+?customers[i][1]?-?customers[i][0]);
????????????now?=?now?+?customers[i][1];
????????}
????????ans?=?ans?/?customers.size();
????????return?ans;
????}
};

題目3：修改后的最大二進(jìn)制字符串

解題思路：看起來(lái)是一道比較復(fù)雜的題，實(shí)際上是個(gè)傻題。手推兩組數(shù)組容易發(fā)現(xiàn)，無(wú)論輸入是什么字符串最終都可以變成前面全0，后面全1的排列，并且把前面的全0使用操作1進(jìn)行替換能獲得最優(yōu)解。需要注意一下，前導(dǎo)1不需要處理，直接輸出即可。

時(shí)間復(fù)雜度：O(n)

解題代碼如下：

class?Solution?{
public:
????string?maximumBinaryString(string?binary)?{
????????int?len?=?binary.size();
????????string?s?=?binary;

????????int?cnt1?=?0,?cnt2?=?0;
????????int?pos?=?-1;
????????for(int?i=0;?i????????????if(s[i]=='0'){
????????????????pos?=?i-1;
????????????????break;
????????????}
????????}
????????for(int?i=pos+1;?i????????????if(s[i]=='0')?cnt1++;
????????????else?cnt2++;
????????}
????????string?t="";
????????for(int?i=0;?i<=pos;?i++)?t+='1';
????????for(int?i=0;?i'0';
????????for(int?i=0;?i'1';
????????for(int?i=0;?i-1;?i++){
????????????if(t[i]=='0'&&t[i+1]=='0'){
????????????????t[i]='1';
????????????}
????????}


????????return?t;
????}
};

題目4：得到連續(xù) K 個(gè) 1 的最少相鄰交換次數(shù)

解題思路：一個(gè)比較套路的題，比賽時(shí)沒(méi)有做出來(lái)，看賽后題解學(xué)會(huì)了，下面分享一下做法。

根據(jù)題意知道，我們需要：

• 找到數(shù)組中個(gè)連續(xù)的1。
• 找到數(shù)組中個(gè)連續(xù)的位置。

然后將數(shù)組中個(gè)連續(xù)的1放到對(duì)應(yīng)的位置中，為什么這樣做沒(méi)有問(wèn)題呢？想象不按照順序放入個(gè)位置，也就是存在交叉的情況，交換次數(shù)只會(huì)更多。

然后假設(shè)的位置在，然后放入的位置為，那么題意就轉(zhuǎn)換成求下式的最小值：

然后我們?cè)O(shè)，那么上式等價(jià)于：

那么這個(gè)式子在何時(shí)取得最小值呢？顯然當(dāng)為的中位數(shù)時(shí)，上式可以取得最小值。

所以，我們首先記錄一下原數(shù)組中所有1的位置，用來(lái)表示，然后再令。然后我們就可以用一個(gè)長(zhǎng)度為的滑動(dòng)窗口在上實(shí)時(shí)滑動(dòng)并更新和計(jì)算答案了。

最后一個(gè)關(guān)鍵的點(diǎn)就是交換次數(shù)如何計(jì)算，假設(shè)當(dāng)前我們的滑動(dòng)窗口包含，中位數(shù)自然等于。那么此時(shí)交換次數(shù)計(jì)算推導(dǎo)如下：

其中后面的求和項(xiàng)可以通過(guò)提前維護(hù)一個(gè)前綴和來(lái)O(1)計(jì)算。

時(shí)間復(fù)雜度：O(n)

解題代碼：

class?Solution?{
public:
????int?minMoves(vector<int>&?nums,?int?k)?{
????????if?(k?==?1)?{
????????????return?0;
????????}
????????
????????int?n?=?nums.size();
????????vector<int>?g;
????????vector<int>?sum?=?{0};
????????int?cnt?=?0;
????????for?(int?i?=?0;?i?????????????if?(nums[i]?==?1)?{
????????????????g.push_back(i?-?cnt);
????????????????sum.push_back(sum.back()?+?g.back());
????????????????cnt?+=?1;
????????????}
????????}
????????
????????int?m?=?g.size();
????????int?ans?=?INT_MAX;
????????for?(int?i?=?0;?i?+?k?<=?m;?++i)?{
????????????int?mid?=?(i?+?i?+?k?-?1)?/?2;
????????????int?q?=?g[mid];
????????????ans?=?min(ans,?(2?*?(mid?-?i)?-?k?+?1)?*?q?+?(sum[i?+?k]?-?sum[mid?+?1])?-?(sum[mid]?-?sum[i]));
????????}
????????
????????return?ans;
????}
};

參考：

https://leetcode-cn.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solution/de-dao-lian-xu-k-ge-1-de-zui-shao-xiang-lpa9i/

歡迎關(guān)注GiantPandaCV, 在這里你將看到獨(dú)家的深度學(xué)習(xí)分享，堅(jiān)持原創(chuàng)，每天分享我們學(xué)習(xí)到的新鮮知識(shí)。( ? ?ω?? )?

有對(duì)文章相關(guān)的問(wèn)題，或者想要加入交流群，歡迎添加BBuf微信：

為了方便讀者獲取資料以及我們公眾號(hào)的作者發(fā)布一些Github工程的更新，我們成立了一個(gè)QQ群，二維碼如下，感興趣可以加入。