java 競賽常用方法

2022 年 4 月 13 日
筆記
演算法

一，基本數據類型

1.int,float.double等轉換為字元串用 String.valueOf方法

eg：double轉換為String

Double dtDouble=12.31354;
String string=String.valueOf(dtDouble);
System.out.println(string);

2.字元串轉換為int，float，double等用其引用類型的parse對應的方法

eg：string 轉換為double

String string="1.254849";
Double dt1=Double.parseDouble(string);
System.out.println(dt1);

3.double保留兩位小數

DecimalFormat為java.text.DecimalFormat

double d = 32.1415926;
//0.00就是兩位，0.000就是三位，依此類推
DecimalFormat decimalFormat=new DecimalFormat("0.00");
String d1=decimalFormat.format(d);
System.out.println(d1);//32.14

二，大數運算

1.BigDecimal

如果直接使用double計算，可能會出現以下情況

double t=1.0-2.2*1.0;
System.out.println(t);//-1.2000000000000002

所以double做精確計算時推薦使用BigDecimal

BigDecimal使用教程

import java.math.BigDecimal;

public class testDecimal {
    public static void main(String[] args) {
        double d1=0.01;
        double d2=0.02;
        BigDecimal d1BigDec=new BigDecimal(Double.toString(d1));
        BigDecimal d2BigDec=new BigDecimal(Double.toString(d2));
        //加法
        BigDecimal addB=d1BigDec.add(d2BigDec);
        Double add=addB.doubleValue();
        System.out.println(add);//0.03
        //減法
        BigDecimal subB=d1BigDec.subtract(d2BigDec);
        Double sub=subB.doubleValue();
        System.out.println(sub);//-0.01
        //乘法
        BigDecimal mulB=d1BigDec.multiply(d2BigDec);
        Double mul=mulB.doubleValue();
        System.out.println(mul);//2.0E-4
        //除法一
        BigDecimal divB=d1BigDec.divide(d2BigDec);
        Double div=divB.doubleValue();
        System.out.println(div);//0.5
        //除法二（如果有除不盡的，會報異常，需要自己指定保留幾位小數）
        //注意這個divide方法有兩個重載的方法，一個是傳兩個參數的，一個是傳三個參數的：
        //兩個參數的方法：
        //@param divisor value by which this {@code BigDecimal} is to be divided. 傳入除數
        //@param roundingMode rounding mode to apply. 傳入round的模式
        //三個參數的方法：
        //@param divisor value by which this {@code BigDecimal} is to be divided. 傳入除數
        //@param scale scale of the {@code BigDecimal} quotient to be returned. 傳入精度
        //@param roundingMode rounding mode to apply. 傳入round的模式
        double dt1=2.0;
        double dt2=3.0;
        BigDecimal dt1BigDec=new BigDecimal(Double.toString(dt1));
        BigDecimal dt2BigDec=new BigDecimal(Double.toString(dt2));
        //保留六位小數
        BigDecimal divideB = dt1BigDec.divide(dt2BigDec, 6, BigDecimal.ROUND_HALF_UP);
        double divide = divideB.doubleValue();
        System.out.println(divide);//0.666667
    }
}

除並求余運算

import java.math.BigDecimal;

public class Main {
     public static void main(String[] args) {
            BigDecimal amt = new BigDecimal(1001);
            BigDecimal[] results = amt.divideAndRemainder(new BigDecimal(50));
            //商 20
            System.out.println(results[0]);
            //餘數1
            System.out.println(results[1]);
        }


}

三，數組

1.數組自帶的方法

2.操縱數組類Arrays（java.util.Arrays）

sort

升序

int scores[] = new int[]{1,2,3,89,4};
Arrays.sort(scores);

降序

Collections為java.util.Collections
不能使用基本類型（int,double, char），如果是int型需要改成Integer，float要改成Float

Integer scores[] = {1,2,3,89,4};
Arrays.sort(scores, Collections.reverseOrder());

