# Java与算法竞赛——注意事项摘录

<<<<<<< HEAD

## Java与算法竞赛——语言相关事项摘录 上

***

> 此处摘录总结一些网上看到的用Java打算法竞赛的常用注意事项和语言相关代码优化。虽然记下来不一定考场上记得就是了。上篇记录一些基本输入输出相关内容，下篇主要介绍容器之类相关语言方向要适应的点。

### 一、输入输出

#### 1. 输入

标准输入方法：

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

优化输入方法：

`Scanner s = new Scanner (new BufferedInputStream(System.in));`

用流处理在数据量大的时候会快一点。

接下来用`Scanner`对象提供的方法来输入：

* 整数：`int a = s.nextInt()`
* 浮点数：`double t = nextDouble()`
* 字符串：`String str = s.nextInt()`

特别地，可以使用`nextLine()`来读取一整行：

`String str = s.nextLine()`

要判断输入是否结束，可以使用`s.hasNext()`：

```java
while(s.hasNext()){
    int a = s.nextInt();
    ...
}
```

#### 2. 输出

标准输出方法：

`System.out.println(n);`

优化输出方法：

`PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));`

`out.println(n);`

`out.printf("%.2f\n", ans);` (可用类似`printf`的方式输出)

如果要格式化输出，可以使用格式类，如`NumberFormat` 或 `DecimalFormat`类：

```java
	public static void main(String[] args) {  
		NumberFormat   formatter   =   new   DecimalFormat( "000000");   
        String  s  =   formatter.format(-1234.567);     //   -001235    
        formatter   =   new   DecimalFormat( "##");   
        s   =   formatter.format(-1234.567);             //   -1235   
        s   =   formatter.format(0);                      //   0   
        formatter   =   new   DecimalFormat( "##00");   
        s   =   formatter.format(0);                     //   00   
        formatter   =   new   DecimalFormat( ".00");   
        s   =   formatter.format(-.567);               //   -.57   
        formatter   =   new   DecimalFormat( "0.00");   
        s   =   formatter.format(-.567);              //   -0.57   
        formatter   =   new   DecimalFormat( "#.#");   
        s   =   formatter.format(-1234.567);         //   -1234.6   
        formatter   =   new   DecimalFormat( "#.######");   
        s   =   formatter.format(-1234.567);        //   -1234.567   
        formatter   =   new   DecimalFormat( ".######");   
        s   =   formatter.format(-1234.567);       //   -1234.567   
        formatter   =   new   DecimalFormat( "#.000000");   
        s   =   formatter.format(-1234.567);      //   -1234.567000           
        formatter   =   new   DecimalFormat( "#,###,###");   
        s   =   formatter.format(-1234.567);      //   -1,235   
        s   =   formatter.format(-1234567.890);  //   -1,234,568   
    }
```

#### 3. 文件读写

输入

```java
FileInputStream fis = new FileInputStream("b.in");  
System.setIn(fis); 
```

输出

```java
FileInputStream fis = new FileInputStream("b.in");  
System.setIn(fis); 
```

这样就可以用重定向的方式在标准输出流读写文件了。

### 二、高精相关

~~y1s1 Java啥都可以用自带类来解决真的爽~~

在Java中没有提供long long，最大提供到long，高于long数据范围的需使用高精度。不过好在Java中提供了简单的高精度方式，不用像某C语言一样要手写。

Java中主要通过调用`BigInteger`和`BigDecimal`来实现高精度。

```java
        BigInteger a = new BigInteger("123456789");
        BigDecimal b = new BigDecimal("233.333");
        BigInteger c = new BigInteger("123");
        System.out.println(c.add(a)); //加
        System.out.println(a.subtract(c)); //减
        System.out.println(a.multiply(c)); //乘
        System.out.println(b.divide(b)); //除
        System.out.println(a.remainder(c)); //取余数
        System.out.println(a.mod(c)); //取余
        System.out.println(c.pow(3)); //c的3次方
        System.out.println(a.gcd(c)); //求最大公约数
        System.out.println(a.compareTo(c)); //比大小，大于则>0，小于则<0，等于则=0
        long d = a.longValue(); //转换为long
        System.out.println(d);
```

