C++刷题强训(day10)--最长回文子串、买股票的最好时期(一)、过河卒

1、最长回文子串

1.1 题目

1.2 思路

1.3 代码实现

2、买卖股票的最好时机

2.1 题目

2.2 思路

2.3 代码实现

3、过河卒

3.1 题目

3.2 思路

3.3 代码实现

1、最长回文子串

1.1 题目

1.2 思路

根据题目可知，在一个长度为n的字符串中求得最长回文子串的长度，回文子串可以理解为对称的字符串。因为具有对称性，那么就可一使用中心拓展的思路，依次遍历字符串，每一个字符向两边拓展，直至结束。

1.3 代码实现

注意一下字符串的长度要分奇数和偶数的情况

class Solution 
{
public:
    int getLongestPalindrome(string A) 
    {
        int left =0,right = 0,ret = 0;
        //当字符串长度为偶数时
        for(int i = 0; i < A.size();i++)
        {
            left = i,right = i+1;
            while(left >= 0 && right <=A.size() && A[left] == A[right])
            {
                left--,right++;
            }
            ret = max(ret,right-left-1);
        }
        //为奇数
        for(int j = 0; j < A.size();j++)
        {
            left = j,right = j;
            while(left >= 0 && right <=A.size() && A[left] == A[right])
            {
                left--,right++;
            }
            ret = max(ret,right-left-1);
        }
        return ret;
    }
};

2、买卖股票的最好时机

2.1 题目

2.2 思路

根据题目只能买卖一次，求得获得利润的最高收益，无论亏损多少，只要没有利润就输出0。那么我们首先就能暴力求解，遍历数组求得每一组的利润，返回最大值，但是暴力求解用了两层for循环，所以会超时。

因此需要再次基础上做优化，暴力求解是回溯重复了太多次，所以我们逆向思维，先考虑卖出的价值，然后就只需要求得该卖点之前的最小价值即可，得到的差就是最大值。

理清思路，接下来就是代码实现。

2.3 代码实现

注意一下，minval和ret的顺序，先求最小值，要考虑自身位置，这样利润最小也是0，不会为负

#include <iostream>
using namespace std;

int main() 
{
    int n = 0;
    cin >> n;
    int arr[n];
    for(int i = 0;i < n;i++)
        cin >> arr[i];
    int ret = 0,minval = arr[0];
    for(int i= 0; i < n;i++)
    {
        minval = min(arr[i],minval);
        ret = max(ret,arr[i]-minval);
    }
    cout << ret << endl;

    return 0;
}

3、过河卒

3.1 题目

3.2 思路

这是一道经典的动态规划题，读完题，要注意马能到达及其所在的位置不能走，马一开始就给出了固定点，且题中也给出了，马能跳跃的点与其所在位置的关系。

注意：

棋盘的大小是(n+1,m+1)。
注意边界控制，从[1,n+1][1,m+1]遍历
分情况：
- a.判断马的控制点阻塞路径，和重合问题
- b.正常执行状态转移方程dp[i][j] = dp[i][j-1] + dp[i-1][j]

创建dp表时，多一行，多一列，初始化dp[0][0] = 0; dp[0][1]或者dp[1][0] = 1;

3.3 代码实现

这道题数据范围很大所以记得用 long long初始化dp表

#include <iostream>
using namespace std;

long long dp[24][24];

int main() 
{
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    dp[0][1] = 1;
    x += 1, y+=1;//dp表创建的时候多了一行多了一列，为了找原数组映射
    for(int i = 1; i <= n+1;i++)
    {
        for(int j = 1;j <= m+1;j++)
        {                           //马能走到的位置           马自身的位置
            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;
}