kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

Java 常用数据结构

Java class 的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;

class Node implements Comparable
{
	int x,y;
	public int compareTo(Object obj){
		Node oo=(Node)obj;
		if(oo.x < this.x || oo.x == this.x && oo.y <this.y)return 1;
		return -1;
	}
}

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		Node a[]=new Node[11];
		int i,j,k,l;
		for(i=1;i<=10;i++) {
			a[i]=new Node();
			a[i].x=Math.abs(5-i); a[i].y=10-Math.abs(7-i);
		}
		Arrays.sort(a, 1, 11);
		for(i=1;i<=10;i++)System.out.println(a[i].x+" "+a[i].y);
	}
}

Java Vector 的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		Vector V=new Vector();
		V.add(1); V.add(1.234); V.add('a'); V.add("abcd");
		System.out.println((Integer)V.get(0));
		System.out.println((Double)V.get(1));
		System.out.println((Character)V.get(2));
		System.out.println((String)V.get(3));
	}
}

Java 队列的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		Queue Q=new LinkedList<Integer>();
		int i,j,k,l;
		while(!Q.isEmpty())Q.poll(); // 清空队列
		for(i=1;i<=10;i++)Q.offer(i);
		for(i=1;i<=10;i++){
			k=(Integer)Q.poll();
			System.out.println(k);
		}
	}
}

Java 优先队列的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		PriorityQueue<Integer> Q = new PriorityQueue<Integer>(30,
			new Comparator<Integer>(){
				public int compare(Integer aa, Integer bb) {
					if(aa < bb)return 1;
					return -1;
				}
			});
		int i,j,k,l;
	   
		Q.clear();
		for(i=1;i<=10;i++)Q.offer(i);
		while(!Q.isEmpty()) {
			k=(Integer)Q.poll();
			System.out.println(k);
		}
	}
}

http://www.yiibai.com/java/util/java_util_hashset.html

Java Collection 的使用

boolean contains(Object o) 如果此set包含指定的元素,此方法返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		Collection set=new HashSet();
		Collection set1=new ArrayList();
		Collection set2=new LinkedList();

		ArrayList LI=new ArrayList();
		LinkedList LD=new LinkedList();

		int i,j,k,l;

		set.clear();          // set1 set2 LI LD 用法类似
		set.add(1); set.add(1.234); set.add('a'); set.add("abcd");
		System.out.println(set.toString());
		set.remove(1); set.remove(3);
		System.out.println(set.toString());
	}
}

http://www.yiibai.com/java/util/java_util_hashmap.html

Java HashMap(很好用) TreeMap

boolean containsKey(Object key) 如果此映射包含指定键的映射此方法返回true。

boolean containsValue(Object value) 如果此映射一个或多个键映射到指定值,该方法返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(System.in);
		Map map=new HashMap();
		int i,j,k,l;
		map.clear();
		for(i=1;i<=10;i++)map.put(Math.pow(10,i), i);
		for(i=1;i<=10;i++)System.out.println((Integer)map.get(Math.pow(10,i)));
		System.out.println();
	   
		Map tree=new TreeMap();
		tree.clear();
		for(i=1;i<=10;i++)tree.put(i,10-i);
		for(i=1;i<=10;i++)
		{
			k=(Integer)tree.get(i);
			System.out.println(k);
		}
	}
}

Java I/O

Java 最简单输入就是用 Scanner 类 但是很慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int a,b;
		while(cin.hasNext())
		{
			a=cin.nextInt(); b=cin.nextInt();
			System.out.println(a+b);
		}
	}
}

输入用 StreamTokenizer ,输出用 PrintWriter 就 很快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.io.*;public class Main
{
	public static void main(String[] args) throws IOException
	{
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		int a, b;
		while(in.nextToken() != StreamTokenizer.TT_EOF)
		{
			a = (int)in.nval;
			in.nextToken();
			b = (int)in.nval;
			out.println(a + b);
		}
		out.flush();
	}
}

但是 StreamTokenizer 有所局限, 用 StringTokenizer 能很好解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
import java.io.*;
import java.math.*;public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int a,b;
		BigInteger c,d;
		String line;
		while((line=in.readLine())!=null)
		{
			st=new StringTokenizer(line);
			a=Integer.parseInt(st.nextToken());
			b=Integer.parseInt(st.nextToken());
			System.out.println(a+b);
		   
			line=in.readLine();
			st=new StringTokenizer(line);
			c=new BigInteger(st.nextToken().trim());
			d=new BigInteger(st.nextToken().trim());
			System.out.println(c.add(d));
		}
	}
}

