代码收藏家 Java常用函数总结
一、字符串操作
1、字符串长度
2、获取第一个字符串
3、内容比较
4、忽略大小写比较
5、获取字符串
6、查找子串索引
7、查找最后一个子串的索引
8、转换为大写
9、转换为小写
10、字符串替换
11、字符串分割
12、字符串连接
13、字符串反转
14、去除空白
15、转换为字符串数组
16、计算字符之间的差值
/**
* 字符串操作
*/
public static void main(String[] args) {
// 字面量
String str1 = "Hello";
// 使用构造函数
String str2 = new String("World");
// 1、字符串长度 结果: 5
System.out.println(str1.length());
// 2、获取第一个字符串 结果: W
System.out.println(str2.charAt(0));
// 3、内容比较 结果: false
System.out.println(str1.equals(str2));
// 4、忽略大小写比较 结果: false
System.out.println(str1.equalsIgnoreCase(str2));
// 5、获取字符串 结果: el
System.out.println(str1.substring(1, 3));
// 6、查找子串索引 结果: 2
System.out.println(str1.indexOf("ll"));
// 7、查找最后一个子串的索引 结果: 3
System.out.println(str1.lastIndexOf("l"));
// 8、转换为大写 结果: HELLO
System.out.println(str1.toUpperCase());
// 9、转换为小写 结果: hello
System.out.println(str1.toLowerCase());
// 10、字符串替换 结果: Heppo
System.out.println(str1.replace("l", "p"));
// 结果: Heppo
System.out.println(str1.replaceAll("l", "p"));
// 11、字符串分割 结果: [a, b, c]
String[] split = "a,b,c".split(",");
System.out.println(Arrays.toString(split));
// 12、字符串连接 结果: a,b,c
System.out.println(String.join(",", "a", "b", "c"));
StringBuilder sb = new StringBuilder();
sb.append(str1).append(str2);
// 结果: HelloWorld
System.out.println(sb.toString());
// 13、字符串反转 结果: dlroWolleH
System.out.println(sb.reverse().toString());
// 14、去除空白 结果: Hello
System.out.println(" Hello ".trim());
// 15、转换为字符串数组 结果: [H, e, l, l, o]
char[] charArray = str1.toCharArray();
System.out.println(Arrays.toString(charArray));
// 16、计算字符之间的差值 结果: 49
System.out.println('a' - '0');
// 结果: 2
System.out.println('c' - 'a');
}
二、StringBuilder操作
1、连接字符串
2、插入字符串
3、替换字符串
4、反转字符
5、提取子字符串
6、修改指定位置的字符
7、获取长度
8、获取容量
9、获取指定位置的字符
10、转换为字符串
11、设置长度
/**
* StringBuilder操作
*/
public static void main(String[] args) {
// 1、连接字符串 结果: Hello World
StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(" ");
sb.append("World");
System.out.println(sb.toString());
// 2、插入字符串 结果: Hellinserto World
sb.insert(4, "insert");
System.out.println(sb.toString());
// 3、替换字符串 结果: Helljavao World
sb.replace(4, 10, "java");
System.out.println(sb.toString());
// 4、反转字符 结果: dlroW oavajlleH
sb.reverse();
System.out.println(sb.toString());
// 5、提取子字符串 结果: lr
System.out.println(sb.substring(1,3));
// 6、修改指定位置的字符 结果: dTroW oavajlleH
sb.setCharAt(1, 'T');
System.out.println(sb.toString());
// 7、获取长度 结果: 15
System.out.println(sb.length());
// 8、获取容量 结果: 34
System.out.println(sb.capacity());
// 9、获取指定位置的字符 结果: T
System.out.println(sb.charAt(1));
// 10、转换为字符串 结果: dTroW oavajlleH
System.out.println(sb.toString());
// 11、设置长度 结果: dTroW
sb.setLength(5);
System.out.println(sb.toString());
}三、数组操作
1、创建数组
2、创建一个二维数组
3、获取数组的长度
4、访问数组元素
5、修改数组
6、遍历数组
7、增强for循环遍历
8、遍历二维数组
9、数组转字符串
10、数组填充
11、数组排序
12、在排序数组中查找元素
13、复制数组
14、复制数组的子范围
15、两个数组是否相等
16、数组转换为列表
17、列表转换为数组
/**
* 数组操作
*/
public static void main(String[] args) {
// 1、创建数组
// 创建一个长度为5的整数数组，默认初始化为0
int[] arr1 = new int[5];
// 创建并初始化数组
int[] arr2 = {1, 2, 3, 4, 5};
// 创建数组
int[] arr3 = new int[]{3, 1, 2, 4, 5};
// 2、创建一个二维数组
int[][] matrix1 = new int[3][3];
// 初始化二维数组
int[][] matrix2 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
// 初始化二维数组
int[][] matrix3 = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
// 3、获取数组的长度 结果: 3
System.out.println(matrix1.length);
// 结果: 3
System.out.println(matrix1[0].length);
// 4、访问数组元素 结果: 0
System.out.println(arr1[0]);
// 5、修改数组 结果: [10, 2, 3, 4, 5]
arr2[0] = 10;
System.out.println(Arrays.toString(arr2));
// 6、遍历数组
for (int i = 0; i < arr3.length; i++) {
// System.out.println(arr3[i]);
}
// 7、增强for循环遍历
for (int num : arr1) {
// System.out.println(num);
}
// 8、遍历二维数组
for (int i = 0; i < matrix2.length; i++) {
for (int j = 0; j < matrix2[i].length; j++) {
// System.out.println(matrix2[i][j]);
}
}
// 9、数组转字符串 结果: [[I@619713e5, [I@708f5957, [I@68999068]
System.out.println(Arrays.toString(matrix3));
// 10、数组填充 结果: [1, 1, 1, 1, 1]
Arrays.fill(arr1, 1);
System.out.println(Arrays.toString(arr1));
// 11、数组排序 结果:[1, 2, 3, 4, 5]
Arrays.sort(arr3);
System.out.println(Arrays.toString(arr3));
// 12、在排序数组中查找元素 结果: 1
System.out.println(Arrays.binarySearch(arr3, 2));
// 13、复制数组 结果: [1, 2, 3, 4, 5]
int[] copyArr = Arrays.copyOf(arr3, 5);
System.out.println(Arrays.toString(copyArr));
// 14、复制数组的子范围 结果: [2, 3]
int[] subArr = Arrays.copyOfRange(arr3, 1, 3);
System.out.println(Arrays.toString(subArr));
// 15、两个数组是否相等 结果: true
System.out.println(Arrays.equals(arr3, copyArr));
// 16、数组转换为列表 结果: [1, 2, 3]
Integer[] arr4 = {1, 2, 3};
List<Integer> list = Arrays.asList(arr4);
System.out.println(list);
// 17、列表转换为数组 结果: [1, 2, 3]
List<Integer> list2 = new ArrayList<>(Arrays.asList(1, 2, 3));
Integer[] newArray = list2.toArray(new Integer[0]);
System.out.println(Arrays.toString(newArray));
}四、List操作
1、创建ArrayList
2、创建LinkedList
3、添加元素
4、获取元素
5、修改元素
6、根据值删除元素
7、根据索引删除元素
8、检查是否包含某元素
9、获取列表长度
10、清除列表
11、for循环遍历List
12、增强for循环遍历List
13、迭代器遍历List
/**
* List操作
*/
public static void main1(String[] args) {
// 1、创建ArrayList 结果: [1, 2, 3]
List<String> arrayList = new ArrayList<>();
List<String> arrayList1 = new ArrayList<>(Arrays.asList("1", "2", "3"));
System.out.println(arrayList1);
// 2、创建LinkedList 结果: [1, 2, 3]
List<String> linkedList = new LinkedList<>();
List<String> linkedList1 = new LinkedList<>(Arrays.asList("1", "2", "3"));
System.out.println(linkedList1);
// 3、添加元素 结果: [4]
arrayList.add("4");
System.out.println(arrayList);
// 4、获取元素 结果: 4
System.out.println(arrayList.get(0));
// 5、修改元素 结果: [10]
arrayList.set(0, "10");
System.out.println(arrayList);
// 6、根据值删除元素 结果: [10]
arrayList.remove("2");
System.out.println(arrayList);
// 7、根据索引删除元素 结果: []
arrayList.remove(0);
System.out.println(arrayList);
// 8、检查是否包含某元素 结果: false
System.out.println(arrayList.contains("3"));
// 9、获取列表长度 结果: 0
System.out.println(arrayList.size());
// 10、清除列表 结果: []
arrayList1.clear();
System.out.println(arrayList1);
// 11、for循环遍历List
for (int i = 0; i < linkedList1.size(); i++) {
// System.out.println(linkedList1.get(i));
}
// 12、增强for循环遍历List
for (String item : linkedList) {
// System.out.println(item);
}
// 13、迭代器遍历List
Iterator<String> iterator = linkedList1.iterator();
while (iterator.hasNext()) {
// System.out.println(iterator.next());
}
}五、Set操作
1、创建HashSet
2、创建LinkedHashSet
3、创建TreeSet
4、添加元素
5、删除元素
6、检查是否包含某元素
7、获取集合大小
8、清空集合
9、for循环遍历
10、增强for循环遍历
11、迭代器遍历
/**
* Set操作
*/
public static void main2(String[] args) {
// 1、创建HashSet 结果: [1, 2, 3]
Set<String> hashSet = new HashSet<>();
Set<String> hashSet1 = new HashSet<>(Arrays.asList("1", "2", "3"));
System.out.println(hashSet1);
// 2、创建LinkedHashSet 结果: [1, 2, 3]
Set<String> linkedHashSet = new LinkedHashSet<>();
Set<String> linkedHashSet1 = new LinkedHashSet<>(Arrays.asList("1", "2", "3"));
System.out.println(linkedHashSet1);
// 3、创建TreeSet 结果: [1, 2, 3]
Set<String> treeSet = new TreeSet<>();
Set<String> treeSet1 = new TreeSet<>(Arrays.asList("1", "2", "3"));
System.out.println(treeSet1);
// 4、添加元素 结果: [1, 2, 3, 4]
hashSet1.add("4");
System.out.println(hashSet1);
// 5、删除元素 结果: [1, 2, 3]
hashSet1.remove("4");
System.out.println(hashSet1);
// 6、检查是否包含某元素 结果: true
System.out.println(hashSet1.contains("3"));
// 7、获取集合大小 结果: 3
System.out.println(hashSet1.size());
// 8、清空集合 结果: 0
hashSet1.clear();
System.out.println(hashSet1.size());
// 9、for循环遍历 （注意：Set不支持通过索引访问元素）
for (int i = 0; i < linkedHashSet1.size(); i++) {
}
// 10、增强for循环遍历
for (String item : linkedHashSet1) {
// System.out.println(item);
}
// 11、迭代器遍历
Iterator<String> iterator = linkedHashSet1.iterator();
while (iterator.hasNext()) {
// System.out.println(iterator.next());
}
}六、Map操作
1、创建HashMap
2、创建LinkedHashMap
3、创建TreeMap
4、获取值
5、删除某个key
6、检查是否包含键
7、检查是否包含值
8、清空Map
9、获取Map大小
10、如果不存在则设置为"1"，如果存在保持原值不变
11、遍历键
12、遍历值
13、遍历键值对
/**
* Map操作
*/
public static void main(String[] args) {
// 1、创建HashMap 结果: {1=1, 2=2}
Map<Integer, String> hashMap = new HashMap<>();
hashMap.put(1, "1");
hashMap.put(2, "2");
System.out.println(hashMap);
// 2、创建LinkedHashMap 结果: {1=1, 2=2}
Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put(1, "1");
linkedHashMap.put(2, "2");
System.out.println(linkedHashMap);
// 3、创建TreeMap 结果: {1=1, 2=2}
Map<Integer, String> treeMap = new TreeMap<>();
treeMap.put(1, "1");
treeMap.put(2, "2");
System.out.println(treeMap);
// 4、获取值 结果: 1
System.out.println(hashMap.get(1));
// 5、删除某个key 结果: {2=2}
linkedHashMap.remove(1);
System.out.println(linkedHashMap);
// 6、检查是否包含键 结果: false
System.out.println(linkedHashMap.containsKey(1));
// 7、检查是否包含值 结果: false
System.out.println(linkedHashMap.containsValue("1"));
// 8、清空Map
treeMap.clear();
// 9、获取Map大小 结果: 0
System.out.println(treeMap.size());
// 10、如果不存在则设置为"1"，如果存在保持原值不变
treeMap.putIfAbsent(1, "1");
// 11、遍历键
for (Integer key : hashMap.keySet()) {
System.out.println("key: " + key);
}
// 12、遍历值
for (String val : hashMap.values()) {
System.out.println("value: " + val);
}
// 13、遍历键值对
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + "Value: " + entry.getValue());
}
}七、Queue操作
1、基于LinkedList创建队列 队列先进先出
2、添加元素到队列尾部 如果队列已满，则抛出 IllegalStateException
3、添加元素到队列尾部 如果队列已满，则返回 false
4、移除并返回队列头部的元素 如果队列为空，则抛出 NoSuchElementException
5、移除并返回队列头部的元素 如果队列为空，如果队列为空，则返回 null
6、查看队列头部的元素但不移除 如果队列为空，则抛出 NoSuchElementException
7、查看队列头部的元素但不移除 如果队列为空，则返回 null
8、检查队列是否为空
9、获取队列大小
10、清空队列
11、队列是否包含某元素
12、增强for遍历
13、迭代器遍历
14、优先级队列 基于优先级堆的无界优先级队列。默认情况下，它是一个最小堆，但可以使用自定义比较器实现最大堆
15、双端队列 左头右尾 先进先出
16、阻塞队列 提供阻塞的 put 和 take 方法，分别为队列满时阻塞生产者，队列空时阻塞消费者
/**
* 队列操作
*/
public static void main(String[] args) throws InterruptedException {
// 1、基于LinkedList创建队列 队列先进先出
Queue<Integer> linkedQueue = new LinkedList<>();
// 2、添加元素到队列尾部 如果队列已满，则抛出 IllegalStateException
linkedQueue.add(1);
// 3、添加元素到队列尾部 如果队列已满，则返回 false 结果: [1, 2, 3]
linkedQueue.offer(2);
linkedQueue.offer(3);
System.out.println(linkedQueue);
// 4、移除并返回队列头部的元素 如果队列为空，则抛出 NoSuchElementException 结果: [2, 3]
linkedQueue.remove();
System.out.println(linkedQueue);
// 5、移除并返回队列头部的元素 如果队列为空，如果队列为空，则返回 null 结果: [3]
linkedQueue.poll();
System.out.println(linkedQueue);
// 6、查看队列头部的元素但不移除 如果队列为空，则抛出 NoSuchElementException 结果: 3
System.out.println(linkedQueue.element());
// 7、查看队列头部的元素但不移除 如果队列为空，则返回 null 结果： 3
System.out.println(linkedQueue.peek());
// 8、检查队列是否为空 结果: false
System.out.println(linkedQueue.isEmpty());
// 9、获取队列大小 结果: 1
System.out.println(linkedQueue.size());
// 10、清空队列
linkedQueue.clear();
// 11、队列是否包含某元素 结果: false
System.out.println(linkedQueue.contains(1));
// 12、增强for遍历
for (Integer item: linkedQueue) {
// System.out.println(item);
}
// 13、迭代器遍历
Iterator<Integer> iterator = linkedQueue.iterator();
while (iterator.hasNext()) {
// System.out.println(iterator.next());
}
// 14、优先级队列 基于优先级堆的无界优先级队列。默认情况下，它是一个最小堆，但可以使用自定义比较器实现最大堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(1);
priorityQueue.offer(3);
priorityQueue.offer(2);
// 结果: [1, 3, 2]
System.out.println(priorityQueue);
// 结果: 1
System.out.println(priorityQueue.poll());
// 结果: 2
System.out.println(priorityQueue.poll());
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>((a, b) -> b - a);
priorityQueue1.offer(1);
priorityQueue1.offer(5);
priorityQueue1.offer(4);
// 结果: [5, 1, 4]
System.out.println(priorityQueue1);
// 结果: 5
System.out.println(priorityQueue1.poll());
// 结果: 4
System.out.println(priorityQueue1.poll());
// 15、双端队列 左头右尾 先进先出
Deque<Integer> arrayDeque = new ArrayDeque<>();
Deque<Integer> linkedDeque = new LinkedList<>();
// add/remove会抛移除
arrayDeque.addFirst(1);
arrayDeque.offerFirst(2);
arrayDeque.offer(3);
// 结果: [2, 1, 3]
System.out.println(arrayDeque);
// offer/poll不会抛异常，会返回true/false
arrayDeque.addLast(11);
arrayDeque.offerLast(12);
arrayDeque.offer(13);
// 结果: [2, 1, 3, 11, 12, 13]
System.out.println(arrayDeque);
arrayDeque.removeLast();
// 结果: [2, 1, 3, 11, 12]
System.out.println(arrayDeque);
arrayDeque.removeFirst();
// 结果: [1, 3, 11, 12]
System.out.println(arrayDeque);
arrayDeque.pollFirst();
// 结果: [3, 11, 12]
System.out.println(arrayDeque);
arrayDeque.pollLast();
// 结果: [3, 11]
System.out.println(arrayDeque);
// offer/poll，正常的先进先出，进从尾部进，出从头部出
arrayDeque.poll();
// 结果: [11]
System.out.println(arrayDeque);
// 16、阻塞队列 提供阻塞的 put 和 take 方法，分别为队列满时阻塞生产者，队列空时阻塞消费者
ArrayBlockingQueue<Integer> arrayBlockingQueue = new ArrayBlockingQueue<>(1);
arrayBlockingQueue.offer(1);
arrayBlockingQueue.offer(2);
// 结果: [1]
System.out.println(arrayBlockingQueue);
arrayBlockingQueue.poll();
arrayBlockingQueue.offer(2);
// 队列满时阻塞生产者 结果: [2]
System.out.println(arrayBlockingQueue);
arrayBlockingQueue.put(1);
// 结果: 阻塞等待
System.out.println(arrayBlockingQueue);
// 队列空时阻塞消费者
arrayBlockingQueue.take();
arrayBlockingQueue.put(3);
// 结果: 阻塞等待
System.out.println(arrayBlockingQueue);
}
八、栈操作
1、基于Stack创建栈
2、基于ArrayDeque的栈
3、基于LinkedList的栈
4、入栈
5、出栈
6、查看栈顶元素但不弹出
7、是否为空
8、获取栈的大小
9、增强for遍历
10、基于迭代器遍历
/**
* 栈操作
*/
public static void main(String[] args) {
// 1、基于Stack创建栈
Stack<Integer> stack = new Stack<>();
// 2、基于ArrayDeque的栈
Deque<Integer> arrayDeque = new ArrayDeque<>();
// 3、基于LinkedList的栈
Deque<Integer> linkedDeque = new LinkedList<>();
// 4、入栈
stack.push(1);
stack.push(2);
stack.push(3);
// 结果: [1, 2, 3]
System.out.println(stack);
// 5、出栈 结果: 3
System.out.println(stack.pop());
// 6、查看栈顶元素但不弹出 结果: 2
System.out.println(stack.peek());
// 7、是否为空 结果: true
System.out.println(arrayDeque.isEmpty());
// 8、获取栈的大小 结果: 0
System.out.println(linkedDeque.size());
// 9、增强for遍历
for (Integer item: stack) {
// System.out.println(item);
}
// 10、基于迭代器遍历
Iterator<Integer> iterator = stack.iterator();
while (iterator.hasNext()) {
// System.out.println(iterator.next());
}
}
九、链表操作
1、创建链表
2、添加到尾部
3、添加到头部
4、添加到尾部
5、获取第一个元素
6、获取最后一个元素
7、获取指定索引的元素
8、修改元素
9、移除头部元素
10、移除头部元素
11、移除尾部元素
12、移除指定索引元素
13、检查链表是否为空
14、获取链表大小
15、清空链表
16、增强for遍历
17、迭代器遍历
18、列表迭代器遍历
19、自定义链表
/**
* 定义链表
*/
static class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
/**
* 打印链表
*/
public static void printList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.println(current.val + " -> ");
current = current.next;
}
System.out.println("null");
}
/**
* 插入节点到链表头部
*/
public static ListNode insertAtHead(ListNode head, int val) {
ListNode newNode = new ListNode(val);
newNode.next = head;
return newNode;
}
/**
* 插入节点到链表尾部
*/
public static ListNode insertAtTail(ListNode head, int val) {
ListNode newNode = new ListNode(val);
if (head == null) {
return newNode;
}
ListNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
return head;
}
/**
* 删除链表中的节点
*/
public static ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
return head.next;
}
ListNode current = head;
while (current.next != null && current.next.val != val) {
current = current.next;
}
if (current.next != null) {
current.next = current.next.next;
}
return head;
}
/**
* 链表操作
*/
public static void main(String[] args) {
// 1、创建链表
LinkedList<Integer> linkedList = new LinkedList<>();
LinkedList<Integer> linkedList1 = new LinkedList<>(Arrays.asList(1, 2, 3));
// 结果: []
System.out.println(linkedList);
// 结果: [1, 2, 3]
System.out.println(linkedList1);
// 2、添加到尾部
linkedList.add(1);
linkedList.add(3);
linkedList.add(4);
// 3、添加到头部
linkedList.addFirst(0);
// 4、添加到尾部
linkedList.addLast(2);
// 结果: [0, 1, 3, 4, 2]
System.out.println(linkedList);
// 5、获取第一个元素 结果: 0
System.out.println(linkedList.getFirst());
// 6、获取最后一个元素 结果: 2
System.out.println(linkedList.getLast());
// 7、获取指定索引的元素 结果: 0
System.out.println(linkedList.get(0));
// 8、修改元素
linkedList.set(0, 10);
// 9、移除头部元素
linkedList.remove();
// 10、移除头部元素
linkedList.removeFirst();
// 11、移除尾部元素
linkedList.removeLast();
// 12、移除指定索引元素
linkedList.remove(1);
// 结果: [3]
System.out.println(linkedList);
// 13、检查链表是否为空 结果: false
System.out.println(linkedList.isEmpty());
// 14、获取链表大小 结果: 1
System.out.println(linkedList.size());
// 15、清空链表
linkedList.clear();
// 16、增强for遍历
for (Integer item : linkedList) {
// System.out.println(item);
}
// 17、迭代器遍历
Iterator<Integer> iterator = linkedList.iterator();
while (iterator.hasNext()) {
// System.out.println(iterator.next());
}
// 18、列表迭代器遍历
ListIterator<Integer> listIterator = linkedList.listIterator();
while (listIterator.hasPrevious()) {
// System.out.println(listIterator.previous());
}
// 19、自定义链表
ListNode head = new ListNode(1);
head = insertAtHead(head, 0);
head = insertAtTail(head, 2);
head = insertAtTail(head, 3);
// 结果: 0 -> 1 -> 2 -> 3 -> null
printList(head);
head = deleteNode(head, 2);
// 结果: 0 -> 1 -> 3 -> null
printList(head);
}十、二叉树操作
1、创建二叉树
2、插入节点
3、前序遍历
4、中序遍历
5、后序遍历
6、层序遍历
7、查找节点
/**
* 二叉树定义
*/
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 插入节点
*/
public static TreeNode insert(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
}
return root;
}
/**
* 二叉树前序遍历
*/
public static void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.println(root.val + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
/**
* 二叉树中序遍历
*/
public static void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.println(root.val + " ");
inOrderTraversal(root.right);
}
/**
* 二叉树后序遍历
*/
public static void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.println(root.val + " ");
}
/**
* 二叉树层序遍历
*/
public static void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
/**
* 查找节点
*/
public static TreeNode search(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return search(root.left, val);
} else {
return search(root.right, val);
}
}
/**
* 二叉树操作
*/
public static void main(String[] args) {
// 1、创建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
// 2、插入节点
root = insert(root, 8);
// 3、前序遍历 结果: 12453678
preOrderTraversal(root);
// 4、中序遍历 结果: 42516378
inOrderTraversal(root);
// 5、后序遍历 结果: 45268731
postOrderTraversal(root);
// 6、层序遍历 结果: 12345678
levelOrderTraversal(root);
// 7、查找节点
TreeNode search = search(root, 2);
System.out.println(search.val);
}十一、图操作
1、创建邻接矩阵
2、邻接矩阵深度优先搜索
3、创建邻接表（图）
4、深度优先搜索
5、广度优先搜索
/**
* 图定义
*/
static class Graph {
// 顶点数量
private int v;
// 邻接表
private LinkedList<Integer>[] adj;
/**
* 构造函数
*/
public Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<>();
}
}
/**
* 添加边
*/
public void addEdge(int v, int w) {
adj[v].add(w);
// 如果是有向图，移除这一行
adj[w].add(v);
}
/**
* 获取邻接表
*/
public LinkedList<Integer>[] getAdj() {
return adj;
}
}
/**
* 图的遍历-深度优先搜索（DFS）
*/
public static void dfs(Graph graph, int v, boolean[] visited) {
visited[v] = true;
System.out.println(v + " ");
for (int neighbor : graph.getAdj()[v]) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
/**
* 图的遍历-广度优先搜索（BFS）
* @param graph
* @param start
*/
public static void bfs(Graph graph, int start) {
boolean[] visited = new boolean[graph.getAdj().length];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.println(v + " ");
for (int neighbor : graph.getAdj()[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
/**
* 图操作
*/
public static void main(String[] args) {
// 1、创建邻接矩阵 结果: [[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]]
int[][] graphArr = {{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 0}};
System.out.println(Arrays.deepToString(graphArr));
boolean[] visited1 = new boolean[graphArr.length];
// 2、邻接矩阵深度优先搜索
dfs(graphArr, 0, visited1);
// 3、创建邻接表（图）
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
// 4、深度优先搜索 结果: 0 1 2 3 4
System.out.println("深度优先搜索");
boolean[] visited = new boolean[5];
dfs(graph, 0, visited);
// 5、广度优先搜索 结果: 0 1 4 2 3
System.out.println("广度优先搜索");
bfs(graph, 0);
}
/**
* 邻接矩阵深度优先搜索
*/
public static void dfs(int[][] graph, int start, boolean[] visited) {
visited[start] = true;
System.out.print(start + " ");
for (int i = 0; i < graph[start].length; i++) {
if (graph[start][i] == 1 && !visited[i]) {
dfs(graph, i, visited);
}
}
}十二、数学操作
1、最大值
2、最小值
3、绝对值
4、向下取整
5、向上取整
6、四舍五入取整
7、幂次方
8、平方根
9、随机数生成
10、生成 0 到 9 之间的整数随机数
11、random类
12、生成 0 到 9 之间的整数随机数
13、生成任意整数随机数
/**
* 数学操作
*/
public static void main(String[] args) {
// 1、最大值 结果: 20
System.out.println(Math.max(10, 20));
// 2、最小值 结果: 10
System.out.println(Math.min(10, 20));
// 3、绝对值 结果: 10
System.out.println(Math.abs(-10));
// 4、向下取整 结果: 3.0
System.out.println(Math.floor(3.7));
// 5、向上取整 结果: 4.0
System.out.println(Math.ceil(3.2));
// 6、四舍五入取整 结果: 4
System.out.println(Math.round(3.5));
// 7、幂次方 结果: 8.0
System.out.println(Math.pow(2, 3));
// 8、平方根 结果: 4.0
System.out.println(Math.sqrt(16));
// 9、随机数生成 结果: 0.0 到 1.0 之间的随机数 结果: 0.7846350296500209
System.out.println(Math.random());
// 10、生成 0 到 9 之间的整数随机数 结果: 1
System.out.println((int) (Math.random() * 10));
// 11、random类
Random random = new Random();
// 12、生成 0 到 9 之间的整数随机数 结果: 6
System.out.println(random.nextInt(10));
// 13、生成任意整数随机数 结果: -840368123
System.out.println(random.nextInt());
}十三、位操作
1、按位与（&）
2、按位或 (|)
3、按位异或 (^)
4、按位取反（~）
5、左移 (<<) 左移乘2
6、右移 (>>) 右移除2
7、无符合右移 (>>>)
8、判断奇偶性
9、交换两个数（不使用临时变量）
10、计算绝对值
11、检查两个数是否有相同符合
12、快速计算2的幂次倍数
/**
* 位操作
*/
public static void main(String[] args) {
// 1、按位与（&）
// 0101
int a = 5;
// 0011
int b = 3;
// 结果: 1，即 0011
System.out.println(a & b);
// 2、按位或 (|)
// 结果: 7，即 0111
System.out.println(a | b);
// 3、按位异或 (^) 结果: 6，即 0110
System.out.println(a ^ b);
// 4、按位取反（~）结果: -6，即 1010
System.out.println(~a);
// 5、左移 (<<) 左移乘2 结果: 10，即 1010
System.out.println(a << 1);
// 6、右移 (>>) 右移除2 结果: 2，即 0010
System.out.println(a >> 1);
// 7、无符合右移 (>>>)
// 11111111111111111111111111111011
int c = -5;
// 结果: 2147483645，即 01111111111111111111111111111101
System.out.println(c >>> 1);
// 8、判断奇偶性
int n = 5;
// 是否奇数 结果: true
System.out.println((n & 1) == 1);
// 是否偶数 结果: false
System.out.println((n & 1) == 0);
// 9、交换两个数（不使用临时变量）
a = a ^ b;
b = a ^ b;
a = a ^ b;
// 结果: 3, 5
System.out.println(a + ", " + b);
// 10、计算绝对值
int absValue = (c ^ (c >> 31)) - (c >> 31);
// 结果: 5
System.out.println(absValue);
// 11、检查两个数是否有相同符合
int d = -5;
int e = 3;
// true 表示相同符号, false 表示不同符号
boolean sameSign = (d ^ e) >= 0;
// 结果: false
System.out.println(sameSign);
// 12、快速计算2的幂次倍数 结果: 2 ^ 3 = 8
System.out.println(1 << 3);
}
十四、线程操作
1. 基础Thread类
2. 实现Runnable接口
3. 实现Callable接口
4. 线程池方式
5、线程同步-synchronized关键字
6、线程同步-ReentrantLock
7、线程通信 wait()和notify()
// 1、基础Thread类
static class MyThread extends Thread {
@Override
public void run() {
System.out.println("Thread is running: " + Thread.currentThread().getName());
}
public static void main(String[] args) {
MyThread thread1 = new MyThread();
MyThread thread2 = new MyThread();
// 启动线程1 结果: Thread is running: Thread-0
thread1.start();
// 启动线程2 结果: Thread is running: Thread-1
thread2.start();
}
}
// 2、实现Runnable接口
static class MyRunnable implements Runnable {
@Override
public void run() {
System.out.println("Thread is running: " + Thread.currentThread().getName());
}
public static void main(String[] args) {
Thread thread1 = new Thread(new MyRunnable());
Thread thread2 = new Thread(new MyRunnable());
// 使用Lambda表达式简化Runnable的实现
Thread thread3 = new Thread(() -> System.out.println("Thread is running: " + Thread.currentThread().getName()));
// 启动线程1 结果: Thread is running: Thread-0
thread1.start();
// 启动线程2 结果: Thread is running: Thread-1
thread2.start();
// 启动线程3 结果: Thread is running: Thread-2
thread3.start();
}
}
// 3、实现Callable接口
static class MyCallable implements Callable<String> {
@Override
public String call() throws Exception {
System.out.println("Thread is running: " + Thread.currentThread().getName());
return Thread.currentThread().getName();
}
public static void main(String[] args) throws ExecutionException, InterruptedException {
MyCallable myCallable = new MyCallable();
// FutureTask实现了RunnableFuture接口，而RunnableFuture接口同时继承了Runnable接口和Future接口
FutureTask<String> futureTask = new FutureTask<>(myCallable);
Thread thread = new Thread(futureTask);
// 启动线程 结果: Thread is running: Thread-0
thread.start();
// 结果: Thread-0
System.out.println(futureTask.get());
}
}
// 4、线程池方式
public static void main(String[] args) throws ExecutionException, InterruptedException {
ThreadPoolExecutor threadPoolExecutor = new ThreadPoolExecutor(4,
4,
60,
TimeUnit.SECONDS,
new ArrayBlockingQueue<>(20000),
new ThreadPoolExecutor.CallerRunsPolicy());
Runnable task1 = () -> System.out.println("task1 is running: " + Thread.currentThread().getName());
Runnable task2 = () -> System.out.println("task2 is running: " + Thread.currentThread().getName());
Callable<String> task3 = () -> {
System.out.println("task3 is running: " + Thread.currentThread().getName());
return Thread.currentThread().getName();
};
// Runnable无返回值，异常处理简单；Callable有返回值，异常处理更加灵活，使用submit()提交，返回一个Future对象，用于获取任务的结果
// 提交任务1 结果: task1 is running: pool-1-thread-1
threadPoolExecutor.execute(task1);
// 提交任务2 结果: task2 is running: pool-1-thread-2
threadPoolExecutor.submit(task2);
// 提交任务3 结果: task3 is running: pool-1-thread-3
Future<String> submit = threadPoolExecutor.submit(task3);
// 结果: pool-1-thread-3
System.out.println(submit.get());
}
/**
* 5、线程同步-synchronized关键字
*/
static class SynchronizedCounter {
private int count = 0;
public synchronized void increment() {
count++;
}
public synchronized int getCount() {
return count;
}
public static void main(String[] args) throws InterruptedException {
SynchronizedCounter synchronizedCounter = new SynchronizedCounter();
Runnable task = () -> {
for (int i = 0; i < 1000; i++) {
synchronizedCounter.increment();
}
};
Thread thread1 = new Thread(task);
Thread thread2 = new Thread(task);
thread1.start();
thread2.start();
thread1.join();
thread2.join();
System.out.println("final count: " + synchronizedCounter.getCount());
}
}
/**
* 6、线程同步-ReentrantLock
*/
static class ReentrantLockCounter {
private int count = 0;
private final Lock lock = new ReentrantLock();
public void increment() {
lock.lock();
try {
count++;
} finally {
lock.unlock();
}
}
public int getCount() {
return count;
}
public static void main(String[] args) throws InterruptedException {
ReentrantLockCounter reentrantLockCounter = new ReentrantLockCounter();
Runnable task = () -> {
for (int i = 0; i < 1000; i++) {
reentrantLockCounter.increment();
}
};
Thread thread1 = new Thread(task);
Thread thread2 = new Thread(task);
thread1.start();
thread2.start();
thread1.join();
thread2.join();
System.out.println("final count: " + reentrantLockCounter.getCount());
}
}
/**
* 7、线程通信 wait()和notify()
*/
static class ProducerConsumer {
// 存储共享数据的变量
private int value;
// 标记数据是否可用
private boolean available = false;
// 生产者调用此方法存入数据
public synchronized void put(int value) throws InterruptedException {
// 如果数据已存在，则等待
while (available) {
// 线程等待，直到数据被消费
wait();
}
// 存储新的数据
this.value = value;
// 标记数据为可用
this.available = true;
// 通知其他等待线程
notify();
}
// 消费者调用此方法获取数据
public synchronized int get() throws InterruptedException {
// 如果没有数据，则等待
while (!available) {
// 线程等待，直到数据被生产
wait();
}
// 标记数据为不可用
this.available = false;
// 通知其他等待线程
notify();
// 返回数据
return value;
}
public static void main(String[] args) {
// 创建生产者消费者模型
ProducerConsumer producerConsumer = new ProducerConsumer();
// 创建生产者线程任务
Runnable producer = () -> {
for (int i = 0; i < 10; i++) {
try {
producerConsumer.put(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Produced: " + i + " at " + System.currentTimeMillis());
}
};
// 创建消费者线程任务
Runnable consumer = () -> {
for (int i = 0; i < 10; i++) {
int value = 0;
try {
value = producerConsumer.get();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Consumed: " + value + " at " + System.currentTimeMillis());
}
};
// 创建和启动生产者线程
Thread producerThread = new Thread(producer);
Thread consumerThread = new Thread(consumer);
// 创建和启动消费者线程
producerThread.start();
consumerThread.start();
}
}
}十五、同步操作
1、ReentrantLock: 可重入的互斥锁，提供了比 synchronized 更灵活的锁机制
2、ReentrantReadWriteLock: 维护了一对相关的锁，一个用于只读操作，一个用于写入操作
3、Semaphore（信号量）: 计数信号量，限制同时访问某资源的线程数量
4、CountDownLatch（计数器）: 允许一个或多个线程等待其他线程完成一组操作
5、CyclicBarrier（栅栏）: 允许一组线程互相等待，直到所有线程都到达某个屏障点
/**
* 1、ReentrantLock: 可重入的互斥锁，提供了比 synchronized 更灵活的锁机制
*/
public static class ReentrantLockExample {
private final Lock lock = new ReentrantLock();
private int count = 0;
public void increment() {
lock.lock();
try {
count++;
} finally {
lock.unlock();
}
}
public int getCount() {
return count;
}
public static void main(String[] args) throws InterruptedException {
ReentrantLockExample reentrantLockExample = new ReentrantLockExample();
Runnable task = () -> {
for (int i = 0; i < 1000; i++) {
reentrantLockExample.increment();
}
};
Thread thread1 = new Thread(task);
Thread thread2 = new Thread(task);
thread1.start();
thread2.start();
thread1.join();
thread2.join();
System.out.println("Final count: " + reentrantLockExample.getCount());
}
}
/**
* 2、ReentrantReadWriteLock: 维护了一对相关的锁，一个用于只读操作，一个用于写入操作
*/
public static class ReentrantReadWriteLockExample {
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
private int count = 0;
public void increment() {
lock.writeLock().lock();
try {
count++;
} finally {
lock.writeLock().unlock();
}
}
public int getCount() {
lock.readLock().lock();
try {
return count;
} finally {
lock.readLock().unlock();
}
}
public static void main(String[] args) throws InterruptedException {
ReentrantReadWriteLockExample reentrantReadWriteLockExample = new ReentrantReadWriteLockExample();
Runnable writeTask = () -> {
for (int i = 0; i < 1000; i++) {
reentrantReadWriteLockExample.increment();
}
};
Runnable readTask = () -> {
for (int i = 0; i < 1000; i++) {
System.out.println("Count: " + reentrantReadWriteLockExample.getCount());
}
};
Thread writeThread = new Thread(writeTask);
Thread readThread = new Thread(readTask);
writeThread.start();
readThread.start();
writeThread.join();
readThread.join();
System.out.println("Final count: " + reentrantReadWriteLockExample.getCount());
}
}
/**
* 3、Semaphore（信号量）: 计数信号量，限制同时访问某资源的线程数量
*/
public static class SemaphoreExample {
private final Semaphore semaphore = new Semaphore(3);
public void task() {
try {
semaphore.acquire();
System.out.println(Thread.currentThread().getName() + " is running task.");
// 模拟任务
Thread.sleep(500);
} catch (Exception e) {
e.printStackTrace();
} finally {
System.out.println(Thread.currentThread().getName() + " has finished task.");
semaphore.release();
}
}
public static void main(String[] args) {
SemaphoreExample semaphoreExample = new SemaphoreExample();
Runnable task = semaphoreExample::task;
for (int i = 0; i < 10; i++) {
new Thread(task).start();
}
}
}
/**
* 4、CountDownLatch（计数器）: 允许一个或多个线程等待其他线程完成一组操作
*/
public static class CountDownLatchExample {
public final CountDownLatch countDownLatch = new CountDownLatch(3);
public void task() {
System.out.println(Thread.currentThread().getName() + " is running task.");
try {
// 模拟任务
Thread.sleep(1000);
} catch (Exception e) {
e.printStackTrace();
} finally {
countDownLatch.countDown();
System.out.println(Thread.currentThread().getName() + " has finished task.");
}
}
public static void main(String[] args) throws InterruptedException {
CountDownLatchExample countDownLatchExample = new CountDownLatchExample();
Runnable task = countDownLatchExample::task;
for (int i = 0; i < 3; i++) {
new Thread(task).start();
}
countDownLatchExample.countDownLatch.await();
System.out.println("All tasks are finished.");
}
}
/**
* 5、CyclicBarrier（栅栏）: 允许一组线程互相等待，直到所有线程都到达某个屏障点
*/
public static class CyclicBarrierExample {
private final CyclicBarrier barrier = new CyclicBarrier(3);
public void task() {
try {
System.out.println(Thread.currentThread().getName() + " is waiting at the barrier.");
barrier.await();
System.out.println(Thread.currentThread().getName() + " has finished task.");
} catch (Exception e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
CyclicBarrierExample cyclicBarrierExample = new CyclicBarrierExample();
Runnable task = () -> {
cyclicBarrierExample.task();
};
for (int i = 0; i < 3; i++) {
new Thread(task).start();
}
}
}
十六、常用算法模板
1、DFS：适用于树和图的遍历、组合问题。
2、BFS：适用于树和图的层次遍历、最短路径问题。
3、二分查找：适用于有序数组的搜索问题。
4、动态规划：适用于最优化问题、序列问题。
5、贪心算法：适用于局部最优问题、调度问题。
6、回溯算法：适用于组合、排列、子集问题。
7、滑动窗口：适用于子数组、子串问题。
8、拓扑排序：适用于依赖关系问题、课程安排问题。9、快慢指针：多用于检测链表中的环、找到环的起点。
10、双指针：处理字符串、数组、链表问题。
11、优先队列：处理调度、合并等问题。
12、并查集：处理动态连通性问题。
13、前缀和：用于快速计算子数组和。
14、单调栈：用于查找数组中前后更大或更小的元素。
15、排序：包括快速排序、归并排序和堆排序等常见排序算法。
/**
* 二叉树定义
*/
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 深度优先搜索模板（DFS）
*/
public class DFSTemplate {
/**
* 深度优先搜索
*/
public void dfs(TreeNode node) {
if (node == null) {
return;
}
// 处理当前节点
System.out.println(node.val);
// 递归处理左右子节点
dfs(node.left);
dfs(node.right);
}
/**
* 二叉树的最大深度
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
/**
* 广度优先搜索模板（BFS）
*/
public class BFSTemplate {
/**
* 广度优先搜索
*/
public void bfs(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
/**
* 二叉树的层序遍历
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
return result;
}
}
/**
* 二分查找模板
*/
public class BinarySearchTemplate {
/**
* 二分查找
*/
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
/**
* 搜索旋转排序数组
*/
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}
/**
* 动态规划（DP）模板
*/
public class DpTemplate {
public int dp(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
// 初始化
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1], nums[i]);
}
return dp[n - 1];
}
/**
* 最长上升子序列
*/
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLength = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
}
/**
* 贪心算法模板
*/
public class GreedyTemplate {
public int solve(int[] nums) {
int result = 0;
for (int num : nums) {
// 执行贪心选择
if (someCondition(num)) {
result += num;
}
}
return result;
}
private boolean someCondition(int num) {
// 自定义条件
return true;
}
/**
* 无重叠区间
*/
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 1;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= end) {
count++;
end = intervals[i][1];
}
}
return intervals.length - count;
}
}
/**
* 回溯算法模板
*/
public class BacktrackingTemplate {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> solve(int[] nums) {
backtrack(new ArrayList<>(), nums);
return result;
}
/**
* 回溯方法
*/
private void backtrack(List<Integer> tempList, int[] nums) {
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (tempList.contains(nums[i])) {
continue;
}
tempList.add(nums[i]);
backtrack(tempList, nums);
// 回溯，尝试所有可能结果
tempList.remove(tempList.size() - 1);
}
}
}
/**
* 全排列
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
} else {
for (int i = 0; i < nums.length; i++) {
if (tempList.contains(nums[i])) {
continue;
}
tempList.add(nums[i]);
backtrack(result, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
}
/**
* 滑动窗口模板
*/
public class SlidingWindowTemplate {
public int solve(int[] nums) {
int left = 0, right = 0;
int maxLength = 0;
while (right < nums.length) {
// 扩大窗口
right++;
// 收缩窗口
while (someCondition()) {
left++;
}
maxLength = Math.max(maxLength, right - left);
}
return maxLength;
}
private boolean someCondition() {
// 自定义条件
return false;
}
/**
* 最长无重复子串
*/
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, right = 0, maxLength = 0;
while (right < s.length()) {
if (!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
right++;
maxLength = Math.max(maxLength, set.size());
} else {
set.remove(s.charAt(left));
left++;
}
}
return maxLength;
}
}
/**
* 拓扑排序模板
*/
public class TopologicalSortTemplate {
public List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {
List<Integer> result = new ArrayList<>();
List<Integer>[] graph = new List[numCourses];
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
graph[pre[1]].add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int course = queue.poll();
result.add(course);
for (int next : graph[course]) {
inDegree[next]--;
if (inDegree[next] == 0) {
queue.offer(next);
}
}
}
return result.size() == numCourses ? result : new ArrayList<>();
}
/**
* 课程表
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new List[numCourses];
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
graph[pre[1]].add(pre[0]);
inDegree[pre[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
count++;
for (int next : graph[course]) {
inDegree[next]--;
if (inDegree[next] == 0) {
queue.offer(next);
}
}
}
return count == numCourses;
}
}
/**
* 快慢指针模板
*/
public class FastSlowPointerTemplate {
/**
* 链表定义
*/
public class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
/**
* 是否有环
*/
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
/**
* 环形链表II
*/
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
// 检测环
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
// 发现环，寻找环的起点
ListNode pointer1 = head;
ListNode pointer2 = slow;
while (pointer1 != pointer2) {
pointer1 = pointer1.next;
pointer2 = pointer2.next;
}
return pointer1;
}
}
return null;
}
}
/**
* 双指针模板
*/
public class TwoPointerTemplate {
public int solve(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int result = 0;
while (left < right) {
// 执行逻辑
int sum = nums[left] + nums[right];
if (sum == target) {
// 找到目标
result++;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return result;
}
/**
* 两数之和II-输入有序数组
*/
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// 注意：返回的索引是从 1 开始
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
// 没找到，返回无效值
return new int[]{-1, -1};
}
}
/**
* 优先队列模板
*/
public class PriorityQueueTemplate {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public int solve(int[] nums) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.offer(num);
}
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
// 根据实际问题返回结果
return 0;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (!pq.isEmpty()) {
current.next = pq.poll();
current = current.next;
if (current.next != null) {
pq.offer(current.next);
}
}
return dummy.next;
}
}
/**
* 并查集模板
*/
public class UnionFindTemplate {
private int[] parent;
private int[] rank;
public UnionFindTemplate(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
/**
* 岛屿数量
*/
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
UnionFind uf = new UnionFind(rows * cols);
int count = 0;
// 初始化并查集和计数
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++;
}
}
}
// 遍历网格，进行合并操作
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
count--;
// 合并相邻的岛屿
if (i > 0 && grid[i - 1][j] == '1') {
uf.union(i * cols + j, (i - 1) * cols + j);
count++;
}
if (i < rows - 1 && grid[i + 1][j] == '1') {
uf.union(i * cols + j, (i + 1) * cols + j);
count++;
}
if (j > 0 && grid[i][j - 1] == '1') {
uf.union(i * cols + j, i * cols + j - 1);
count++;
}
if (j < cols - 1 && grid[i][j + 1] == '1') {
uf.union(i * cols + j, i * cols + j + 1);
count++;
}
}
}
}
return count;
}
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
}
/**
* 前缀和模板
*/
public class PrefixSumTemplate {
public int[] calculatePrefixSum(int[] nums) {
int n = nums.length;
int[] prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
return prefixSum;
}
public int rangeSum(int[] prefixSum, int left, int right) {
return prefixSum[right + 1] - prefixSum[left];
}
private int[] prefixSum;
/**
* 区域和检索-数组不可变
*/
public PrefixSumTemplate(int[] nums) {
int n = nums.length;
prefixSum = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
}
public int sumRange(int left, int right) {
return prefixSum[right + 1] - prefixSum[left];
}
}
/**
* 单调栈模板
*/
public class MonotonicStackTemplate {
public int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() <= nums[i]) {
stack.pop();
}
result[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(nums[i]);
}
return result;
}
/**
* 每日温度
*/
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] result = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int index = stack.pop();
result[index] = i - index;
}
stack.push(i);
}
return result;
}
}
/**
* 快速排序模板
*/
public class QuickSortTemplate {
public void quickSort(int[] nums, int left, int right) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
}
private int partition(int[] nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, right);
return i;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
/**
* 归并排序模板
*/
public class MergeSortTemplate {
public void mergeSort(int[] nums, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
private void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
System.arraycopy(temp, 0, nums, left, temp.length);
}
}
/**
* 堆排序模板
*/
public class HeapSortTemplate {
public void heapSort(int[] nums) {
int n = nums.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(nums, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(nums, 0, i);
// Call max heapify on the reduced heap
heapify(nums, i, 0);
}
}
private void heapify(int[] nums, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
// If left child is larger than root
if (left < n && nums[left] > nums[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && nums[right] > nums[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
swap(nums, i, largest);
// Recursively heapify the affected sub-tree
heapify(nums, n, largest);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
/**
* 冒泡排序模板
*/
public class BubbleSortTemplate {
public void bubbleSort(int[] nums) {
int n = nums.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
swapped = true;
}
}
// 如果在内层循环中没有发生交换，说明数组已经有序，提前结束
if (!swapped) {
break;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}作者：星夜孤帆
