LeetCode 226場(chǎng)周賽題解
?【GiantPandaCV導(dǎo)語(yǔ)】這是LeetCode第226場(chǎng)周賽題解，本周考察的知識(shí)點(diǎn)有枚舉，貪心，前綴和，Manacher回文算法，動(dòng)態(tài)規(guī)劃，圖論等。
?
比賽鏈接
https://leetcode-cn.com/contest/weekly-contest-226/ 最終Rank：231 / 4033。
題目一：盒子中小球的最大數(shù)量
解題思路：按照題意模擬一下即可。 時(shí)間復(fù)雜度： 空間復(fù)雜度： 解題代碼如下：
class?Solution?{
public:
????int?a[100];
????int?f(int?x){
????????int?ans=0;
????????while(x){
????????????ans+=x%10;
????????????x/=10;
????????}
????????return?ans;
????}
????int?countBalls(int?lowLimit,?int?highLimit)?{
????????int?ans=0;
????????for(int?i=lowLimit;?i<=highLimit;?i++){
????????????a[f(i)]++;
????????}
????????for(int?i=1;?i<100;?i++){
????????????if(a[i]>ans){
????????????????ans=a[i];
????????????}
????????}
????????return?ans;
????}
};
題目二：從相鄰元素對(duì)還原數(shù)組
解題思路：看了一分鐘似乎沒(méi)有思路？然后再想想我們會(huì)發(fā)現(xiàn)如果把這個(gè)相鄰關(guān)系看成一個(gè)無(wú)向圖的邊這個(gè)圖會(huì)是什么樣子？其實(shí)這個(gè)圖會(huì)退化成一條鏈，我們只需要找到這個(gè)鏈的頭部或者尾部節(jié)點(diǎn)就可以一下把這個(gè)鏈拎起來(lái)，然后我們就獲得了答案了。頭部節(jié)點(diǎn)或者尾部節(jié)點(diǎn)怎么找？直接找入度或者出度為0的點(diǎn)就可以了。另外注意一下，圖中節(jié)點(diǎn)可能是負(fù)數(shù)，所以需要加一個(gè)offset（我直接取了100000）來(lái)方便處理。 時(shí)間復(fù)雜度： 空間復(fù)雜度： 解題代碼如下：
class?Solution?{
public:
????int?cnt[200010];
????vector?<int>?G[200010];
????vector?<int>?ans;
????void?dfs(int?root,?int?fa){
????????ans.push_back(root-100000);
????????for(int?i=0;?i????????????int?v?=?G[root][i];
????????????if(v?==?fa)?continue;
????????????dfs(v,?root);
????????}
????}
????vector<int>?restoreArray(vector<vector<int>>&?adjacentPairs)?{
????????int?n?=?adjacentPairs.size();
????????for(int?i=0;?i????????????int?u?=?adjacentPairs[i][0];
????????????int?v?=?adjacentPairs[i][1];
????????????u?+=?100000;
????????????v?+=?100000;
????????????G[u].push_back(v);
????????????G[v].push_back(u);
????????????cnt[v]++;
????????????cnt[u]++;
????????}
????????int?id?=?0;
????????for(int?i=0;?i<200010;?i++){
????????????if(cnt[i]==1){
????????????????id?=?i;
????????????????break;
????????????}
????????}
????????ans.clear();
????????dfs(id,?-1);
????????return?ans;
????}
};
題目三：你能在你最喜歡的那天吃到你最喜歡的糖果嗎？
解題思路：其實(shí)是一個(gè)非常簡(jiǎn)單的題目，只要推一下第一組樣例應(yīng)該就差不多了。對(duì)于每一個(gè)查詢，我們可以O(shè)(1)判斷是否可以在第 favoriteDayi天吃到favoriteTypei類糖果。具體怎么判斷呢？我們可以看到由于第二個(gè)條件的限制，在吃第類糖果的時(shí)候，那么類一定被吃掉了，那么我們可以i對(duì)所有的糖果維護(hù)一個(gè)前綴和。然后我們反向思考什么情況下這個(gè)人在第天是吃不到favoriteTypei類蘋果的：一種情況就是這個(gè)人每天都吃了 dailyCapi（上限）這么多個(gè)蘋果，但是還是不夠數(shù)，也就是說(shuō)favoriteTypei類之前的蘋果還有剩余。另外一種情況就是這個(gè)人每天只吃一個(gè)蘋果，但是到 favoriteDayi天吃的蘋果數(shù)量（也就是天數(shù)）都已經(jīng)超過(guò)了favoriteTypei前所有的蘋果數(shù)量，這樣也是不行的。時(shí)間復(fù)雜度： 空間復(fù)雜度： 解題代碼如下：
class?Solution?{
public:
????int?n;
????long?long?sum[100010];
????bool?check(long?long?type,?long?long?day,?long?long?cap){
????????if(sum[type-1]>=(long?long)(cap*day))?return?false;
????????if(day>sum[type])?return?false;
????????return?true;
????}
????vector<bool>?canEat(vector<int>&?candiesCount,?vector<vector<int>>&?queries)?{
????????n?=?candiesCount.size();
????????for(int?i=1;?i<=n;?i++){
????????????sum[i]=sum[i-1]+candiesCount[i-1];
????????}
????????vector<bool>ans;
????????for(int?i=0;?i????????????long?long?type?=?queries[i][0];
????????????long?long?day?=?queries[i][1];
????????????long?long?cap?=?queries[i][2];
????????????type++;
????????????day++;
????????????if(check(type,?day,?cap)){
????????????????ans.push_back(true);
????????????}
????????????else{
????????????????ans.push_back(false);
????????????}
????????}
????????return?ans;
????}
};
題目四：回文串分割 IV
解題思路：這道題其實(shí)有兩種解法，一種是適合本地2e3的數(shù)據(jù)范圍，一種是適合2e4的數(shù)據(jù)范圍，接下來(lái)我就講一下這兩種做法。
解題方法一：O(n^2) DP
解題思路：這是針對(duì)本題的數(shù)據(jù)范圍的一種解法，我們?cè)O(shè) dp[i][j]表示字符串中的這一段字串是否是回文串，我們可以從后往前枚舉字串的起點(diǎn)進(jìn)行DP方程狀態(tài)的更新。維護(hù)完這個(gè)數(shù)組之后我們就可以枚舉第一個(gè)子段的終點(diǎn)和第二個(gè)子段的起點(diǎn)來(lái)判斷獲得最終答案了。時(shí)間復(fù)雜度： 空間復(fù)雜度： 解題代碼：
class?Solution
{
public:
?bool?checkPartitioning(string?s)
?{
??int?n?=?s.length();
??vector<vector<bool>>?p(n,?vector<bool>(n));
??for?(int?i?=?n?-?1;?i?>=?0;?--i)?{
???p[i][i]?=?true;
???for?(int?j?=?i?+?1;?j?????if?(s[i]?==?s[j])?{
?????p[i][j]?=?(i?+?1?==?j?||?p[i?+?1][j?-?1]);
????}
???}
??}
??for?(int?i?=?0;?i????if?(p[0][i])?{
????for?(int?j?=?i?+?1;?j?1;?++j)?{
?????if?(p[i?+?1][j]?&&?p[j?+?1][n?-?1])?{
??????return?true;
?????}
????}
???}
??}
??return?false;
?}
};
解題方法二：枚舉+Manacher
解題思路：先用Manacher算法得到以每個(gè)點(diǎn)為中心的最大回文串的左右邊界 le[i]、ri[i]。并且當(dāng)le[i]==1（即該回文串向左可以到達(dá)字符串的邊界）時(shí)，記錄下來(lái)，le1[ri[i]]=1，表示存在一個(gè)回文串左邊界為1，右邊界為ri[i]。同理，當(dāng)ri[i]==n-1（字符串右邊界）時(shí)，ri1[le[i]]=1。然后遍歷中間的回文串的回文中心，令t1=p[i]-1（回文串長(zhǎng)度），t2=le[i]（回文串左邊界），t3=ri[i]（回文串右邊界），當(dāng)le1[t2]==1&&ri1[t3]==1時(shí)即找到了方案。如果不滿足，t1-=2，t2+=2，t3-=2，繼續(xù)判斷，直到t1<=0。要注意的是當(dāng)t2==1或者t3==n-1時(shí)該回文串不能作為中間回文串。關(guān)于Manacher算法不了解的讀者請(qǐng)看：https://oi-wiki.org/string/manacher/時(shí)間復(fù)雜度： 空間復(fù)雜度： 解題代碼：
const?int?maxn=2e3+5;
int?T,n,ans,p[maxn<<1],le[maxn<<1],ri[maxn<<1];
int?le1[maxn<<1],ri1[maxn<<1];
char?s[maxn<<1],ss[maxn];
void?manacher(){
????int?mid=0,r=0;
????for(int?i=1;i????????if(r>=i)?p[i]=min(p[(mid<<1)-i],r-i+1);
????????while(s[i-p[i]]==s[i+p[i]])?++p[i];
????????if(i+p[i]>r)?r=i+p[i]-1,mid=i;
????????int?tmp=p[i]-1;
????????le[i]=i-tmp,ri[i]=i+tmp;
????????if(le[i]==1)?le1[ri[i]]=1;
????????if(ri[i]==n-1)?ri1[le[i]]=1;
????}
}
class?Solution?{
public:
????bool?checkPartitioning(string?s2)?{
????????ans?=?0;
????????n?=?s2.size();
????????for(int?i=0;?i????????
????????s[0]='~',s[1]='|';
????????for(int?i=0;i????????????s[2*i+2]=ss[i],s[2*i+3]='|';
????????n=2*n+2;
????????for(int?i=0;i????????????p[i]=0,le1[i]=0,ri1[i]=0;
????????manacher();
????????for(int?i=1;i????????????int?t1=p[i]-1,t2=le[i],t3=ri[i];
????????????if(t2==1||t3==n-1){
????????????????t1-=2;
????????????????t2+=2;
????????????????t3-=2;
????????????}
????????????while(t1>0){
????????????????if(le1[t2]&&ri1[t3]){
????????????????????ans=1;
????????????????????break;
????????????????}
????????????????t1-=2;
????????????????t2+=2;
????????????????t3-=2;
????????????}
????????????if(ans)?break;
????????}
????????if(ans)?return?true;
????????else?return?false;
????}
};
來(lái)看一下兩種解法在評(píng)測(cè)機(jī)上的耗時(shí)情況：
歡迎關(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群，二維碼如下，感興趣可以加入。
評(píng)論
圖片
表情