自定義規則排序

Comparator為java.util.Comparator

 Integer[] arr = {5,4,7,9,2,12,54,21,1};
        //降序
        Arrays.sort(arr, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return b-a;
            }
        });
        System.out.println(Arrays.toString(arr));

fill

作用：把數組所有元素都賦值為指定數

int [] scores={12,21,13,24};
Arrays.fill(scores,22);//將數組中所有元素都賦值為22

copyOfRange

作用：將數組指定的範圍複製到一個新數組中

        int [] scores1={12,21,13,24};
        int[]scores= Arrays.copyOfRange(scores1,1,3);
        //21,13
        for(int i=0;i<scores.length;i++){
            System.out.println(scores[i]);
        }

toString

作用：將數組內容轉換稱為字元串

int[] arr = {1,3,5,6};
String s = Arrays.toString(arr);
 //列印字元串，輸出內容
System.out.println(s);//[1,3,5,6]

asList

作用：將數組轉換為集合

只有是引用類型的才能使用泛型

Integer[] a = {1,2,3,4};
List<Integer> list= Arrays.asList(a);

四，集合

1.集合自帶的方法

2.操作集合的類Collections（java.util.Collections）

sort

自定義規則排序

package shuZu;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class sort {
    public static void main(String[] args) {
        List<Student> stus = new ArrayList<>();
        Student stu1 = new Student();
        Student stu2 = new Student();
        Student stu3 = new Student();
        Student stu4 = new Student();
        Student stu5 = new Student();
        Student stu6 = new Student();

        stu1.setAge(30);
        stu2.setAge(20);
        stu3.setAge(40);
        stu4.setAge(30);
        stu5.setAge(40);
        stu6.setAge(20);

        stu1.setNum(1);
        stu2.setNum(2);
        stu3.setNum(3);
        stu4.setNum(4);
        stu5.setNum(5);
        stu6.setNum(6);

        stu1.setName("張三");
        stu2.setName("李四");
        stu3.setName("王五");
        stu4.setName("趙六");
        stu5.setName("陳七");
        stu6.setName("周八");

        stus.add(stu1);
        stus.add(stu2);
        stus.add(stu3);
        stus.add(stu4);
        stus.add(stu5);
        stus.add(stu6);

        Collections.sort(stus, new Comparator<Student>() {

            @Override
            public int compare(Student s1, Student s2) {
                int flag;
                // 首選按年齡升序排序
                flag = s1.getAge() - s2.getAge();
                if (flag == 0) {
                    // 再按學號升序排序
                    flag = s1.getNum() - s2.getNum();
                }
                return flag;
            }
        });

        System.out.println("年齡       學號       姓名  ");
        for (Student s : stus) {
            System.out.println(s.getAge() + "   " + s.getNum() + "   " + s.getName());
        }
    }
}
class Student{
    int age;
    int num;
    String name;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

將集合翻轉並將結果都添加到另外一個集合（reverse(list)，addAll(list)）

//將tem的每位數字加入集合list，將list倒序，將list全添加到result集合裡面
private void tc(int tem, List<Integer> result) {
        // TODO Auto-generated method stub
        List<Integer>list=new ArrayList<>();
        while(tem!=0) {
            int t=tem%10;
            tem/=10;
            list.add(t);
        }
        Collections.reverse(list);
        result.addAll(list);
        
    }

補充：hashMap按值排序

輸入

第一行輸入n個字元串

其餘n行：n個字元串

輸出每個字元串從大到小出現次數

格式出現次數 – 字元串

eg:

實現程式碼

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Map<String, Integer>map=new HashMap<>();
        Scanner sca=new Scanner(System.in);
        int n=sca.nextInt();
        sca.nextLine();
        for(int i=0;i<n;i++) {
            String str=sca.nextLine();
            int num=map.getOrDefault(str, 0)+1;
            map.put(str, num);
        }
        List<Map.Entry<String, Integer>>list=new ArrayList<>();
        for(Map.Entry<String, Integer>mv:map.entrySet()) {
            list.add(mv);
        }
        Collections.sort(list,new Comparator<Map.Entry<String, Integer>>() {

            @Override
            public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
                // TODO Auto-generated method stub
                return o2.getValue()-o1.getValue();
            }
        });
        System.out.println();
        for(int i=0;i<list.size();i++) {
            Map.Entry<String, Integer> mvEntry=list.get(i);
            String key=mvEntry.getKey();
            Integer value=mvEntry.getValue();
            System.out.println(value +" - "+ key);
        }
    }
}

