蓝桥杯 本质上升序列

news/2024/6/16 11:26:07/文章来源:https://blog.csdn.net/weixin_64443786/article/details/137173045

题目描述:

小蓝特别喜欢单调递增的事物。 在一个字符串中,如果取出若干个字符,将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。 例如,在字符串 lanqiao 中,如果取出字符 n 和 q,则 nq组成一个单 调递增子序列。类似的单调递增子序列还有 lnq、 i、 ano 等等。小蓝发现,有些子序列虽然位置不同,但是字符序列是一样的,例如取第 二个字符和最后一个字符可以取到 ao,取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。 对于一个字符串,小蓝想知道,本质不同的递增子序列有多少个? 例如,对于字符串
lanqiao,本质不同的递增子序列有 21 个。它们分别 是 l、 a、 n、 q、 i、 o、 ln、 an、 lq、 aq、 nq、ai、 lo、 ao、 no、 io、 lnq、anq、 lno、 ano、 aio。 请问对于以下字符串(共 200
个小写英文字母,分四行显示):(如果你把 以下文字复制到文本文件中,请务必检查复制的内容是否与文档中的一致。在 试题目录下有一个文件inc.txt,内容与下面的文本相同)
本质不同的递增子序列有多少个?

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

解题思路:

拿到题目一看是字母比较大小,直接想到遍历字符串比较就行

1:先创建一个数组a[]=new int [字符串的具体长度],它的数值是统计以每一个字符结尾的子字符串的个数的,比如“12”,a[0]的值代表以1结尾的子字符串=1,a[1]以2结尾有 “2”,“12”,所以a[1]=2;

2:因为每个字符都是字符串的子序列,可以令a[i]=1;

3:不难理解,a[i]的值又全体a[j]共同决定(0<j<i)

比如说有一个字符串有数字构成(和字符一样):127837;


按照a的定义 7 17 27 127属于a[5],因为他们的结尾都是7且都是上升序列,但是累加时这四个和a[2]对应的序列集重复 因此需要在a[5]-a[2]

代码:

String s="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";int a[]=new int[200];int count=0;for(int i=0;i<200;i++) {a[i]=1;}for(int i=1;i<200;i++) {for(int j=0;j<i;j++) {if(s.charAt(i)>s.charAt(j)) {a[i]+=a[j];}else if(s.charAt(i)==s.charAt(j)) {a[i]-=a[j];}}}for(int i=0;i<200;i++) {count+=a[i];}System.out.println(count);

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

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

相关文章

最新AI智能系统ChatGPT网站源码V6.3版本,GPTs、AI绘画、AI换脸、垫图混图+(SparkAi系统搭建部署教程文档)

一、前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持GPT…

CentOS7安装flink1.17完全分布式

前提条件 准备三台CenOS7机器&#xff0c;主机名称&#xff0c;例如&#xff1a;node2&#xff0c;node3&#xff0c;node4 三台机器安装好jdk8&#xff0c;通常情况下&#xff0c;flink需要结合hadoop处理大数据问题&#xff0c;建议先安装hadoop&#xff0c;可参考 hadoop安…

备考ICA----Istio实验13---使用 Istio Ingress 暴露应用

备考ICA----Istio实验13—使用Istio Ingress TLS暴露应用 1. 环境部署 清理之前实验遗留,并重新部署httpbin服务进行测试 # 清理之前的环境 kubectl delete vs httpbin kubectl delete gw mygateway # 部署httpbin kubectl apply -f istio/samples/httpbin/httpbin.yaml 确认…

【数据结构】非线性结构---二叉树

1、树 1.1 树的相关概念 节点的度&#xff1a;一个节点含有的子树的个数称为该节点的度&#xff1b; 如上图&#xff1a;A的为6 叶节点或终端节点&#xff1a;度为0的节点称为叶节点&#xff1b; 如上图&#xff1a;B、C、H、I...等节点为叶节点 非终端节点或分支节点&#…

51单片机学习笔记14 LCD1602显示屏使用

51单片机学习笔记14 LCD1602显示屏使用 一、LCD1602介绍1. 简介2. 引脚定义3. DDRAM4. 字模5. 指令&#xff08;1&#xff09;清屏指令 0x01&#xff08;2&#xff09;光标归位指令 0x02&#xff08;3&#xff09;进入模式设置指令 0x06&#xff08;4&#xff09;显示开关控制指…

JavaScript中什么叫深拷贝?

在 JavaScript 中&#xff0c;深拷贝指的是创建一个新的对象&#xff0c;这个新的对象与原始对象完全独立&#xff0c;没有任何共享的属性或者数据&#xff0c;它们不共享同一块内存地址。深拷贝会复制原始对象的所有属性和嵌套对象的所有属性&#xff0c;包括嵌套对象中的属性…

Ts递归查找多个根节点树结构某一条数据

// 递归查找树结构数据 function getIsNode(nodes: any, code: string) {let found false;function search(nodes: any) {nodes.forEach((node: any) > {if (node.code code) { //code相等&#xff0c;视为找到&#xff0c;将found设置为truefound true;}// 否则查找子节…

数据结构进阶篇 之【选择排序】详细讲解(选择排序,堆排序)

