ACM等算法比赛中JAVA 常用"STL"总结:TreeMap,Queue,PriorityQueue等

时间:2022-09-30 17:59:35

第一个:显然是I/O的class啦~!

/*IO相关*/
class InputReader
{
	public InputReader() {
		// TODO Auto-generated constructor stub
		tokenizer = new StringTokenizer("");
		reader = new BufferedReader(new InputStreamReader(System.in));
	}
	public String nextTokenizer()	throws IOException
	{
		while (!tokenizer.hasMoreTokens())
		{
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
		
	}
	public int nextInt()	throws IOException
	{
		return Integer.valueOf(nextTokenizer());
	}

	StringTokenizer tokenizer;
	BufferedReader	reader;
}


Map使用:

比赛常用HashMap和TreeMap


先介绍TreeMap:

二叉树Map嘛,自然就是log级各种运算的时间。所以对自定义结构体需要定义比较函数。


比如常用的比较器这样写。

	/*常用的包含x,y节点的node的class*/
	class nodexy
	{
		int x,y;
		nodexy(){}
		nodexy(int xx, int yy)
		{
			x = xx;
			y = yy;
		}
	}

	/*使用这样的比较函数*/
	static Comparator<nodexy> cmp = new Comparator<nodexy>() 
	{
		public int compare(nodexy o1, nodexy o2) {
			// TODO Auto-generated method stub
			if (o1.x==o2.x)	return o1.y-o2.y;
			return o1.x-o2.x;
		}
	};

下面是一个简单的TreeMap的样例:

	public static void main(String args[])	throws IOException
	{	
		Map<Integer, Integer>q = new TreeMap<Integer, Integer>();	//int,int类型的TreeMap,没有包含比较器!
		q.put(1, 1);
		q.put(2, 2);
		q.put(3, 3);
		q.put(3, 4);	//重复的key的value只保留最后一个~ key才是关键字
		q.put(-1,0);
		q.put(-11,4);
		q.put(12,2);
		@SuppressWarnings("rawtypes")	//消除下面的警告信息
		Iterator it = q.entrySet().iterator();	//和C++一样用迭代器遍历
		System.out.print("size = " + q.size()+"\n");		//总元素数量
		while (it.hasNext())
		{
			@SuppressWarnings("unchecked")	//消除下面的警告信息
			Map.Entry<Integer, Integer> ent = (Entry<Integer, Integer>) it.next();
			int key = ent.getKey();	//key
			int value = ent.getValue(); //value
			System.out.println(key+" " + value);
		}
	}

	public static void main(String args[])	throws IOException
	{	
		TreeMap<Integer, Integer>q = new TreeMap<Integer, Integer>();	//int,int类型的TreeMap,没有包含比较器!
		q.put(1, 1);
		q.put(2, 2);
		q.put(3, 3);
		q.put(3, 4);	//重复的key的value只保留最后一个~ key才是关键字
		q.put(-1,0);
		q.put(-11,4);
		q.put(12,2);
		@SuppressWarnings({ "rawtypes", "unused" })	//消除下面的警告信息
		Iterator it = q.entrySet().iterator();	//和C++一样用迭代器遍历
		System.out.print("size = " + q.size()+"\n");		//总元素数量
		
		/*
		 * 不需要输出一次啦,直接这样
		while (it.hasNext())
		{
			@SuppressWarnings("unchecked")	//消除下面的警告信息
			Map.Entry<Integer, Integer> ent = (Entry<Integer, Integer>) it.next();
			int key = ent.getKey();	//key
			int value = ent.getValue(); //value
			System.out.println(key+" " + value);
		}
		*/
		int ans = q.get(12);
		System.out.println(ans);	//输出了2
		
		/*对于不存在的键值的处理, 先判断是否是null*/
		if (q.get(13) != null)
		{
			ans = q.get(13);
			System.out.println(ans);	
		}else System.out.println("nothing");//输出了nothing
		
		System.out.println(q.higherKey(4));//比4大的是12,所以输出12
		System.out.println(q.higherKey(12));//比12大的没有,输出null
		System.out.println(q.lastKey());	//输出最后一个key,也就是12,也是对的
		
		q.remove(2);	//删除键为2的
		if (q.get(2) != null)
		{
			ans = q.get(2);
			System.out.println(ans);	
		}else System.out.println("nothing");//因为2被删了,所以输出了nothing
		
	}


关于遍历,访问,删除迭代器指向内容的话


