參考鏈接： Java中StringTokenizer類的示例| 1(構造函數)

算法競賽中的JAVA使用筆記?

?

?

?算法競賽中的JAVA使用筆記

? ?輸入與輸出

? ? ?基本輸入輸入掛輸出控制臺輸入輸出重定向到文件 大整數與高精度

? ? ?大整數BigInteger高精度BigDecimal高精度開方 字符串與進制轉換

? ? ?字符串基本操作進制轉換 排序

? ? ?默認排序實現Comparator接口自定義比較器對自定義類的排序用lambda自定義比較器僅 JAVA8 以上支持 CSTL中部分數據結構在JAVA中對應的用法

? ? ?setmapvectorlistpriority_queuequeuestackdeque? ?

?

?

本文介紹了Java在程序算法競賽解題時常用的一些知識，包括基本的輸入輸出、Java的優勢大數高精類、字符串與進制轉換、排序以及C++ STL中部分數據結構在JAVA中對應的用法，旨在作為C/C++選手使用Java解題時的參考，并不會介紹基礎的Java入門語法。?

本文在本人新博客的鏈接：http://www.myblog.link/2016/11/14/Note-of-java/?

?

輸入與輸出?

基本輸入?

Scanner in = new Scanner (System.in);//基本方法

Scanner in = new Scanner (new BufferedInputStream(System.in));//更快

XXX foo = in.nextXXX();//然后這樣給一個XXX類型的變量從標準輸入獲取值

while(in.hasNext()) doSomeThing();//循環到EOF時這么寫，后面也可以加上變量類型?

輸入掛?

class InputReader {

? ? BufferedReader buf;

? ? StringTokenizer tok;

? ? InputReader() {

? ? ? ? buf = new BufferedReader(new InputStreamReader(System.in));

? ? }

? ? boolean hasNext() {

? ? ? ? while (tok == null || !tok.hasMoreElements()) {

? ? ? ? ? ? try {

? ? ? ? ? ? ? ? tok = new StringTokenizer(buf.readLine());

? ? ? ? ? ? } catch (Exception e) {

? ? ? ? ? ? ? ? return false;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return true;

? ? }

? ? String next() {

? ? ? ? if (hasNext())

? ? ? ? ? ? return tok.nextToken();

? ? ? ? return null;

? ? }

? ? int nextInt() {

? ? ? ? return Integer.parseInt(next());

? ? }

? ? long nextLong() {

? ? ? ? return Long.parseLong(next());

? ? }

? ? double nextDouble() {

? ? ? ? return Double.parseDouble(next());

? ? }

? ? BigInteger nextBigInteger() {

? ? ? ? return new BigInteger(next());

? ? }

? ? BigDecimal nextBigDecimal() {

? ? ? ? return new BigDecimal(next());

? ? }

}?

輸出?

PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));//使用緩存加速，比直接使用System.out快

out.println(n);?

out.printf("%.2f\n", ans); // 與c語言中printf用法相同?

控制臺輸入輸出重定向到文件?

FileInputStream fis = new FileInputStream("b.in");??

System.setIn(fis);??

PrintStream ps = new PrintStream(new FileOutputStream("b.out"));??

System.setOut(ps);?

大整數與高精度?

大整數BigInteger?

import java.math.BigInteger;?

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

BigInteger add(BigInteger other)?

BigInteger subtract(BigInteger other)?

BigInteger multiply(BigInteger other)?

BigInteger divide(BigInteger other)

BigInteger [] dividedandRemainder(BigInteger other) //數組第一位是商，第二位是余數

BigInteger pow(int other)// other次方

BigInteger mod(BigInteger other)?

BigInteger gcd(BigInteger other)?

int compareTo(BigInteger other) //負數則小于,0則等于,正數則大于

static BigInteger valueOf(long x)

//輸出數字時直接使用 System.out.println(a) 即可?

高精度BigDecimal?

BigDecimal add(BigDecimal other)

BigDecimal subtract(BigDecimal other)

BigDecimal multiply(BigDecimal other)

BigDecimal divide(BigDecimal other)

BigDecimal divide(BigDecimal divisor, int scale, BigDecimal.ROUND_HALF_UP)//除數，保留小數位數，保留方法四舍五入

BigDecimal.setScale()方法用于格式化小數點 //setScale(1)表示保留一位小數，默認用四舍五入方式?

高精度開方?

//求sqrt(x)，保留前n位數字（不是小數點后n位），n位后直接舍棄（非四舍五入）

