Java刷leetcode基础必备_leetcode java 基础类

十大排序算法

冒泡排序，选择排序，插入排序，希尔排序；
归并排序，快速排序，堆排序；
计数排序，桶排序，基数排序。

回溯

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

递归

把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件。
递归两个条件：
1.可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。（自身调用）
2.存在一种简单情境，可以使递归在简单情境下退出。（递归出口）

动态规划

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度。

图

//图结构模板
public static class Graph {
    //点编号和点信息
    public Map<Integer, Node> nodes;
    //图中所有的边
    public Set<Edge> edges;
    //初始化
    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}
//点
public static class Node {
    //点值
    public int value;
    //入度
    public int in;
    //出度
    public int out;
    //相连的点
    public List<Node> nexts;
    //对应的边
    public List<Edge> edges;
    //初始化
    public Node(int val) {
        value = val;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}
//边
public static class Edge {
    //边的权重
    public int weight;
    //出点
    public Node from;
    //入点
    public Node to;
    //初始化
    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}
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
39
40
41
42
43
44
45
46
47
48

比较器

//数组排序
Arrays.sort(arrs, new Comparator<type>() {
    @Override
    public int compare(type o1, type o2) {
        //o1 o2假设按照已经排好序的顺序传入，返回负数
        //否则，返回正数
        return 正负数
    }
});
//list排序
Collections.sort(list, new Comparator<type>() {
    @Override
    public int compare(type o1, type o2) {
        //o1 o2假设按照已经排好序的顺序传入，返回负数
        //否则，返回正数
        return 正负数
    }
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

常用结构

ArrayList

//创建动态数组
List<type> list = new ArrayList<>();
//添加元素
list.add(元素);
list.add(下标, 元素);
//访问元素
list.get(下标);
//更改元素
list.set(下标, 元素);
//删除元素
list.remove(下标);
//获取长度
list.size();
//遍历
for(int i = 0; i < list.size(); i++) {
    list.get(i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

HashMap

//创建哈希表
Map<type, type> map = new HashMap<>();
//添加元素
map.put(键, 值);
//访问元素
map.get(键);
//删除元素
map.remove(键);
//包含键值对数量
map.size();
//遍历
for(type key : map.keySet()) {
    map.get(key);
}
//是否包含某个key
map.containsKey(key);
//替换元素
map.put(键, 值);
map.replace(键, 值);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

HashSet

//创建哈希集合
Set<type> set = new HashSet<>();
//添加元素
set.add(元素);
//判断元素是否存在
set.contains(元素);
//删除元素
set.remove(元素);
//包含元素数量
set.size();
//遍历
for(type i : set) {
    // 使用i
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

ArrayDeque

//创建队列
Queue<type> queue = new ArrayDeque<>();
//队尾插入元素
queue.offer(元素);
//查看队头元素
queue.peek();
//返回并删除队头元素
queue.poll();
//队列长度
queue.size();

//创建双端队列
Deque<type> deque = new ArrayDeque<>();
//队头插入元素
deque.offerFirst(元素);
//队尾插入元素
deque.offerLast(元素);
//查看队头元素
deque.peekFirst();
//查看队尾元素
deque.peekLast();
//返回并删除队头元素
deque.pollFirst();
//返回并删除队尾元素
deque.pollLast();
//双端队列长度
deque.size();

//创建栈
ArrayDeque<type> stack = new ArrayDeque<>();
//压栈
stack.push(元素);
//栈顶元素
stack.peek();
//弹出
stack.pop();
//压栈元素数量
stack.size();
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

PriorityQueue

//创建堆(默认最小堆)，可使用比较器改为最大堆
PriorityQueue<type> priorityQueue = new PriorityQueue<>();
//堆元素数量
priorityQueue.size();
//添加元素
priorityQueue.offer(元素);
//访问堆顶元素
priorityQueue.peek();
//弹出堆顶元素
priorityQueue.poll();
1
2
3
4
5
6
7
8
9
10

String

//创建字符串
String s = "字符串";
//根据下标访问某个字符
s.charAt(下标);
//字符串长度
s.length();
//根据下标分割字符串
//开始下标到字符串末尾
s.substring(开始下标);
//开始下标到结束下标(不包含结束下标的字符)
s.substring(开始下标, 结束下标);
//根据某个符号分割字符串,如根据"-"分割"字符-串",结果返回字符串数组"字符"和"串"
String[] temp = s.split("分割符号");
//去除字符串首尾空格
s.trim();
//其他类型数据转String
String.valueOf(数据);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17