【C++】 —— 笔试刷题day_10

一、最长回文字符串

题目解析

这道题，给定一个字符串，让我们找出其最长的回文子串的长度 题目描述很简单，直接来看这道题的思路

算法思路

对于这道题，有很多种解法

• 动态规划
• 车拉马算法：这样一个专门解决最长回文字符串的一种思想
• 中心扩展算法

这里就只来看一下 中心扩展算法，剩余在之后了解过后再来分享。

什么是中心扩展算法呢？ 简单来说就是以某一个位置为中心，向两边扩展寻找回文字符串。

什么意思呢？

如上图，我们遍历到i位置时，我们定义left和right分别向两边遍历，直到遍历结束或者left和right的位置的数据不相等。

那这里我们就遇到了一些问题：

回文字符串的长度可能为奇数，也可能为偶数：如果是奇数的话，i是整个子串的中间；但如果是偶数的话，是没有中心的（也就是说i和i+1位置的数据是相等的） 长度的计算： 我们left和right遍历结束后，然后去计算长度呢？

对于上述的第一个问题，我们之间两种情况分别遍历一次就好了；（left = i-1 , right = i+1遍历表示长度为奇数的时候，left = i , right = i+1表示长度为偶数的时候） 对于如何奇数的问题，我们找一个实际情况分析一下：

可以看到，我们遍历结束后，以i为中心的子串长度为right - left - 1。

所以我们整体的思路就清楚了

• 遍历整个字符串
• 以i位置为中心向左右两边进行遍历，（两种情况都遍历一次）
• 更新结果，每进行以i为中心遍历之后，更新一下结果。

代码实现

class Solution {
  public:
    int getLongestPalindrome(string A) {
        int n = A.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < n && A[left] == A[right]) {
                left--;
                right++;
            }
            ret = max(ret, right - left - 1);
            left = i, right = i + 1;
            while (left >= 0 && right < n && A[left] == A[right]) {
                left--;
                right++;
            }
            ret = max(ret, right - left - 1);
        }
        return ret;
    }
};

二、买股票的最好时机(一)

题目解析

题目给一个数组paices表示股票每天的价格，我们可以买入一次和卖出一次股票，让我们求出来我们可以获得的最大利益；这里有几个要注意的点：

• 买入股票必须在卖出股票之前
• 如果我们不能获得任何利润，就返回0（简单来说，如果我们获得的最大利益是<0的就返回0）
• 买卖股票没有手续费（就是没有损耗）

算法思路

了解了题目，现在来看这道题的思路：

这道题可以使用动态规划，博主在做这道题时就是使用这种思路；

也可以使用一点小小的贪心，（不要被名字吓到了，其实很简单的）

现在来看第一种思路：

这里给了数组paices，我们创建一个对应的数组dp

• 这里dp[i]表示的是，在第i天以后（包括第i天）卖出，股票价格的最高价。
• 这里状态转移方程 dp[i] = max(paices[i] , dp[i+1])，什么意思呢？（就是，在第i天以后的最高价就等于第i天的价格和第i+1天以后的最高价。
• 这样我们再次遍历数组：表示，我们在哪一天买入，所以我们获得的利润ret = max(ret , dp[i+1] - poices[i])。

这样我们就获得了最大利润，这里要注意，如果最大利润小于0，我们要返回0。（这里我们上述操作是没有考虑当天买入当天卖出的，如果我们考虑了，最大利润的最小值就是0，就不需要进行特殊判断了。

简单总结一下：这里也是简单使用了动态规划，思路还是非常简单的。

现在来看另外一种思路：

这一种思路也算是在暴力解法的基础上进行优化。

首先这道题暴力解法：双层遍历整个数组paices，依次找到利润最大值即可。 时间复杂度为O(n^2)

这里进行简单优化：

• 我们这里考虑在哪一天卖出即可。（也可以考虑在哪一天买入）
• 从左到右遍历数组，定义prveMin表示第i天之前的最低价格，ret表示最终结果。
• 这样我们在遍历的过程中，其含义就是在第i天卖出，我们就要用第i天的价格（卖出时价格）减去第i天之前的最低价格（买入时价格），再更新结果即可。

这里和上面一样，我们没有考虑 当天买入当天卖出，所以利润可能小于0，（如果考虑了利润就是>=0的了）。

代码实现

动态规划：

#include <iostream>
#include<vector>
using namespace std;
const int N = 100001;
int dp[N];
int main() {
    int n;
    cin >> n;
    vector<int> paices(n);
    for (int i = 0; i < n; i++) {
        cin >> paices[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = max(paices[i], dp[i + 1]);
    }
    int ret = 0;
    for (int i = 0; i < n - 1; i++) {
        if (dp[i] - paices[i])   ret = max(ret, dp[i] - paices[i]);
    }
    cout << ret << endl;
    return  0;
}

贪心算法优化：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int min_prve = 10000;
    int ret = 0;
    while (n--) {
        int x;
        cin >> x;
        min_prve = min(min_prve, x);
        ret = max(ret, x - min_prve);
    }
    cout << ret << endl;
    return 0;
}

这里注意： 我们并没有使用数组去存储这些数据，因为这些数据我们在遍历的过程中只使用了一次，所以就没必要存储下来； 当然也是可以将它们中输入的数据存储下来的。

三、过河卒

题目解析

这道题，我们从(0 , 0)位置开始，往下或者往右走，题目要求我们求出来走到B点(n , m)一共有多少种走法； 在走的过程中：

• 我们不能走到马的位置(x , y)和其能够控制的位置（一步能够走到的位置）；
• 题目当中是告诉我们马能够控制的位置和马的位置的关系的： （|x1 - x| + |y1 - y| = 3），这样我们直接按照这个公式去判断即可。

算法思路

在初次看到这道题时，博主把它想成了广度优先遍历bfs（因为博主在做这道题之前刚做过一道也是求从某个位置到另外一个位置有多少种解法）

但是，使用BFS来解决这道题，我们会发现实现起来特别麻烦（相当于模拟实现了整个过程），而且占用的空间内存太大了。

现在就来看这道题的解题思路：动态规划：

• dp[i][j]：dp[i][j]的含义就是从(0 , 0)位置开始，走到(i , j)位置一共有多少种走法。
• 状态转移方程： 对于动态转移方程，我们先看题目说明：我们可以从当前位置向下和向右走，所以我们只能从(i , j-1)和(i-1 , j)位置到达(i , j)；所以我们到达(i , j)位置的走法dp[i][j] = dp[i-1][j] + dp[i][j+1]。

对于dp[i][j]和状态转移方程如上述所示，现在来看需要注意的几个点

1. 这里题目要求的是从(0 , 0)位置到(n , m)位置的走法，为了方便我们进行填表操作，我们要将为题转化为 从(1 , 1)位置到(n , m)位置的做法；这样做了变动以后，我们马的坐标也要从(x , y)变成(x+1 , y+1)。
2. 我们的表尽量开辟大一些（这里25*25就够用了）。
3. 我们在填表的时候，给dp[0][1]或者dp[1][0]赋值成1就可以开始填表了。
4. 我们在填表的过程中，如果遇到了马的位置以及马的控制点，将位置赋值成0即可（表示走不到该位置）
5. 根据题目中给的数据，最后返回的结果比较大，所以我们要定义long long类型

代码实现

#include <iostream>
using namespace std;
const int N = 25;
long long dp[N][N];
int main() {
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    n+=1,m+=1,x+=1,y+=1;
    dp[0][1] =1;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=m;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][m]<<endl;
    return 0;
}

到这里，进入刷题就结束了，感谢各位的支持。 继续加油！！！