Java算法比赛常用API(笔记)
大数类 BigInteger 和 BigDecimal
创建
//1.直接声明
BigInteger a;
BigDecimal b;
//2.使用构造函数初始化
BigInteger a = new BigInteger("123456789101112131415");
BigDecimal b = new BigDecimal("123456.123456");
赋值
BigInteger.valueOf(long val);
BigDecimal.valueOf(double val);
BigInteger a;
BigDecimal b;
//注意 val 不能超过 long 类型的最大取值9223372036854775807, 超过int时要在数后面加L如:
a = BigInteger.valueOf(123456789101112L); //大于int范围的要加L
b = BigDecimal.valueOf(123456.12341235); // 超出的小数位数会自动舍弃
加法
BigInteger.add(BigInteger);
BigDecimal.add(BigDecimal);
BigInteger a, b, c;
a = BigInteger.valueOf(123456789); // 赋值为 123456789
b = BigInteger.valueOf(987654321); // 赋值为 987654321
c = a.add(b);
System.out.print(c);
输出:
1111111110
1111111110
减法
BigInteger.subtract(BigInteger);
BigDecimal.sbutract(BigDecimal);
乘法
BigInteger.multiply(BigInteger);
BigDecimal.multiply(BigDecimal);
除法
BigInteger.divide(BigInteger);
BigDecimal.divide(BigDecimal);
*取余
BigInteger.mod(BigInteger);
BigInteger a, b, c;
a = BigInteger.valueOf(987654321); // 赋值为 987654321
b = BigInteger.valueOf(123456789); // 赋值为 123456789
c = a.mod(b);
System.out.print(c);
输出:
9
*求最大公因数、
BigInteger.gcd(BigInteger);
BigInteger a, b, c;
a = BigInteger.valueOf(987654321); // 赋值为 987654321
b = BigInteger.valueOf(123456789); // 赋值为 123456789
c = a.gcd(b);
System.out.print(c);
输出:
9
求最值
BigInteger.max(BigInteger) , BigDecimal.max(BigDecimal) 最大值
BigInteger.min(BigInteger) , BigDecimal.min(BigDecimal) 最小值
*(a^b)%mod
BigInteger.modPow(BigInteger, BigInteger);
BigInteger a, b, c, mod;
a = BigInteger.valueOf(987654321); // 赋值为 987654321
b = BigInteger.valueOf(123456789); // 赋值为 123456789
mod = BigInteger.valueOf(10007);
c = a.modPow(b, mod); //(a^b)%mod
System.out.println(c);
输出:
718
比较大小
BigInteger.compareTo(BigInteger);
BigDecimal.compareTo(BigDecimal);
BigInteger a, b;
int c;
a = BigInteger.valueOf(987654321); // 赋值为 987654321
b = BigInteger.valueOf(123456789); // 赋值为 123456789
c = a.compareTo(b); // a 和 b
System.out.println(c);
c = b.compareTo(b); // b 和 b
System.out.println(c);
c = b.compareTo(a); // c 和 c
System.out.println(c);
输出:
1
0
-1
可见, 对于a.compareTo(b), a和b进行比较如果:
a > b 返回 1
a == b 返回 0
a < b 返回-1
*进制转化
使用构造函数BigInteger(String, int index);可以把一个index进制的字符串,转化为10进制的BigInteger;
BigInteger a = new BigInteger("111110", 2);把111110变为10进制赋值给a
System.out.println(a.toString(16));把a转化为16进制的字符串输出
类型转化
BigInteger.toBigDecimal() //把BigInteger 转化为 BigDecimal
BigDecimal.toBigInteger() //把BigDecimal 转化为 BigInteger
BigInteger a = new BigInteger(1);
BigDecimal b = new BigDecimal(2);
b.toBigInteger(); // 把BigDecimal转为BigInteger
a.toBigDecimal(); // 把BigInteger转为BigDecimal
-BigDecimal的精度问题
BigDecimal的舍入模式
想象一个数轴,从负无穷到正无穷,向哪舍入,就是趋向于哪, 向0就是舍入后要更趋近于0.
ROUND_DOWN 向零舍入。 即1.55 变为 1.5 , -1.55 变为-1.5
ROUND_CEILING 向正无穷舍入. 即 1.55 变为 1.6 , -1.55 变为 -1.5
ROUND_FLOOR 向负无穷舍入. 即 1.55 变为 1.5 , -1.55 变为 -1.6
ROUND_HALF_UP 四舍五入 即1.55 变为1.6, -1.55变为-1.6
ROUND_HALF_DOWN 五舍六入 即 1.55 变为 1.5, -1.5变为-1.5
ROUND_HALF_EVEN 如果舍入前一位的数字为偶数,则采用HALF_DOWN奇数则采用HALF_UP 如1.55 采用HALF_UP 1.45采用HALF_DOWN
ROUND_UP 向远离0的方向舍入 即 1.55 变为 1.6 , -1.55 变为-1.6
ROUND_UNNECESSARY 有精确的位数时,不需要舍入
import java.math.*;
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args){
BigDecimal a, b, c;
a = BigDecimal.valueOf(1.51);
b = BigDecimal.valueOf(1.37);
c = a.divide(b,100,BigDecimal.ROUND_DOWN);//采用向0舍入并并保留100位小数
System.out.println(c);
}
}
输出:
1.1021897810218978102189781021897810218978102189781021897810218978102189781021897810218978102189781021
保留n位小数
setScale(int newScale, RoundingMode roundingMode);
import java.math.*;
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args){
BigDecimal a = new BigDecimal("1.10218");
a = a.setScale(4,BigDecimal.ROUND_HALF_UP);//四舍五入保留四位小数
System.out.println(a);
}
}
Math类
求最值
最小值
Math.min(int a, int b)
Math.min(float a, float b)
Math.min(double a, doubleb)
Math.min(long a, long b)
最大值
Math.max(int a, int b)
Math.max(float a, float b)
Math.max(double a, doubleb)
Math.max(long a, long b)
Math.min() 和 Math.max() 方法分别返回一个最小值和一个最大值。
public class Main{
public static void main(String[] args){
int a = 10;
int b = 20;
System.out.println(Math.min(a, b));
System.out.println(Math.max(a, b));
}
}
求平方根
Math.sqrt(double a)
返回正确舍入的 double 值的正平方根。
求绝对值
Math.abs(double a)
Math.abs(int a)
Math.abs(flota)
Math.abs(long)
返回一个类型和参数类型一致的绝对值
public class Main{
public static void main(String[] args){
int a = -10;
System.out.println(Math.abs(a));
}
}
求幂(a^b)
Math.pow(double a, double b)
注意无论是传入int还是long都会返回一个double类型的数。
所以要求int类型的幂时,要对结果进行类型转换。
取整
Math.ceil(double x)
向上取整,返回大于该值的最近 double 值
System.out.println(Math.ceil(1.4)); // 2.0
System.out.println(Math.ceil(-1.6)); // -1.0
Math.floor(double x)
向下取整,返回小于该值的最近 double 值
System.out.println(Math.floor(1.6)); // 1.0
System.out.println(Math.floor(-1.6)); // -2.0
Math.round(double x);
四舍五入取整
System.out.println(Math.round(1.1)); // 1
System.out.println(Math.round(1.6)); // 2
System.out.println(Math.round(-1.1)); // -1
System.out.println(Math.round(-1.6)); // -2
得到一个随机数
Math.random()
生成一个[0,1)之间的double类型的伪随机数
所以为了得到一个[1, b] 之间的整数可以这样做:
int a = (int)(Math.random()*b + 1); // [1, b]
如果要得到[a, b]的一个整数则是:
int a = (int)(Math.random()*(b - a + 1) + a) // + 1 是因为random()最大取不到1,所以上限取整后就会少1.
三角函数
Math.cos(double a) 余弦
Math.acos(double a) 反余弦
Math.sin(double a) 正弦值
Math.asin(double a) 反正弦值
Math.tan(double a) 正切值
Math.atan(double a) 反正切
我们可以用acos()方法求π
因为
cos(π) = -1
所以
acos(-1) = π
String 、StringBuilder、StringBuffer常用方法和区别
摘要
本文将介绍String、StringBuilder类的常用方法。
在java中String类不可变的,创建一个String对象后不能更改它的值。所以如果需要对原字符串进行一些改动操作,就需要用StringBuilder类或者StringBuffer类,StringBuilder比StringBuffer更快一些,缺点是StringBuilder不是线程安全的,但在算法竞赛中一般我们用不到多线程。所以,主要推荐使用StringBuilder类。
String:
方法概述:
String 类包括的方法可用于检查序列的单个字符、比较字符串、搜索字符串、提取子字符串、创建字符串副本并将所有字符全部转换为大写或小写。
String的遍历
String有两种遍历方式,第一种charAt()方法
第二种是先转化为字符数组,再挨个遍历
charAt(int i);//返回索引i处的字符
length();//返回此字符串的长度
isEmpty();//判空 当length()为0时返回true
String s = "123456";
for(int i = 0; i < s.length(); i++)
System.out.println(s.charAt(i)+" ");// 1 2 3 4 5 6
toCharArray();//返回此字符串的字符数组
String s = "123456";
char[] s1 = new char[10];
s1 = s.toCharArray();
for(int i = 0; i < s1.length; i++){
System.out.print(s1[i]+" ");// 1 2 3 4 5 6
*String的比较
compareTo(String anotherString)//按字典顺序比较两个字符串
compareToIgnoreCase(String anotherString)//按字典顺序且不区分大小写比较两个字符串
equals(String anotherString)//判断两个字符串是否相等,相等返回true否则返回false
equalsIgnoreCase(String str)//同上,不区分大小写。
String s = "abcde";
String s1 = "Abcde";
int f = s.compareTo(s1);
int f1 = s1.compareToIgnoreCase(s);
Boolean f2 = s.equals(s1);
Boolean f3 = s.equalsIgnoreCase(s1);
System.out.println(f);// 32
System.out.println(f1); // 0
System.out.println(f2); // false
System.out.println(f3); // true
输出
32
0
false
true
compareTo()和compareToIgnoreCase()方法的返回值:
a.compareTo(b)
如果a > b 返回大于0的整数
如果a == b 返回0
如果a < b 返回小于0的整数
其实是返回a和b第一个不同字符的差值。
搜索子字符串
indexOf(int ch);// 返回指定字符在此字符串中第一次出现的索引
indexOf(int ch, int fromindex); // 同上, 从指定索引开始搜索
indexOf(String str);//返回子串在此字符串中第一次出现的索引
indexOf(String str, int fromindex);同上,从指定索引开始搜索
lastIndexOf(int ch);//返回指定字符在此字符串最后一次出现的索引
lastIndexOf(int ch, int fromindex);//同上, 从指定索引开始搜索
lastIndexOf(String str);//返回子串在此字符串最后一次出现的索引
lastIndexOf(String str, int fromindex);//同上, 从指定索引开始搜索
startsWith(String prefix);// 检查是否以某一前缀开始
(以上如果不存在,均返回 -1,如果要判断某个字符,应传入字符的Unicode编码)
String s = "12345346";
String s1 = "34";
int f = s.indexOf(s1); // 从索引0开始搜索
int f1 = s.indexOf(s1, 6); // 从索引6开始搜索
int f2 = s.lastIndexOf(s1);
Boolean f3 = s.startsWith("12");
System.out.println(f); // 2
System.out.println(f1);// -1
System.out.println(f2);// 5
System.out.println(f3);// true
输出:
2
-1
5
true
字符串拆分
split(String regex); // 根据正则表达式拆分
String s = "ABC DEF";
String s1[] = s.split(" ");//根据空格拆分
System.out.println(s1[0]);// ABC
System.out.println(s1[1]);// DEF
提取子字符串
substring(int beginIndex, int endIndex);//返回从begin开始到end-1结束的子串
String s = "123456";
String s1 = s.substring(0,3);// 123
System.out.println(s1);
子串的替换
replaceAll(String s1,String s2);//用s2替换目标字符串中出现的所有s1
replaceFirst(String s1,String s2);//用s2替换目标字符串中出现的第一个s1
String s = "11123456";
String s1 = s.replaceAll("1", "a");
String s2 = s.replaceFirst("1","a");
System.out.println(s1);///aaa23456
System.out.println(s2);///a1123456
转换大小写
toUpperCase(); //将此字符串中的所有字母都换为大写
toLowerCase()//将此字符串中的所有字母都换为小写
将其他类型的数据转化为字符串
valueOf(char[] data);//返回 char数组的字符串表示形式
valueOf(char[] data,int offset, int count)//返回 char 数组参数的特定子数组的字符串表示形式。
valueOf(int i);//返回 int 参数的字符串表示形式。
int a = 10;
String s = String.valueOf(a);
System.out.print(s); // 10
StringBulider
一个可变的字符序列。
构造方法
StringBuilder();//构建一个空的可变字符串。
StringBuilder(String str);//构建一个值为str的可变字符串。
StringBuilder s = new StringBuilder();//
StringBuilder s1 = new StringBuilder("123456");//123456
遍历
charAt(int i);// 返回索引i位置的字符
length();//返回此字符串的长度
StringBuilder s = new StringBuilder("123");
for(int i = 0; i < s.length(); i++)
System.out.println(s.charAt(i)+" ");// 1 2 3
增加
append(String str);//在此字符串追加str。
append(StringBuilder str);//在此字符串追加str。
append(char[] str, int offset, int len);//将char的子数组追加到此字符串
StringBuilder s = new StringBuilder("123");
StringBuilder s1 = new StringBuilder("456");
s.append(s1);
System.out.print(s);// 123456
删除
delete(int start, int end);//移除此序列从start到end-1的字符串
deleteCharAt(int index);//移除指定索引上的char
StringBuilder s = new StringBuilder("123");
StringBuilder s1 = new StringBuilder("456");
s.delete(0, 1);
s1.deleteCharAt(1);
System.out.println(s);// 23
System.out.println(s1);// 46
修改
setCharAt(int index, char ch);//将指定索引处的字符替换为ch
查找
indexOf(String str);//返回子字符串第一次出现的索引
indexOf(String str, int fromIndex);//同上,从指定位置查找
lastIndexOf(String str);//返回子字符串最后一次出现的索引
lastIndexOf(String str, int fromIndex);//同上,从指定位置查找
字符串反转
reverse();//将此字符串反转
字符串截取
substring(int start);//返回此字符串从start开始至length-1结束的String
substring(int start, int end);//返回此字符串从start开始至end-1结束的String
toString();//返回此序列中的String表示形式。
(注意以上方法的返回值都是String而不是StringBuilder)
Calendar日期类
在蓝桥杯中有关于日期计算的问题,正好java中的Date类和Calendar类提供了对日期处理的一些方法。Date类大部分方法已经废弃了,所以本文将详细介绍Calendar类。
Calendar类
Calendar 类是一个抽象类,它为特定瞬间与一组诸如YEAR、MONTH、DAY_OF_MONTH、HOUR 等日历字段之间的转换提供了一些方法,并为操作日历字段(例如获得下星期的日期)提供了一些方法。
瞬间可用毫秒值来表示,它是距历元(即格林威治标准时间 1970 年 1 月 1 日的 00:00:00.000,格里高利历)的偏移量。
常用的日历字段
YEAR 指示年的 get 和 set 的字段数字。
MONTH 指示月份的 get 和 set 的字段数字。
DAY_OF_MONTH get 和 set 的字段数字, 指示一个月中的某天。
DAY_OF_WEEK get 和 set 的字段数字, 指示一个星期中的某天。
DAY_OF_YEAR get 和 set 的字段数字, 指示当前年中的天数。
DAY_OF_WEEK_IN_MONTH get 和 set 的字段数字, 指示当前月中的第几个星期。
HOUR get 和 set 的字段数字,指示当天中的某小时
MINUTE get 和 set 的字段数字,指示当前小时中的某分钟
SECOND get 和 set 的字段数字,指示当前分钟中的某秒
time 以毫秒为单位,表示自格林威治标准时间 1970 年 1月 1 日 0:00:00 后经过的时间。
(字段就是Calendar类的成员变量,用于存储当前日历的年月日等时间信息。)
Calendar类的实例化
getInstance();//返回一个默认时区和语言环境的日历
Calendar calendar = Calendar.getInstance();//赋值给calendar
设置特定日期
set(int field, int value);//第一个参数是日期字段,诸如YEAR、MONTH 等将给定的日历字段设置为给定值。
set(int year, int month, int date)// 设置日历字段年月日的值
Calendar calendar = Calendar.getInstance();//创建个实例
int year = 2020;
int month = 1;//1是二月 0是1月
int day = 1;
calendar.set(Calendar.YEAR, year);// 将year的值赋给calender的YEAR字段
calendar.set(Calendar.MONTH, month);//将month的值赋给calender的MONTH字段
calendar.set(Calendar.DAY_OF_MONTH, day);//将day的值赋值给calendder的DAT_OF_MONTH字段
//以上就完成了对calender的字段设置。
有趣的是MONTH字段是从0月开始计数的,所以12月对应的值是11。DAY_OF_WEEK中星期天对应的是1,星期一对应的是2,星期六对应的是7,而YEAR和DAY_OF_MONTH都是从1开始计数
获取当前Calender实例的字段信息
get(int field);// 获取给定字段的值
Calendar calendar = Calendar.gttInstance();
// 设置日期为: 2020.1.21
calendar.set(Calendar.YEAR, 2020);
calendar.set(Calendar.MONTH, 0);
calendar.set(Calendar.DAY_OF_MONTH, 21);
// 获取2020.1.21是星期几
System.out.print(calendar.get(Calendar.DAY_OF_WEEK));
输出:
3 // 3代表星期二
增减时间
add(int field, int amount);// 根据日历的规则,为给定的日历字段添加或减去指定的时间量。
ArrayList(Vector) 和 LinkedList
ArrayList
ArrayList 类可以实现可增长的对象数组。
构造方法
ArrayList();//构造一个空向量,使其内部数据数组的大小为 10,其标准容量增量为零。
ArrayList(int initialCapacity);//使用指定的初始容量和容量增量构造一个空的向量。
增加元素
add(E e);//将指定元素添加到末尾
add(int index, E element)//在此向量的指定位置插入指定的元素
删除元素
remove(int index);//移除此向量中指定位置的元素
clear();//从此向量中移除所有元素。
修改元素
set(int index, E element);//用指定的元素替换此向量中指定位置处的元素
查找元素
get(int index)//返回向量中指定位置的元素
indexOf(Object o)//返回此向量中第一次出现的指定元素的索引,如果此向量不包含该元素,则返回 -1。
lastIndexOf(Object o)返回此向量中最后一次出现的指定元素的索引;如果此向量不包含该元素,则返回 -1。
容器大小
size();//返回此向量中的组件数。
判空
isEmpty();//测试此向量是否不包含组件
转化为数组
toArray();//返回一个数组,包含此向量中以恰当顺序存放的所有元素。
转化为字符串
toString();//返回此向量的字符串表示形式,其中包含每个元素的 String 表示形式。
拷贝
ArrayList<Integer> Arr1 = new ArrayList<>();
ArrayList<Integer> Arr2 = new ArrayList<>();
// 将Arr2的值拷贝给Arr1
Arr1 = Arr2; // Arr1之前的值会自动被垃圾回收
以下两种方式也适用于其他集合的拷贝
只要该集合的构造函数支持参数为集合就可以使用此方法拷贝
ArrayList<Integer> Arr2 = new ArrayList<>();
// 将Arr2的值拷贝给Arr1
ArrayList<Integer> Arr1 = new ArrayList<>(Arr2);
clone()
只要该集合支持clone,就可以使用此方法拷贝
ArrayList<Integer> Arr1 = new ArrayList<>();
ArrayList<Integer> Arr2 = new ArrayList<>();
// 将Arr2的值拷贝给Arr1
Arr1 = (ArrayList<Integer>) Arr2.clone();
实例
ArrayList<Integer> V = new ArrayList<>();
V.add(1);
V.add(1);
V.set(0, 0);
System.out.print(V.toString());
输出:
[0, 1]
LinkedList
LinkedList是List 接口的链接列表实现。实现所有可选的列表操作,并且允许所有元素(包括 null)。除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。
add(E e)//在末尾添加一个元素
addFirst(E e)//在开头添加一个元素
addLast(E e)//在末尾添加一个元素
offer(E e)//将指定元素添加到此列表的末尾(最后一个元素)
clear()//从此列表中移除所有元素
element()获取但不移除此列表的头(第一个元素)。
peek()//获取但不移除此列表的头(第一个元素)。
poll()//获取并移除此列表的头(第一个元素)
getFirst()返回此列表的第一个元素。
getLast()返回此列表的最后一个元素
indexOf(Object o)返回此列表中首次出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。
lastIndexOf(Object o)返回此列表中最后出现的指定元素的索引,如果此列表中不包含该元素,则返回 -1。
pop()从此列表所表示的堆栈处弹出一个元素。
push(E e)将元素推入此列表所表示的堆栈。
remove()获取并移除此列表的头(第一个元素)。
remove(int index)移除此列表中指定位置处的元素
size()//返回元素个数
大体上来说LinkedList和ArrayList的方法用法都一样,无非是get,set等方法,不过LinkedList可以用作栈和队列(链表实现),因为它包含了(
push,pop)栈的进出,(offer,poll)队列的进出等方法。
ArrayList的遍历
通过迭代器
Iterator iterator=students.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
for循环和get方法
for(int i = 0; i < n; i++)
System.out.println(E.get(i))
for each
for(int x : E){ //构造容器时用的什么类型,就定义什么类型。
System.out.println(x);
}
stack和queue
上面已经说过,LinkedList可以用来实现栈和队列。
在JAVA中Stack也有专门的类,是通过Vector实现的。
Stack<Integer> Stack = new Stack<>(); //第一种栈的实现方式
LinkedList<Integer> Stack = new LinkedList<>(); // LinkedList没有实现Stack接口,但是我们只需要用其中的关于栈的方法。
Queue<Integer> Queue = new LinkedList<>();//LinkedList类实现了Queue接口,因此我们可以把LinkedList当成Queue来用。
在使用这些容器类的时候,我们不需要背会其所有的方法,只需要知道一个大概就行了,忘记了可以查。
HashMap 和 TreeMap
HashMap
HashMap是基于哈希表的 Map 接口的实现,是无序的
clear()//清空。
containsKey(Object key)//如果包含指定键,返回true
containsValue(Object value)//如果包含指定值, 返回true
get(Object key)//返回指定键所映射的值;如果对于该键来说,此映射不包含任何映射关系,则返回 null。
isEmpty()//如果此映射不包含键-值映射关系,则返回 true
put(K key, V value)//在此映射中关联指定值与指定键。
remove(Object key)//从此映射中移除指定键的映射关系(如果存在)。
size()返回此映射中的键-值映射关系数。
HashMap<Integer, Integer> m = new HashMap<>();//定义格式
m.put(100,1);
System.out.print(m.get(100)); // 1
TreeMap
TreeMap是基于红黑树实现的,是有序的, 可进行排序。
此实现为 containsKey、get、put 和 remove 操作提供受保证的 log(n) 时间开销
clear()//清空
containsKey(Object key)//如果包含指定键,返回true
containsValue(Object value)//如果包含指定值, 返回true
get(Object key)//返回指定键的值, 如果不存在返回null
firstKey()//返回此映射中当前第一个(最低)键。
lastKey()返回映射中当前最后一个(最高)键
ceilingKey(K key)返回大于等于给定键的最小键;如果不存在这样的键,则返回 null。
floorKey(K key)返回小于等于给定键的最大键;如果不存在这样的键,则返回 null。
HashMap和TreeMap的遍历方式
HashMap和TreeMap可以根据迭代器遍历,但,它俩不能直接遍历,
可以遍历键的集合, 值的集合, 键值对的集合。
通过keySet()获得键,然后根据键遍历值
使用while + Iterator
TreeMap<Integer, String> m = new TreeMap<>();
m.put(1,"A");
m.put(2,"B");
Set<Integer> s = m.keySet();
Iterator it = s.iterator();
Integer key = null; // 这里必须必须声明为类。
while(it.hasNext()){
key = (Integer)it.next();
String value = m.get(key);
System.out.print(value);
}
使用增强for
TreeMap<Integer, String> m = new TreeMap<>();
m.put(1,"A");
m.put(2,"B");
for(int k : m.keySet()){
System.out.print(m.get(k));
}
使用while 和 Iterator
TreeMap<Integer, String> m = new TreeMap<>();
m.put(1,"A");
m.put(2,"B");
Collection<String> s = m.values();
Iterator it = s.iterator();
String value = null; // 这里必须必须声明为类。
while(it.hasNext()){
value = (String)it.next();
System.out.print(value);
}
使用增强for
TreeMap<Integer, String> m = new TreeMap<>();
m.put(1,"A");
m.put(2,"B");
for(String value : m.values()){
System.out.print(value);
}
HashSet 和 TreeSet
set容器的特点是不包含重复元素,也就是说自动去重。
HashSet
HashSet基于哈希表实现,无序。
add(E e)//如果容器中不包含此元素,则添加。
clear()//清空
contains(Object o)//查询指定元素是否存在,存在返回true
isEmpty()// 判空
iterator()//返回此容器的迭代器
remove// 如果指定元素在此set中则移除
size()//返回元素数量
TreeSet
基于红黑树实现。有序。
add(E e)// 如果不存在,则添加。
clear()//清空
contains(Object o)//查询指定元素是否存在,存在返回true
isEmpty()// 判空
iterator()//返回此容器的迭代器
remove// 如果指定元素在此set中则移除
size()//返回元素数量
以上方法都和HashSet一致,由于是红黑树实现的,所以TreeSet和TreeMap可以二分查找一个比当前元素大的最小元素,或者比当前元素小的最大元素。
ceiling(E e)//返回一个大于等于当前元素的最小元素,不存在返回null
floor(E e)//返回一个小于等于当前元素的最大元素,不存在返回null
higher(E e)//返回此 set 中严格大于给定元素的最小元素,不存在返回null
lower(E e)//返回此set中严格小于给定元素的最大元素,不存在返回null
first()//返回第一个元素
last()//返回最后一个元素
声明:
TreeSet<Integer> s = new TreeSet<>();
HashSet<Integer> s = new HashSet<>();
实例:
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static TreeSet<Integer> s = new TreeSet<>();
public static void main(String[] args) throws IOException {
s.add(10);
s.add(20);
s.add(30);
Iterator<Integer> it = s.iterator();
while(it.hasNext()){ // 遍历
int x = it.next();
out.write(x+"\n");
}
out.write("\n");
out.write(s.lower(20)+"\n"); // lower
out.flush();
}
输出:
10
20
30
10
PriorityQueue(优先队列)
PriorityQueue
翻译过来就是优先队列,本质是一个堆, 默认情况下堆顶每次都保留最小值,每插入一个元素,仍动态维护堆顶为最小值。
初始化
PriorityQueue()//使用默认的初始容量(11)创建一个 PriorityQueue,并根据其自然顺序对元素进行排序。
PriorityQueue<Integer> Q = new PriorityQueue<>(); // 初始化
常用函数
add(E e)//将指定的元素插入此优先级队列。
clear()//清空
contains(Object o) // 如果包含指定元素返回true
iterator()//返回在此队列中的元素上进行迭代的迭代器。
offer(E e) // 将指定元素插入此优先队列
peek() // 获取第一个元素,及最小或最大元素
poll() // 获取并移除第一个
remove(Object o) // 移除指定元素
size() // 返回元素个数
实现大根堆的两种方式
因为java中的优先队列默认是小根堆,要实现大根堆可以用以下两种方法:
使用自定义比较器
将所有数据变为之前自身的负数之后在插入, 因为添加个负号就相当于是逆序了嘛。1 < 2 < 3 取负之后变为 -1 > - 2 > - 3
public static void main(String[] args){
Scanner in = new Scanner(new InputStreamReader(System.in));
PriorityQueue<Integer> Q = new PriorityQueue<>();
int a;
for(int i = 0; i < 10; i++){
a = in.nextInt();
Q.add(a);
System.out.print(Q.peek()+" ");// 输出当前队列的最小元素
}
}
输入: 1 -1 -2 -3 10 -4 -5 -6 -7 -8
输出: 1 -1 -2 -3 -3 -4 -5 -6 -7 -8
sort方法的自定义比较器写法
对数组排序
Arrays.sort(arr, new Comparator<Integer>() { // arr是数组名,<>中是待排序集合所包含的数据类型
public int compare(int a, int b){ // 待排序集合中的元素是什么数据类型,这里的两个函数参数就定义为什么数据类型
return a - b; 升序
// return b - a; 降序
// a - b > 0 交换ab位置,反之不变, 即返回值为正数时,交换数组中正在比较的
//两个元素的位置,返回值为负数时,不交换。
}
})
例题:快速排序
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
可以将字符串数组转化为整型数组之后在排序,为了演示自定义比较器的写法这里直接对字符串数组进行排序:
import java.io.*;
import java.util.*;
public class Main{
// 输入输出模板
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static int n;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(in.readLine());
String s[] = in.readLine().split(" ");// 读入数据
Arrays.sort(s, new Comparator<String>() { // 排序
public int compare(String a, String b) {
if(a.length() == b.length()){ // 如果长度相等则直接比较字典序
return a.compareTo(b);
}
else{ // 长度长的一定大
return a.length() - b.length();
}
}
});
for(String p : s){
out.write(p+" ");
}
out.flush();
}
}
对集合进行排序
创建TreeSet实例,对其从大到小排序。
因为TreeSet是自动排序和去重的, 默认为升序,我们可以重写比较器构造一个降序的TreeSet, 之后添加数据就会自动排序。
import java.io.*;
import java.util.*;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
TreeSet<Integer> s = new TreeSet<>(new Comparator<Integer>(){
public int compare(Integer a, Integer b) {
return b - a;
}
});
s.add(10);
s.add(5);
s.add(4);
s.add(6);
s.add(7);
s.add(8);
s.add(1);
s.add(2);
s.add(3);
s.add(9);
for(Integer p : s){
out.write(p+" ");
}
out.flush();
}
}
输出:
10 9 8 7 6 5 4 3 2 1
对自定义对象数组排序
创建学生类, 按照年龄从小到大排序
import java.io.*;
import java.util.*;
class student{
int age;
String name;
student(int a, String b){
this.age = a;
this.name = b;
}
}
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
student s[] = new student[4]; //创建学生对象数组
s[0] = new student(10, "1");
s[1] = new student(9, "2");
s[2] = new student(8, "3");
s[3] = new student(7, "4");
Arrays.sort(s, new Comparator<student>() {
public int compare(student a, student b) { //
return a.age - b.age; // 按照年龄大小升序排列
}
});
for(student p : s){
out.write(p.age+" "+p.name + "\n");
}
out.flush();
}
}
输出:
7 4
8 3
9 2
10 1
大致就是这样了,还可以对要排序的类实现Comparable接口,重写compareTo方法。
代码:
```
//对pair类实现Comparable接口后,直接调用sort函数排序就行了。
static class pair implements Comparable[HTML_REMOVED]{
int a, b, w;
pair(int u, int v, int x){
a = u;
b = v;
w = x;
}
public int compareTo(pair p) {
return this.w - p.w;
}
}
整理自:
https://blog.csdn.net/GD_ONE/article/details/104061907?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param
666