	public static void main(String args[])	throws IOException
	{	
		TreeMap<Integer, Integer>q = new TreeMap<Integer, Integer>();	//int,int类型的TreeMap,没有包含比较器!
		q.put(1, 1);
		q.put(2, 2);
		q.put(3, 3);
		q.put(3, 4);	//重复的key的value只保留最后一个~ key才是关键字
		q.put(-1,0);
		q.put(-11,4);
		q.put(12,2);
		@SuppressWarnings({ "rawtypes", "unused" })	//消除下面的警告信息
		Iterator it = q.entrySet().iterator();	//和C++一样用迭代器遍历
		System.out.print("size = " + q.size()+"\n");		//总元素数量
		
		
		while (it.hasNext())
		{
			@SuppressWarnings("unchecked")	//消除下面的警告信息
			Map.Entry<Integer, Integer> ent = (Entry<Integer, Integer>) it.next();
			int key = ent.getKey();	//key
			int value = ent.getValue(); //value
			if (key==-1 || key == 1 || key==12)it.remove();	//删除迭代器这个值,并且向后迭代!
			System.out.println(key+" " + value);
		}
		System.out.println();
		System.out.println();
		/*再出输出一次,发现-1,1,12都已经被删啦!*/
		it = q.entrySet().iterator();
		while (it.hasNext())
		{
			@SuppressWarnings("unchecked")	//消除下面的警告信息
			Map.Entry<Integer, Integer> ent = (Entry<Integer, Integer>) it.next();
			int key = ent.getKey();	//key
			int value = ent.getValue(); //value
			System.out.println(key+" " + value);
		}
	}<span style="white-space:pre">	</span>


/*下面例子依然是TreeMap,但是我们修改了key为一个class, 同时设置了比较函数~,比较经典*/
class Pack
{
	int a, b;
	Pack(){}
	Pack(int x, int y)
	{
		a=x;
		b=y;
	}
	boolean same(Pack tmp)
	{
		if (tmp.a == a && tmp.b==b)	return true;
		return false;
	}
};


public class Doit {
	
	//一边访问,一边删除迭代器指向的内容
	