private static BigDecimal sqrt(BigDecimal x, int n) {

? ? ? ? BigDecimal ans = BigDecimal.ZERO;

? ? ? ? BigDecimal eps = BigDecimal.ONE;

? ? ? ? for (int i = 0; i < n; ++i) {

? ? ? ? ? ? while (ans.pow(2).compareTo(x) < 0) {

? ? ? ? ? ? ? ? ans = ans.add(eps);

? ? ? ? ? ? }

? ? ? ? ? ? ans = ans.subtract(eps);

? ? ? ? ? ? eps = eps.divide(BigDecimal.TEN);

? ? ? ? }

? ? ? ? return ans;

? ? }?

字符串與進制轉換?

字符串基本操作?

String st = "abcdefg";

char [] ch;

ch = st.toCharArray(); // 字符串轉換為字符數組.

for (int i = 0; i < ch.length; i++){

? ? ch[i] += 1; //字符數組可以像C++ 一樣操作

}

System.out.println(ch); // 輸入為“bcdefgh”.?

進制轉換?

String s = Integer.toString(a, x); //把int型數據轉換乘X進制數并轉換成string型

// 0123456789abcdefghijklmnopqrstuvwxyz, 2<=x<=36

int b = Integer.parseInt(s, x);//把字符串當作X進制數轉換成int型?

排序?

默認排序?

原型：?

Arrays.sort(int[] a, int fromIndex, int toIndex)?

這種形式是對數組部分排序，也就是對數組a的下標從fromIndex到toIndex-1的元素排序，? 注意：下標為toIndex的元素不參與排序哦！?

實現Comparator接口自定義比較器?

原型：?

public static <T> void sort(T[] a,int fromIndex, int toIndex,? Comparator<? super T> c)?

將整形數組從大到小排序:?

public class Main {

? ? public static void main(String[] args) {

? ? ? ? //注意，要想改變默認的排列順序，不能使用基本類型（int,double, char）

? ? ? ? //而要使用它們對應的類

? ? ? ? Integer[] a = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};

? ? ? ? //定義一個自定義類MyComparator的對象

? ? ? ? Comparator cmp = new MyComparator();

? ? ? ? Arrays.sort(a, cmp);

? ? ? ? for(int i = 0; i < a.length; i ++) {

? ? ? ? ? ? System.out.print(a[i] + " ");

? ? ? ? }

? ? }

}

//Comparator是一個接口，所以這里我們自己定義的類MyComparator要implents該接口

//而不是extends Comparator

class MyComparator implements Comparator<Integer>{

? ? //返回值為負則o1排在o2前面，反正在后面，為0則表示相等

? ? @Override

? ? public int compare(Integer o1, Integer o2) {

? ? ? ? //如果n1小于n2，我們就返回正值，如果n1大于n2我們就返回負值，

? ? ? ? //這樣顛倒一下，就可以實現反向排序了

? ? ? ? if(o1 < o2) {?

? ? ? ? ? ? return 1;

? ? ? ? }else if(o1 > o2) {

? ? ? ? ? ? return -1;

? ? ? ? }else {

? ? ? ? ? ? return 0;

? ? ? ? }

? ? }

}?

對自定義類的排序?

對自己定義的類，除了上述在sort時制定比較器，還可以類似C++重載<，在定義類的時候實現Comparable接口，然后用方法1的語法進行排序，這樣比較簡潔，推薦！? 以下是一個完整例子：?

import java.util.Arrays;

?

class Point implements Comparable<Point>{

? ? ?int x,y;

? ? //自定義的比較函數，跟2的語法類似，此例中先x后y從小到大排序

? ? @Override

? ? public int compareTo(Point o) {

? ? ? ? return x!=o.x? x-o.x: y-o.y;

? ? }

}

?

public class Main {

?

? ? public static void main(String[] args) {

? ? ? ? //Java里的數組要先new數組，再new每個元素，不是數組有了每個元素也就有了

? ? ? ? Point[] p = new Point[3];

? ? ? ? for(int i = 0;i < p.length;++i){

? ? ? ? ? ? p[i] = new Point();

? ? ? ? }

? ? ? ? //不用上面的for把每個元素new出來直接進行下面的賦值會空指針的

? ? ? ? //其實應該在Point里重載有參的構造函數，直接在new的時候初始化，這樣代碼簡潔些

? ? ? ? p[0].x = 3;

? ? ? ? p[0].y = 3;

? ? ? ? p[1].x = 1;

? ? ? ? p[1].y = 4;

? ? ? ? p[2].x = 3;

? ? ? ? p[2].y = 1;

? ? ? ? //sort還可以在第2、3個參數上指定排序起止

? ? ? ? Arrays.sort(p);//先x后y從小到大排序

? ? ? ? for(Point t:p){

? ? ? ? ? ? System.out.println(t.x + " " + t.y);

? ? ? ? }

? ? }

}

