`
java-mans
  • 浏览: 11342861 次
文章分类
社区版块
存档分类
最新评论

【100题】第四十六题 括号匹配

 
阅读更多

一,题目

四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())

二,解答

解法一:左右括号成一对则抵消

可以将左括号看成1右括号看成 -1,然后对8个数进行全排列

对每个排列判断,是否符合条件,逐个相加,sum>=0直到遍历完该序列,符合条件则count++

如果出现sum<0则失败

解法二:采用八位bit,从0000 0000 1111 1111遍历,遇到0 -1遇到1 1

如果加完该序列所有位等于0,且递加过程中sum始终大于零则符合条件

三,源码


#include<iostream>
#include <vector>
using namespace std ;
void Print(vector<char> v)
{
	for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg)
		cout<<*beg<<" ";
	cout<<endl;
}
void MatchNums(int nSize,int nLen,vector<char> &v)
{
	int nLeftBrackets=0;
	int nRightBrackets=0;
	for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg)
	{
		if(*beg=='(')
			nLeftBrackets++;
		else
			nRightBrackets++;
		if(nRightBrackets>nLeftBrackets)
			return;
		if(nLeftBrackets+nRightBrackets==nSize&&nLeftBrackets==nRightBrackets)
			Print(v);
	}
	
	if (nLen>0)
	{
		v.push_back('(');
		MatchNums(nSize,nLen-1,v);
		v.pop_back();
		v.push_back(')');
		MatchNums(nSize,nLen-1,v);
		v.pop_back();
	}
}
int main()
{
	vector <char> v;
	int n=4;
	MatchNums(n,n,v);
	return 1;
}


分享到:
评论

相关推荐

    汇编语言_期末考试_试题.

    一、单项选择题(本大题共20小题,每小题1分,共20分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.CPU要访问的某一存储单元的实际地址称...

    数据结构实验.rar

    3、(必做题)请实现:对于一个可能包括括号{}、[]、()的表达式,判定其中括号是否匹配。 实验六: 1、(必做题)假设二叉树中数据元素类型是字符型,请采用二叉链表实现二叉树的以下基本操作: (1)根据二叉树的...

    learn_code

    LeetCode LeetCode编程题集第二题:两数相加中等第三题:无重复字符的最长子串中等第四题:寻找两个有序分段的中位数困难第五题:最长回文子串中等第六题:Z字形变换中等第七题:二次反转简单第八题:字符串转换整体...

    世界500强面试题.pdf

    1.5.9. 四对括号可以有多少种匹配排列方式.................................................124 1.5.10. 输入一个正数 n,输出所有和为 n 连续正数序列 ................................125 1.6. 面试题集合(五...

    perl语言脚本文档说明

    第6学时 模式匹配 64 6.1 简单的模式 64 6.2 元字符 66 6.2.1 一个简单的元字符 66 6.2.2 非输出字符 66 6.2.3 通配符 66 6.2.4 字符类 68 6.2.5 分组和选择 69 6.2.6 位置通配符 69 6.3 替换 70 6.4 练习...

    24日学好Perl语言

    第6学时 模式匹配 64 6.1 简单的模式 64 6.2 元字符 66 6.2.1 一个简单的元字符 66 6.2.2 非输出字符 66 6.2.3 通配符 66 6.2.4 字符类 68 6.2.5 分组和选择 69 6.2.6 位置通配符 69 6.3 替换 70 6.4 练习:清除输入...

    PERL编程24学时教程.pdf

    第6学时 模式匹配 64 6.1 简单的模式 64 6.2 元字符 66 6.2.1 一个简单的元字符 66 6.2.2 非输出字符 66 6.2.3 通配符 66 6.2.4 字符类 68 6.2.5 分组和选择 69 6.2.6 位置通配符 69 6.3 替换 70 6.4 练习:清除输入...

    perl学习文档

    第6学时 模式匹配 64 6.1 简单的模式 64 6.2 元字符 66 6.2.1 一个简单的元字符 66 6.2.2 非输出字符 66 6.2.3 通配符 66 6.2.4 字符类 68 6.2.5 分组和选择 69 6.2.6 位置通配符 69 6.3 替换 70 6.4 练习:清除输入...

    Perl编程24学时教程(PDF格式,共24章)

    第一部分主要讲述Perl的基本概念,第二部分重点介绍Perl的一些高级特性,第三部分介绍如何使用Perl进行CGI编程,第四部分(即附录)讲述如何在不同的操作系统下安装Perl的各个模块。 本书结构清晰,讲解透彻,通俗易懂...

    PERL编程24学时教程

    第6学时 模式匹配 64 6.1 简单的模式 64 6.2 元字符 66 6.2.1 一个简单的元字符 66 6.2.2 非输出字符 66 6.2.3 通配符 66 6.2.4 字符类 68 6.2.5 分组和选择 69 6.2.6 位置通配符 69 6.3 替换 70 6.4 练习:清除输入...

    perl编程24学时教程.rar

    第一部分主要讲述Perl的基本概念,第二部分重点介绍Perl的一些高级特性,第三部分介绍如何使用Perl进行CGI编程,第四部分(即附录)讲述如何在不同的操作系统下安装Perl的各个模块。 本书结构清晰,讲解透彻,通俗易懂...

    leetcode题库-leetcodeindex:容易查找leetcode问题以及难度

    正则表达式匹配 27.00% 难的 11 盛水最多的容器 51.40% 中等的 12 整数转罗马 55.50% 中等的 13 罗马到整数 56.10% 简单的 14 最长公共前缀 35.70% 简单的 15 3总和 27.20% 中等的 16 3和最近 46.10% 中等的 17 电话...

    java 面试题 总结

    JAVA相关基础知识 1、面向对象的特征有哪些方面 1.抽象: 抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题,而只是选择其中的一部分,暂时不用...

    Word常用查找与替换实例及方法

    实例35:批量替换选择题选项四行为一行 22 实例36:选择题选项对齐 23 实例37:如何使括号内的文字不显示(显示为白色) 24 实例38:巧制试卷填空题 25 实例39:化学分子式的处理 26 实例40:英文直引号替换为中文...

    C#微软培训资料

    第十六章 组织应用程序 .198 16.1 基 本 概 念 .198 16.2 使用名字空间 .200 16.3 使用指示符 .203 16.4 程 序 示 例 .206 16.5 小 结 .213 第十七章 文 件 操 作 .215 17.1 .Net 框架结构提供的 I/O ...

    C程序范例宝典(基础代码详解)

    实例102 括号匹配检测 141 实例103 用栈及递归计算多项式 143 实例104 链队列 144 实例105 循环缓冲区问题 147 3.4 串与广义表 149 实例106 串的模式匹配 149 实例107 简单的文本编辑器 151 实例108 ...

    JAVA WEB 开发详解:XML+XSLT+SERVLET+JSP 深入剖析与实例应用.part2

    第3章 对xml文档进行分析 46 3.1 dom、sax和jaxp 46 3.2 使用dom解析xml文档 47 3.2.1 dom结构模型 47 3.2.2 dom解析器工厂 50 3.2.3 jaxp的错误类和异常类 52 3.2.4 用dom解析xml文档实例 53 3.3 使用sax...

    JAVA WEB 开发详解:XML+XSLT+SERVLET+JSP 深入剖析与实例应用.part5

    第3章 对xml文档进行分析 46 3.1 dom、sax和jaxp 46 3.2 使用dom解析xml文档 47 3.2.1 dom结构模型 47 3.2.2 dom解析器工厂 50 3.2.3 jaxp的错误类和异常类 52 3.2.4 用dom解析xml文档实例 53 3.3 使用sax...

Global site tag (gtag.js) - Google Analytics