輸出

2 - 2 -1 -1 22
1 - 1 28 74 35
1 - 1 11 66 0
1 - 3 35 28 7

補充：HashSet的遍歷

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Main {
public static void main(String[] args) {
    //HashSet沒有get方法，所以只能通過加強for循環或迭代器實現遍歷
    Set<Integer>set=new HashSet<>();
    set.add(1);
    set.add(2);
    set.add(9);
    set.add(2);
    set.add(7);
    //加強for循環
    for(Integer s:set) {
        System.out.println(s);
    }
    //迭代器
    Iterator<Integer> itor=set.iterator();
    while(itor.hasNext()) {
        System.out.println(itor.next());
    }
}
}

五，字元串

toCharArray

作用：字元串轉換為字元數組

String str="Hello";
char[] chars = str.toCharArray();

其它方法

創建實例：

String str = new String(); str = “String”;

1、char charAt(int index)：返回指定索引位置的字元

 　　System.out.println(str.charAt(0));
 　　//return "S";

2、String substring(int beginIndex)：返回指定起始位置至字元串末尾的字元串

 　　System.out.println(str.substring(1));
　//return "tring"

String substring(int beginIndex, int endIndex)：返回指定起始位置（含）到結束位置（不含）之間的字元串

     System.out.println(str.substring(1, 3));
    //return "tr";

3、一個或多個空格分割字元串

String的split方法支援正則表達式；
正則表達式\s表示匹配任何空白字元，+表示匹配一次或多次。

String [] arr = str.split("\\s+");
for(String ss : arr){
    System.out.println(ss);
}

4、int indexOf(String str)：返回指定字元串的索引位置

 　　System.out.println(str.indexOf("i"));
 　　//return "3";

 　　System.out.println(str.indexOf("ing"));
 　　//return "3";

int indexOf(String str, int fromIndex)：返回從指定索引位置fromIndex開始的str的索引位置,如果沒有返回-1

System.out.println(str.indexOf("ing", 2));
　//return "3";

5、String replace(CharSequence oldString, CharSequence newString): 用newString替換字元串中的oldString

　System.out.println(str.replace("g", "gs"));
  //return "Strings";

6、String trim()：返回一個去除兩頭空格的新字元串

 　　String str1 = new String();
 　　str1 =  " "+"string"+" ";
 　　System.out.println(str1.length());
 　　//return "8"
 　　str1 = str1.trim();
 　　System.out.println(str.length());
 　　//return "6"

7、String[ ] split(String regex)：指定正則表達式分隔符，返回一個字元串數組

 　　String str2 = new String();
 　　str2 = "A/B/C";
 　　String s[] = str2.split("/");
 　　System.out.println("s[0] = "+s[0]);
 　　//return"A"
 　　for(String ss: s) {
 　　System.out.print(ss+" ");
 　　}
 　　//return"A B C"

　String[ ] split(String regex, int limit)：指定正則表達式分隔符regex和分隔份數limit，返回一個字元串數組　

 　　String str2 = new String();
 　　str2 = "A/B/C";
 　　String s[] = str2.split("/", 2);
 　　for(String ss: s) {
 　　System.out.print(ss+" ");
 　　}
 　　//return"A B/C"