?

用lambda自定義比較器(僅 JAVA8 以上支持)?

方法2中對整形數組從大到小排序使用lambda可以直接寫成：?

Arrays.sort(a, (x,y)->(y-x));?

方法3中排序自定義的Point類，不需要實現Comparable接口，可以直接這樣：?

Arrays.sort(p, (a,b)->(a.x!=b.x?a.x-b.x:a.y-b.y));?

C++STL中部分數據結構在JAVA中對應的用法?

set?

如果要像C++中使用set進行去重，或者查詢是否存在這方面的應用，在Java中主要使用HashSet類。? HashSet定義、插入、查詢是否存在、刪除元素的例子如下：?

Set<Integer> s = new HashSet<Integer>();//無序，對應標準C++的unordered_set

s.add(1);

System.out.println(s.contains(1) ?? "1 is in set s" : "1 isn't in set s");

//根據key刪除元素

m.remove(1);?

Set遍歷放在下文的Map中演示，因為Java中Map是轉化為Set遍歷的。?

HashSet中元素是無序的（可以理解為順序不確定），LinkedHashSet是遍歷時是按照插入順序排序的，TreeSet是升序排列的，最接近C++中的set，但是在沒有要求元素有序的情況下，Java中一般是使用HashSet的（因為復雜度的優勢?我感覺是這樣的），這也是我在例子中使用HashSet來對應set的原因（其實我感覺C++中這種情況使用unordered_set會更好啊，可能是因為C++11才出現，比較晚，所有不普及）。下節的map的情況與之類似。如果使用有序的TreeSet，還可以進行如下的查找操作：?

TreeSet<Integer> s = new TreeSet<Integer>();

//使用s.add(1);等把1-5都加進去，代碼省略

System.out.println(s.ceiling(3));? ?//>=3的最小的數，輸出3

System.out.println(s.floor(3));? ? ?//<=3的最大的數，輸出3

System.out.println(s.higher(3));? ? //>3的最小的數，輸出4

System.out.println(s.lower(3));? ? ?//<3的最大的數，輸出2

System.out.println(s.headSet(3));? ?//<3的數組成的TreeSet，輸出[1, 2]

System.out.println(s.tailSet(3));? ?//>=3的數組成的TreeSet，輸出[3, 4, 5]

System.out.println(s.subSet(2,4));? //>=2且<4的數組成的TreeSet，輸出[2, 3]

System.out.println(s.subSet(2,false,4,true));? ?//>2且<=4的數組成的TreeSet，輸出[3, 4]?

map?

如果只需要C++中map的key對value的映射功能，而不關心順序，Java中一般使用HashMap類，例子如下：?

//這里使用的是HashMap，是無序的，對于標準C++的unordered_map

//定義與存取

Map<Integer, Integer> m = new HashMap<Integer, Integer>();

m.put(1, 111);

System.out.println(m.get(1));//如果get一個不存在的key，則返回null，否則返回對應value

//用迭代器遍歷

Iterator<Entry<Integer, Integer>> it = m.entrySet().iterator();

while(it.hasNext()){

? ?Entry<Integer, Integer> e = it.next();

? ?System.out.println(e.getKey() + " " + e.getValue());

}

//根據key刪除元素

m.remove(1);

//用for-each循環遍歷

for(Map.Entry<Integer, Integer> e:m.entrySet()){

? ?System.out.println(e.getKey() + " " + e.getValue());

}?

如需有序，與Set類似，有LinkedHashMap、TreeMap等類可以使用。?

vector?

在Java中，C++的vector對應的是ArrayList類。雖然Java中也有Vector這個類，但它是歷史遺留下來的，不建議使用。?

ArrayList<Integer> a = new ArrayList<Integer>();//創建一個儲存整形的ArrayList

a.add(1);? ?//向其最后添加“1”這個元素

a.add(2);? ?//向其最后添加“2”這個元素

a.add(1, 3);? ? //向其index為1的位置添加“3”這個元素，原來index為1及后續元素向后順延一位；index以0起始

System.out.println(a);? //輸出a，結果為[1, 3, 2]

a.remove(1);? ? //刪除index為1的元素，注意不是刪除值為1的元素

