🦄個人主頁:修修修也

🎏所屬專欄:刷題

??操作環境:牛客網

---

一.OR26 最長回文子串

牛客網題目鏈接(點擊即可跳轉):OR26 最長回文子串

題目詳情:

本題詳情如下圖:

---

題目思路:

本題解題思路如下:

??????? 本題思路用中心擴展算法,遍歷所有字符,將每個字符作為回文串的中心向外擴展,記錄下每次拓展的最長的回文串的長度,最后返回最長的回文串長度即可.但是要考慮回文串的長度是奇數還是偶數,如下圖所示:

---

解題代碼:

本題解題代碼如下:

class Solution 
{
public:/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** * @param A string字符串 * @return int整型*/int getLongestPalindrome(string A) {// 中心拓展算法int max_len=0;for(int i=0;i<A.size();i++){int left,right;for(int j=0;j<2;j++){left=i-1+j;right=i+1;while(left>=0 && right<A.size() && A[left]==A[right]){left--;right++;}max_len = max(right-left-1,max_len);}}return max_len;}
};

---

二.NC369 [NOIP2002 普及組] 過河卒

牛客網題目鏈接(點擊即可跳轉):NC369 [NOIP2002 普及組] 過河卒

題目詳情:

本題詳情如下圖:

---

題目思路:

本題解題思路如下:

??????? 常規二維dp填表可解,狀態轉換方程為dp[n][m]=dp[n-1][m]+dp[n][m-1];

??????? 填表注意下面四種填表特殊情況:如果是馬的控制點,那么dp[i][j]=0,如果是首行,那么dp[i][j]=dp[i][j-1],如果是首列,那么dp[i][j]=dp[i-1][j],如果是dp[0][0]則值填1.

??????? 特別注意題目給的馬的跳躍點方程后面的條件,也是一定要寫入判斷中的,不能忘了!否則會多錯誤計算馬的跳躍點.

---

解題代碼:

本題解題代碼如下

class Solution 
{
public:int crossRiver(int n, int m, int x, int y) {//求dp方程:dp(n,m)=dp(n-1,m)+dp(n,m-1);//填dp表long long dp[20][20]={0};//x+=1;//y+=1;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){if((i!=x&&j!=y&&(abs(i-x)+abs(j-y))==3) || (i==x&&j==y)){dp[i][j]=0;}else if(i==0 && j==0){dp[i][j]=1;}else if(i==0){dp[i][j]=dp[i][j-1];}else if(j==0){dp[i][j]=dp[i-1][j];}else {dp[i][j]=dp[i][j-1]+dp[i-1][j];}}}return dp[n][m];}
};

---

結語

??????? 說點啥好呢...一切都在慢慢向好發展, 堅持下去, 也就最后一兩個月時間就可以得到結果了,加油!