【GiantPandaCV導(dǎo)語】這是LeetCode的第224場周賽的題解，本期考察的知識點(diǎn)有暴力，排序，記憶化搜索等等。

比賽鏈接

• https://leetcode-cn.com/contest/weekly-contest-224/

題目一：可以形成最大正方形的矩形數(shù)目

解題思路：直接暴力枚舉每個正方形，然后保存下最大的邊長，維護(hù)一下最大邊長的個數(shù)即可。時間復(fù)雜度：解題代碼如下：

class?Solution?{
public:
????int?countGoodRectangles(vector<vector<int>>&?rectangles)?{
????????int?max_len=0,cnt=0;
????????for(int?i=0;i????????{
????????????int?minlr=min(rectangles[i][0],rectangles[i][1]);
????????????if(minlr==max_len)
????????????????cnt++;
????????????else?if(minlr>max_len)
????????????{
????????????????cnt=1;
????????????????max_len=minlr;
????????????}
????????}
????????return?cnt;
????????
????}
};

題目二：同積元組

題面

解題思路：題目給出了不同正整數(shù)組成的數(shù)組，要求計算a*b=c*d的個數(shù)，首先想到的是對所有a*b的結(jié)果進(jìn)行統(tǒng)計，由于數(shù)組中不存在相同的數(shù)，那么就可以直接對統(tǒng)計的結(jié)果進(jìn)行計算即可，由于數(shù)的范圍是1e4，這里采用map。時間復(fù)雜度：解題代碼如下：

class?Solution?{
public:
????int?tupleSameProduct(vector<int>&?nums)?{
????????map<int,int>?mp;
????????for(int?i=0;i????????????for(int?j=i+1;j????????????????mp[nums[i]*nums[j]]++;
????????int?ans=0;
????????for(auto?it=mp.begin();it!=mp.end();it++)
????????{
????????????int?cnt?=it->second;
????????????ans?+=?(cnt)*(cnt-1)/2*8;
????????}
????????return?ans;
????}
};

題目三：重新排列后的最大子矩陣

解題思路：題目給出一個01矩陣，可以將矩陣的列任意排列，求最大子矩陣的面積；我們可以先將每個點(diǎn)向下最長1的長度維護(hù)出來，然后對于每一行，將該行的每個最長的長度進(jìn)行排序，遍歷一遍這個排序后的向下高度，即可求出來以這行點(diǎn)為矩形左上起點(diǎn)的最大面積時間復(fù)雜度：解題代碼如下：

class?Solution?{
public:
????int?largestSubmatrix(vector<vector<int>>&?matrix)?{
????????int?n=matrix.size(),m=matrix[0].size();
????????vector<vector<int>>?dp(n,?vector<int>(m,?0));
????????for(int?j=0;j????????{
????????????for(int?i=n-1;i>=0;i--)
????????????{
????????????????if(matrix[i][j]==0)
????????????????????dp[i][j]=0;
????????????????else
????????????????{
????????????????????if(i==n-1)
????????????????????????dp[i][j]=1;
????????????????????else
????????????????????????dp[i][j]=?1?+dp[i+1][j];
????????????????}
????????????}
????????}
????????int?ans=0;
????????for(int?i=0;i????????{
????????????vector<int>?tmp;
????????????for(int?j=0;j????????????????tmp.push_back(dp[i][j]);
????????????sort(tmp.rbegin(),tmp.rend());
????????????for(int?j=0;j????????????????ans=max(ans,tmp[j]*(j+1));
????????}
????????return?ans;
????}
};

題目四：貓和老鼠 II

解題思路：給出一個矩陣問貓和老鼠誰獲勝，由于矩陣大小最大只有8*8，那么直接記憶化搜索即可，令dp[who][Mi][Mj][Ci][Cj][step]表示who在(鼠在Mi Mj，貓在Ci Cj)這個狀態(tài)下走了step步時，是否存在必勝狀態(tài)，如果為0表示還沒有搜到，如果為1表示who在該狀態(tài)下存在必勝策略，如果為-1表示必敗。初始化為必敗，然后不停的存在是否存在必勝策略。

1.如果who等于老鼠，必勝態(tài)為下一步能走到食物或者下一步走到的狀態(tài)為必勝態(tài)。

2.如果who等于貓，那么貓的必勝狀態(tài)為下一步走到食物或者下一步遇到老鼠或者下一步超過限制步數(shù)或者下一步為必勝態(tài)。

注意這樣直接搜索可能會超時就有一些優(yōu)化手段，首先是dp中的第一維who是兩維，分別表示貓和老鼠，其實(shí)這一維可以去掉，用step%2表示即可，第二由于老鼠和貓都可以原地移動，那么對于某些圖假設(shè)貓和老鼠都只能原地移動，其實(shí)這種圖貓是必勝的，也就是說有些圖可以剪枝，這里直接將步數(shù)限制在200步也可以通過。

時間復(fù)雜度：解題代碼如下：

class?Solution?{
public:
???mapvector<string>,int>,int>?mmp;
????int?C,M,dir[4][2]=?{-1,0,0,-1,1,0,0,1},n,m;
????int?dp[8][8][8][8][205];
????void?dfs(vector<string>?&grid,int?step,int?Mi,int?Mj,int?Ci,int?Cj)
????{
????????int?who=?step%2;
????????if(step>=200)??//步數(shù)超過200則直接判斷
????????{
????????????if(who==0)???//如果當(dāng)前是老鼠，則直接失敗
????????????????dp[Mi][Mj][Ci][Cj][step]=-1;
????????????else?????????//如果當(dāng)前是貓，則直接勝利
????????????????dp[Mi][Mj][Ci][Cj][step]=1;
????????????return?;
????????}
????????dp[Mi][Mj][Ci][Cj][step]=-1;??//初始化為失敗，去尋找是否存在必勝策略
????????if(who==0)????????????????????//who==0表示當(dāng)前是老鼠
????????{
????????????for(int?i=0;?i<4;?i++)
????????????{
????????????????for(int?k=0;?k<=M;?k++)
????????????????{
????????????????????int?di=?Mi?+dir[i][0]*k;
????????????????????int?dj=?Mj?+dir[i][1]*k;
????????????????????if(di>=0&&di=0&&dj????????????????????{
????????????????????????if(grid[di][dj]=='#')???//不能越過墻
????????????????????????????break;
????????????????????????if(grid[di][dj]=='C')??
????????????????????????????continue;
????????????????????????else?if(grid[di][dj]=='F')??//如果是食物，則必勝，直接返回
????????????????????????{
????????????????????????????dp[Mi][Mj][Ci][Cj][step]=1;
????????????????????????????return?;
????????????????????????}
????????????????????????else??????????????????????//否則嘗試走一步，判斷下一步貓是否必敗
????????????????????????{
????????????????????????????swap(grid[Mi][Mj],grid[di][dj]);
????????????????????????????if(dp[di][dj][Ci][Cj][step+1]==0)
????????????????????????????????dfs(grid,step+1,di,dj,Ci,Cj);
????????????????????????????swap(grid[Mi][Mj],grid[di][dj]);
????????????????????????????if(dp[di][dj][Ci][Cj][step+1]==-1)??//如果下一步貓必敗，則
????????????????????????????{??????????????????????????????????//當(dāng)前必勝
????????????????????????????????dp[Mi][Mj][Ci][Cj][step]=1;
????????????????????????????????return?;
????????????????????????????}
????????????????????????}
????????????????????}
????????????????}
????????????}
????????}
????????else
????????{
????????????for(int?i=0;?i<4;?i++)
????????????{
????????????????for(int?k=0;?k<=C;?k++)
????????????????{
????????????????????int?di=?Ci?+?dir[i][0]*k;
????????????????????int?dj=?Cj?+?dir[i][1]*k;
????????????????????if(di>=0&&di=0&&dj????????????????????{
????????????????????????if(grid[di][dj]=='#')
????????????????????????????break;
????????????????????????if(grid[di][dj]=='M'||grid[di][dj]=='F')??//貓抓到老鼠或者食物
????????????????????????{
????????????????????????????dp[Mi][Mj][Ci][Cj][step]=1;
????????????????????????????return?;
????????????????????????}
????????????????????????else
????????????????????????{
????????????????????????????swap(grid[Ci][Cj],grid[di][dj]);
????????????????????????????if(dp[Mi][Mj][di][dj][step+1]==0)??//同理
????????????????????????????????dfs(grid,step+1,Mi,Mj,di,dj);
????????????????????????????swap(grid[Ci][Cj],grid[di][dj]);
????????????????????????????if(dp[Mi][Mj][di][dj][step+1]==-1)
????????????????????????????{
????????????????????????????????dp[Mi][Mj][Ci][Cj][step]=1;
????????????????????????????????return?;
????????????????????????????}
????????????????????????}
????????????????????}
????????????????}
????????????}
????????}
????}
????bool?canMouseWin(vector<string>&?grid,?int?catJump,?int?mouseJump)?{
????????????C=catJump,M=mouseJump;
????????????n=grid.size(),m=grid[0].size();
????????????int?CI,CJ,MI,MJ;
????????????memset(dp,0,sizeof(dp));
????????????for(int?i=0;?i????????????????for(int?j=0;?j????????????????{
????????????????????if(grid[i][j]=='C')
????????????????????????CI=i,CJ=j;
????????????????????if(grid[i][j]=='M')
????????????????????????MI=i,MJ=j;
????????????????}
????????????dfs(grid,0,MI,MJ,CI,CJ);
????????????if(dp[MI][MJ][CI][CJ][0]==1)
????????????????return?true;
????????????return?false;
????????}
};

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

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

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