题目:
代码及实现思路如下:
import java.io.BufferedInputStream; import java.util.Scanner; import java.util.Stack; import java.util.Vector; public class _4_6 { public static void main(String[] args) { /* 设计两个栈,S1和S2. S1为int栈: 用于存放输入进来的"\"的位置,用i表示(输入数据时即可用于遍历,s.length(),s.charAt(i)). 如果遇到了"/",则计算i与栈顶数之差,并将栈顶数弹栈。 S2为Area类型的栈: Area类包含一个记录最左侧"\"位置的pos(int)以及当前积水处的面积L(int)。 S2.size()就是积水处到的数量。 */ //定义一个Area类型的类 class Area{ int pos; int L; Area(int pos, int L){ this.pos = pos; this.L = L; } } Scanner cin = new Scanner(new BufferedInputStream(System.in)); System.out.println("请输入一个水坝:(只能包含\\, _, /)"); String dam = cin.nextLine(); int N = dam.length(); Stack<Integer> S1 = new Stack<Integer>(); Stack<Area> S2 = new Stack<Area>(); for(int i=0;i<N;i++){ if(dam.charAt(i) == '\\'){ S1.push(i); } else if(dam.charAt(i) == '/'){ if(S1.size() == 0){continue;}//如果没有与之对应的\,那么这个位置的/无效,直接跳到下一个循环即可 else{ int square = i - S1.peek();//计算每一个小面积 //对S2进行操作 if(S2.size()==0){//如果栈为空,则直接压栈 Area new_area = new Area(S1.peek(), square); S2.push(new_area); } else{ if(S2.peek().pos < S1.peek()){ //如果栈内面积涉及的\在新计算的面积的左边,说明两个凹槽不重叠,记录新的水坑面积,即执行压栈操作 Area new_area = new Area(S1.peek(), square); S2.push(new_area); } else if(S2.peek().pos > S1.peek()){ //如果栈内面积涉及的\在新计算的面积的右边,说明两个凹槽重叠,合并水坑面积,并记录更新新位置;这个操作可能嵌套,要循环 Area new_area = new Area(S1.peek(), square);//用一个值来暂存最左侧的\和目前的面积值 while(S2.size()>0 && S2.peek().pos > S1.peek()) { new_area = new Area(S1.peek(), S2.peek().L + new_area.L);//每次循环将面积值合并 S2.pop(); } S2.push(new_area); } } S1.pop();//计算完成后,将S1的位置弹栈 } } }/**/ Stack<Area> S3 = new Stack<Area>(); while(S2.size()!=0){ S3.push(S2.pop()); } System.out.println("水坑数量有:" + S3.size()); System.out.println("每个水坑的面积分别为:"); while(S3.size()!=0){ System.out.println(S3.pop().L + " "); } } } // int sum = 0; // // for(int i=0;i<N;i++){ // if(dam.charAt(i) == '\\'){ // S1.push(i);//只要是“\”,就对S1执行入栈操作 // } // else if(dam.charAt(i) == '/' && S1.size()>0){//如果是/,且S1栈内不为空 // int j = S1.peek();//记录S1栈顶的值 // S1.pop();//S1出栈 // sum+=i-j; // int a = i-j;//记录小面积 // while (S2.size()>0 && S2.peek().pos>j){//只要S2不为空且S2的栈顶值大于S1的栈顶值 // a += S2.peek().L; // S2.pop(); // } // Area temp = new Area(j, a); // S2.push(temp); // } // } /*Vector<Integer> ans = new Vector<>(); while(S2.size()>0){ans.addElement(S2.peek().L);S2.pop();}*/
输入:
\\///\_/\/\\\\/_/\\///__\\\_\\/_\/_/\
输出:
水坑数量有:5 每个水坑的面积分别为: 4 2 1 19 9