【刷题汇总 -- 最长回文子串、买卖股票的最好时机(一)、[NOIP2002 普及组] 过河卒】

C++日常刷题积累

  • 今日刷题汇总 - day010
    • 1、最长回文子串
      • 1.1、题目
      • 1.2、思路
      • 1.3、程序实现
    • 2、买卖股票的最好时机(一)
      • 2.1、题目
      • 2.2、思路
      • 2.3、程序实现
      • 2.4、程序实现 -- 优化
    • 3、[NOIP2002 普及组] 过河卒
      • 3.1、题目
      • 3.2、思路
      • 3.3、程序实现 -- dp
    • 4、题目链接

今日刷题汇总 - 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 普及组] 过河卒

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/793506.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一个便捷的web截图库~【送源码】

随着时间的发展&#xff0c;前端开发的范围越来越广&#xff0c;能够实现的功能也越来越多&#xff0c;要实现的功能也五花八门&#xff0c;今天就给大家介绍一个web截图库,让前端也能实现截图功能—— js-web-screen-shot js-web-screen-shot js-web-screen-shot 是一个基于 …

Linux服务器CPU占用率达到100%排查思路

1、找到最耗CPU的进程pid&#xff0c;执行命令 top 2、找到最耗CPU的线程tid // 执行 top -Hp [pid] 定位应用进程对应的线程 tid // 按shift p 组合键&#xff0c;按照CPU占用率排序 > top -Hp 14246 3、将线程pid转化为16进制 // printf "%x\n" [tid] 将tid…

Redis+Caffeine 实现两级缓存实战

RedisCaffeine 实现两级缓存 背景 ​ 事情的开始是这样的&#xff0c;前段时间接了个需求&#xff0c;给公司的商城官网提供一个查询预计送达时间的接口。接口很简单&#xff0c;根据请求传的城市仓库发货时间查询快递的预计送达时间。因为商城下单就会调用这个接口&#xff…

camunda最终章-springboot

1.实现并行流子流程 1.画图 2.创建实体 package com.jmj.camunda7test.subProcess.entity;import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;import java.io.Serializable; import java.util.ArrayList; import java.util.List;Data …

ComfyUI+MuseV+MuseTalk图片数字人

电脑配置 GPU12G&#xff0c;如果自己电脑配置不够&#xff0c;选择云gpu&#xff0c;我就是用的这个&#xff0c;自己电脑太老配置跟不上 环境&#xff1a; Python 3.11.8 torch 2.2.1 cuda_12.1 资源提供&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1_idZbF…

开始Linux之路(暑假提升)

人生得一知己足矣&#xff0c;斯世当以同怀视之。——鲁迅 Linux操作系统简单操作指令 1、ls指令2、pwd命令3、cd指令4、mkdir指令(重要)5、whoami命令6、创建一个普通用户7、重新认识指令8、which指令9、alias命令10、touch指令11、rmdir指令 及 rm指令(重要)12、man指令(重要…

【视频】R语言广义加性模型GAMs非线性效应、比较分析草种耐寒性实验数据可视化

全文链接&#xff1a;https://tecdat.cn/?p36979 原文出处&#xff1a;拓端数据部落公众号 广义加法模型&#xff08;Generalized Additive Models, GAMs&#xff09;作为一种高度灵活的统计工具&#xff0c;显著扩展了广义线性模型&#xff08;Generalized Linear Models, …

C基础day9

一、思维导图 二、课后练习 1> 使用递归实现 求 n 的 k 次方 #include<myhead.h>int Pow(int n,int k) {if(k 0 ) //递归出口{return 1;}else{return n*Pow(n,k-1); //递归主体} }int main(int argc, const char *argv[]) {int n0,k0;printf("请输入n和k:&…

Python统计实战:时间序列分析之绘制观测值图和按年折叠图