输出

> 123456912 123456666 15185185047 1 90 90 1860867 3 1 123456789

注意：使用这两个类时只能使用其内部的方法来进行加减，不能直接使用运算符。

\#补充：关于取余（remainder)与取模（mod）的区别：

> 例子：
>
> -14 取余 3 = -2
>
> -14 mod 3 = 1

取余运算为数学意义上的取余，其结果可以为负，目的是使商尽可能大的情况下获得余数。

而取模运算返回值一定为正，且要求第二个参数（如本例的3）必须>0。目的是使商尽量小的情况下获得正余数。

> Java默认的%运算符是取余，而python是取模。

### 三、常用容器

#### 1. Set

使用`java.util.Hashtag`来实现。

```java
Set<Integer> s = new HashSet<>();
s.add(233);
System.out.println(s.contains(233)); //true
```

#### 2. Map

使用`java.util.HashMap`来实现

```java
Map<Integer,Integer> m = new HashMap<>();
m.put(1, 233);
m.put(2, 666);
m.remove(1);
System.out.println(m.get(1));
```

因为map是无序的，所以需要使用迭代器来遍历map。

```java
Iterator<Map.Entry<Integer, Integer>> it = m.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry<Integer, Integer> e = it.next();
            System.out.println(e.getKey() + " " + e.getValue());
        }
```

#### 3. vector\&list

c++的`vector`对应java中的容器为`Arraylist`。使用`Arraylist`可以用数组的数据结构实现元素的增删查找等等。`ArrayList`是通过**数组**的实现方式实现的，和数组类似，适合查改而不适合插入。

使用`Arraylist`下的方法对其进行增删查改：

```java
ArrayList<Integer> a = new ArrayList<>();
        a.add(123);
        a.set(0,888);
        a.remove(0);
        a.clear();
        a.add(999);
```

其中需要注意，`set(int index, int value)`方法是用于修改`Arraylist`的现有元素的值，不能用于添加元素。如果搜索到的index没有值，会报错。

还可以通过其自带的方法对其进行排序、拷贝：

```java
ArrayList<Integer> b = (ArrayList<Integer>) a.clone();
a.add(666);
Collections.sort(a);
```

至于输出，可以用get()方法来获取单个元素值，通过for循环遍历；也可以和普通数组一样用foreach方式输出：

```java
System.out.println(a.get(1)); 

        for(int i : a){
            System.out.println(i); 
        }
```

> 结果：
>
> 999 666 999

注意：`ArrayList`只能存放引用数据类型，不能存放基础数据类型。

> java还提供另外一种容器 `LinkedList`，与`ArrayList`不同，`LinkedList`是通过**链表**实现的，因此可以直接使用内置的方法执行插入元素操作。当然同列表一样，相对于数组它更适合插入/删除中间元素，而不适合查改。

#### 4. 优先队列

优先队列通过`PriorityQueue`类来实现。优先队列会自动将加入的元素排序，其默认顺序是升序（队首最小）。

定义与增删元素：

```java
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.add("mcyou");
        pq.add("abc");
        pq.add("233");
        pq.remove("abc");
```

> 可以使用offer()方法代替add()方法，区别是offer()不会产生报错。

读取队首：

```java
System.out.println(pq.peek());
System.out.println(pq.poll());
System.out.println(pq.peek());
System.out.println(pq.size());
```

peak()方法可取出队首元素但不删除它，poll()方法则会取出首元素的同时删除它。size()方法可以取出队中的元素数量。

> 输出效果：
>
> 233 233 mcyou 2

如果需要降序排序（队首最大），则需要在定义时声明：

`PriorityQueue<String> pq = new PriorityQueue<>(Collections.reverseOrder());`

修改后重新运行，输出如下：

> qq qq mcyou 2

#### 5. 队列/双向队列

