当前位置: 首页 > news >正文

【c++笔试强训】(第三十一篇)

目录

最⻓回⽂⼦序列(动态规划-区间dp)

题目解析

讲解算法原理

编写代码

添加字符(字符串)

题目解析

讲解算法原理

编写代码


最⻓回⽂⼦序列(动态规划-区间dp)

题目解析

1.题目链接:最长回文子序列_牛客题霸_牛客网

2.题目描述

描述

给定一个字符串,找到其中最长的回文子序列,并返回该序列的长度。

注:回文序列是指这个序列无论从左读还是从右读都是一样的。

本题中子序列字符串任意位置删除k(len(s)>=k>=0)个字符后留下的子串。

数据范围:字符串长度满足 1 \le n \le 10001≤n≤1000

进阶:空间复杂度 O(n^2)O(n2) , 时间复杂度 O(n^2)O(n2)

输入描述:

输入一个字符串

输出描述:

输出最长回文子序列

示例1

输入:

abccsb

输出:

4

说明:

分别选取第2、3、4、6位上的字符组成“bccb”子序列是最优解      

示例2

输入:

abcdewa

输出:

3

说明:

分别选取第一个和最后一个a,再取中间任意一个字符就是最优解   

讲解算法原理

解法:
算法思路:

基础的区间dp问题:
1. 状态表⽰: dp[i][j] 表⽰:字符串 [i, j] 范围内的最⻓回⽂⼦序列的⻓度;2. 状态转移⽅程:
◦ 当 i == j 的时候,只有⼀个字符,⻓度为1;
◦ 当 i < j 的时候,分情况讨论:
▪ s[i] == s[j]:dp[i][j] = dp[i + 1][j - 1];▪ s[i] != s[j]:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
3. 返回值: dp[0][n - 1] 。

编写代码

c++算法代码:

#include <iostream>
#include <string>
using namespace std;
int dp[1010][1010];
int main()
{string s;cin >> s;int n = s.size();for(int i = n - 1; i >= 0; i--){dp[i][i] = 1; for(int j = i + 1; j < n; j++) { if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); }}cout << dp[0][n - 1] << endl;return 0;
}

java算法代码:

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in); char[] s = in.next().toCharArray(); int n = s.length; int[][] dp = new int[n][n];for(int i = n - 1; i >= 0; i--){dp[i][i] = 1; for(int j = i + 1; j < n; j++) { if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]); }}System.out.println(dp[0][n - 1]);}
}

添加字符(字符串)

题目解析

1.题目链接:添加字符_牛客笔试题_牛客网

2.题目描述

牛牛手里有一个字符串A,羊羊的手里有一个字符串B,B的长度大于等于A,所以牛牛想把A串变得和B串一样长,这样羊羊就愿意和牛牛一起玩了。
而且A的长度增加到和B串一样长的时候,对应的每一位相等的越多,羊羊就越喜欢。比如"abc"和"abd"对应相等的位数为2,为前两位。
牛牛可以在A的开头或者结尾添加任意字符,使得长度和B一样。现在问牛牛对A串添加完字符之后,不相等的位数最少有多少位?

输入描述:

第一行为字符串A,第二行为字符串B,A的场地小于等于B的长度,B的长度小于等于50.字符均为小写字母。输出描述:

输出一个整数表示A串添加完字符之后,不相等的位数最少有多少位?

示例1

输入

abe
cabc

输出

1

讲解算法原理

解法:
算法思路:

枚举所有字符串a与字符串b相对应的位置。

编写代码

c++算法代码:

#include <iostream>
#include <string>
using namespace std;
string a, b;
int main()
{cin >> a >> b;int m = a.size(), n = b.size(); int ret = m;for(int i = 0; i <= n - m; i++) // 枚举 b 的起始位置 {int tmp = 0; for(int j = 0; j < m; j++) { if(a[j] != b[i + j]) { tmp++; }}ret = min(tmp, ret);}cout << ret << endl;return 0;
}