Java 还可以 直接用 BufferedReader 类来输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
import java.io.*;
import java.math.*;public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader read=new BufferedReader(new InputStreamReader(System.in));
		int a,b,rr,t;
		while(true)
		{
			while((rr=read.read())==10 || rr==13 || rr==32);
			if(rr<0)break;
			if(rr=='-'){ t=1; a=0; } else { a=rr-48; t=0; }
			while((rr=read.read())!=32 && rr!=13 && rr!=10)a=a*10+rr-48;
			if(t==1)a=-a;
			while((rr=read.read())==10 || rr==13 || rr==32);
			if(rr=='-'){ t=1; b=0; } else { b=rr-48; t=0; }
			while((rr=read.read())!=10 && rr!=13 && rr!=10)b=b*10+rr-48;
			if(t==1)b=-b;
			System.out.println(a + b);
		}
	}
}

Java 文件输入 输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;
import java.io.*;public class Main {
	public static void main(String[] args) throws Exception {
		Scanner cin = new Scanner(new FileInputStream("in.txt"));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(new FileOutputStream("out.txt")));
		int a,b;
		while(cin.hasNext())
		{
			a=cin.nextInt(); b=cin.nextInt();
			out.println(a + b);
		}
		out.flush();
	}
} 

Java 向文件中加入数据

1
PrintWriter out=new PrintWriter(new OutputStreamWriter(new FileOutputStream("out.txt")), false);

Java 基本

1. 最简单 Java 程序 // a+b

1
2
3
4
5
6
7
8
9
10
import java.util.*;

public class Main {
	public static void main(String[] args) {
	Scanner cin = new Scanner ( System.in );
	int a,b;
	a=cin.nextInt(); b=cin.nextInt();
	System.out.println(a+b);
	}
}

当输入有多组数据时,可以改成

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner cin = new Scanner ( System.in );
		int a,b;
		while(cin.hasNext())
		{
			a=cin.nextInt(); b=cin.nextInt();
			System.out.println(a+b);
		}
	}
}

2. Java 浮点

定义 double f;
输入 f=cin.f=cin.nextDouble();
输出 System.out.println(f);
也可以指定小数位数 System.out.printf(“%0.2f\n”, f);
注意 System.out.printf(“%0.2f\n”, f); 中用 “\n” 在 HDU 中提交会 PE ,但在 PKU 中不会

3. Java 数组

与 C/C++ 不同之处在于定义
Java定义格式
int a[]=new int[111]; 或者 int a[]; a=new int[111];
二维 int a[][]=new int[111][111];
其他基本与 C/C++ 一样

4. Java 字符串,字符数组

字符串定义 String ss;
输入 ss=cin.next(); ss=cin.nextLine();
ss=cin.next(); 相当于 C/C++ scanf(“%s”,ss);
ss=cin.nextLine(); 相当于 C/C++ gets(ss);
字符串不能改变其中某个字符
得到第 k 个字符 c=ss.charAt(k-1);

字符数组定义 char ch[]=new char[111];
因为字符串无法改变其中某个字符,所以可以将其转换成字符数组
即 ch=ss.toCharArray(); 剩下的又和 C/C++ 没多少差别了

Java 中的 StringBuffer 和String 差不多
但 StringBuffer 可以动态改变,支持删除,插入等操作

5 .Java 大整数,大浮点数

Java 大整数,大浮点数可以表示一个很大很大的数,省去手写高进度的麻烦
要用Java 大整数,大浮点数必须先将 math 导入,即加一句 import java.math.*;
大整数 BigInteger
大浮点数 BigDecimal
定义 BigInteger bd; BigDecimal bf;
把 int 转换成 BigInteger 格式 bd=BigInteger.valueOf(a);

大数之间的加减乘除 取模

1
2
3
4
5
6
加  BigInteger add(BigInteger other)        
减   BigInteger subtract(BigInteger other)
乘   BigInteger multiply(BigInteger other)
除   BigInteger divide(BigInteger other)
取模 BigInteger mod(BigInteger other)
例如 bd=bd.add(cd);   // bd=bd+cd;

大小比较

1
2
3
int compareTo(BigInteger other)
例如 k=bd.compareTo(cd);
k >0 时 bd>cd

计算 2333

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
	Scanner cin = new Scanner ( System.in );
	BigInteger bd,cd;
	int i,j;
	bd=BigInteger.valueOf(1);
	for(i=1;i<=333;i++)bd=bd.multiply(BigInteger.valueOf(2));
	System.out.println(bd);
	}
}

输出:17498005798264095394980017816940970922825355447145699491406164851279623993595007385788105416184430592