今日刷題匯總 - day010

1、最長回文子串

1.1、題目

1.2、思路

讀完了題知道，在一個長度為n的字符串中，求最長回文子串的長度。回文子串可以理解為對稱的字符串。因為具有對稱性，那么基本思路就是“中心擴展法”，也就是依次字符串，然后遍歷到該字符就向其兩邊擴展，如果兩邊的字符相等，那么就記錄到retlen變量中，遍歷完最后得到最大長度返回即可。為了方便理解，畫個圖：

此外，分析示例，還得注意奇數偶數的區別，那么接下來就是程序實現。

1.3、程序實現

首先，按照思路分析的“中心擴展法”，遍歷字符串，且從i處從中心站展開，依次求得的retlen,與retlen不斷比較更新，然后又因為需要區分奇數和偶數的情況，所以分別求得最大值，最后再比較依次得到最終最大的retlen返回即可。

class Solution
{
public:int getLongestPalindrome(string A){size_t len = A.size();int left = 0;int right = 0;int retlen = 0;//偶數for(int i = 0;i < len; i++){left = i;right = i + 1;while(left >= 0 && right < len && A[left] == A[right]){left--;right++;}retlen = max(retlen ,right - left - 1);}//奇數for(int j = 0;j < len;j++){left = j;right = j;while(left >= 0 && right < len && A[left] == A[right]){left--;right++;}retlen = max(retlen ,right - left - 1);}return retlen ;}
};

2、買賣股票的最好時機(一)

2.1、題目

2.2、思路

讀完題，知道對于一組股票的買賣機制，只能買賣一次，讓求得獲得的利潤的最高收益，如果無論什么時候買入賣出都是虧，不管虧多少，即沒有利潤則輸出0即可。那么，基本思路就是枚舉/蠻力法，求得每一組的利潤差，返回最大值，嘗試過后，發現兩層for會超時，此題限制1ms解決。因此，需要在蠻力法基礎上優化，所以蠻力法也寫一寫，然后，基于蠻力法，回溯重復了太多次，進行優化，思考發現，如果我們反過來逆向思維，先考慮賣出的價值，然后，就只需要求得該賣出點之前的最小價值即可，得到的差就是最大差，也就是說只需要遍歷一遍即可。接下來就是程序實現。

2.3、程序實現

首先，根據蠻力法思路分析，依次枚舉所有情況，求得最大差值輸出即可，此題會超時。所以得進行優化。

#include <iostream>
using namespace std;const int N = 1e5 +10;int arr[N];int main()
{int n;cin >> n;for(int i = 0;i < n;i++)cin >> arr[i];int maxval = 0;for(int i = 0;i < n; i++){for(int j = i;j < n;j++){maxval = max(maxval , arr[j]- arr[i]);}}cout << maxval << endl;return 0;
}

2.4、程序實現 – 優化

基于上述的蠻力法，進行優化，為了方遍理解，根據思路分析畫個演示圖：

那么程序實現，按照要求寫好輸入，然后定義minval初始化arr[0]當作假設的最小值進行遍歷比較更新即可，再定義一個maxSub表示遍歷至 i 位置時，與minval的最大差值，值得注意的是，遍歷時注意minval和maxSub的順序性，先求最小值minval再求maxSub即可。

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n = 0;cin >> n;vector<int> arr(n);int m = 0;while(n--){cin >> arr[m];m++;}int minval = arr[0];int submax = 0;for(int i = 0;i<arr.size();i++){minval = min(arr[i],minval);submax = max(submax, arr[i] - minval);}cout << submax << endl;return 0;
}

3、[NOIP2002 普及組] 過河卒

3.1、題目

3.2、思路

讀完題，知道讓求從A點按照一定的規則，走到B點最多有多少條的路徑。分析題目需要知道，按照一定的規則，可以向右或向下走就想到了動態規劃dp思路，然后題目中還需要注意的是，馬的控制點不能被走(訪問)，也就是象棋中馬在坐標上走的斜"日"所設計的點，且包括馬的起始點都被稱為控制點。其中，馬是一開始就給出的固定點(x,y)，且題目也給了馬跳躍點與馬起始點的關系。此外，還得注意的是，根據示例和棋盤得知，棋盤的大小是(n+1)(m+1)。
所以，綜合所述，思考分析得出：
(1)、可使用動態規劃dp思路解題;
(2)、馬的控制點，除了斜“日”外，還包括自身的起始位置；
(3)、棋盤的大小是(n+1)(m+1).
所以分析了注意點后，那么就回歸到動態規劃的dp狀態表示和狀態轉移方程上來；
由題目的走的規則，定義dp[i][j]狀態表示：走到該位置最多有幾條路徑；
推導狀態轉移方程：dp[i][j] = d[i][j-1] + d[i-1][j] ;
此外注意如果B點起始位置就與馬的起始位置或控制點重合，還有就是B點的上方和左方全部被阻塞，即是控制點，那么以上極端情況，此時dp[i][j] = 0; 那么接下來，就是程序實現。

3.3、程序實現 – dp

首先，根據思路的分析寫好輸入，定義開辟好dp數組(兩個坑點稍后說)，根據棋盤的大小為了坐標能夠統一描述所以這里就額外多開辟一行一列，那么x和y就需要映射坐標+=1即可，然后探究dp的初始化問題，畫個圖更清晰：

接著，實際二維數組就從[1，n+1]和[1，m+1]遍歷，不斷判斷極端情況的處理即可，最后輸出dp[n+1][m+1]即可。到此，思路沒有問題，總結步驟為一下幾點：
(1)、映射x和y的坐標;
(2)、根據(多開辟一層)數組定義初始化dp[0][1] =1 或 dp[1][0] = 1均可;
(3)、遍歷二位數組，注意邊界控制從[1，n+1]和[1，m+1]遍歷;
a、判斷極端情況：1.馬的控制點阻塞路徑 2.重合問題;
b、正常執行狀態轉移方程：dp[i][j] = d[i][j-1] + d[i-1][j] ;
(4)、最后輸出dp[n+1][m+1]即可.
另外，上面提到的兩個坑點，在于我寫好后，提交不通過，發現，數據超范圍了，所以最好使用long long開辟數組，還有一個坑點是在于開辟的大小范圍由于多開辟的一層使用，所以這里至少大于等于22才行。之前使用dp[21][21]無法通過所有用例哈。

#include <iostream>
using namespace std;long long dp[22][22];int main()
{int n,m,x,y;cin >> n >> m >> x >> y;//映射坐標x += 1;y += 1;//初始化dp[0][1] = 1;//遍歷for(int i = 1;i <= n+1; i++){for(int j = 1;j <= m+1; j++){//極端情況的處理:  1.馬控制點 2.自身重合if((i != x && j != y && abs(i - x) + abs(j - y) == 3) || (i == x && j == y)){dp[i][j] = 0;}else{dp[i][j] = dp[i][j-1] + dp[i-1][j];}}}cout << dp[n+1][m+1] << endl;return 0;
}

4、題目鏈接

最長回文子串
買賣股票的最好時機(一)
[NOIP2002 普及組] 過河卒