?

【GiantPandaCV導(dǎo)語】這是LeetCode第226場周賽題解，本周考察的知識點有枚舉，貪心，前綴和，Manacher回文算法，動態(tài)規(guī)劃，圖論等。

?

比賽鏈接

• https://leetcode-cn.com/contest/weekly-contest-226/
• 最終Rank：231 / 4033。

題目一：盒子中小球的最大數(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;
????}
};

題目二：從相鄰元素對還原數(shù)組

• 解題思路：看了一分鐘似乎沒有思路？然后再想想我們會發(fā)現(xiàn)如果把這個相鄰關(guān)系看成一個無向圖的邊這個圖會是什么樣子？其實這個圖會退化成一條鏈，我們只需要找到這個鏈的頭部或者尾部節(jié)點就可以一下把這個鏈拎起來，然后我們就獲得了答案了。頭部節(jié)點或者尾部節(jié)點怎么找？直接找入度或者出度為0的點就可以了。另外注意一下，圖中節(jié)點可能是負數(shù)，所以需要加一個offset（我直接取了100000）來方便處理。
• 時間復(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;
????}
};

題目三：你能在你最喜歡的那天吃到你最喜歡的糖果嗎？

• 解題思路：其實是一個非常簡單的題目，只要推一下第一組樣例應(yīng)該就差不多了。對于每一個查詢，我們可以O(shè)(1)判斷是否可以在第favoriteDayi天吃到favoriteTypei類糖果。具體怎么判斷呢？我們可以看到由于第二個條件的限制，在吃第類糖果的時候，那么類一定被吃掉了，那么我們可以i對所有的糖果維護一個前綴和。然后我們反向思考什么情況下這個人在第天是吃不到favoriteTypei類蘋果的：
• 一種情況就是這個人每天都吃了dailyCapi（上限）這么多個蘋果，但是還是不夠數(shù)，也就是說favoriteTypei類之前的蘋果還有剩余。
• 另外一種情況就是這個人每天只吃一個蘋果，但是到favoriteDayi天吃的蘋果數(shù)量（也就是天數(shù)）都已經(jīng)超過了favoriteTypei前所有的蘋果數(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

• 解題思路：這道題其實有兩種解法，一種是適合本地2e3的數(shù)據(jù)范圍，一種是適合2e4的數(shù)據(jù)范圍，接下來我就講一下這兩種做法。

解題方法一：O(n^2) DP

• 解題思路：這是針對本題的數(shù)據(jù)范圍的一種解法，我們設(shè)dp[i][j]表示字符串中的這一段字串是否是回文串，我們可以從后往前枚舉字串的起點進行DP方程狀態(tà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算法得到以每個點為中心的最大回文串的左右邊界le[i]、ri[i]。并且當(dāng)le[i]==1（即該回文串向左可以到達字符串的邊界）時，記錄下來，le1[ri[i]]=1，表示存在一個回文串左邊界為1，右邊界為ri[i]。同理，當(dāng)ri[i]==n-1（字符串右邊界）時，ri1[le[i]]=1。然后遍歷中間的回文串的回文中心，令t1=p[i]-1（回文串長度），t2=le[i]（回文串左邊界），t3=ri[i]（回文串右邊界），當(dāng)le1[t2]==1&&ri1[t3]==1時即找到了方案。如果不滿足，t1-=2，t2+=2，t3-=2，繼續(xù)判斷，直到t1<=0。要注意的是當(dāng)t2==1或者t3==n-1時該回文串不能作為中間回文串。關(guān)于Manacher算法不了解的讀者請看：https://oi-wiki.org/string/manacher/
• 時間復(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;
????}
};

來看一下兩種解法在評測機上的耗時情況：

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

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

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