Util类

一、Sort

1.排序0~n-1，第n个元素不参与排序。
2.如果要排类数组的话，要重写比较器，再加上cmp参数。
3.默认升序，如果要逆序，就必须用Integer数组，不能用int。

Arrays.sort(a, 0, n, cmp);
Arrays.sort(a, 1, q+1, Collections.reverseOrder()); //逆序排下标1~q

二、Class

1.相当于结构体，可以放在public class Main里
2.如果要排序，则需重写比较器

static class hh
{
    int v, id;
    public hh(int v, int id) 
    {
        this.v = v;
        this.id = id;
    }
}
static Comparator<hh> cmp = new Comparator<hh>() 
{
    public int compare(hh o1, hh o2) 
    {
        return o1.v - o2.v; //按v的升序排序
        //return o2.v - o1.v; //按v的降序排序
    };
};

3.类数组赋值方法：

hh[] a = new hh[1000];
a[0] = new hh(num1,num2);

三(1)、List

1.实现方式：

List<Integer> list = new LinkedList<Integer>();

2.下标从0开始
3.不能自动排序，元素可以重复
4.方法有：add get remove size
5.元素类型只能是对象，如Integer，而不能用int。
6.删除一个元素后，后面元素的下标都会往前移动。
7.输出用for-each方式

三(2)、ArrayList

1.实现方式和排序方法：

ArrayList<Integer> res = new ArrayList<>();

Collections.sort(res);  //升序
Collections.sort(res, (a, b)->b - a);  //降序

sum.sort((o1,o2)->{  //适用于类数组排序
            if (o1.s != o2.s) return o1.s - o2.s;
            if (o1.c != o2.c) return o1.c - o2.c;
            return o1.d - o2.d;
        });

2.链表数组

static ArrayList<Edge>[] h = new ArrayList[N];

if (h[a] == null) h[a] = new ArrayList<>();  //每个元素先初始化才能用

四、Set

1.两种实现方式：

TreeSet<Integer> set1 = new TreeSet<Integer>();
HashSet<Integer> set2 = new HashSet<Integer>();

HashSet是哈希表实现的，数据无序
TreeSet是二叉树实现的，数据自动从小到大排好序
2.Set中的数据都是唯一的
3.输出用for-each方式

for(int x : set1)
{
    System.out.println(x+" ");
}

五、映射(Map)

1.两种实现方式：

TreeMap<String, Integer> map1 = new TreeMap<String, Integer>();
HashMap<String, Integer> map2 = new HashMap<String, Integer>();

HashMap:数组方式存储key/value，key不可以重复，value允许重复 (没有自动排序)
TreeMap:基于红黑二叉树的NavigableMap的实现，key不可以重复，value允许重复，会按照排序后的顺序迭代元素，主要用于存入元素的时候对元素进行自动排序，迭代输出的时候就按排序顺序输出。(自动按照key进行排序，从小到大。如果key是String，则会像 1616 4615 54 61651 8 这样排)
2.put 放入键值对

map1.put(key, value);

3.get 通过键来获取对应的值
4.利用keyset 集合遍历map

Set<String> key = map1.keySet();
for(String k : key)
{
    System.out.println(k + ":" + map1.get(k));
}

六、队列(queue)、优先队列(PriorityQueue)

1.两种实现方式

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
Queue<Integer> q = new LinkedList<Integer>();

队列先进先出，优先队列会对元素进行自动排序。
2.方法
size()返回队列中的元素个数
peek()返回队首元素
poll()移除队列首元素，同时返回首元素的值
3.输出

while(!q.isEmpty())
{
    System.out.println(q.poll()+" ");
}

4.优先队列当最小堆用。(如哈夫曼树)
https://www.acwing.com/activity/content/code/content/2484360/

七、栈(Stack)

1.实现方式

Stack<Integer> s = new Stack<Integer>();

后进先出
2.方法
size()元素个数
push()放入元素
peek()输出栈顶元素
pop()弹出栈顶元素，也就是返回栈顶元素的值，并删除。相当于队列的poll()
get(3)输出下标为3的元素，下标从0开始。(先后放进去1 2 3 4 5，会输出4，但栈顶是从5开始)

八、向量(Vector) 用的少

1.实现方式

Vector<Integer> v = new Vector<Integer>();

2.方法
add()添加
get()获取
remove(2)删除下标为2的元素(从0开始)，并且返回该元素的值。删除后，后面的元素也是整体前移。
size()计算大小

String类

一、判断String是否相等

用equals()，不能用==

二、返回索引 i 处的字符

charAt(int i);

三、将String转换为字符数组

String a = "asd";
char arr[] = a.toCharArray();
for (char n : arr)
    System.out.print(n + " ");

四、String和其他基本数据类型的转换

1.可以使用toString将其他数据类型转换为String类，但这种方法只对包装类起作用(如：Integer)
2.使用String自带的valueOf()方法，支持将基本的数据类型转换
3.注意：int转String用String.valueOf()，别用 +""，差了好几倍时间。
4.而将String转换为其他，可以用自带类的.parseXXX(string)方法