	static Comparator<Pack> cmp = new Comparator<Pack>() {
		@Override
		public int compare(Pack o1, Pack o2) {
			// TODO Auto-generated method stub
			if (o1.a==o2.a)	return o1.b-o2.b;
			return o1.a-o2.a;
		}
	};

	
	public static void main(String args[])	throws IOException
	{	
		TreeMap<Pack, Integer>q = new TreeMap<Pack, Integer>(cmp);	//int,int类型的TreeMap,没有包含比较器!
		q.put(new Pack(1,1), 1);
		q.put(new Pack(2,2), 2);
		q.put(new Pack(2,3), 3);
		q.put(new Pack(1,-1), 4);	//重复的key的value只保留最后一个~ key才是关键字
		q.put(new Pack(5,2),0);
		q.put(new Pack(5,3),4);
		q.put(new Pack(4,2),2);
		q.put(new Pack(4,2),2);		
		@SuppressWarnings("rawtypes")
		Iterator it = q.entrySet().iterator();	//和C++一样用迭代器遍历
		System.out.print("size = " + q.size()+"\n");		//总元素数量,输出为7个
		
		
		while (it.hasNext())
		{
			@SuppressWarnings("unchecked")	//消除下面的警告信息
			Map.Entry<Pack, Integer> ent = (Entry<Pack, Integer>) it.next();
			Pack key = ent.getKey();
			int key1 = ent.getKey().a;	//key
			int key2 = ent.getKey().b;
			int value = ent.getValue(); //value
			if (key.same(new Pack(5,3)) || key.same(new Pack(2,2)))it.remove();	//删除迭代器这个值,并且向后迭代! 
			System.out.println(key1+" "+key2+" " + value);
		}
		System.out.println();
		System.out.println();
		
		/*再出输出一次,发现-1,1,12都已经被删啦!*/
		it = q.entrySet().iterator();
		while (it.hasNext())
		{
			@SuppressWarnings("unchecked")	//消除下面的警告信息
			Map.Entry<Pack, Integer> ent = (Entry<Pack, Integer>) it.next();
			Pack key = ent.getKey();
			int key1 = ent.getKey().a;	//key
			int key2 = ent.getKey().b;
			int value = ent.getValue(); //value
			System.out.println(key1+" "+key2+" " + value);
		}
	}
}

===============================================大分割线=========================


实现c++的vector功能的arraylist.


用一个class的例子


class Pack
{
	int a, b;
	Pack(){}
	Pack(int x, int y)
	{
		a=x;
		b=y;
	}
	boolean same(Pack tmp)
	{
		if (tmp.a == a && tmp.b==b)	return true;
		return false;
	}
};


public class Doit {
	
	//一边访问,一边删除迭代器指向的内容
	
	static Comparator<Pack> cmp = new Comparator<Pack>() {
		@Override
		public int compare(Pack o1, Pack o2) {
			// TODO Auto-generated method stub
			if (o1.a==o2.a)	return o1.b-o2.b;
			return o1.a-o2.a;
		}
	};

	
	public static void main(String args[])	throws IOException
	{	
		ArrayList<Pack>q = new ArrayList<Pack>();
		q.add(new Pack(5,5));//塞入队尾
		q.add(new Pack(4,4));
		q.add(new Pack(7,7));
		System.out.println(q.get(0).a + " " + q.get(0).b);
		System.out.println(q.get(1).a + " " + q.get(1).b);
		System.out.println(q.get(2).a + " " + q.get(2).b);
		//Pack sb[] = q.toArray();
		
		Pack sb[];
		sb = q.toArray(new Pack[q.size()]);	//转换成数组
		for (int i = 0; i != q.size(); ++ i)
		{
			System.out.println(sb[i].a);
		}
		
	}
}



关于数组排序:

class Pack
{
	int a, b;
	Pack(){}
	Pack(int x, int y)
	{
		a=x;
		b=y;
	}
	boolean same(Pack tmp)
	{
		if (tmp.a == a && tmp.b==b)	return true;
		return false;
	}
};


public class Doit {
	
	//一边访问,一边删除迭代器指向的内容
	

	static Comparator<Pack> cmp = new Comparator<Pack>() {
		
		@Override
		public int compare(Pack o1, Pack o2) {
			// TODO Auto-generated method stub
			if (o1.a==o2.a)	return o1.b-o2.b;
			return o1.a-o2.a;
		}
	};
	
	
	public static void main(String args[])	throws IOException
	{	
		ArrayList<Pack>q = new ArrayList<Pack>();
		q.add(new Pack(5,5));//塞入队尾
		q.add(new Pack(4,4));
		q.add(new Pack(7,7));
		q.add(new Pack(4,3));
		q.add(new Pack(4,2));
		q.add(new Pack(4,10));
		q.add(new Pack(4,4));
		/*访问arraylist内元素方法用get*/
		System.out.println(q.get(0).a + " " + q.get(0).b);	
		System.out.println(q.get(1).a + " " + q.get(1).b);
		System.out.println(q.get(2).a + " " + q.get(2).b);
		//Pack sb[] = q.toArray();
		
		/*arraylist转化为数组*/
		Pack sb[];
		sb = q.toArray(new Pack[q.size()]);	//转换成数组
		/*
		for (int i = 0; i != q.size(); ++ i)
		{
			System.out.println(sb[i].a);
		}
		*/
		/*数组排序的方法*/
		Arrays.sort(sb,0, q.size(),cmp);   //排序,[L,R)区间进行排序。 例子是[0,q.size()) 之间的数字进行排序
		for (int i = 0; i != q.size(); ++ i)	//输出了数组中的元素,从小到大
		{
			System.out.println(sb[i].a + " " + sb[i].b);
		}
	}
}


容器的排序:

class Pack
{
	int a, b;
	Pack(){}
	Pack(int x, int y)
	{
		a=x;
		b=y;
	}
	boolean same(Pack tmp)
	{
		if (tmp.a == a && tmp.b==b)	return true;
		return false;
	}
};


public class Doit {
	
