栈的java实现和栈的应用举例 - coolxing - ITeye技术网站
博客分类：
[例子和习题出自数据结构(严蔚敏版), 本人使用java进行实现.
转载请注明作者和出处,
如有谬误, 欢迎在评论中指正. ]
栈是一种先进后出的数据结构, 首先定义了栈需要实现的接口:
public interface MyStack&T& {
* 判断栈是否为空
boolean isEmpty();
void clear();
* 栈的长度
int length();
* 数据入栈
boolean push(T data);
* 数据出栈
栈的数组实现, 底层使用数组:
public class MyArrayStack&T& implements MyStack&T& {
private Object[] objs = new Object[16];
private int size = 0;
public boolean isEmpty() {
return size == 0;
public void clear() {
// 将数组中的数据置为null, 方便GC进行回收
for (int i = 0; i & i++) {
objs[size] =
public int length() {
public boolean push(T data) {
// 判断是否需要进行数组扩容
if (size &= objs.length) {
objs[size++] =
* 数组扩容
private void resize() {
Object[] temp = new Object[objs.length * 3 / 2 + 1];
for (int i = 0; i & i++) {
temp[i] = objs[i];
@SuppressWarnings("unchecked")
public T pop() {
if (size == 0) {
return (T) objs[--size];
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("MyArrayStack: [");
for (int i = 0; i & i++) {
sb.append(objs[i].toString());
if (i != size - 1) {
sb.append(", ");
sb.append("]");
return sb.toString();
栈的链表实现, 底层使用链表:
public class MyLinkedStack&T& implements MyStack&T& {
* 栈顶指针
* 栈的长度
public MyLinkedStack() {
public boolean isEmpty() {
return size == 0;
public void clear() {
public int length() {
public boolean push(T data) {
Node node = new Node();
node.data =
node.pre =
// 改变栈顶指针
public T pop() {
if (top != null) {
Node node =
// 改变栈顶指针
top = top.
return node.
* 将数据封装成结点
private final class Node {
两种实现的比较, 主要比较数据入栈和出栈的速度:
public void testSpeed() {
MyStack&Person& stack = new MyArrayStack&Person&();
int num = ;
long start = System.currentTimeMillis();
for (int i = 0; i & i++) {
stack.push(new Person("xing", 25));
long temp = System.currentTimeMillis();
System.out.println("push time: " + (temp - start));
while (stack.pop() != null)
System.out.println("pop time: " + (System.currentTimeMillis() - temp));
MyArrayStack中入栈和出栈10,000,000条数据的时间:
push time: 936
pop time: 47
将MyArrayStack改为MyLinkedStack后入栈和出栈的时间:
push time: 936
pop time: 126
可见两者的入栈速度差不多, 出栈速度MyArrayStack则有明显的优势.
为什么测试结果是这样的? 可能有些朋友的想法是数组实现的栈应该具有更快的遍历速度, 但增删速度应该比不上链表实现的栈才对. 但是栈中数据的增删具有特殊性: 只在栈顶入栈和出栈. 也就是说数组实现的栈在增加和删除元素时并不需要移动大量的元素, 只是在数组扩容时需要进行复制. 而链表实现的栈入栈和出栈时都需要将数据包装成Node或者从Node中取出数据, 还需要维护栈顶指针和前驱指针.
栈的应用举例
1. 将10进制正整数num转换为n进制
private String conversion(int num, int n) {
MyStack&Integer& myStack = new MyArrayStack&Integer&();
Integer result =
while (true) {
// 将余数入栈
myStack.push(result % n);
result = result /
if (result == 0) {
StringBuilder sb = new StringBuilder();
// 按出栈的顺序倒序排列即可
while ((result = myStack.pop()) != null) {
sb.append(result);
return sb.toString();
2. 检验符号是否匹配. '['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的.
遍历字符串的每一个char, 将char与栈顶元素比较. 如果char和栈顶元素配对, 则char不入栈, 否则将char入栈. 当遍历完成时栈为空说明字符串是合法的.
public boolean isMatch(String str) {
MyStack&Character& myStack = new MyArrayStack&Character&();
char[] arr = str.toCharArray();
for (char c : arr) {
Character temp = myStack.pop();
// 栈为空时只将c入栈
if (temp == null) {
myStack.push(c);
// 配对时c不入栈
else if (temp == '[' && c == ']') {
// 配对时c不入栈
else if (temp == '(' && c == ')') {
// 不配对时c入栈
myStack.push(temp);
myStack.push(c);
return myStack.isEmpty();
3. 行编辑: 输入行中字符'#'表示退格, '@'表示之前的输入全都无效.
使用栈保存输入的字符, 如果遇到'#'就将栈顶出栈, 如果遇到@就清空栈. 输入完成时将栈中所有字符出栈后反转就是输入的结果:
private String lineEdit(String input) {
MyStack&Character& myStack = new MyArrayStack&Character&();
char[] arr = input.toCharArray();
for (char c : arr) {
if (c == '#') {
myStack.pop();
} else if (c == '@') {
myStack.clear();
myStack.push(c);
StringBuilder sb = new StringBuilder();
Character temp =
while ((temp = myStack.pop()) != null) {
sb.append(temp);
// 反转字符串
sb.reverse();
return sb.toString();
浏览 22281
draem0507 写道
public T pop() {
if (size == 0) {
T t=(T) objs[--size]；
objs[--size]=
--size 进行了两次应该有问题吧
public T pop() {
if (size == 0) {
T t=(T) objs[--size]；
objs[size]=
楼主每次都是尽可能的置null吗，应该是一个好习惯吧pop本来就是弹出对象的时候,把栈里头的对象也一并清楚。平时对象一般不管的哈
public T pop() {
if (size == 0) {
T t=(T) objs[--size]；
objs[--size]=
--size 进行了两次应该有问题吧
public T pop() {
if (size == 0) {
T t=(T) objs[--size]；
objs[size]=
楼主每次都是尽可能的置null吗，应该是一个好习惯吧
浏览: 370880 次
来自: 北京
浏览量：47376
vvv_110 写道简单明了
通俗易懂，很不错。已经安装完毕。。
hapjin 写道lz，请问下，“ 如果java中的锁不是可重 ...
lz，请问下，“ 如果java中的锁不是可重入的，那么调用Lo ...posts - 389,&
comments - 31,&
trackbacks - 0
随笔分类 - 数据结构+算法
摘要: URLEncode： 用于编码URL字符串，数字和字母保持不变，空格变为'+'，其他（如：中文字符）先转换为十六进制表示，然后在每个字节前面加一个标识符%，例如：“啊”字 Ascii的十六进制是0xB0A1——&%B0%A1代码实现： 1 unsigned char CHAR_TO_HEX( un...
可笑痴狂 阅读(66) |
摘要: Base64编码说明 Base64编码要求把3个8位字节（3*8=24）转化为4个6位的字节（4*6=24），之后在6位的前面补两个0，形成8位一个字节的形式。 如果剩下的字符不足3个字节，则用0填充，输出字符使用'='，因此编码后输出的文本末尾可能会出现1或2个'='。 为了保证所输出的编码位...
可笑痴狂 阅读(110) |
摘要: 郁闷的C小加（二）时间限制：1000 ms | 内存限制：65535 KB难度：4描述聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换（详情请参考“郁闷的C小加（一）”），C小加很高兴。但C小加是个爱思考的人，他又想通过这种方法计算一个表达式的值。即先把表达式转换为后缀表达式，再求值。这时又要考虑操作数是小数和多位数的情况。输入第一行输入一个整数T，共有T组测试数据（T 2 #include 3 #include 4 #include 5 #include 6 7 8 9 char str[1005]; 10 stack...
可笑痴狂 阅读(198) |
摘要: 范围统计问题（参考刘汝佳《算法竞赛入门经典》P146）问题描述： 给出 n 个整数和 m 次询问，对于每次询问 (a, b), 输出闭区间 [a, b] 内的整数的个数分析： 预处理： 把数据存在数组里并从小到大排序 问题一： 大于等于 a 的第一个元素的下标 L 是什么？ 它等于 a 的lower_bound 值。 如果所有元素都小于a，则 L = n，相当于把不存在的元素看做无穷大。 问题二： 小于等于b 的最后一个元素的 &下一个下标& R 是什么？ 它等于 b 的...
可笑痴狂 阅读(76) |
摘要: 目标:学会用猜数字（二分）的方法，换个角度来解决问题(参考刘汝佳的&&算法入门经典&&P151)问题描述： 把一个包含n个正整数的序列划分成m个连续的子序列（每个正整数恰好属于一个序列）。 设第i个序列的各数之和为S(i)，你的任务是让所有S(i)的最大值尽量小。 例如序列1 2 3 2 5 4划分为3个子序列的最优方案为 1 2 3 | 2 5 | 4， 其中S(1),S(2),S(3)分别为6，7，4，那么最大值为7； 如果划分为 1 2 | 3 2 | 5 4，则最大值为9，不是最小。问题分析： 能否使m个连续子序列所有的s(i)均不超过x，则该命题成立的最小的x
可笑痴狂 阅读(193) |
摘要: 校园网络时间限制：3000 ms | 内存限制：65535 KB难度：5描述南阳理工学院共有M个系，分别编号1~M,其中各个系之间达成有一定的协议，如果某系有新软件可用时，该系将允许一些其它的系复制并使用该软件。但该允许关系是单向的，即：A系允许B系使用A的软件时，B未必一定允许A使用B的软件。现在，请你写一个程序，根据各个系之间达成的协议情况，计算出最少需要添加多少个两系之间的这种允许关系，才能使任何一个系有软件使用的时候，其它所有系也都有软件可用。输入第一行输入一个整数T，表示测试数据的组数(T&10)每组测试数据的第一行是一个整数M，表示共有M个系(2&=M&=100)
可笑痴狂 阅读(446) |
摘要: 求逆序数时间限制：2000ms | 内存限制：65535KB难度：5描述在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。比如 1 3 2 的逆序数就是1。输入第一行输入一个整数T表示测试数据的组数（1&=T&=5)每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）随后的一行共有N个整数Ai(0&=Ai&)，表示数列中的所有元素。数据保证在多组测试数据中，多于10万个数
可笑痴狂 阅读(199) |
摘要: 算法合集之《信息学中守恒法的应用》（不错的文章保存一下）by三江小渡【摘要】本文提出和总结了“守恒法”，以及它在信息学竞赛中的一些应用。守恒的本质是寻找变化中的不变量。守恒法能帮助我们跳过、避开纷繁复杂的细节，直接看透问题的本质。【关键字】守恒法 不变量【正文】一、 引言现实生活和实际问题是纷繁复杂的。问题1 两个质量相等的小球，速度分别为5m/s, 4m/s，他们相向运动，完全弹性碰撞之后速度分别变成多少？问题2 10g C 和10g O2在密闭容器中反应一个小时。最后的总质量是多少？问题1 我们大概耳熟能详：动量守恒、动能守恒，两个方程就能解出速度。实际上小球碰撞的过程是复杂的，究竟两对力
可笑痴狂 阅读(1218) |
摘要: RPG的错排Time Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 4631Accepted Submission(s): 1895Problem Description今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜，第一次猜：R是公主，P是草儿，G是月野兔；第二次猜：R是草儿，P是月野兔，G是公主；第三次猜：R是草儿，P是公主，G是月野兔；......
可笑痴狂 阅读(160) |
摘要: 选课时间(题目已修改,注意读题)Time Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 1857Accepted Submission(s): 1493Problem Description又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知道学n个学分共有多少组合。你来帮帮他吧。（xhd认为一样学分的课没区别）Input输入数据的第一行是一个数据T，表示有T组数据。每组数据的第一行是两个整数n(1 6 #include 7 ...
可笑痴狂 阅读(128) |
摘要: 人见人爱A^BTime Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 13930Accepted Submission(s): 9852Problem Description求A^B的最后三位数表示的整数。说明：A^B的含义是“A的B次方”Input输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1&=A,B&=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。Output对于每个测试实例，请输出A^B的
可笑痴狂 阅读(252) |
摘要: fibonacci数列(二)时间限制：1000ms | 内存限制：65535KB难度：3描述In the Fibonacci integer sequence,F0= 0,F1= 1, andFn=Fn- 1+Fn- 2forn≥ 2. For example, the first ten terms of the Fibonacci sequence are:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …An alternative formula for the Fibonacci sequence is.Given an integern, your goal is
可笑痴狂 阅读(170) |
摘要: 三个水杯时间限制：1000ms | 内存限制：65535KB难度：4描述给出三个水杯，大小不一，并且只有最大的水杯的水是装满的，其余两个为空杯子。三个水杯之间相互倒水，并且水杯没有标识，只能根据给出的水杯体积来计算。现在要求你写出一个程序，使其输出使初始状态到达目标状态的最少次数。输入第一行一个整数N(0&N&50)表示N组测试数据接下来每组测试数据有两行，第一行给出三个整数V1 V2 V3 (V1&V2&V3 V1&100 V3&0)表示三个水杯的体积。第二行给出三个整数E1 E2 E3 （体积小于等于相应水杯体积）表示我们需要的最终状态输出每行输出相应测
可笑痴狂 阅读(1035) |
摘要: 输入n输出1到n这个集合中包含的所有子集/*//方法一：//思路：构造一个位向量visit，而不是直接构造子集A本身#include&iostream&void fun(int *visit, int cur, int n){ if(cur == n+1) { for(int i = 1;i &=++ i) if(visit[i]) cout && i && ' '; cout&& } visit[cur]...
可笑痴狂 阅读(1229) |
摘要: Anniversary partyTime Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 2225Accepted Submission(s): 963Problem DescriptionThere is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical struc
可笑痴狂 阅读(187) |
摘要: Jungle RoadsTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 15610Accepted: 6988DescriptionThe Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so
可笑痴狂 阅读(532) |
摘要: 懒省事的小明时间限制：3000 ms | 内存限制：65535 KB难度：3描述 小明很想吃果子，正好果园果子熟了。在果园里，小明已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。小明决定把所有的果子合成一堆。 因为小明比较懒，为了省力气，小明开始想点子了: 每一次合并，小明可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。小明在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以小明在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的...
可笑痴狂 阅读(124) |
摘要: 擅长排列的小明时间限制：1000 ms | 内存限制：65535 KB难度：4描述小明十分聪明，而且十分擅长排列计算。比如给小明一个数字5，他能立刻给出1-5按字典序的全排列，如果你想为难他，在这5个数字中选出几个数字让他继续全排列，那么你就错了，他同样的很擅长。现在需要你写一个程序来验证擅长排列的小明到底对不对。输入第一行输入整数N（1&N&10）表示多少组测试数据，每组测试数据第一行两个整数 n m (1&n&9,0&m&=n)输出在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例样例输入23 14 2样例输出
可笑痴狂 阅读(152) |
摘要: Flying to the MarsTime Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 6271Accepted Submission(s): 2053Problem DescriptionIn the year 8888, the Earth is ruled by the PPF Empire . As the population growing , PPF needs to find more land for the newborns .
可笑痴狂 阅读(385) |
摘要: QuestionsTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 1096Accepted: 394DescriptionHolding a collegiate programming contest is a very exhausting work. There is a well-known proverb that one fool can ask so many questions that a hundred clever men will not answer. And during a collegiate p
可笑痴狂 阅读(117) |
摘要: 郁闷的C小加（一）时间限制：1000 ms | 内存限制：65535 KB难度：3描述我们熟悉的表达式如a+b、a+b*(c+d)等都属于中缀表达式。中缀表达式就是（对于双目运算符来说）操作符在两个操作数中间：num1 operand num2。同理，后缀表达式就是操作符在两个操作数之后：num1 num2 operand。ACM队的“C小加”正在郁闷怎样把一个中缀表达式转换为后缀表达式，现在请你设计一个程序，帮助C小加把中缀表达式转换成后缀表达式。为简化问题，操作数均为个位数，操作符只有+-*/ 和小括号。输入第一行输入T，表示有T组测试数据（T&10）。每组测试数据只有一行，是一个长
可笑痴狂 阅读(96) |
摘要: EntropyTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 3314Accepted: 1323DescriptionAn entropy encoder is a data encoding method that achieves lossless data compression by encoding a message with &wasted& or &extra& information removed. In other words, entropy encoding r
可笑痴狂 阅读(270) |
摘要: 前缀式计算时间限制：1000 ms | 内存限制：65535 KB难度：3描述先说明一下什么是中缀式：如2+(3+4)*5这种我们最常见的式子就是中缀式。而把中缀式按运算顺序加上括号就是：(2+((3+4)*5))然后把运算符写到括号前面就是+(2 *( +(3 4) 5) )把括号去掉就是：+ 2 * + 3 4 5最后这个式子就是该表达式的前缀表示。给你一个前缀表达式，请你计算出该前缀式的值。比如：+ 2 * + 3 4 5的值就是 37输入有多组测试数据，每组测试数据占一行，任意两个操作符之间，任意两个操作数之间，操作数与操作符之间都有一个空格。输入的两个操作数可能是小数，数据保证输入的
可笑痴狂 阅读(222) |
摘要: 表达式求值时间限制：3000 ms | 内存限制：65535 KB难度：3描述Dr.Kong设计的机器人卡多掌握了加减法运算以后，最近又学会了一些简单的函数求值，比如，它知道函数min(20,23)的值是20，add(10,98)的值是108等等。经过训练，Dr.Kong设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式。假设表达式可以简单定义为:1.一个正的十进制数x是一个表达式。2.如果x和y是表达式，则函数min(x,y)也是表达式,其值为x,y中的最小数。3.如果x和y是表达式，则函数max(x,y)也是表达式,其值为x,y中的最大数。4．如果x和y是表达式，则函数add(x,y)也是
可笑痴狂 阅读(628) |
摘要: Fence RepairTime Limit: 2000MSMemory Limit: 65536KTotal Submissions: 15706Accepted: 4998DescriptionFarmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤
可笑痴狂 阅读(533) |
摘要: 1751: E: ExpressionsTime Limit: 2000 ms Memory Limit: 10000 kB Total Submit : 86(18 users)Accepted Submit : 14(13 users)Page View : 2351Font Style: Aa Aa Aa Arithmetic expressions are usually written with the operators in between the two operands (which is called infix notation). For example, (x+y).
可笑痴狂 阅读(101) |
摘要: /* 功能Function Description: 赫夫曼编码---正误待验证(调试时候感觉有地方好像出错了) 开发环境Environment: DEV C++ 4.9.9.1 技术特点Technique: 版本Version: 作者Author: 可笑痴狂 日期Date:
备注Notes: 作用： 输入大写字母组成的字符串，然后以其出现的次数为权重进行编码*/#include&iostream&#incl...
可笑痴狂 阅读(126) |
摘要: 表达式求值时间限制：3000 ms | 内存限制：65535 KB难度：4描述ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）输入第一行输入一个整数n，共有n组测试数据（n&10)。每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。数据保证除数不会为0输出
可笑痴狂 阅读(389) |
摘要: D的小L时间限制：4000 ms | 内存限制：65535 KB难度：2描述 一天TC的匡匡找ACM的小L玩三国杀，但是这会小L忙着哩，不想和匡匡玩但又怕匡匡生气，这时小L给匡匡出了个题目想难倒匡匡(小L很D吧)，有一个数n(0&n&10),写出1到n的全排列，这时匡匡有点囧了，，，聪明的你能帮匡匡解围吗？输入第一行输入一个数N（0&N&10）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个整数x(0&x&10)输出按特定顺序输出所有组合。特定顺序：每一个组合中的值从小到大排列，组合之间按字典序排列。样例输入223样例输出1221123
可笑痴狂 阅读(180) |
摘要: 树的判定时间限制：1000 ms | 内存限制：65535 KB难度：4描述A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.There is exactly one node, called the root, to which no directed edges
可笑痴狂 阅读(121) |
摘要: 1 /* 2 功能Function Description: 约瑟夫问题--猴子选大王 3 开发环境Environment: DEV C++ 4.9.9.1 4 技术特点Technique: 5 版本Version: 6 作者Author: 可笑痴狂 7 日期Date:
备注Notes: 9 题目来源： 10 /practice/274611 *...
可笑痴狂 阅读(147) |
摘要: 1 /* 功能Function Description: POJ-2244 约瑟夫问题 2 开发环境Environment: DEV C++ 4.9.9.1 3 技术特点Technique: 4 版本Version: 5 作者Author: 可笑痴狂 6 日期Date:
备注Notes: 8 题意： 9 编号为1到n，一号先出去，然后向后数第m个人再出去，求最小的m值时期最后剩余的是2号10 ...
可笑痴狂 阅读(65) |
摘要: /* 功能Function Description: 约瑟夫环+枚举 POJ-1012 开发环境Environment: DEV C++ 4.9.9.1 技术特点Technique: 版本Version: 作者Author: 可笑痴狂 日期Date:
备注Notes: 大致题意： 有k个坏人k个好人坐成一圈，前k个为好人（编号1~k），后k个为坏人(编号k+1~2k) 现在有一个报数m，从编号为1的人开始报数，报到m的人就要自动死去。 问...
可笑痴狂 阅读(226) |
摘要: Tree RecoveryTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 7819Accepted: 4947DescriptionLittle Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary trees with capital letters in the nodes. This is an example of one of her creation
可笑痴狂 阅读(69) |
摘要: 括号配对问题时间限制：3000 ms | 内存限制：65535 KB难度：3描述现在，有一行括号序列，请你检查这行括号是否配对。输入第一行输入一个数N（0&N&=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有&[&,&]&,&(&,&)&四种字符输出每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No样例输入3[(])(])([[]()])样
可笑痴狂 阅读(164) |
摘要: 找球号(一）时间限制：3000 ms | 内存限制：65535 KB难度：3描述在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0&=i&=),编号可重复，现在说一个随机整数k(0&=k&=)，判断编号为k的球是否在这堆球中（存在为&YES&,否则为&NO&），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。输入第一行有两个整数m，n(0&=n&=&=m&=1000000)；m表示这堆球里有m
可笑痴狂 阅读(100) |
摘要: 找球号(二）时间限制：1000 ms | 内存限制：65535 KB难度：5描述在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个整数编号i(0&=i&=),编号可重复，还有一个空箱子，现在有两种动作：一种是&ADD&，表示向空箱子里放m(0&m&=100)个球，另一种是&QUERY”，表示说出M(0&M&=100)个随机整数ki(0&=ki&=),分别判断编号为ki 的球是否在这个空箱子中（存在为&YES&,否则为&NO&quot
可笑痴狂 阅读(146) |
摘要: 红黑树时间限制：3000 ms | 内存限制：65535 KB难度：3描述什么是红黑树呢？顾名思义，跟枣树类似，红黑树是一种叶子是黑色果子是红色的树。。。当然，这个是我说的。。。《算法导论》上可不是这么说的：如果一个二叉查找树满足下面的红黑性质，那么则为一个红黑树。1）每个节点或是红的，或者是黑的。2）每个叶子节点(NIL)是黑色的3）如果一个节点是红色的，那么他的两个儿子都是黑的。4）根节点是黑色的。5）对于每个节点，从该节点到子孙节点的所有路径上包含相同数目的黑色节点。我们在整个过程中会用到这些性质，当然，为了公平起见，其实即使你不知道这些性质，这个题目也是可以完成的（为什么不早说。。。。
可笑痴狂 阅读(99) |
摘要: Tempter of the BoneTime Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 35460Accepted Submission(s): 9511Problem DescriptionThe doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, a
可笑痴狂 阅读(496) |
摘要: 汉诺塔（三）时间限制：3000 ms | 内存限制：65535 KB难度：3描述在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。现在我们把三根针编号为1，2，3。所有的金片在初始时都在1号针上，现在给你的任务
可笑痴狂 阅读(101) |
摘要: 畅通工程再续Time Limit:
MS (Java/Others) Memory Limit:
K (Java/Others)Total Submission(s): 6616 Accepted Submission(s): 1977Problem Description相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件...
可笑痴狂 阅读(51) |
摘要: 代码一：普里母算法#include&stdio.h&int map[101][101];int visit[101];int prim(int n);int main(){ int n,m,a,b,i,j; while(~scanf(&%d&,&n)) { for(i=1;i&=n;++i) { visit[i]=0; for(j=1;j&=n;++j) scanf(&%d&,&map[i][j]); } scanf(&%d&,&m); for(i=1;i&=m;++i) { sc
可笑痴狂 阅读(64) |
摘要: http://poj.org/problem?id=1502第一篇C++代码学到几个函数：括号里边都是数组名atof（） 将字符串转换成浮点数值atoi() 将字符串转换成整数值atol() 将字符串转换成长整数值strtod() 将字符串转换成双精度型数值strtol() 将字符串转换成长型数值用迪杰斯特拉求最短路中的最大值#include&iostream&#include&cstring&int G[102][102],dis[102];void dijs(int n){int k,i,j,t,int visit[1
可笑痴狂 阅读(90) |
摘要: 迷宫城堡Time Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 2944Accepted Submission(s): 1264Problem Description为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N&=10000)和M条通道(M&=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请
可笑痴狂 阅读(91) |
摘要: 吝啬的国度时间限制：1000ms |内存限制：65535KB难度：3描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。输入第一行输入一个整数M表示测试数据共有M(1&=M&=5)组每组测试数据的第一行输入一个正整数N(1&=N&=100000)和一个正整数S(1&=S&=100000)，N表示城市的总个数，S表示参观者所在城市的编号随后的N-1行，每行有两个正整数a,b(1&=a,b&lt
可笑痴狂 阅读(57) |
摘要: 布线问题时间限制：1000ms |内存限制：65535KB难度：4描述南阳理工学院要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件：1、把所有的楼都供上电。2、所用电线花费最少输入第一行是一个整数n表示有n组测试数据。(n&5)每组测试数据的第一行是两个整数v,e.v表示学校里楼的总个数(v&=500)随后的e行里，每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c&=100)。（哪两栋楼间如果没有指明花费，则表示这两栋楼直接连通需要费用太大或者不可能连通）随后的1行里，有v个整数,其中第i个数表示从第i号楼接线到外界供电设施
可笑痴狂 阅读(37) |
摘要: 一笔画问题时间限制：3000ms |内存限制：65535KB难度：4描述zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。规定，所有的边都只能画一次，不能重复画。输入第一行只有一个正整数N(N 3 #include 4 int p[1005],visit[1005],G[]; 5 int point, 6 7 void DFS(int i) 8 { 9 int v=i;10 visit[i]=1;11 for(v=0;v 2 #include 3 #include 4 5 ...
可笑痴狂 阅读(290) |
摘要: Eddy's pictureTime Limit:
MS (Java/Others)Memory Limit:
K (Java/Others)Total Submission(s): 3746Accepted Submission(s): 1844Problem DescriptionEddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his smal
可笑痴狂 阅读(155) |
摘要: 吝啬的国度时间限制：1000ms |内存限制：65535KB难度：3描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。输入第一行输入一个整数M表示测试数据共有M(1&=M&=5)组每组测试数据的第一行输入一个正整数N(1&=N&=100000)和一个正整数S(1&=S&=100000)，N表示城市的总个数，S表示参观者所在城市的编号随后的N-1行，每行有两个正整数a,b(1&=a,b&lt
可笑痴狂 阅读(112) |
摘要: /*//代码一：克鲁斯卡尔算法（超时）#include&stdio.h&#include&malloc.h&#include&string.h&#include&string.h&struct edge{int v1;int v2;}t;int v,e,int find(int father[],int v){int temp=v;while(father[temp]&0)temp=father[temp];}void Kruskal(struct edge edges[],int n){int
可笑痴狂 阅读(130) |
摘要: 一笔画问题时间限制：3000 ms | 内存限制：65535 KB难度：4描述zyc从小就比较喜欢玩一些小游戏，其中就包括画一笔画，他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。规定，所有的边都只能画一次，不能重复画。输入第一行只有一个正整数N(N&=10)表示测试数据的组数。每组测试数据的第一行有两个正整数P,Q(P&=1000,Q&=2000)，分别表示这个画中有多少个顶点和多少条连线。（点的编号从1到P）随后的Q行，每行有两个正整数A,B(0&A,B&P)，表示编号为A和B的两点之间有连线。输出如果存在符合条件的连线，则输出&Yes&qu
可笑痴狂 阅读(63) |