为了解决特定问题而进行的学习是提高效率的最佳途径。这种方法能够使我们专注于最相关的知识和技能&#xff0c;从而更快地掌握解决问题所需的能力。 &#xff08;以下练习题来源于《统计学—基于Python》。请在Q群455547227下载原始数据。&#xff09; 练习题 下表是某地区2…

复杂度(上卷)

前言 在正式进入今天的主题之前&#xff0c;我们不妨先来回顾一下初步学习数据结构后必须知道的概念。&#x1f3b6; 数据结构 数据结构是计算机存储、组织数据的方式&#xff0c;指相互间存在一种或多种特定关系的数据元素的集合。 &#xff08;没有一种单一的数据结构能够…

如何保证RocketMQ消息不丢失

rocket mq在生产阶段、Brocker存储阶段、消费阶段都会出现消息丢失。 1、生产者防止丢失消息。 a.同步阻塞的方式发送消息&#xff0c;加上失败重试机制&#xff0c;可能broker存储失败&#xff0c;可以通过查询确认 b.异步发送需要重写回调方法&#xff0c;检查发送结果 c…

人脸表情识别Facial Expression Recognition基于Python3和Keras2(TensorFlow后端)

人脸表情识别项目是一个结合了计算机视觉和深度学习技术的高级应用&#xff0c;主要用于分析和理解人类面部表情所传达的情感状态。这样的系统可以用于多种场景&#xff0c;比如情绪分析、用户交互、市场调研、医疗诊断以及人机接口等领域。 一个典型的人脸表情识别项目可以分…

kafka与zookeeper的SSL认证教程

作者 乐维社区&#xff08;forum.lwops.cn&#xff09;许远 在构建现代的分布式系统时&#xff0c;确保数据传输的安全性至关重要。Apache Kafka 和 Zookeeper 作为流行的分布式消息队列和协调服务&#xff0c;提供了SSL&#xff08;Secure Sockets Layer&#xff09;认证机制&…

红酒与威士忌:跨界碰撞的味觉火花

在品酒的世界里&#xff0c;红酒与威士忌&#xff0c;两者如同两位优雅的舞者&#xff0c;各自在舞台上闪耀着不同的光芒。然而&#xff0c;当它们相遇&#xff0c;那跨界碰撞的味觉火花&#xff0c;却仿佛一场不可预测的华丽盛宴&#xff0c;让人为之倾倒。 一、红酒的浪漫与威…

测试狗:“微观结构表征+理论计算”助力《Science》论文发表

特大喜讯&#xff1a;祝贺四川大学王玉忠院士&#xff0c;赵海波教授&#xff0c;马健文硕士研究生&#xff08;第一作者&#xff09;在《Science》上发表新的研究成果&#xff0c;测试狗和计算狗分别提供了SEM、Micro-CT、FTIR和理论计算支持&#xff0c;供相关领域的科研工作…

【经典面试题】环形链表

1.环形链表oj 2. oj解法 利用快慢指针&#xff1a; /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) {ListNode* slow head, *fast…

centos9中mysql指令提示解决方案

CentOS 9 中没有 MySQL 的官方插件&#xff0c;因为 MySQL 不是 CentOS 的默认数据库&#xff0c;它是 MariaDB 的一部分。 如果想要一个命令行提示的 MySQL 客户端&#xff0c;可以使用第三方工具 &#xff0c;如mycli 首先&#xff0c;确保已经安装了 MySQL&#xff0c;且操…

【C语言】C语言-身份证管理系统(源码+注释)【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…

Java链表LinkedList经典题目

一.LinkedList的方法 首先先看一下链表的方法&#xff1a; 方法解释boolean add(E e)尾插void add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一…

【7.10更新】Win11 23H2 正式版:22631.3880镜像下载!

微软向Win11 23H2用户推送了七月最新更新补丁KB5040442&#xff0c;系统更新后&#xff0c;版本号将升至22631.3880。本次更新包括了一些安全质量更新&#xff0c;并修复了6月可选更新导致的任务栏无法加载、交互问题&#xff0c;建议大家更新。该版本系统离线制作而成&#xf…