	//一边访问,一边删除迭代器指向的内容
	

	static Comparator<Pack> cmp = new Comparator<Pack>() {
		
		@Override
		public int compare(Pack o1, Pack o2) {
			// TODO Auto-generated method stub
			if (o1.a==o2.a)	return o1.b-o2.b;
			return o1.a-o2.a;
		}
	};
	
	
	public static void main(String args[])	throws IOException
	{	
		ArrayList<Pack>q = new ArrayList<Pack>();
		q.add(new Pack(5,5));//塞入队尾
		q.add(new Pack(4,4));
		q.add(new Pack(7,7));
		q.add(new Pack(4,3));
		q.add(new Pack(4,2));
		q.add(new Pack(4,10));
		q.add(new Pack(4,4));
		q.add(new Pack(2,4));
		/*访问arraylist内元素方法用get*/
		System.out.println(q.get(0).a + " " + q.get(0).b);	
		System.out.println(q.get(1).a + " " + q.get(1).b);
		System.out.println(q.get(2).a + " " + q.get(2).b);
		//Pack sb[] = q.toArray();
		System.out.println();
		System.out.println();
		System.out.println();
		
		
		Collections.sort(q,cmp);
		Iterator it = q.iterator();
		while (it.hasNext())
		{
			Pack tmp = (Pack) it.next();
			System.out.println(tmp.a+" "+tmp.b);
		}
		
	}
}


================================

另一种做比较器的方法 用接口实现:

class Pack
{
	int a, b;
	Pack(){}
	Pack(int x, int y)
	{
		a=x;
		b=y;
	}
	boolean same(Pack tmp)
	{
		if (tmp.a == a && tmp.b==b)	return true;
		return false;
	}
};

class MyCmp implements Comparator<Pack>
{
	//@Override
	public int compare(Pack o1, Pack o2) {
		// TODO Auto-generated method stub
		if (o1.a==o2.a)	return o1.b-o2.b;
		return o1.a - o2.a;
	}
}


public class Doit {
	
	//一边访问,一边删除迭代器指向的内容
	

