生成n对括号的所有合法排列-阿里云开发者社区

开发者社区> 技术mix呢> 正文

生成n对括号的所有合法排列

简介:
+关注继续查看

实例

n = 3,所有的合法序列

((()))  (()()) (())() ()(()) ()()()     

思路

针对一个长度为2n的合法排列,第1到2n个位置都满足如下规则

1
左括号的个数≥右括号的个数

所以,我们就可以按照这个规则去打印括号

假设在位置k我们还剩余left个左括号和right个右括号

  • 如果left和right均为零,则说明我们已经完成一个合法排列,可以将其打印出来
  • 如果left>0,打印左括号
  • 如果right>0 并且 right>left 打印右括号

针对n=2,问题的解空间如下:

参考代码

复制代码
vector<string> generateParenthesis(int n) 
{
    vector<string> ans;
    generate(n, n, "", ans);
    return ans;
}
void generate(int leftNum, int rightNum, string s, vector<string> &result)  
{  
    if(leftNum == 0 && rightNum == 0)  
    {  
        result.push_back(s);  
    }  
    if(leftNum > 0)  
    {  
        generate(leftNum-1, rightNum, s+'(', result);  
    }  
    if(rightNum > 0 && leftNum < rightNum)  
    {  
        generate(leftNum, rightNum-1, s+')', result);  
    }  
} 
复制代码

扩展

该问题和《编程之美》的买票找零问题一样:2n个人排队买票,其中n个人持50元,n个人持100元。每张票50元,且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序,不至于使售票处找不开钱?

可以把50块钱看成(,100块钱看成)。只有(始终大于等于)才可以找开钱。

结论

 





本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/p/3836757.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
6915 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
2854 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4485 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7758 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
9426 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
5458 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
2141 0
+关注
2968
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载