算法竞赛知识点总结（JAVA版）

字数统计: 1.8k字   |   阅读时长≈ 7分

摘要：算法竞赛中一些常用知识总结（JAVA版）

前言：今天总结了一下以往算法竞赛中常用到的知识点，包括常用到的方法，和一些常见的问题

OJ术语

简称 英文名称 中文名称
OJ Online Judge 在线判题系统
AC Accepted 通过
WA Wrong Answer 答案错误
TLE Time Limit Exceed 超时
OLE Output Limit Exceed 超过输出限制
MLE Memory Limit Exceed 超内存
RE Runtime Error 运行时错误
PE Presentation Error 格式错误
CE Compile Error 无法编译

常见数据结构的特点

数据结构 优点 缺点
数组 插入快，若是知道下标，可以非常快速的存储 查找慢，删除慢，大小固定
有序数组 比无序的数组结构查找更快 删除和插入慢，大小固定
栈 提供后进先出方式的存储 存储其他的项很慢
队列 提供先进后出的方式的存储 存储其他的项很慢
链表 插入快，删除快 查找慢
二叉树 查找，插入，删除都快（若树保持平衡) 删除算法复杂
红—黑树 查找，插入，删除都快（树总是平衡的） 算法复杂
2-3-4树 查找，插入，删除都快。树总是平衡的。类似的树对磁盘的存储有用 算法复杂
哈希表 如果关键字已知则存储极快。插入快 删除慢，如果不知道关键字则存储很慢，对存储的空间使用不充分
堆 插入，删除快，对最大数据项的存储很快 对其他数据项存在慢
图 对现实世界的建模 有些算法慢且复杂

String类

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
31
32
33
34
35
36
37
38
int indexOf();
	//返回指定字符串位置
int lastIndexOf();
    //返回指定字符串在此字符串中最后一次出现处的索引。
String substring(int beginIndex,int endIndex)
    //返回字符串的索引为:beginIndex到endIndex间的字符串（不包含endIndex）
int compareTo(String str);
    //按字典顺序将此 String 对象表示的字符序列与参数字符串所表示的字符序列进行比较。
    //如果按字典顺序此 String 对象位于参数字符串之前，则比较结果为一个负整数。
    //如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数。
    //如果这两个字符串相等，则结果为 0。
    //如：
        String a="a";
        String b="z";
        System.out.println(a.compareTo(b));// -25
        String a="z";
        String b="a";
        System.out.println(a.compareTo(b));// 25
        String a="z";
        String b="z";
        System.out.println(a.compareTo(b));// 0
char charAt(int index)；
    //返回字符串指定索引的字符；
String replace(参数1，参数2)
    //用参数2替换参数1，并返回替换后的字符串
String[] split(String regex)
    //分割字符串
    //如：
        String a="abss-afss-df";
        String[] strings=a.split("-");
        System.out.println(strings.length);
        for (String s:strings
             ) {
            System.out.print(s+" ");
        }
     //输出：
     //3
	 //abss afss df

Spring类型转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
在Java中将String转换为char。
1. 使用String.charAt(index)（返回值为char）可以得到String中某一指定位置的char。
2. 使用String.toCharArray()（返回值为char[]）可以得到将包含整个String的char数组。这样我们就能够使用从0开始的位置索引来访问string中的任意位置的元素。

在Java中将String转换为Long。
Long.valueOf("String")返回Long包装类型
包装类型： Byte，Integer，Short，Long，Boolean，Character，Float，Double等

Long.parseLong("String")返回long基本数据类型
基本数据类型：byte，int， short， long， boolean，char， float，double等

在Java中将String转换为int。
(1)Integer.parseInt(str)
(2)Integer.valueOf(str).intValue()

Math类

1
2
3
4
5
6
7
8
9
10
 abs(数值类型参数)
    //返回参数的绝对值
 max(参数1，参数2)
    //返回两个参数的最大值
 min(参数1，参数2)
    //返回两个参数的最小值
double pow(double a,double b)
    //返回第一个参数的第二个参数次幂的值。
double sqrt(double a);
	//返回参数的正平方根

List接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//接口实现类：
//ArrayList LinkedList 等
void add(int index,Object o)
    //在列表的指定位置插入指定元素
    //index参数可省略，则向尾部添加指定的元素
boolean contains(Object o)
	//如果列表包含指定的元素，则返回true。