注意： . 、 | 和 * 等轉義字元，必須得加 \

　　注意：多個分隔符，可以用 | 作為連字元

8、*String toLowerCase()：轉換為小寫字母* *String toUpperCase()：轉換為大寫字母*

9、boolean startsWith(String prefix)：如果字元串以prefix開頭返回true，否則返回false 　 boolean endsWith(String suffix)：如果字元串以suffix結尾返回true，否則返回false

10、boolean equals(Object other)：如果字元串與other相等返回true，否則返回false 　 boolean equalsIgnoreCase(String other)：如果字元串與other相等（忽略大小寫）返回true，否則返回false

字元串查找 indexOf

補充：字元判斷方法

public class Main {
public static void main(String[] args) {
    char c = 'a';
    Boolean arr[]=new Boolean[6];
    arr[0]=Character.isDigit(c);//判斷字元是否數字
    arr[1]=Character.isLetter(c);//判斷字元是否字母
    arr[2]=Character.isLetterOrDigit(c);//判斷字元是否字母或數字
    arr[3]=Character.isLowerCase(c);//判斷字元是否小寫字母
    arr[4]=Character.isUpperCase(c);//判斷字元是否大寫字母
    arr[5]=Character.isWhitespace(c);//判斷字元是否空格[/size]
    for(int i=0;i<arr.length;i++) {
        System.out.println(arr[i]);
    }
}

六，隊列

import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        //add()和remove()方法在失敗的時候會拋出異常(不推薦)
        Queue<String> queue = new LinkedList<String>();
        //添加元素
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("poll="+queue.poll()); //返回第一個元素，並在隊列中刪除
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("element="+queue.element()); //返回第一個元素 
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("peek="+queue.peek()); //返回第一個元素 
        for(String q : queue){
            System.out.println(q);
        }
    }

Queue 中 element() 和 peek()都是用來返回隊列的頭元素，不刪除。

在隊列元素為空的情況下，element() 方法會拋出NoSuchElementException異常，peek() 方法只會返回 null

add()和offer()方法的區別是

區別：兩者都是往隊列尾部插入元素，不同的時候，當超出隊列界限的時候，add（）方法是拋出異常讓你處理，而offer（）方法是直接返回false

所以

添加元素推薦用offer()，返回並刪除頭元素用 poll()，只返回頭元素用peek()

補充：優先順序隊列

以leecode題目連接所有點的最小費用為例

題目描述

給你一個points 數組，表示 2D 平面上的一些點，其中 points[i] = [xi, yi] 。

連接點 [xi, yi] 和點 [xj, yj] 的費用為它們之間的曼哈頓距離：|xi – xj| + |yi – yj| ，其中 |val| 表示 val 的絕對值。

請你返回將所有點連接的最小總費用。只有任意兩點之間有且僅有一條簡單路徑時，才認為所有點都已連接。

來源：力扣（LeetCode）鏈接：//leetcode-cn.com/problems/min-cost-to-connect-all-points 著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

    public Queue<EDGE> priorityQueue = new PriorityQueue<EDGE>(new Comparator<EDGE>() {

        @Override
        public int compare(EDGE o1, EDGE o2) {
            // TODO Auto-generated method stub
            return o1.quanZhi - o2.quanZhi;
        }
    });

    public int getQuanZhi(int xi, int yi, int xj, int yj) {
//        |xi - xj| + |yi - yj|
        return Math.abs(xi - xj) + Math.abs(yi - yj);
    }

    public int vic[];

    public int minCostConnectPoints(int[][] points) {
        vic = new int[points.length + 1];
        // 以節點0為起點開始搜索
        vic[0] = 1;
        int size = 1;
        int result = 0;
        // 將與節點0相連的節點加入優先順序隊列
        for (int i = 1; i < points.length; i++) {
            priorityQueue.offer(new EDGE(0, i, getQuanZhi(points[0][0], points[0][1], points[i][0], points[i][1])));
        }
        while (!priorityQueue.isEmpty()) {
            EDGE edge = priorityQueue.poll();
            int end = edge.end;
            // 如果該節點以及訪問過，則continue
            if (vic[end] == 1) {
                continue;
            }
            result += edge.quanZhi;
            // 節點個數加一
            size++;
            if (size == points.length) {
                break;
            }
            vic[end] = 1;
            // 以該節點來將其周圍節點加入進去
            for (int i = 0; i < points.length; i++) {
                priorityQueue.offer(new EDGE(end, i, getQuanZhi(points[end][0], points[end][1], points[i][0], points[i][1])));
            }
        }
        return result;
    }
}

