京东测开笔试题_qq_38131333的博客-程序员宅基地

技术标签: 括号匹配方案  刷题  输出最短字符串  

1. 给定一个字符串s, 请计算输出含有连续两个s作为子串的最短字符串。 注意两个s可能有重叠部分。例如,"ababa"含有两个"aba".

输入描述 :

输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 50),s中每个字符都是小写字母.

输出描述:

输出一个字符串,即含有连续两个s作为子串的最短字符串。

输入例子1:

abracadabra

输出例子2:

abracadabracadabra

代码实现:

#include<iostream>
#include<string>
using namespace std;

int main(){
    string s;
    cin >> s;
    int i=0,j=1;
    int len = s.size();
    while(j<len){
        if(s[i] != s[j])
            j++;
        else{
            while(j<len && s[i] == s[j]){
                i++;
                j++;
            }
            if(j>=len)
                break;
            else
                i = 0;
        }
    }
    string s2 = s.substr(i);
    cout<< s << s2 <<endl;
    return 0;
}

2.括号匹配方案

合法的括号匹配序列被定义为:
1. 空串""是合法的括号序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
3. 如果"X"是一个合法的序列,那么"(X)"也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成
例如"", "()", "()()()", "(()())", "(((())))"都是合法的。 东东现在有一个合法的括号序列s,一次移除操作分为两步:
1. 移除序列s中第一个左括号
2. 移除序列s中任意一个右括号.保证操作之后s还是一个合法的括号序列
东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空
如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
例如: s = "()()()()()",输出1, 因为每次都只能选择被移除的左括号所相邻的右括号.
s = "(((())))",输出24, 第一次有4种情况, 第二次有3种情况, ... ,依次类推, 4 * 3 * 2 * 1 = 24

输入描述:

输入包括一行,一个合法的括号序列s,序列长度length(2 ≤ length ≤ 20).

输出描述:

输出一个整数,表示方案数

输入例子1:

(((())))

输出例子1:

24

代码实现:

#include<iostream>
#include<string>
#include<stack>
using namespace std;