int indexOf()
    //返回指定字符串位置
int size()
    //返回集合类中存放元素的个数
set(int index,Object o)
    //用指定的元素替换列表中的指定位置的元素
remove(int i)
    //参数是 int类型：移除列表中指定位置的元素，并返回该元素
    //参数是 Object类型：移除列表中第一次出现的该元素，并返回boolean类型
boolean isEmpty()
    //判断列表是否为空，若是返回true

Stack类

1
2
3
4
5
6
7
8
boolean empty()
    //判断堆栈是否是空
E peek()
    //返回堆栈的顶部的对象，但不移除他
E pop()
    //移除堆栈的顶部的对象，并返回该对象
E push(E item)
    //把项压入堆栈顶部

Queue（队列）

1
2
3
4
5
6
boolean offer(e)
    //插入元素
E poll()
    //获取并移除队列的头元素
E element()
    //获取，但不移除此队列的头元素

Arrays

1
2
void sort(数组参数)
    //将参数的数组按升序进行排序

##BigInteger（整形）和BigDecimal（浮点型）

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
31
32
33
34
35
//BigDecimal类型构造方法
BigDecimal(double val)
          //将 double 转换为 BigDecimal，后者是 double 的二进制浮点值准确的十进制表示形式。
BigDecimal(int val)
          //将 int 转换为 BigDecimal。
BigDecimal(long val)
          //将 long 转换为 BigDecimal。
BigDecimal(String val)
          //将 BigDecimal 的字符串表示形式转换为 BigDecimal。
//BigInteger类型构造方法
BigInteger(int val)
          //将 int 转换为 BigInteger。
BigInteger(String val)
          //将 BigDecimal 的字符串表示形式转换为 BigInteger。
//BigInteger转换方法
BigInteger valueOf(long val)
          //返回其值等于指定 long 的值的 BigInteger。
		  //如：BigInteger bi1=new BigInteger(1000);
//通用方法
BigInteger(BigDecimal).max(BigInteger(BigDecimal))
    //返回最大数
BigInteger(BigDecimal).min(BigInteger(BigDecimal))
    //返回最小数
BigInteger(BigDecimal).add(BigInteger(BigDecimal))
    //相当于：+
BigInteger(BigDecimal).subtract(BigInteger(BigDecimal))
    //相当于：-
BigInteger(BigDecimal).multiply(BigInteger(BigDecimal))
    //相当于：*
BigInteger(BigDecimal).divide(BigInteger(BigDecimal))
    //相当于：/
BigInteger(BigDecimal).mod(BigInteger(BigDecimal))
    //相当于：%
BigInteger(BigDecimal).abs()
    //返回其值是此 BigIntege(BigDecimal)r 的绝对值的 BigInteger(BigDecimal)。

TreeSet

1
2
3
4
5
6
contains()
//如果此 set 包含指定的元素，则返回 true。
floor()
//返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。
higher()
//返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

十进制转二进制

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
31
十进制转成十六进制：
Integer.toHexString(int i)
十进制转成八进制
Integer.toOctalString(int i)
十进制转成二进制
Integer.toBinaryString(int i)
十六进制转成十进制
Integer.valueOf("FFFF",16).toString()
八进制转成十进制
Integer.valueOf("876",8).toString()
二进制转十进制
Integer.valueOf("0101",2).toString()
有什么方法可以直接将2,8,16进制直接转换为10进制的吗？
java.lang.Integer类
parseInt(String s, int radix)
使用第二个参数指定的基数，将字符串参数解析为有符号的整数。
examples from jdk:
parseInt("0", 10) returns 0
parseInt("473", 10) returns 473
parseInt("-0", 10) returns 0
parseInt("-FF", 16) returns -255
parseInt("1100110", 2) returns 102
parseInt("2147483647", 10) returns 2147483647
parseInt("-2147483648", 10) returns -2147483648
parseInt("2147483648", 10) throws a NumberFormatException
parseInt("Kona", 10) throws a NumberFormatException
parseInt("Kona", 27) returns 411787
进制转换如何写（二，八，十六）
Integer.toBinaryString
Integer.toOctalString
Integer.toHexString

四舍五入

1
String.format("%.2f", Math.pow(r,2) * 3.14)

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

教练，我想学技术！
我主要是以后端技术为主，偶尔看看网络安全相关的内容，或者编写一些有趣的脚本！