民以食为天&#xff0c;我以乐为先 嘴上来的嘘寒问暖&#xff0c;不如直接打笔巨款 一、选择排序 1.直接选择排序 SelectSort 1.1 基本思想 1.2 实现原理 1.3 代码实现 1.4 直接选择排序的特性总结 2.堆排序 HeapSort 跳转链接&#xff1a;数据结构 之 堆的应用 二、完…

OpenHarmony实战开发-如何通过Stage模型实现一个简单的游戏卡片

介绍 本示例展示了如何通过Stage模型实现一个简单的游戏卡片。 通过卡片支持的点击事件进行交互&#xff0c;让用户通过点击的先后顺序把一个乱序的成语排列成正确的成语。使用了C和TS的混合编程方式&#xff0c;将获取随机数的能力下沉到C实现&#xff0c;并通过NAPI的能力将…

牛客NC153 信封嵌套问题【中等 动态规划,最长递增子序列 Java,Go,PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/9bf77b5b018d4d24951c9a7edb40408f 相同的题目&#xff1a; https://www.lintcode.com/problem/602 思路 本质是求最长子序列问题envelopes 先按 w 升序排序&#xff0c;再按 h 降序 排序&#xff0c;只需考虑h…

基于深度学习的机场航拍小目标检测系统(网页版+YOLOv8/v7/v6/v5代码+训练数据集)

摘要&#xff1a;在本博客中介绍了基于YOLOv8/v7/v6/v5的机场航拍小目标检测系统。该系统的核心技术是采用YOLOv8&#xff0c;并整合了YOLOv7、YOLOv6、YOLOv5算法&#xff0c;从而进行性能指标的综合对比。我们详细介绍了国内外在机场航拍小目标检测领域的研究现状、数据集处理…

Nginx三大常用功能“反向代理,负载均衡,动静分离”

注意&#xff1a;以下案例在Windows系统计算机作为宿主机&#xff0c;Linux CentOS 作为虚拟机的环境中实现 一&#xff0c;Nginx配置实例-反向代理 1.反向代理 案例一 实现效果&#xff1a;使用nginx反向代理&#xff0c;访问 www.123.com 直接跳转到127.0.0.1:8080 准备工…

vue3源码解析——ref和reactive定义响应式的区别

ref 和 reactive 是 Vue 3.0 中用于定义响应式数据的两个新 API。它们有以下区别&#xff1a; ref 定义单个响应式数据 数据类型可以是任意类型。它通常用于定义原始数据类型为响应式数据。返回一个响应式对象&#xff0c;该对象包含一个 .value 属性&#xff0c;可用于获取和设…

Golang Gin框架

1、这篇文章我们简要讨论一些Gin框架 主要是给大家一个基本概念 1、Gin主要是分为路由和中间件部分。 Gin底层使用的是net/http的逻辑&#xff0c;net/http主要是说&#xff0c;当来一个网络请求时&#xff0c;go func开启另一个协程去处理后续(类似epoll)。 然后主协程持续…

网络安全 | 什么是DDoS攻击?

关注WX&#xff1a;CodingTechWork DDoS-介绍 DoS&#xff1a;Denial of Service&#xff0c;拒绝服务。DDoS是通过大规模的网络流量使得正常流量不能访问受害者目标&#xff0c;是一种压垮性的网络攻击&#xff0c;而不是一种入侵手段。NTP网络时间协议&#xff0c;设备需要…

DSP实时计算平台设计方案:912-基于6U CPCIe的双路光纤图像DSP实时计算平台

基于6U CPCIe的双路光纤图像DSP实时计算平台 一、设备概述 设备基于6U CPCIe架构&#xff0c;通过背板交换实现4片信号处理板卡的互联传输&#xff0c;每个信号处理板卡支持双TMS320C6678&#xff0c;支持2路光纤的图像处理&#xff0c;实现FPGA的预处理和备份工…

Java基础知识总结(第八篇):集合:Collection(List、Set)、Map、Collections 工具类

声明: 1. 本文根据韩顺平老师教学视频自行整理&#xff0c;以便记忆 2. 若有错误不当之处, 请指出 系列文章目录 Java基础知识总结&#xff08;第一篇&#xff09;&#xff1a;基础语法 Java基础知识总结&#xff08;第二篇&#xff09;&#x…

159 Linux C++ 通讯架构实战14,epoll 函数代码实战

ngx_epoll_init函数的调用 //&#xff08;3.2&#xff09;ngx_epoll_init函数的调用&#xff08;要在子进程中执行&#xff09; //四章&#xff0c;四节 project1.cpp&#xff1a;nginx中创建worker子进程&#xff1b; //nginx中创建worker子进程 //官方nginx ,一个…

HarmonyOS 应用开发之页面和自定义组件生命周期

在开始之前&#xff0c;我们先明确自定义组件和页面的关系&#xff1a; 自定义组件&#xff1a;Component装饰的UI单元&#xff0c;可以组合多个系统组件实现UI的复用&#xff0c;可以调用组件的生命周期。 页面&#xff1a;即应用的UI页面。可以由一个或者多个自定义组件组成…

Topaz Video AI for Mac v5.0.0激活版 视频画质增强软件

Topaz Video AI for Mac是一款功能强大的视频处理软件&#xff0c;专为Mac用户设计&#xff0c;旨在通过人工智能技术为视频编辑和增强提供卓越的功能。这款软件利用先进的算法和深度学习技术&#xff0c;能够自动识别和分析视频中的各个元素&#xff0c;并进行智能修复和增强&…