	static Comparator<Pack> cmp = new MyCmp();
	
	
	public static void main(String args[])	throws IOException
	{	
		ArrayList<Pack>q = new ArrayList<Pack>();
		q.add(new Pack(5,5));//塞入队尾
		q.add(new Pack(4,4));
		q.add(new Pack(7,7));
		q.add(new Pack(4,3));
		q.add(new Pack(4,2));
		q.add(new Pack(4,10));
		q.add(new Pack(4,4));
		q.add(new Pack(2,4));
		/*访问arraylist内元素方法用get*/
		System.out.println(q.get(0).a + " " + q.get(0).b);	
		System.out.println(q.get(1).a + " " + q.get(1).b);
		System.out.println(q.get(2).a + " " + q.get(2).b);
		//Pack sb[] = q.toArray();
		System.out.println();
		System.out.println();
		System.out.println();
		
		
		Collections.sort(q,cmp);
		Iterator it = q.iterator();
		while (it.hasNext())
		{
			Pack tmp = (Pack) it.next();
			System.out.println(tmp.a+" "+tmp.b);
		}
		
	}
}


===========分界线===========================================================

POJ 2386 挑战P32 BFS/DFS搜索裸题 queue使用方法
    
    
   
   
static Queue<Coordinate> queue = new LinkedList<Coordinate>();//队列必须new LinkedList类型
    queue.offer(new Coordinate(arg0, arg1)); 塞入新元素
    queue.poll();//弹出头元素
     long nowx = queue . peek (). x ; //peek读取头元素


没有什么好说的
    
    
   
   
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.security.Principal;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main
{
static InputReader reader = new InputReader(System.in);
static PrintWriter writer = new PrintWriter(System.out);
static long n, m;
static char map[][] = new char [150][150];
static Queue<Coordinate> queue = new LinkedList<Coordinate>();
static boolean vis[][] = new boolean[150][150];
final static long dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
final static long dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
//false为没哟放,true为访问过
public static void main(String args[])
{
try
{
init();
doit();
}catch (IOException e){
System.out.println("chuwenti");
}
finally
{
writer.close();
}
}
static void init() throws IOException
{
for (int i = 0; i != 150; ++ i)
for (int j = 0; j != 150; ++ j)
vis[i][j] = false;
n = reader.nextInt();
m = reader.nextInt();
for (int i = 0; i != n; ++ i)
{
String tmp = reader.nextString();
map[i] = tmp.toCharArray();
}
//debug 输出读入的数据监测是否正确
/*
for (int i = 0; i != n; ++ i)
{
for (int j = 0; j != m; ++ j)
writer.print(map[i][j]);
writer.print('\n');
}
*/
}
static void bfs(long arg0, long arg1)
{
queue.offer(new Coordinate(arg0, arg1));
while (!queue.isEmpty())
{
long nowx = queue.peek().x;
long nowy = queue.peek().y;
queue.poll();
for (int i = 0; i != 8; ++ i)
{
long willx = nowx + dx[i];
long willy = nowy + dy[i];
if (willx <0 || willy <0 || willx >= n || willy >= m) continue;
if (map[(int) willx][(int) willy] == '.') continue;
queue.offer(new Coordinate(willx, willy));
map[(int) willx][(int) willy] = '.';
}
}
}
static void doit()
{
long ans = 0;
for (int i = 0; i != n; ++ i)
for (int j = 0; j != m; ++ j)
{
if (map[i][j] == '.') continue;
bfs(i, j);
ans ++;
}
writer.println(ans);
}
}
 
 
class InputReader {
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
this.tokenizer = new StringTokenizer("");
}
 
public String nextToken() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
 
public int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
public String nextString() throws IOException
{
return nextToken();
}
 
private BufferedReader reader;
private StringTokenizer tokenizer;
}
 
class Coordinate
{
long x, y;
public Coordinate() {
// TODO Auto-generated constructor stub
x = -2;
y = -2;
}
public Coordinate(long x, long y) {
// TODO Auto-generated constructor stub
this.x = x;
this.y = y;
}
}
====================分界线==============================


POJ 3253 挑战P47 贪心,JAVA heap注意事项, PrintWriter注意事项

    
    
   
   
static Comparator<Integer> myCmp = new MyCmp();
static PriorityQueue<Integer> q = new PriorityQueue<Integer>(mkh,myCmp);
切记,构造函数第一个需要填写数字。否则在部分OJ编译失败。并且这个数字大小写11即可。