int main(){
    string input;
    cin>>input;
    stack<int> in;
    int output=1;
    int len = input.size();
    for(int i=0;i<len;i++)
    {
        if(input[i]=='(')
            in.push(input[i]);
        else{
            output = output*in.size();
            in.pop();
        }
    }
    cout<< output <<endl;
    return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38131333/article/details/82558369

智能推荐

Docker安装graylog和详解_kkagr的博客-程序员宅基地

1、安装graylog1、创建目录/usr/local/graylog 注意自己服务器的id该目录下新建文件 graylog.yml 或者 compose.yml写入内容:version: '2'services: # MongoDB: https://hub.docker.com/_/mongo/ mongodb: image: mongo:3 # Elastic...

k8s集群上clickhouse集群的简单使用_qq_38196982的博客-程序员宅基地_clickhouse k8s

假设集群名字为cluster11.下载数据集curl https://datasets.clickhouse.tech/hits/tsv/hits_v1.tsv.xz | unxz --threads=`nproc` &gt; hits_v1.tsvcurl https://datasets.clickhouse.tech/visits/tsv/visits_v1.tsv.xz | unxz --threads=`nproc` &gt; visits_v1.tsv连接数据库clickh

使用Rocket chip generator配置和生成RISC-V RTL代码_远古架构师alanwu的博客-程序员宅基地_rtl代码自动生成

一、代码同步和环境准备Rocket chip generator可以生成三种目标代码:高性能时钟周期精确的验证器、基于FPGA版的RTL代码和可综合版的RTL代码。生成需要用到Chisel工具和JAVA环境,之前文章已经写过怎么同步好代码和环境,参考:https://blog.csdn.net/heyuming20062007/article/details/120544437?spm=1001.2014.3001.5501https://blog.csdn.net/heyuming20062007

简析 addToBackStack使用和Fragment执行流程_weixin_34064653的博客-程序员宅基地

在使用Fragment的时候我们一般会这样写:        FragmentTransaction transaction = getSupportFragmentManager().beginTransaction();        transaction.replace(R.id.content_view, fragment, fragment.getClass().getName()...

成功解决Error: failed to normalize chaincode path: ‘go list‘ failed with: go: github.com/golang/protobuf_余府的博客-程序员宅基地

在fabric-sample中部署链码时报错,报错原因是下载依赖的连接被拒绝,如下所示Error: failed to normalize chaincode path: 'go list' failed with: go: github.com/golang/[email protected]: Get "https://proxy.golang.org/github.com/golang/protobuf/@v/v1.3.2.mod": dial tcp 172.217.160.81:443: conne

Java 8 Lambda 表达式_荆轲刺秦的博客-程序员宅基地_java8 lambda表达式

本文介绍了 Lambda 表达式以及方法引用这 Java 8 的两大亮点,赶紧学习起来吧!

随便推点

报表问题~~只有这么多分了~~~~-_-~_aibi9196的博客-程序员宅基地

报表问题~~只有这么多分了~~~~-_-~ VCL组件开发及应用http://www.delphi2007.net/DelphiVCL/html/delphi_20061226124437110.html用的是acreport,有两个数据集,adoquery1(主表),bill_sf(从表) 现在在设计报表时想实现这样的功能,在报表中要添加这两个数据集, ...

基于四系统的文本分类(TextClassify_FourSystems)_月逝天的博客-程序员宅基地

基于四系统的文本分类(TextClassify_FourSystems)说明环境数据Train最后说明本文主要是实现NLP文本分类任务,目前该系统为四系统融合模型,其中包括基于字向量char的CNN模型、RCNN模型 以及 基于词向量word2vec的CNN模型、RCNN模型。目前的融合规则采用权值平均法进行融合。github:环境python3tensorflow数据所使用的数据为网上的cnews数据,共10个类别,分为训练集,验证集和测试集。 类别如下:体育, 财经, 房产, 家居,

SandboxEscaper又爆出严重零时差漏洞_weixin_34092370的博客-程序员宅基地

2019独角兽企业重金招聘Python工程师标准&gt;&gt;&gt; ...

基准电路学习_xcn wz的博客-程序员宅基地

基准电路电压基准电压基准模拟电路至高境界:PVT(Process工艺,Voltage电压,Temperature温度)用偏置电路解决电压问题,用基准电路解决温度问题(补偿)Bandgap Voltage Reference(BGR)BGR电路结构:{VM电压模I−V,电压叠加CM电流模V−I,电流叠加\begin{cases}VM &amp; 电压模 I-V,电压叠加\\CM &amp; 电流模V-I,电流叠加\end{cases}{VMCM​电压模I−V,电压叠加电流模V−I,电流叠加​ht

【C#】——注册表技术(一)_苦荼冬生的博客-程序员宅基地_c# 注册表

注册表技术注册表是一个庞大的数据库系统,它记录了用户安装在计算机上的软件、硬件信息和每一个程序的相互关系。注册表中存放着很多参数,直接控制着整个系统的启动、硬件驱动程序的装载以及应用程序的运行。Windows 注册表概述    Windows 注册表包含Windows 安装、用户喜好以及已安装软件和设备的所有配置信息的核心存储库。现在商用软件基本上都使用注册表来存储这些信息,COM 组件必须把他的...

JAVAWeb分页功能实现_William_GJIN的博客-程序员宅基地_javaweb分页前端实现

当管理成百上千条数据,并在列表显示时,数据全部放在一页显示效率低而且加载速度会变慢。这时就需要将数据分页显示。示例:具体思路为,编写 PageBean 获取总的记录数、每页显示条数和当前页码,并通过计算获取总页码数。并按页获取数据存入 list,每次点下一页获取之后的数据,每次点前一页显示之前的数据,根据当前页码和每页显示数,多次获取列表数据并显示。并要注意下一页上一页功能可能出现的bug。...

推荐文章

热门文章

相关标签