​​​​​48days强训——day10

第一题：最长回文子串

链接：最长回文子串_牛客题霸_牛客网

描述 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。 数据范围： 1≤n≤10001≤n≤1000 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n2)O(n2) 进阶: 空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n) 示例1 输入： "ababc" 返回值： 3 说明： 最长的回文子串为"aba"与"bab"，长度都为3 示例2 输入： "abbba" 返回值： 5 示例3 输入： "b" 返回值： 1

题解：枚举所有的中⼼点，然后向两边扩散。

代码：

代码语言：javascript代码运行次数：0运行复制

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

第二题： 买卖股票的最好时机(一)

链接：买卖股票的最好时机(一)_牛客题霸_牛客网

题目：

描述 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天 2.如果不能获取到任何利润，请返回0 3.假设买入卖出均无手续费 数据范围： 0≤n≤105,0≤val≤1040≤n≤105,0≤val≤104 输入描述： 第一行输入一个正整数 n 表示数组的长度 第二行输入 n 个正整数，表示股票在第 i 天的价格 输出描述： 输出只买卖一次的最高收益 示例1 输入： 7 8 9 2 5 4 7 1 输出： 5 说明： 在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。 示例2 输入： 3 2 4 1 输出： 2 示例3 输入： 3 3 2 1 输出： 0

题解：因为只能买卖⼀次，因此，对于第i天来说，如果在这天选择卖出股票，应该在 内，股票最低点买⼊股票，此时就可以获得最⼤利润。

代码：

代码语言：javascript代码运行次数：0运行复制

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n;
int arr[N];
int main() 
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    int maxval = 0, minval = arr[0];
    for (int i = 1; i < n; i++) {
        minval = min(arr[i], minval);
        maxval = max(maxval, arr[i] - minval);
    }
    cout << maxval << endl;
    return 0;
}

第三题：[NOIP2002 普及组] 过河卒

链接：[NOIP2002 普及组] 过河卒_牛客题霸_牛客网

描述 棋盘上 A点有一个过河卒，需要走到目标 B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，A 点 (0, 0)、B点(n,m)，同样马的位置坐标是需要给出的。 现在要求你计算出卒从 A点能够到达

注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 ∣x1−x∣+∣y1−y∣=3，且x1≠x,y1≠y ∣x1−x∣+∣y1−y∣=3，且x1​=x,y1​=y 数据范围： 1≤n,m≤20 1≤n,m≤20 ，马的坐标 0≤x,y≤20 0≤x,y≤20 1≤a,b,c,d≤1000 1≤a,b,c,d≤1000 输入描述： 仅一行，输入 n,m,x,y 四个正整数。分别表示B点坐标和马的坐标 输出描述： 输出路径总数 示例1 输入： 6 6 3 3 输出： 6 示例2 输入： 5 4 2 3 输出： 3 示例3 输入： 2 5 3 5 输出： 1

题解：简单路径dp问题：相当于是有障碍物的路径类问题，标记⾛到障碍物上的⽅法数为0即可。

代码：

代码语言：javascript代码运行次数：0运行复制

#include <bits/stdc++.h>
using namespace std;

long long dp[25][25];

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++)
        {
            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-1][j] + dp[i][j-1];
        }
    }
    cout << dp[n+1][m+1] << endl;
    return 0;
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-14，如有侵权请联系 cloudcommunity@tencent 删除前往查看int设计数据数组算法