tk's blog
  • tk's blog Read Me
  • 算法相关
    • 数据结构
      • 【集训整理】 旋转treap模板
      • 二叉树及相关数据结构的java语言实现
      • 快乐树0x01:AVL树的java实现
      • 快乐树0x02 线段树实现(c++)
      • 链表的Java语言实现
    • 算法
      • DP的背包问题小结-java语言描述
      • 【集训整理】2-SAT问题 模板题
      • 【集训整理】Tarjan算法 模板题
      • 【集训整理】差分约束 模板题
      • 【集训整理】最近公共祖先LCA 模板题
      • 二分查找与二分答案-java实现
      • 动态规划-java语言练习一:暴力DP
      • 快速幂
      • 状态压缩DP-java描述
      • 差分
      • 乘法逆元
    • 题解
      • CFRound-GoodBye2022题解
  • java相关
    • Java与算法竞赛——注意事项摘录
    • java面向对象简要总结 一
    • java面向对象简要总结 三
    • java面向对象简要总结 二
  • 后端相关
    • Linux-Crontab命令
    • Spring Data JPA 使用方法
    • Spring集成Artemis实现JSM的异步消息传递
    • Spring使用自定义配置项
    • MIT6.824分布式系统Lab1.MapReduce笔记
    • MIT6.824分布式系统Lab2-Raft-A笔记
    • MIT6.824分布式系统Lab2-Raft-B笔记
  • 杂谈
    • 杂谈-关于2021
  • 杂项
    • c语言 scanf的返回值
    • 系统设计
  • 计科基础
    • 编译原理
      • 编译原理:词法分析笔记
    • CSAPP 第二章笔记
    • 计算机组成原理笔记
    • CSAPP Lab1. Datalab
    • CSAPP Lab2 Bomblab
  • C++每日一题
    • C++每日一题 Day 1 肥宅水
    • C++每日一题 Day 2 数字反转
    • C++每日一题 Day 3 理五的凡尔赛风气
    • C++每日一题 Day 4 我喜欢这个数
    • C++每日一题 Day 5 数字楼梯
    • C++每日一题 Day 6 插火把
    • C++每日一题 Day 7 贪吃蛇
    • C++每日一题 Day 8 蒙德最强战力
    • C++每日一题 Day 9 璃月七星选举
    • C每日一题 Day 2 肥宅水
    • C每日一题 Day 3 理五的凡尔赛风气
    • C语言每日一题 Day 1 荧妹好感队
由 GitBook 提供支持
在本页
  • Java与算法竞赛——语言相关事项摘录 上
  • 一、输入输出
  • 二、高精相关
  • 三、常用容器
  • Java与算法竞赛——语言相关事项摘录 上
  • 一、输入输出
  • 二、高精相关
  • 三、常用容器
  1. java相关

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():

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类:

	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. 文件读写

输入

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

输出

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

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

二、高精相关

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

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

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

        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来实现。

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

2. Map

使用java.util.HashMap来实现

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。

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下的方法对其进行增删查改:

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没有值,会报错。

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

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

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

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

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

结果:

999 666 999

注意:ArrayList只能存放引用数据类型,不能存放基础数据类型。

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

4. 优先队列

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

定义与增删元素:

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

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

读取队首:

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类。

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与算法竞赛——语言相关事项摘录 上


此处摘录总结一些网上看到的用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():

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类:

	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. 文件读写

输入

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

输出

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

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

二、高精相关

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

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

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

        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来实现。

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

2. Map

使用java.util.HashMap来实现

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。

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下的方法对其进行增删查改:

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没有值,会报错。

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

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

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

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

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

结果:

999 666 999

注意:ArrayList只能存放引用数据类型,不能存放基础数据类型。

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

4. 优先队列

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

定义与增删元素:

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

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

读取队首:

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类。

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相关下一页java面向对象简要总结 一

最后更新于2年前

2db037fcf6de5bcf588074205a43fc7a350195a0

【经验总结】Java在ACM算法竞赛编程中易错点 - Angel_Kitty
【经验总结】Java在ACM算法竞赛编程中易错点 - Angel_Kitty
算法竞赛中的JAVA使用笔记