Integer a=new Integer(100);
String s1=a.toString();//类自带的toString()方法
int i=99;
String s2=String.valueOf(i);//String自带的valueOf()方法
Integer b=Integer.parseInt(s2);//每个类都有.parseXXX(String s)方法

五、搜索子字符串

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编码

六、提取子字符串

substring(int beginIndex, int endIndex)；//返回从begin开始到end-1结束的子串

String s = "123456";
String s1 = s.substring(0,3);
System.out.println(s1);  //123

七、子串的替换

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()//将此字符串中的所有字母都换为小写

九、字符串翻转

String str = "123456";
String newStr = new StringBuilder(str).reverse().toString();
System.out.println(newStr);

十、格式化输出double

System.out.println(String.format("%.6f",l)); //保留小数点后6位
String.format("%02d", h);  //不足两位则补0

十一、连接字符串

String s = "www:";
s = s.concat("abcde.com");
System.out.println(s);   //输出：www.abcde.com

十二、截取多个字符

String Str1 = new String("www.abcde.com");
char[] Str2 = new char[5];
Str1.getChars(4, 9, Str2, 0);
System.out.println(Str2);    //输出：abcde

好用的方法

一、Arrays.fill

1.相当于C++中的memset，很方便。

int[] arr = new int[100];
Arrays.fill(arr, -1);

2.但在二维数组中使用时要注意

for(int i=0;i<N;i++)
{
    Arrays.fill(f[i], -0x3f3f3f3f);  //初始化为负无穷，0x3f3f3f3f是正无穷
}

二、数组的拷贝 一般用不上

https://blog.csdn.net/huaxin0304/article/details/109296436

三、日期类(Calendar) 如果用这个类去判断日期是否合法，会TLE，请酌情使用。

https://blog.csdn.net/huaxin0304/article/details/109296436

四、大数类(BigInteger)

https://blog.csdn.net/huaxin0304/article/details/109296436
https://www.acwing.com/activity/content/code/content/2717118/

五、判断单个字符用“==”而不是equal

if('1' == x[0].charAt(1))

六、通过 %N + N 防止 x % N 的结果为负数

int k = (x % N + N) % N;

七、所有边的权都是1时才能用BFS搜索最短路。DFS、BFS都好好看看

八、判断日期是否合法

https://www.acwing.com/activity/content/code/content/2589735/

https://www.acwing.com/activity/content/code/content/2603135/

九、split使用正则表达式

正则表达式\s表示匹配任何空白字符，+表示匹配一次或多次。例如：

String[] string = str.split("\\s+");

https://www.acwing.com/activity/content/code/content/2604187/

十、通过毫秒数算时间

https://www.acwing.com/activity/content/code/content/2737517/

十一、数组能开的最大范围

int[] n = new int[N];  //N 最大是10000000 (10^7)，不然编译错误
int[][] n = new int[N][N];  //N 最大是1000 (10^3)，不然内存超限

十二、ArrayList模拟树

https://www.acwing.com/activity/content/code/content/2765089/

十三、int、long的范围

int 2*10^9
long 9*10^19 (2^64 -1)

十四、double不能直接用 == 比大小

若两者之差小于某个非常小的数，则相等。

Math.abs(l[i].k - k) < 1e-8;

十五、位移运算符

2^(d-1) 即 1 << d - 1
注意：+、-运算符的优先级高于<< >>位移运算符

十六、char的封装类型

是Character

十七、long和int的转换问题

long类型 = 一些int类型运算操作时，必须要转long

f[n-i+1] = (n-i+1)*(long)i;

十八、char转int

-'0'就可以了

十九、十进制转十六进制 (麻烦)

static char get(int x)
{   
    if(x <= 9) return (char) (x + '0');
    return (char) (x - 10 + 'A');
}

static String base(int n,int b)//n为输入整数，b为要转化的进制
{   
    if(n == 0) return "0";  //0要特判
    String num = "";  //不能初始化为null
    while(n > 0) //将十进制转化为b进制 
    {   
        num += get(n % b); // 将求得的数转化为字符并加入到字符串中 
        n /= b;
    }

    return new StringBuffer(num).reverse().toString(); //将字符串倒序 
}

二十、直接用函数实现进制转换 (推荐)

1.十进制转为二、八、十六进制

String s1 = Integer.toBinaryString(n);
String s2 = Integer.toOctalString(n);
String s3 = Integer.toHexString(n);

注意转换生成的字母默认是小写，可以用下面的方法转为大写

char a = s.charAt(i);
if(Character.isLetter(a)) a = Character.toUpperCase(a);

2.其他进制转为十进制
例如16进制，分为是否带有0x标识符两种情况。

int x1 = Integer.parseInt("1A", 16);
int x2 = Integer.parseInt("0x1A".substring(2), 16);

二十一、Java计算字符串中某个字符出现的次数

发现一篇 好文章