LeetCode 221場周賽題解
【GiantPandaCV導(dǎo)語】這是LeetCode的第221場周賽的題解，本期考察的知識點有模擬，貪心，優(yōu)先隊列，01Trie樹等。
比賽鏈接
https://leetcode-cn.com/contest/weekly-contest-221/
題目一：判斷字符串的兩半是否相似
解題思路：直接模擬即可。時間復(fù)雜度：O(s.length)解題代碼如下：
class?Solution?{
public:
????bool?yuan(char?c){
????????if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U')?return?1;
????????else?return?0;
????}
????bool?check(string?t1,?string?t2){
????????int?cnt1=0,?cnt2=0;
????????for(int?i=0;?i????????????if(yuan(t1[i]))?cnt1++;
????????}
????????for(int?i=0;?i????????????if(yuan(t2[i]))?cnt2++;
????????}
????????return?cnt1==cnt2;
????}
????bool?halvesAreAlike(string?s)?{
????????string?t1?=?"",?t2?=?"";
????????int?len?=?s.size();
????????for(int?i=0;?i????????????if(i2)?t1+=s[i];
????????????else?t2+=s[i];
????????}
????????bool?ans=check(t1,?t2);
????????return?ans;
????}
};
題目二：吃蘋果的最大數(shù)目
解題思路：這道題的核心思路是要每次優(yōu)先吃最早過期的蘋果。然后，我們用優(yōu)先隊列保存到當(dāng)前時間為止擁有的蘋果（蘋果有數(shù)量和過期時間兩個屬性），每次從優(yōu)先隊列里面取出最早過期的蘋果。
如果取到的蘋果已經(jīng)過期，即過期的時間小于等于當(dāng)前的天數(shù)，那么將其從優(yōu)先隊列中移除并繼續(xù)取。直到取到第一個可以吃的蘋果，并吃掉它，將它的數(shù)量減1，如果蘋果的數(shù)量不為0，則再次將其放入優(yōu)先隊列。
直到隊列為空，程序結(jié)束。
時間復(fù)雜度：O(nlogn)
解題代碼：
struct?node{
????//?cnt代表個數(shù)，idx代表過期時間
????int?cnt,?idx;
????node(){}
????node(int?cnt_,?int?idx_):cnt(cnt_),idx(idx_){}
????bool?operator<(const?node&?rhs)?const{
????????return?idx?>?rhs.idx;
????}
};
class?Solution?{
public:
????int?eatenApples(vector<int>&?apples,?vector<int>&?days)?{
????????int?n?=?apples.size();
????????int?ans?=?0;
????????priority_queue???pq;
????????int?i?=?0;
????????int?nn=n;???//定義可變右邊界
????????while(i????????????while(!pq.empty()?&&?pq.top().idx<=i){?//移除爛掉的蘋果
????????????????pq.pop();
????????????}
????????????if(i0){??//添加有效蘋果到優(yōu)先隊列里
????????????????pq.push(node(apples[i],i+days[i]));
????????????????nn=max(nn,i+days[i]+1);?//比較，獲得較大的右側(cè)邊界
????????????}
????????????if(!pq.empty()){
????????????????node?now=pq.top();??//拿出靠前的一堆蘋果，并吃掉一個
????????????????pq.pop();
????????????????now.cnt-=1;
????????????????ans++;
????????????????if(now.cnt>0){??//如果這堆沒吃完，再放回去
????????????????????pq.push(now);
????????????????}
????????????}
????????????i++;
????????}
????????return?ans;
????}
};
題目三：球會落在何處
解題思路：仔細(xì)觀察可以發(fā)現(xiàn)
如果在當(dāng)前格子中 為''，那么它右邊格子也應(yīng)該為''，小球才能移動到下一行。 如果在當(dāng)前格子中 為'/'，那么它右邊格子也應(yīng)該為'/'，小球才能移動到下一行。 其它情況均無法移動到最后一行。時間復(fù)雜度：O(n*m)
解題代碼如下：
class?Solution?{
public:
????vector<int>?ans;
????vector<int>?findBall(vector<vector<int>>&?grid)
????{
????????int?m?=?grid.size();
????????int?n?=?grid[0].size();
????????ans.resize(n);
????????//?初始化每一個小球的位置
????????for?(int?i?=?0;?i?????????????ans[i]?=?i;
????????}
????????for?(int?i?=?0;?i?//?計算小球?qū)⒊霈F(xiàn)在下一行的哪個位置
????????????for?(int?j?=?0;?j?//?計算每一列的每一個小球
????????????????if?(ans[j]?==?-1)?{?//?如果當(dāng)前列的小球已經(jīng)停止向下運動,?跳過
????????????????????continue;
????????????????}
????????????????int?now?=?ans[j];?//?得到小球在這一列的位置
????????????????//?根據(jù)輔助圖,?如果在當(dāng)前格子中?為'\'，那么它右邊格子也應(yīng)該為'\'，小球才能移動到下一行
????????????????if?(grid[i][now]?==?1?&&?now?1?&&?grid[i][now?+?1]?==?1)?{
????????????????????ans[j]?+=?1;
????????????????}?else?if?(grid[i][now]?==?-1?&&?now?>=?1?&&?grid[i][now?-?1]?==?-1)?{?//?如果在當(dāng)前格子中?為'/'，那么它右邊格子也應(yīng)該為'/'，小球才能移動到下一行
????????????????????ans[j]?-=?1;
????????????????}?else?{?//?其他情況都無法向下移動
????????????????????ans[j]?=?-1;
????????????????}
????????????}
????????}
????????return?ans;
????}
};
題目四：與數(shù)組中元素的最大異或值
解題思路：我們可以使用01字典樹來存儲數(shù)組中的所有元素。另外，由于每個查詢包含一個上界，因此我們可以在字典樹的每一個節(jié)點再維護一個以當(dāng)前節(jié)點為根節(jié)點的子樹的最小元素。它的作用是，如果當(dāng)前節(jié)點的子樹的最小元素大小都大于，我們就沒有必要繼續(xù)對這個子樹進行搜索了。
然后考慮每一次查詢，我們從高位到低位進行依次處理，實際上有以下兩種情況：
如果的當(dāng)前二進制位為1，那么我們應(yīng)該在Trie樹上優(yōu)先走位為0的分支；否則，我們需要嘗試走Trie樹上位為1的分支，如果分支不存在或者分支的最小元素已經(jīng)超過了，則本地查詢無解。 如果的當(dāng)前二進制位為0，那么我們應(yīng)該優(yōu)先走當(dāng)前位為1的分支，但要求這一分支的最小元素不超過；否則，我們繼續(xù)走當(dāng)前位為0的分支。
如果我們能順利走到了最低位，那么我們就獲得了這一查詢的最優(yōu)解。
時間復(fù)雜度：O(n+q*log(maxx))
空間復(fù)雜度：O(nlog(maxx)+q)
解題代碼如下：
struct?TrieNode?{
????int?minn?=?1e9;
????TrieNode*?children[2]{};
};
class?Solution?{
public:
????vector<int>?maximizeXor(vector<int>&?nums,?vector<vector<int>>&?queries)?{
????????TrieNode*?root?=?new?TrieNode();
????????for?(int?j?=?0;?j?????????????int?num?=?nums[j];
????????????TrieNode*?p?=?root;
????????????for?(int?i?=?30;?i?>=?0;?--i)?{
????????????????int?nxt?=?(num?&?(1?<1?:?0;
????????????????if?(!p->children[nxt])?p->children[nxt]?=?new?TrieNode();
????????????????p?=?p->children[nxt];
????????????????p->minn?=?min(p->minn,?num);
????????????}
????????}
????????vector<int>?ans;
????????for?(int?j?=?0;?j?????????????int?x?=?queries[j][0],?limit?=?queries[j][1];
????????????int?sum?=?0;
????????????TrieNode*?p?=?root;
????????????for?(int?i?=?30;?i?>=?0;?--i)?{
????????????????if?(x?&?(1?<????????????????????if?(p->children[0])?{
????????????????????????p?=?p->children[0];
????????????????????????sum?^=?(1?<????????????????????}?else?if?(!p->children[1]?||?(p->children[1]->minn?>?limit))?{
????????????????????????ans.push_back(-1);
????????????????????????break;
????????????????????}?else?{
????????????????????????p?=?p->children[1];
????????????????????}
????????????????}?else?{
????????????????????if?(p->children[1]?&&?(p->children[1]->minn?<=?limit))?{
????????????????????????p?=?p->children[1];
????????????????????????sum?^=?(1?<????????????????????}?else?if?(!p->children[0])?{
????????????????????????ans.push_back(-1);
????????????????????????break;
????????????????????}?else?{
????????????????????????p?=?p->children[0];
????????????????????}
????????????????}
????????????????if?(i?==?0)?ans.push_back(sum);
????????????}
????????}
????????return?ans;
????}
};
歡迎關(guān)注GiantPandaCV, 在這里你將看到獨家的深度學(xué)習(xí)分享，堅持原創(chuàng)，每天分享我們學(xué)習(xí)到的新鮮知識。( ? ?ω?? )?
有對文章相關(guān)的問題，或者想要加入交流群，歡迎添加BBuf微信：
為了方便讀者獲取資料以及我們公眾號的作者發(fā)布一些Github工程的更新，我們成立了一個QQ群，二維碼如下，感興趣可以加入。
評論
圖片
表情