System.out.println(a);? //輸出a，結果為[1, 2]

a.remove(Integer.valueOf(1));? ?//刪除值為1的元素

System.out.println(a);? //輸出a，結果為[2]

a.set(0, 1);? ? //將index為0的元素的值改成1

System.out.println(a.get(0));? ?//取出index為0的元素并輸出，結果為1?

list?

在Java 中，C++的list對于LinkedList類，其基本用法跟ArrayList類似，只是實現上使用鏈表而不是數組，從而在一些操作的復雜度上有變化，將上文代碼的ArrayList改為LinkedList可直接使用，故在此省略。（其實它還實現了C++中queue、deque、stack等的功能，有使用鏈表實現的這些數據結構的需求的話可以用它。）?

priority_queue?

在Java中，C++的priority_queue對應的是PriorityQueue類（終于碰到名字像的了？用起來都是坑啊）。示例如下：?

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();//定義一個儲存整形的優先隊列，值【小】的在前

pq.offer(1);//將1添加進去，不能用add(),雖然能過編譯！！！

pq.offer(3);

pq.offer(2);

//跟C++的不同，你可以遍歷它，但是你會發現遍歷的結果并不是排序了的……我這里輸出1 3 2?

for(int t :pq){

? ? System.out.print(t + " ");

}

System.out.println();

System.out.println(pq.peek());//取出第一個值（默認是最【小】的那個），并不刪除它，這句代碼輸出1！！！

System.out.println(pq.poll());//取出第一個值（默認是最【小】的那個），并且刪除它，這句代碼輸出1！！！

System.out.println(pq);//輸出剩下的元素，結果是[2, 3]，但是并不是排序之后的！！！這只是巧合，不信試試其他值?

用起來發現方法名都變得不認識了，可以遍歷但是又無序，取數據的時候默認還是取最小的，跟C++相反。當然，可以自定義比較器：?

class MyComp implements Comparator<Integer> {

? ? @Override

? ? public int compare(Integer o1, Integer o2) {

? ? ? ? return o2 - o1;

? ? }

}

?

public class Main {

? ? public static void main(String[] args) {

? ? ? ? PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new MyComp());

? ? ? ? // ……

? ? }

}?

覺得麻煩？那就直接lambda搞起?

PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>((a, b) -> (b - a));?

queue?

C++中的queue在Java中可以使用ArrayDeque類，實例如下：?

ArrayDeque<Integer> queue = new ArrayDeque<Integer>();

queue.offer(1);//成功返回true，失敗返回false,別寫成push了，否則……看看下個例子就知道了

queue.offer(2);

queue.offer(3);

System.out.println(queue.peek());//類似于C++中queue的front()，返回第一個元素

while (!queue.isEmpty()) {

? ? System.out.println(queue.pop());//跟C++中的queue()一樣可以刪除第一個元素，但是會返回它，不像C++中是void的

}?

上述代碼的輸出為1、1、2、3（我就不換行了）。?

stack?

C++中的stack在Java中使用ArrayDeque類（你沒看錯，還是它，我知道Java也有Stack類，那也是歷史遺留問題），語法基本相同，下面是例子：?

ArrayDeque<Integer> stack = new ArrayDeque<Integer>();

stack.push(1);//跟上面那個代碼的不同之處就在這了

stack.push(2);

stack.push(3);

System.out.println(stack.peek());//類似于C++中stack的top()，返回棧頂元素

while(!stack.isEmpty()){

? ? System.out.println(stack.pop());//跟C++中的pop()一樣可以彈出棧頂元素，但是會返回它，不像C++中是void的

}?

上述代碼的輸出為3、3、2、1（我就不換行了）。?

deque?

deque對應的……不用說了，就是ArrayDeque了。如果你已經被上面的方法名搞暈了的話，試試用下面幾個：?

ArrayDeque<Integer> deque = new ArrayDeque<Integer>();

deque.addFirst(2);

deque.addFirst(1);//往頭加

deque.addLast(3);//往尾加

System.out.println(deque.getFirst());//從頭取

System.out.println(deque.getLast());//從尾取

System.out.println(deque.removeFirst());//從頭刪

System.out.println(deque.removeLast());//從尾刪?

以上代碼輸出1、3、1、3。這些方法加入的時候已經滿了則拋出IllegalStateException異常，讀取或刪除的時候為空則拋出NoSuchElementException異常。?

不要忘了ArrayDeque是可以遍歷的喲，包括把它當stack或者queue用的時候……