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()
:
2. 输出
标准输出方法:
System.out.println(n);
优化输出方法:
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
out.println(n);
out.printf("%.2f\n", ans);
(可用类似printf
的方式输出)
如果要格式化输出,可以使用格式类,如NumberFormat
或 DecimalFormat
类:
3. 文件读写
输入
输出
这样就可以用重定向的方式在标准输出流读写文件了。
二、高精相关
y1s1 Java啥都可以用自带类来解决真的爽
在Java中没有提供long long,最大提供到long,高于long数据范围的需使用高精度。不过好在Java中提供了简单的高精度方式,不用像某C语言一样要手写。
Java中主要通过调用BigInteger
和BigDecimal
来实现高精度。
输出
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
来实现。
2. Map
使用java.util.HashMap
来实现
因为map是无序的,所以需要使用迭代器来遍历map。
3. vector&list
c++的vector
对应java中的容器为Arraylist
。使用Arraylist
可以用数组的数据结构实现元素的增删查找等等。ArrayList
是通过数组的实现方式实现的,和数组类似,适合查改而不适合插入。
使用Arraylist
下的方法对其进行增删查改:
其中需要注意,set(int index, int value)
方法是用于修改Arraylist
的现有元素的值,不能用于添加元素。如果搜索到的index没有值,会报错。
还可以通过其自带的方法对其进行排序、拷贝:
至于输出,可以用get()方法来获取单个元素值,通过for循环遍历;也可以和普通数组一样用foreach方式输出:
结果:
999 666 999
注意:ArrayList
只能存放引用数据类型,不能存放基础数据类型。
java还提供另外一种容器
LinkedList
,与ArrayList
不同,LinkedList
是通过链表实现的,因此可以直接使用内置的方法执行插入元素操作。当然同列表一样,相对于数组它更适合插入/删除中间元素,而不适合查改。
4. 优先队列
优先队列通过PriorityQueue
类来实现。优先队列会自动将加入的元素排序,其默认顺序是升序(队首最小)。
定义与增删元素:
可以使用offer()方法代替add()方法,区别是offer()不会产生报错。
读取队首:
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
类。
作为双向队列,相比于普通的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与算法竞赛——语言相关事项摘录 上
此处摘录总结一些网上看到的用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()
:
2. 输出
标准输出方法:
System.out.println(n);
优化输出方法:
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
out.println(n);
out.printf("%.2f\n", ans);
(可用类似printf
的方式输出)
如果要格式化输出,可以使用格式类,如NumberFormat
或 DecimalFormat
类:
3. 文件读写
输入
输出
这样就可以用重定向的方式在标准输出流读写文件了。
二、高精相关
y1s1 Java啥都可以用自带类来解决真的爽
在Java中没有提供long long,最大提供到long,高于long数据范围的需使用高精度。不过好在Java中提供了简单的高精度方式,不用像某C语言一样要手写。
Java中主要通过调用BigInteger
和BigDecimal
来实现高精度。
输出
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
来实现。
2. Map
使用java.util.HashMap
来实现
因为map是无序的,所以需要使用迭代器来遍历map。
3. vector&list
c++的vector
对应java中的容器为Arraylist
。使用Arraylist
可以用数组的数据结构实现元素的增删查找等等。ArrayList
是通过数组的实现方式实现的,和数组类似,适合查改而不适合插入。
使用Arraylist
下的方法对其进行增删查改:
其中需要注意,set(int index, int value)
方法是用于修改Arraylist
的现有元素的值,不能用于添加元素。如果搜索到的index没有值,会报错。
还可以通过其自带的方法对其进行排序、拷贝:
至于输出,可以用get()方法来获取单个元素值,通过for循环遍历;也可以和普通数组一样用foreach方式输出:
结果:
999 666 999
注意:ArrayList
只能存放引用数据类型,不能存放基础数据类型。
java还提供另外一种容器
LinkedList
,与ArrayList
不同,LinkedList
是通过链表实现的,因此可以直接使用内置的方法执行插入元素操作。当然同列表一样,相对于数组它更适合插入/删除中间元素,而不适合查改。
4. 优先队列
优先队列通过PriorityQueue
类来实现。优先队列会自动将加入的元素排序,其默认顺序是升序(队首最小)。
定义与增删元素:
可以使用offer()方法代替add()方法,区别是offer()不会产生报错。
读取队首:
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
类。
作为双向队列,相比于普通的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
2db037fcf6de5bcf588074205a43fc7a350195a0 算法竞赛中的JAVA使用笔记
最后更新于