关键词:
题目:
代码及实现思路如下:
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
挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现
题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情
挑战程序设计竞赛(算法和数据结构)——3.6希尔排序的java实现(代码片段)
题目&思路:代码:importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Scanner;publicclassShellSortpublicstaticlongcnt;publicstaticintA[]=newint[1000000];publicstaticintn;publ 查看详情
挑战程序设计竞赛(算法和数据结构)——7.7最小成本排序的java实现(代码片段)
题目&思路:代码:importjava.util.*;publicclassMinimumCostSortpublicstaticfinalintMAX=1000;publicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();in 查看详情
挑战程序设计竞赛(算法和数据结构)——17.4最大正方形的java实现(代码片段)
题目&思路:代码:importjava.util.Scanner;publicclassLargestSquarepublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intH=cin.nextInt();intW=cin.nextInt();intmap[] 查看详情
挑战程序设计竞赛(算法和数据结构)——5.5迭代器和二分查找的java实现(代码片段)
迭代器代码:importjava.util.Arrays;importjava.util.Iterator;publicclassIteratorDemopublicstaticvoidmain(String[]args)int[]arr=newint[]1,2,3,4,5,6,7,8,9,8,2,6,5,7,1,3,4,5,6;Iterator<Integer 查看详情
挑战程序设计竞赛(算法和数据结构)——5.4散列法习题java代码实现(代码片段)
题目:散列法相关的代码可以参考之前一篇博文https://blog.csdn.net/weixin_42887138/article/details/121254659importjava.lang.ref.PhantomReference;importjava.util.Scanner;publicclass_5_4publicstaticvoidmain(String[]arg 查看详情
挑战程序设计竞赛(算法和数据结构)——4.4链表习题的java实现(代码片段)
链表有初始化、插入元素、删除元素、查找元素等方法。在创建链表的过程中,最关键的是搞清楚链表的几个关键数据构成:链表由一个个节点互相串联构成,节点作为一个基础的对象,可由类Node(随便取个... 查看详情
挑战程序设计竞赛(算法和数据结构)——4.3队列习题的java实现(代码片段)
题目:基本思路:将任务定义为一个包含名称和时间的Task类,定义一个Task类型的队列,并循环下列算法:用时间sum_time来记录处理情况,只要队列不为空,就不断执行当处理一个队头任务时,首先... 查看详情
挑战程序设计竞赛(算法和数据结构)——分割(下)&快速排序的java实现(代码片段)
在《挑战程序设计竞赛(算法和数据结构)——7.2分割(上)JAVA实现》中实现了将任一数组的元素以最后一个元素为界,小的排在前,大的排在后的功能,参照以下链接:https://blog.csdn.net/weixin_42887... 查看详情
挑战程序设计竞赛(算法和数据结构)——16.12凸包(安德鲁算法)的java实现(代码片段)
题目与思路:代码:importjava.util.*;//数据结果套数据结构时,需要一层一层初始化publicclassConvexHullpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();Vector<GraghBasic.Point>S=newVector<GraghBasic.Poi... 查看详情
挑战程序设计竞赛(算法和数据结构)——16.13线段相交问题(曼哈顿算法)的java实现(代码片段)
题目与思路:代码:importjava.util.*;publicclassManhattanGeometrypublicstaticclassEpElementprivateGraghBasic.PointP;privateStringdirection;//left,right,bottom,topprivateintid;EpElement()EpElement(GraghBasic.PointP,Stringdirection,intid)this.P=P;this.direction=direction;this... 查看详情
挑战程序设计竞赛(算法和数据结构)——12.2图的表示java实现(代码片段)
题目:importjava.util.Scanner;publicclassGraphImplementpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intn=cin.nextInt();//建立图的邻接矩阵intM[][]=newint[n][n];for(inti=0;i<n;i++)intid=cin.nextInt();intdegree=cin.nextInt();for(i... 查看详情
挑战程序设计竞赛(算法和数据结构)——13.3单源最短路径(dijkstra算法)的java实现(代码片段)
题目:代码:importjava.io.BufferedInputStream;importjava.io.BufferedReader;importjava.util.Scanner;publicclassSingleSourceShortestPathpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();//初始化邻接矩阵MintM[][]... 查看详情
挑战程序设计竞赛(算法和数据结构)——7.2分割(上)java实现(代码片段)
题目:思路:示例1:示例2:代码如下:importjava.io.BufferedInputStream;importjava.util.Scanner;publicclassPartitionpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();int[]A=newint[n];for(inti=... 查看详情
挑战程序设计竞赛(算法和数据结构)——12.5连通分量的java实现(代码片段)
题目:讲解:注意:定义了一个Vector类型的数组,不仅需要初始化Vector类型的数组,还需初始化每一个Vector类型的容器。否则会出现以下异常:Exceptioninthread“main”java.lang.NullPointerException:Cannotinvoke“java.uti... 查看详情
挑战程序设计竞赛(算法和数据结构)——7.1归并排序java实现(代码片段)
归并排序思路:代码如下:importjava.io.BufferedInputStream;importjava.util.Scanner;publicclassMergeSortpublicstaticvoidmain(String[]args)Scannercin=newScanner(newBufferedInputStream(System.in));intn=cin.nextInt();int[]S=newint[n];for(inti=0;i<n;i++)S[i... 查看详情
挑战程序设计竞赛(算法和数据结构)——15.3关节点的java实现(代码片段)
题目:代码:importjava.util.ArrayList;importjava.util.HashSet;importjava.util.Scanner;importjava.util.Set;publicclassArticulationPointpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intN=cin.nextInt();intm=cin.nextInt();ArrayList<Integer>G[]=n... 查看详情
挑战程序设计竞赛(算法和数据结构)——15.3关节点的java实现(代码片段)
题目:代码:importjava.util.ArrayList;importjava.util.HashSet;importjava.util.Scanner;importjava.util.Set;publicclassArticulationPointpublicstaticvoidmain(String[]args)Scannercin=newScanner(System.in);intN=cin.nextInt();intm=cin.nextInt();ArrayList<Integer>G[]=n... 查看详情