首页 / 算法 / 算法 - 堆栈类和嵌套循环实例运用
算法 - 堆栈类和嵌套循环实例运用
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法 - 堆栈类和嵌套循环实例运用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3603字，纯文字阅读大概需要6分钟。
内容图文
最近碰到两个算法题，觉得比较有代表性，特记录分享如下：
题1： 给定一个整形数字，求一串数字，这串数字需要满足相加等于这个给定的数字，且这串数字必须顺序排列。
题2： 有一个字符串，判断字符串内的括号(大括号，小括号，中括号，尖括号等等)是全闭合的，也就是说一个正括号后必须是相同括号类型的反括号，比如{{[]}}是合法的，({])是非法，括号中可夹杂数字，字母。
开始拿到第一个题目，首先就想到了和冒泡算法有点类似，原理又有些不同。
第一个和后面数字依次相加，直到和等于给定数字就把所有加数转成字符串输出，然后第二个数和后面数字依次相加直到和等于给定数字就把所有加数转成字符串输出，
如此循环直到第一个加数大于等于给定数字。
下面是具体实现代码：
1. 根据参数a初始化一个长度为a的数组，数组从1开始。
2. 取第一个数和后面数相加，如何和等于a则将加数存放在list容器。
public List<String> a (int a) {
int[] arr=newint[a];
for (int i=0; i<a;i++){
arr[i]=i+1;
}
List<String> strList = new ArrayList<String>();
for (int i = 1; i < arr.length; i++) {
int sum = i;
String str = i + ",";
for (int j = i+1; j < arr.length; j++) {
sum += j;
str += j + ",";
if (sum == a) {
strList.add(str);
}
}
}
return strList;
}
第二个题目刚开始拿到时不知道如何处理，首先想到的是创建三个list容器来存放三种括号，然后将字符串转换成char一个个遍历，如果碰到正括号就直接存入容器，碰到反括号就去容器验证最后一个是不是正括号，乍一看感觉没问题于是开始写代码。
写着写着发现哪里不对劲，仔细一想这种方法不能识别各种括号的位置关系，只能判断正括号和反括号是不是成对出现，比如[(])这种会被程序识别为合法，其实这种是非法的。
于是，冷静下来重新思考，突然灵光一现，可以利用堆栈类来处理啊，碰到正括号就压入栈顶，碰到反括号就判断栈顶是不是相同类型的正括号，是就移除栈顶元素，最后判断栈是否为空，为空则返货valid，否则返回invalid。
于是开始写代码，调试，结果却悲剧了，提示错误，重新review代码，无果。查看错误信息peek是unknown source，初步判断是堆栈类哪个地方出问题了。
public
void
check1(String s) {
Stack<Character> sc=new Stack<Character>();
char[] c=s.toCharArray();
for (int i = 0; i < c.length; i++) {
if (c[i]==‘(‘||c[i]==‘[‘||c[i]==‘{‘) {
sc.push(c[i]);
}
elseif (c[i]==‘)‘) {
if (sc.peek()==‘(‘) {
sc.pop();
}
}elseif (c[i]==‘]‘) {
if (sc.peek()==‘[‘) {
sc.pop();
}
}elseif (c[i]==‘}‘) {
if (sc.peek()==‘{‘) {
sc.pop();
}
}
}
if (sc.empty()) {
System.out.println("valid");
}else {
System.out.println("not valid");
}
}
Exception in thread "main" java.util.EmptyStackException at java.util.Stack.peek(Unknown Source) at Sum.check1(Sum.java:68) at Sum.main(Sum.java:91)
苦思不得解，于是上网查资料发现是由于堆栈是空导致peek报错。重新review代码，发现是由于遇到反括号时堆栈为空，而此时代码执行peek导致出错。
找到问题原因就好办了，马上在遇到反括号时检查堆栈是否为空，为空则将反括号压入堆栈然后退出循环，否则执行peek。
重新运行代码，问题成功修复！
public
void
check(String s) {
Stack<Character> sc=new Stack<Character>();
char[] c=s.toCharArray();
for (int i = 0; i < c.length; i++) {
if (c[i]==‘(‘||c[i]==‘[‘||c[i]==‘{‘) {
sc.push(c[i]);
}
elseif (c[i]==‘)‘) {
if (sc.empty()) {sc.push(c[i]); continue;}
elseif (sc.peek()==‘(‘) {
sc.pop();
}
}elseif (c[i]==‘]‘) {
if (sc.empty()) {sc.push(c[i]); continue;}
elseif (sc.peek()==‘[‘) {
sc.pop();
}
}elseif (c[i]==‘}‘) {
if (sc.empty()) {sc.push(c[i]); continue;}
elseif (sc.peek()==‘{‘) {
sc.pop();
}
}
}
if (sc.empty()) {
System.out.println("String \""+s+"\" is valid");
// System.out.println(sc.size());
}else {
System.out.println("String \""+s+"\" is not valid");
// System.out.println(sc.size()); }
}
测试和结果：
public
static
void
main(String[] args){
Sum test = new Sum();
//当第一个字符就是反括号：
test.check(")");
test.check("]");
test.check("}");
test.check("[]");
test.check("[a(d(dwe)we)we{we[wew]we}we]");
test.check1("(s[d]s{d}sss)");
System.out.println(test.a(15));
System.out.println(test.a(5000));
}
String ")" is not valid String "]" is not valid String "}" is not valid String "[]" is valid String "[a(d(dwe)we)we{we[wew]we}we]" is valid valid [1,2,3,4,5,, 4,5,6,, 7,8,] [23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,, 188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,, 305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,, 998,999,1000,1001,1002,]
原文：http://www.cnblogs.com/clarke157/p/7017075.html
内容总结
以上是互联网集市为您收集整理的算法 - 堆栈类和嵌套循环实例运用全部内容，希望文章能够帮你解决算法 - 堆栈类和嵌套循环实例运用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。