class EDGE {
    public int start;
    public int end;
    public int quanZhi;

    public EDGE(int start, int end, int quanZhi) {
        this.start = start;
        this.end = end;
        this.quanZhi = quanZhi;
    }
}

七，棧

import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Stack<Integer>stack=new Stack<>();
        //入棧
        stack.push(3);
        stack.push(5);
        stack.push(2);
        //出棧
        while(!stack.isEmpty()) {
            Integer tInteger=stack.pop();
            System.out.print(tInteger);
        };
    }
}

八，操作日期的類GregorianCalendar

以藍橋杯任意年月輸出日曆為例

題目描述

已知2007年1月1日為星期一。設計一函數按照下述格式列印2007年以後（含）某年某月的日曆，2007年以前的拒絕列印。為完成此函數，設計必要的輔助函數可能也是必要的。其中輸入為年分和月份。

注意：短線「-」個數要與題目中一致，否則系統會判為錯誤。

樣例輸入

2010 9

樣例輸出

---------------------
 Su Mo Tu We Th Fr Sa
---------------------
           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
---------------------

程式碼實現

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Calendar;
import java.util.GregorianCalendar;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stringTokenizer = new StringTokenizer("");

    static String nextLine() throws IOException {
        return bufferedReader.readLine();
    }

    static String next() throws IOException {
        while (!stringTokenizer.hasMoreTokens()) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        }
        return stringTokenizer.nextToken();
    }

    static int nextInt() throws NumberFormatException, IOException {
        return Integer.parseInt(next());
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        int yera = nextInt();
        int mouth = nextInt();
        //mouth是從0到11的
        //創建日期對象，將年月日（1）放進去
        GregorianCalendar gregorianCalendar = new GregorianCalendar(yera,mouth-1,1);
        //獲取該月天數
        int days=gregorianCalendar.getActualMaximum(Calendar.DAY_OF_MONTH);
        //獲取該月第一天是星期幾,需要減一
        int xq=gregorianCalendar.get(Calendar.DAY_OF_WEEK)-1;
        System.out.println("---------------------");
        System.out.println(" Su Mo Tu We Th Fr Sa");
        System.out.println("---------------------");
        //輸入前面空格
        int t=0;
        for(int i=0;i<xq;i++) {
            System.out.print("   ");
            t++;
        }
        for(int i=1;i<=days;i++) {
            System.out.printf("%3d", i);
            t++;
            if(t%7==0) {
                System.out.println();
            }
        }
        if(t%7!=0) {
            System.out.println();
        }
        System.out.println("---------------------");
    
    }
}

九，優化io流（不用scanner）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokenizer = new StringTokenizer("");

    static String nextLine() throws IOException {// 讀取下一行字元串
        return reader.readLine();
    }

    static String next() throws IOException {// 讀取下一個字元串
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {// 讀取下一個int型數值
        return Integer.parseInt(next());
    }

    static double nextDouble() throws IOException {// 讀取下一個double型數值
        return Double.parseDouble(next());
    }

    public static void main(String[] args) throws IOException {
       String str= next();
       String str1= next();
       String str2= next();
       String str3= next();
       String str4= next();
       System.out.println(tokenizer.toString());
    }
}

Tags: 演算法