java算法代码:

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in); char[] a = in.next().toCharArray(); char[] b = in.next().toCharArray(); int m = a.length, n = b.length; int ret = m;for(int i = 0; i <= n - m; i++) // 枚举 b 的起始位置 {int tmp = 0; for(int j = 0; j < m; j++) { if(a[j] != b[i + j]) { tmp++; }}ret = Math.min(ret, tmp);}System.out.println(ret);}
}

相关文章:

【c++笔试强训】(第三十一篇)

目录 最⻓回⽂⼦序列&#xff08;动态规划-区间dp&#xff09; 题目解析 讲解算法原理 编写代码 添加字符&#xff08;字符串&#xff09; 题目解析 讲解算法原理 编写代码 最⻓回⽂⼦序列&#xff08;动态规划-区间dp&#xff09; 题目解析 1.题目链接&#xff1a;最…...

Go 1.19.4 HTTP编程-Day 20

1. HTTP协议 1.1 基本介绍 HTTP协议又称超文本传输协议&#xff0c;属于应用层协议&#xff0c;在传输层使用TCP协议。HTTP协议属是无状态的&#xff0c;对事务处理没有记忆能力&#xff0c;如果需要保存状态需要引用其他技术&#xff0c;如Cookie。HTTP协议属是无连接的&…...

MySQL 8.0 的主主复制(双向复制)

在 Windows Server 2022 Datacenter 上配置 MySQL 8.0 的主主复制&#xff08;双向复制&#xff09;&#xff0c;步骤与 Linux 类似&#xff0c;但有一些特定的配置和路径需要注意。以下是详细的简化步骤&#xff1a; 1. 使用 root 用户登录 确保你以 root 用户登录到 MySQL …...

四、自然语言处理_03LSTM与GRU

0、前言 随着循环神经网络&#xff08;RNN&#xff09;在各种序列数据处理任务中被广泛应用&#xff0c;研究人员逐渐发现了其在处理长序列数据时会容易出现梯度消失&#xff08;vanishing gradient&#xff09;和梯度爆炸&#xff08;exploding gradient&#xff09;问题&…...

磁盘系列基础知识(一):硬盘;IDE;ATA;SATA;AHCI;SCSI;SAS

磁盘系列基础知识&#xff08;一&#xff09;硬盘 IDE ATA SATA AHCI SCSI SAS 硬盘厂家 西部数据Western Digital/WD. 希捷 SEAGATE、三星 SAMSUNG、东之 Toshiba、英特尔 Intel、金士顿 Kingston、闪迪 SanDisk、 英睿达 Crucial、浦科特 Plextor 硬盘类别 HDD &#xff08;…...

taro小程序进入腾讯验证码

接入原因 昨天突然晚上有人刷我们公司的登录发送短信接口&#xff0c;紧急将小程序的验证码校验更新上去了 接下来就是我们的接入方法&#xff0c;其实很简单&#xff0c;不过有时候可能大家着急就没有仔细看文档&#xff0c;腾讯验证码文档微信小程序地址&#xff0c;注意这里…...

原子类相关

原子引用 JUC 并发包提供了&#xff1a; AtomicReferenceAtomicMarkableReferenceAtomicStampedReference AtomicReference 使用举例 public interface DecimalAccount {// 获取余额BigDecimal getBalance();// 取款void withdraw(BigDecimal amount);/*** 方法内会启动 10…...

RabbitMQ 客户端 连接、发送、接收处理消息

RabbitMQ 客户端 连接、发送、接收处理消息 一. RabbitMQ 的机制跟 Tcp、Udp、Http 这种还不太一样 RabbitMQ 服务&#xff0c;不是像其他服务器一样&#xff0c;负责逻辑处理&#xff0c;然后转发给客户端 而是所有客户端想要向 RabbitMQ服务发送消息&#xff0c; 第一步&a…...

Java Web 3 Axios Vue组件库

一 Ajax 1 同步 异步 2 原生Ajax 比较繁琐 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Documen…...

双目相机的标定,视差图,深度图,点云生成思路与实现。