java提供了`queue`类和`deque`两种类，不过既然有deque那就直接用deque吧。

注意：对应的是`ArrayDeque`类。

```java
ArrayDeque<Integer> queue = new ArrayDeque<Integer>()
queue.offer(1); //尽量还是用offer()
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek()); //返回第一个元素
while (!queue.isEmpty()) {
	System.out.println(queue.pop());
```

作为双向队列，相比于普通的queue：

还可以使用`offerFist()`或者`offerLast()` 来在队首或者队尾添加元素。

还可以使用`peekFirst()`或者`peekLast()` 获得队尾或者队首的元素。

还可以使用`pollFirst()`或者`pollLast()`移除并返回队尾或队首的元素。

其他容器的`pop()`、`push()`、`foreach遍历`等等方法这里也适用。

> 队列的意义在于新添加的数据置于队尾，先pop的数据位于队首。所以一般是用offer()来直接在队尾添加元素、用peek()或者poll()取元素，尽量不用push()之类本身与单向队列顺序相违背的方法，否则容易导致混乱。

#### 6. 栈

java也提供了`Stack`类，用以处理先进先出的数据结构。不过使用`deque`来代替也没什么毛病就是了。

栈内置方法介绍：

| 序号 | 方法描述                                            |
| -- | ----------------------------------------------- |
| 1  | boolean empty() 测试堆栈是否为空。                       |
| 2  | Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。             |
| 3  | Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。          |
| 4  | Object push(Object element) 把项压入堆栈顶部。           |
| 5  | int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。 |

声明示例：`Stack<Integer> st = new Stack<Integer>();`

