Java在ACM中的应用

发表于   |   分类于   |     |   阅读次数

基本使用框架

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

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        
    }
}

Java的输入

Scanner类

首先，先将Scanner初始化成一个对象：

1
Scanner s = new Scanner(System.in);

读一个整数：

1
int n = s.nextInt();

相当于C或C++中的：

1
2
3
int n;
scanf("%d", &n);
cin >> n;

读一个字符串：

1
String str = s.next();

相当于C或C++中的：

1
2
3
char str[500];
scanf("%s", str);
cin >> str;

读一个浮点数：

1
double t = s.nextDouble();

相当于C或C++中的：

1
2
3
double t;
scanf("%lf", &t);
cin >> t;

读一整行：

1
String str = s.nextLine();

相当于：

1
2
3
char str[500];
gets(str);
cin.getline(str, 100, '\0');

判断是否有下一个输入可以用以下语句：

1
2
3
s.hasNext();
s.hasNextInt();
s.hasNextDouble();

少量的输入推荐使用Scanner，但是大量的数据的输入就推荐使用BufferedReader类了，就像可以用scanf替换cin一样。

BufferedReader类

Java的快速输入输出类：

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
26
27
28
29
30
31
32
33
34
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Reader r = new Reader(System.in);
        double x = r.nextDouble();
        int n = r.nextInt();
        String str = r.next();
    }
}

class Reader {
    final BufferedReader reader;
    StringTokenizer tokenizer;
    public Reader(InputStream input) {
        reader = new BufferedReader(new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    public String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

Java的输出

普通输出

输出一般可以直接用System.out.print()和System.out.println()，前者不输出换行，而后者输出。

1
2
3
System.out.println(n);                 //输出换行
System.out.print(n);                   //不输出换行
System.out.printf("%s %d", str, n);    //和C语言的printf用法类似

或者可以使用如下的方法：

1
2
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
out.println(n);

浮点数输出

对于输出浮点数保留几位小数的问题，可以使用DecimalFormat类来实现：

1
2
3
4
5
6
7
8
9
import java.text.*;
//三位四舍五入
DecimalFormat f = new DecimalFormat("#.00#");
//保留三位小数
DecimalFormat g = new DecimalFormat("0.000"); 
double a = 123.45678, b = 0.12; 
System.out.println(f.format(a)); 
System.out.println(f.format(b)); 
System.out.println(g.format(b));

以上代码的输出结果如下：

123.457
.12
0.120

大数类

在ACM中的做题时，经常会遇见一些大数的问题，这是当我们用C或是C++时就会觉得比较麻烦，因为我们必须要通过数组来模拟加减乘除的运算。因此我们可以使用Java提供的BigInteger、BigDecimal类来实现大数的计算。

1
2
3
4
5
import java.math.*;
BigInteger a = BigInteger.valueOf(100);
BigInteger b = BigInteger.valueOf(50);
BigInteger c = a.add(b);    //c = a + b
System.out.println(c);      //输出c的值

主要有以下方法可以使用：

1
2
3
4
5
6
7
8
9
10
11
12
//加
BigInteger add(BigInteger other)
//减
BigInteger subtract(BigInteger other)
//乘
BigInteger multiply(BigInteger other)
//除
BigInteger divide(BigInteger other)
//求余
BigInteger mod(BigInteger other)
int compareTo(BigInteger other)
static BigInteger valueOf(long x)

BigInteger类的对象不可进行加减乘除四则运算，要调用其成员函数进行运算。另外BigInteger类不是int的扩展类型，所以不能把int类型值直接赋值给BigInteger。

BigInteger类型有自己的常量：

1
2
3
BigInteger.ZERO;
BigInteger.ONE;
BigInteger.TEN;

BigDecimal的用法和BigInteger的用法类似，在这里就不多说了。

字符串应用

ACM中还会经常遇到字符串的处理方面的问题：StringBuffer 和StringBuilder这两个类有很多又用的方法可供使用。对于要进行大量变化的字符串处理建议使用StringBuffer类，而不是经常变化的字符串建议使用String类，它们特点取决于Java中对String和StringBuffer的内存分配不相同的原因了。另外字符串处理中经常可能要用到的是另外一个知识了，那就是正则表达式了，如果能够很好的撑握正则表达式的用法，那么字符串处理可以说你已经完成一半的任务了。如果正则表达式没有完全撑握，StringBuilder就是它的一个替代品。另外StringTokenizer也是一个很有用的工具，因为不会使用，所以在这里就不多谈了。

本节就简单的来讲一下String类的使用方法。String类用来存储字符串，可以用charAt()方法来取出其中某一下标的字符，下标从0开始：

1
String str = "Hello";                     // str.charAt(1) = 'e'

用substring方法可得到子串：

1
System.out.println(str.substring(0, 4))   // output "Hell"

注意substring方法应用的是前闭后开区间，第二个参数位置的字符不包括在内。这样做使得str.substring(a, b)包含b - a个字符。

字符串连接可以直接用 + 号进行连接，如：

1
2
3
String a = "Hello"; 
String b = "World"; 
System.out.println(a + ", " + b + "!");    // output "Hello, World!"

如想直接将字符串中的某字节改变，可以使用另外的StringBuffer类。

以下是一个简单的StringBuffer类的测试例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.lang.StringBuffer;
public class StringBufferTest {

    public static void main(String[] args) {
        StringBuffer str = new StringBuffer("abc");
        StringBuffer str2 = str;
        str = str2.append(str.reverse());
        System.out.println(str);
        str.insert(1, "aaaaaa");
        System.out.println(str);
        System.out.println(str.charAt(1));
        System.out.println(str.lastIndexOf("ba"));
    }
}

程序的输出结果如下：

cbacba
caaaaaabacba
a
10

其他注意事项

  1. Java是面向对象的语言，思考方法需要变换一下，里面的函数统称为方法，不要搞错。
  2. Java里的数组有些变动，多维数组的内部其实都是指针，所以Java不支持fill多维数组。 数组定义后必须初始化，如int[] a = new int[100];
  3. 布尔类型为boolean，只有true和false二值，在if (…) / while (…) 等语句的条件中必须为boolean类型，在C/C++中的if (n % 2)类似的语句在Java中无法编译通过。
  4. 下面在java.util包里Arrays类的几个方法可替代C/C++里的memset、qsort/sort和 bsearch:
    1
    2
    3
    Arrays.fill();
    Arrays.sort();
    Arrays.binarySearch();