该文档记录从双目相机标定到点云生成的所有过程&#xff0c;同时会附上代码。 代码直接能跑。https://github.com/stu-yzZ/stereoCamera 目录 大致思路如下&#xff1a; 一、相机标定 1、相机参数介绍 2、单目相机标定 3、双目相机标定 二、图片畸变矫正 三、极线矫正…...

【H2O2|全栈】MySQL的基本操作(三)

目录 前言 开篇语 准备工作 案例准备 多表查询 笛卡尔积 等值连接 外连接 内连接 自连接 子查询 存在和所有 含于 分页查询 建表语句 结束语 前言 开篇语 本篇继续讲解MySQL的一些基础的操作——数据字段的查询中的多表查询和分页查询&#xff0c;与单表查询…...

2、C++命名空间

命名空间 命名空间是一种用来避免命名冲突的机制; 原理是将一个全局的作用域分成一个个命名空间&#xff0c;每个命名空间是个单独的作用域,从而有效避免命名冲突。 注意&#xff1a;命名空间定义在全局 命名空间定义格式 使用&#xff1a; …...

Elemenu-UI时间日期单个组件,限制当前日期之后的时间

element的时间日期组件&#xff0c; type"datetime" &#xff0c;当你设置了:picker-options"pickerOptions"之后 pickerOptions: { disabledDate(time) { return time.getTime() > Date.now(); }, }, 会发现&#xff0c;他只会限制日期&#xff0c;但不…...

flutter修改状态栏学习

在flutter中如何动态更改状态栏的颜色和风格。 前置知识点学习 AnnotatedRegion AnnotatedRegion 是 Flutter 中的一个小部件&#xff0c;用于在特定区域中提供元数据&#xff08;metadata&#xff09;以影响某些系统级的行为或外观。它通常用于改变系统 UI 的外观&#xff…...

解决Unity编辑器Inspector视图中文注释乱码

1.问题介绍 新创建一个脚本&#xff0c;用VS打开编辑&#xff0c;增加一行中文注释保存&#xff0c;在Unity中找到该脚本并选中&#xff0c;Inspector视图中预览的显示内容&#xff0c;该中文注释显示为乱码&#xff0c;如下图所示&#xff1a; 2.图示解决步骤 按上述步骤操作…...

关于csgo的游戏作弊与封禁

关于csgo的游戏作弊与封禁 一.关于作弊 什么叫作弊&#xff1f; 1.换肤&#xff0c;换库存 2.各种参&#xff08;回溯&#xff0c;自瞄&#xff0c;透视&#xff0c;急停&#xff0c;连跳&#xff0c;假身&#xff0c;子弹跟踪等&#xff09; 3.某一部分更改游戏内存&…...

严格单元测试造就安全软件

在信息技术迅速发展的今天&#xff0c;软件在各个行业中扮演着至关重要的角色&#xff0c;尤其是在汽车行业&#xff0c;其中软件的可靠性和安全性直接影响到人们的生命安全。软件缺陷所带来的潜在风险不容小觑&#xff0c;尤其在涉及到自动驾驶和车辆控制等关键系统时&#xf…...

ubuntu 根分区逻辑卷扩容

1、虚拟机关机通过管理界面给磁盘扩容。 rootcurtis:/home/curtis/git_code# pvdisplay--- Physical volume ---PV Name /dev/vda3VG Name ubuntu-vgPV Size <239.00 GiB / not usable 0Allocatable yes (but full)PE…...

如何查看电脑生产日期

查看电脑的生产日期通常可以通过以下方法实现&#xff0c;具体方式取决于操作系统和电脑类型&#xff1a; 方法 1&#xff1a;检查电脑 BIOS 生产日期通常记录在 BIOS 中。可以通过以下步骤查看&#xff1a; 重启电脑并进入 BIOS&#xff1a; 启动时按下特定的键&#xff08;…...

MAC M1 mysql 8.0 如何修改root用户密码

关闭mysql服务 使用brew方式安装&#xff0c;可以通过一下命令关闭 brew services stop mysql使用安装包安装的方式 可以选择&#x1f34e;->系统偏好设置->最下方单机MySQL图标->stop mysql server 启动 MySQL 到安全模式 sudo mysqld_safe --skip-grant-tables …...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...