> 参考
>
> [【经验总结】Java在ACM算法竞赛编程中易错点 - Angel\_Kitty](https://www.cnblogs.com/ECJTUACM-873284962/p/7342030.html)

\=======

## Java与算法竞赛——语言相关事项摘录 上

***

> 此处摘录总结一些网上看到的用Java打算法竞赛的常用注意事项和语言相关代码优化。虽然记下来不一定考场上记得就是了。上篇记录一些基本输入输出相关内容，下篇主要介绍容器之类相关语言方向要适应的点。

### 一、输入输出

#### 1. 输入

标准输入方法：

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

优化输入方法：

`Scanner s = new Scanner (new BufferedInputStream(System.in));`

用流处理在数据量大的时候会快一点。

接下来用`Scanner`对象提供的方法来输入：

* 整数：`int a = s.nextInt()`
* 浮点数：`double t = nextDouble()`
* 字符串：`String str = s.nextInt()`

特别地，可以使用`nextLine()`来读取一整行：

`String str = s.nextLine()`

要判断输入是否结束，可以使用`s.hasNext()`：

```java
while(s.hasNext()){
    int a = s.nextInt();
    ...
}
```

#### 2. 输出

标准输出方法：

`System.out.println(n);`

优化输出方法：

`PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));`

`out.println(n);`

`out.printf("%.2f\n", ans);` (可用类似`printf`的方式输出)

如果要格式化输出，可以使用格式类，如`NumberFormat` 或 `DecimalFormat`类：

```java
	public static void main(String[] args) {  
		NumberFormat   formatter   =   new   DecimalFormat( "000000");   
        String  s  =   formatter.format(-1234.567);     //   -001235    
        formatter   =   new   DecimalFormat( "##");   
        s   =   formatter.format(-1234.567);             //   -1235   
        s   =   formatter.format(0);                      //   0   
        formatter   =   new   DecimalFormat( "##00");   
        s   =   formatter.format(0);                     //   00   
        formatter   =   new   DecimalFormat( ".00");   
        s   =   formatter.format(-.567);               //   -.57   
        formatter   =   new   DecimalFormat( "0.00");   
        s   =   formatter.format(-.567);              //   -0.57   
        formatter   =   new   DecimalFormat( "#.#");   
        s   =   formatter.format(-1234.567);         //   -1234.6   
        formatter   =   new   DecimalFormat( "#.######");   
        s   =   formatter.format(-1234.567);        //   -1234.567   
        formatter   =   new   DecimalFormat( ".######");   
        s   =   formatter.format(-1234.567);       //   -1234.567   
        formatter   =   new   DecimalFormat( "#.000000");   
        s   =   formatter.format(-1234.567);      //   -1234.567000           
        formatter   =   new   DecimalFormat( "#,###,###");   
        s   =   formatter.format(-1234.567);      //   -1,235   
        s   =   formatter.format(-1234567.890);  //   -1,234,568   
    }
```

#### 3. 文件读写

输入

```java
FileInputStream fis = new FileInputStream("b.in");  
System.setIn(fis); 
```

输出

```java
FileInputStream fis = new FileInputStream("b.in");  
System.setIn(fis); 
```

这样就可以用重定向的方式在标准输出流读写文件了。

### 二、高精相关

~~y1s1 Java啥都可以用自带类来解决真的爽~~

在Java中没有提供long long，最大提供到long，高于long数据范围的需使用高精度。不过好在Java中提供了简单的高精度方式，不用像某C语言一样要手写。

Java中主要通过调用`BigInteger`和`BigDecimal`来实现高精度。

```java
        BigInteger a = new BigInteger("123456789");
        BigDecimal b = new BigDecimal("233.333");
        BigInteger c = new BigInteger("123");
        System.out.println(c.add(a)); //加
        System.out.println(a.subtract(c)); //减
        System.out.println(a.multiply(c)); //乘
        System.out.println(b.divide(b)); //除
        System.out.println(a.remainder(c)); //取余数
        System.out.println(a.mod(c)); //取余
        System.out.println(c.pow(3)); //c的3次方
        System.out.println(a.gcd(c)); //求最大公约数
        System.out.println(a.compareTo(c)); //比大小，大于则>0，小于则<0，等于则=0
        long d = a.longValue(); //转换为long
        System.out.println(d);
```

输出

> 123456912 123456666 15185185047 1 90 90 1860867 3 1 123456789

注意：使用这两个类时只能使用其内部的方法来进行加减，不能直接使用运算符。

\#补充：关于取余（remainder)与取模（mod）的区别：

> 例子：
>
> -14 取余 3 = -2
>
> -14 mod 3 = 1

取余运算为数学意义上的取余，其结果可以为负，目的是使商尽可能大的情况下获得余数。

而取模运算返回值一定为正，且要求第二个参数（如本例的3）必须>0。目的是使商尽量小的情况下获得正余数。

> Java默认的%运算符是取余，而python是取模。

### 三、常用容器

#### 1. Set

使用`java.util.Hashtag`来实现。

```java
Set<Integer> s = new HashSet<>();
s.add(233);
System.out.println(s.contains(233)); //true
```

#### 2. Map

使用`java.util.HashMap`来实现

```java
Map<Integer,Integer> m = new HashMap<>();
m.put(1, 233);
m.put(2, 666);
m.remove(1);
System.out.println(m.get(1));
```

因为map是无序的，所以需要使用迭代器来遍历map。

```java
Iterator<Map.Entry<Integer, Integer>> it = m.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry<Integer, Integer> e = it.next();
            System.out.println(e.getKey() + " " + e.getValue());
        }
```

#### 3. vector\&list

c++的`vector`对应java中的容器为`Arraylist`。使用`Arraylist`可以用数组的数据结构实现元素的增删查找等等。`ArrayList`是通过**数组**的实现方式实现的，和数组类似，适合查改而不适合插入。

使用`Arraylist`下的方法对其进行增删查改：

```java
ArrayList<Integer> a = new ArrayList<>();
        a.add(123);
        a.set(0,888);
        a.remove(0);
        a.clear();
        a.add(999);
```

其中需要注意，`set(int index, int value)`方法是用于修改`Arraylist`的现有元素的值，不能用于添加元素。如果搜索到的index没有值，会报错。

还可以通过其自带的方法对其进行排序、拷贝：

```java
ArrayList<Integer> b = (ArrayList<Integer>) a.clone();
a.add(666);
Collections.sort(a);
```

至于输出，可以用get()方法来获取单个元素值，通过for循环遍历；也可以和普通数组一样用foreach方式输出：

```java
System.out.println(a.get(1)); 

        for(int i : a){
            System.out.println(i); 
        }
```

> 结果：
>
> 999 666 999

注意：`ArrayList`只能存放引用数据类型，不能存放基础数据类型。

> java还提供另外一种容器 `LinkedList`，与`ArrayList`不同，`LinkedList`是通过**链表**实现的，因此可以直接使用内置的方法执行插入元素操作。当然同列表一样，相对于数组它更适合插入/删除中间元素，而不适合查改。

#### 4. 优先队列

优先队列通过`PriorityQueue`类来实现。优先队列会自动将加入的元素排序，其默认顺序是升序（队首最小）。

定义与增删元素：

```java
        PriorityQueue<String> pq = new PriorityQueue<>();
        pq.add("mcyou");
        pq.add("abc");
        pq.add("233");
        pq.remove("abc");
```

> 可以使用offer()方法代替add()方法，区别是offer()不会产生报错。

读取队首：

```java
System.out.println(pq.peek());
System.out.println(pq.poll());
System.out.println(pq.peek());
System.out.println(pq.size());
```

peak()方法可取出队首元素但不删除它，poll()方法则会取出首元素的同时删除它。size()方法可以取出队中的元素数量。

> 输出效果：
>
> 233 233 mcyou 2

如果需要降序排序（队首最大），则需要在定义时声明：

`PriorityQueue<String> pq = new PriorityQueue<>(Collections.reverseOrder());`

修改后重新运行，输出如下：

> qq qq mcyou 2

#### 5. 队列/双向队列

java提供了`queue`类和`deque`两种类，不过既然有deque那就直接用deque吧。

注意：对应的是`ArrayDeque`类。

```java
ArrayDeque<Integer> queue = new ArrayDeque<Integer>()
queue.offer(1); //尽量还是用offer()
queue.offer(2);
queue.offer(3);
System.out.println(queue.peek()); //返回第一个元素
while (!queue.isEmpty()) {
	System.out.println(queue.pop());
```

作为双向队列，相比于普通的queue：

还可以使用`offerFist()`或者`offerLast()` 来在队首或者队尾添加元素。

还可以使用`peekFirst()`或者`peekLast()` 获得队尾或者队首的元素。

还可以使用`pollFirst()`或者`pollLast()`移除并返回队尾或队首的元素。

其他容器的`pop()`、`push()`、`foreach遍历`等等方法这里也适用。

> 队列的意义在于新添加的数据置于队尾，先pop的数据位于队首。所以一般是用offer()来直接在队尾添加元素、用peek()或者poll()取元素，尽量不用push()之类本身与单向队列顺序相违背的方法，否则容易导致混乱。

#### 6. 栈

java也提供了`Stack`类，用以处理先进先出的数据结构。不过使用`deque`来代替也没什么毛病就是了。

栈内置方法介绍：

| 序号 | 方法描述                                            |
| -- | ----------------------------------------------- |
| 1  | boolean empty() 测试堆栈是否为空。                       |
| 2  | Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。             |
| 3  | Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。          |
| 4  | Object push(Object element) 把项压入堆栈顶部。           |
| 5  | int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。 |

声明示例：`Stack<Integer> st = new Stack<Integer>();`

> 参考
>
> [【经验总结】Java在ACM算法竞赛编程中易错点 - Angel\_Kitty](https://www.cnblogs.com/ECJTUACM-873284962/p/7342030.html)
>
> > > > > > > 2db037fcf6de5bcf588074205a43fc7a350195a0 [算法竞赛中的JAVA使用笔记](https://www.myblog.link/2016/11/14/Note-of-java/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/java-xiang-guan/java-yu-suan-fa-jing-sai-zhu-yi-shi-xiang-zhai-lu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.