同时, PrintWriter必须close,否则无输出!

    
    
   
   
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main
{
static Comparator<Integer> myCmp = new MyCmp();
static PriorityQueue<Integer> q = new PriorityQueue<Integer>(20000,myCmp);
static Integer num[] = new Integer[30000];
static int n;
static PrintWriter writer = new PrintWriter(System.out);
static InputReader reader = new InputReader(System.in);
public static void main(String args[]) throws IOException
{
init();
doit();
}
static void init() throws IOException
{
n = reader.nextInteger();
for (int i = 0; i != n; ++ i)
{
num[i] = reader.nextInteger();
}
}
static void doit()
{
//System.out.println("!");
long ans = 0;
for (int i = 0; i != n; ++ i)
q.offer(num[i]);
while (!q.isEmpty())
{
if (q.size() == 1)
{
break;
}
long arg0 = q.poll();
long arg1 = q.poll();
ans += arg0 + arg1;
q.offer(Integer.valueOf( (int) (arg0 + arg1)));
}
writer.println(ans);
writer.close();
}
}
 
class MyCmp implements Comparator<Integer>
{
//@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o1 - o2;
}
}
 
class InputReader
{
public InputReader(InputStream in) {
// TODO Auto-generated constructor stub
this.reader = new BufferedReader(new InputStreamReader(in));
this.tokenizer = new StringTokenizer("");
}
public String nextTokenizer() throws IOException
{
while (!tokenizer.hasMoreTokens())
{
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
public Integer nextInteger() throws IOException
{
return Integer.valueOf(nextTokenizer());
}
private StringTokenizer tokenizer;
private BufferedReader reader;
}
=============分割线==================

POJ 1182 挑战P89 并查集 食物链 关于new 对象数组

   
   
  
  
static Animal animal[] = new Animal[50010];
for (int i = 0; i != 50010; ++ i)    animal[i] = new Animal(); 必须这样,否则并不能初始化!!!!

并查集还得练!思考不够详细!

    
    
   
   
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main
{
static int n, m;
static InputReader reader = new InputReader();
static Animal animal[] = new Animal[50010];
public static void main(String args[]) throws IOException
{
initAndDoit();
}
public static void initAndDoit() throws IOException
{
n = reader.nextInt();
m = reader.nextInt();
for (int i = 0; i != 50010; ++ i) animal[i] = new Animal();
int ans = 0;
for (int test = 0; test != m; ++ test)
{
int flag = reader.nextInt();
int a = reader.nextInt(), b = reader.nextInt();
if (a > n || b > n) //满足条件2和条件3,假话
{
++ ans;
continue;
}
int x = getFather(a);
int y = getFather(b);
if (flag == 1) //同类
{
if (x == y)
{
if (animal[a].relationship != animal[b].relationship) ans ++;
continue;
}
animal[x].father = y;
animal[x].relationship = (animal[b].relationship - animal[a].relationship + 3) % 3;
 
}
if (flag == 2) //a吃b
{
if (x == y)
{
if ((animal[a].relationship ) != (animal[b].relationship + 1) % 3)
{
ans ++;
}
}else
{
animal[x].father = y;
animal[x].relationship = (animal[b].relationship - animal[a].relationship + 4) % 3;
}
}
}
System.out.println(ans);
}
public static int getFather(int arg0)
{
// System.out.println(arg0 + " " + animal[arg0].father);
int index = animal[arg0].father;
if (index == -1) return arg0;
int relationship = animal[arg0].relationship;
//System.out.println(index + " " + arg0);
animal[arg0].father = getFather(index);
animal[arg0].relationship = (relationship + animal[index].relationship) % 3;
return animal[arg0].father;
}
}
 
class Animal
{
int father;
int relationship;
Animal()
{
this.father = -1;
this.relationship = 0;
}
}
 
 
class InputReader
{
InputReader()
{
this.reader = new BufferedReader(new InputStreamReader(System.in));
this.tokenizer = new StringTokenizer("");
}
public String nextTokenizer() throws IOException
{
while (!tokenizer.hasMoreTokens())
{
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
public int nextInt() throws IOException
{
return Integer.valueOf(nextTokenizer());
}
private StringTokenizer tokenizer;
private BufferedReader reader;
}