Java常用类、方法

/* char || Character */
// string转化为char数组，以及Character判断是否为数字
for (char c : string.toCharArray()) {
    if (!Character.isDigit(c)) {
        return false;
    }
}
/* int || Integer */
// 将string转换为整数
try {
    int num = Integer.parseInt(string);
} catch (NumberFormatException e) {
    return false;
}
// int最大值
Integer.MAX_VALUE;

// Arrays计算数组均值、最大值、最小值、求和
Arrays.stream(nums).average().getAsDouble();
Arrays.stream(nums).max().getAsInt();
Arrays.stream(nums).min().getAsInt();
Arrays.stream(nums).sum();
// List流计算List均值、最大值、最小值、求和
Double avg = list.stream().mapToLong(Integer::intValue).average().getAsDouble();
int max = list.stream().mapToInt(Integer::intValue).max().getAsInt();
int min = list.stream().mapToInt(Integer::intValue).min().getAsInt();
int sum = list.stream().mapToInt(Integer::intValue).sum();
// Collections计算List最大值、最小值
int max = Collections.max(list);
int min = Collections.min(list);

// 声明
String string = "string";
StringBuilder strBuilder = new StringBuilder(string);
// 取字符
string.charAt(index);
strBuilder.charAt(index);
// 长度
string.length();
strBuilder.length();
// 字符串拼接
string = string.concat("aaaa");
// 子串
string.substring(start, end); // [start, end)
// 判断开头元素是否为指定元素
string.startsWith("0");
// 替换
string.replace('a', 'b');
// 修改
strBuilder.setCharAt(index, 'a');
// 添加
strBuilder.append('a');
// 删除
strBuilder.deleteCharAt(index);
// 返回一个String
strBuilder.toString();
// String转化为字符数组
char[] ch = string.toCharArray();

// 声明
List<Integer> list = new ArrayList<>();
// 拿到list的副本
List<Integer> copy_list = new ArrayList<>(list);
// 排序
Arrays.sort(nums);
// 返回一个list
Arrays.asList({1, 2, 3});
// 填充数组
Arrays.fill(nums, 0);
// 数组转化为list
List<Integer> list = new ArrayList<>(Arrays.asList(nums));
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
// list转化为数组
int[] array = list.stream().mapToInt(i -> i).toArray();
// 取数
list.get(index);
// 大小
list.size();
// 添加
list.add(item);
// 删除
list.remove(index);
// 清空
list.clear();

// 声明
Set<ListNode> set = new HashSet<>();
// 判断包含
set.contains();
// 添加
set.add();
// 大小
set.size();
// 迭代器
for (int elem : set) {}

// 自定义类实现Comparable接口
class ListNode implements Comparable<ListNode> {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
    @Override
    public int compareTo(ListNode o) {
        // 这里的“等于返回1”，保证了相同value的元素不会被覆盖
        if(o.val >= this.val) return 1;
        else return -1;
    }
}
// 声明
Set<ListNode> tree = new TreeSet<>();
// 添加
tree.add(new ListNode(1));
// 迭代器
for(ListNode e : tree) {}

// 声明
Map<Integer, Integer> map = new HashMap<>();
// 判断包含Key
map.containsKey(key);
// 用Key取Value
map.get(key);
// 添加
map.put(key, value);
// Entry迭代器
for(Map.Entry<Integer, Integer> e:map.entrySet()) {}

// 声明
Stack<Integer> stack = new Stack<>();
// 判断空
stack.isEmpty();
// 添加
stack.push(item);
// 取出
stack.pop();
// 查看但不取出栈顶
stack.peek();

// 声明
Queue<Integer> queue = new LinkedList<>();
// 判断空
queue.isEmpty();
// 添加
queue.offer(item);
// 取出
queue.poll();
// 查看但不取出队首
queue.peek();

// 声明
Deque<Integer> deque = new LinkedList<>();
// 判断空
deque.isEmpty();
// 添加
deque.offerFirst(item);
deque.offerLast(item);
// 取出
deque.pollFirst();
deque.pollLast();
// 查看但不取出
deque.peekFirst();
deque.peekLast();

/*Comparator接口说明:
 * 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
 * 对于队列：排在前面意味着往队头靠
 * 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
 *                                从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
 * */
// 声明(模拟小顶堆)
PriorityQueue<Integer> pq = new PriorityQueue<>((e1, e2) -> e1 - e2);
// 判断空
pq.isEmpty();
// 添加
pq.offer(item);
// 取出
pq.poll();
// 查看但不取出
pq.peek();

// 反转list
List<Integer> ans = new ArrayList<>();
Collections.reverse(ans);
// 随机排序
Collections.shuffle(ans);
// 交换两个索引位置的元素
Collections.swap(ans, i, j);
/* 自定义排序 */
// List<List<String>> tickets
// 以下排序可以按照 <List<String> 中第二个 String，将其以字典序排列
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
// 以下排序可以先按 <List<String> 中第1个 String 再按第2个 String，将其以字典序排列
Collections.sort(tickets, new Comparator<List<String>>() {
    @Override
    public int compare(List<String> o1, List<String> o2) {
        int cmp = o1.get(0).compareTo(o2.get(0));
        if (cmp == 0) {
            cmp = o1.get(1).compareTo(o2.get(1));
        }
        return cmp;
    }
});
// 或者用list自己的sort方法
tickets.sort(Comparator.comparing((List<String> o) -> o.get(0))
                      .thenComparing(o -> o.get(1)));

// 取最大值
Math.max(a, b);
// 取最小值
Math.min(a, b);
// 取绝对值
Math.abs(a);
// 取幂
Math.pow(a, b);
// 取平方根
Math.sqrt(a);
// 取自然对数
Math.log(a);
// 取以10为底的对数
Math.log10(a);

// 声明
Scanner sc = new Scanner(System.in);
// 判断是否还有下一个整数
sc.hasNextInt();
// 读取整数
int num = sc.nextInt();
// 读取字符串
String str = sc.nextLine();

String input = "[1(2), 1(1), -1(3)]";
Pattern pattern = Pattern.compile("(-?\\d+)\\((\\d+)\\)");
Matcher matcher = pattern.matcher(input);
List<List<Integer>> result = new ArrayList<>();
while (matcher.find()) {
    List<Integer> pair = new ArrayList<>();
    pair.add(Integer.parseInt(matcher.group(1)));
    pair.add(Integer.parseInt(matcher.group(2)));
    result.add(pair);
}
System.out.println(result);
// 输出：[[1, 2], [1, 1], [-1, 3]]

import java.util.*;
// import java.util.List;
// import java.util.Scanner;
 
public class AcmInputOutput {
    public static void main(String [] args) {
        AcmInputOutput acm = new AcmInputOutput();
        acm.inputNumberWithLine();
    }
 
    // 主要掌握scan.hasNext()、scan.hasNextInt()、scan.nextInt()、
    // scan.hasNextLine()、scan.nextLine()的使用
 
    // 1. 数字处理
    // 读取 Long：in.hasNextLong() 和 in.nextLong()；
    // 读取小数：in.nextFloat() 或 in.nextDouble()；
    // 及其hasNextFloat() 或 hasNextDouble()；
 
    // 1.1. 基础数字，数量未知
    // 多组空格分隔的两个数
    public void twoNumberInLine() {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);
        }
    }
 
    // 1.2. 告知数量
    // 先输入数据个数，后面输入空格分隔的数，可换行
    public void inputNumber() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            System.out.println(a);
        }
    }
 
    // 1.3. 告知结束符
    // 输入空格分隔的数，以某个特定数结束，例如0
    public void inputEndWith() {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int a = in.nextInt();
            if (a == 0) {
                break;
            }
            System.out.println(a);
        }
    }
 
    // 1.4. 数组或链表：按行处理，每行数量不定，行数也不定，行内数字空格分隔
    // 按字符串处理，先读取一行，再按空格分隔
    public void inputNumberWithLine() {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            List<Integer> list = new ArrayList<>();
            String[] nums = in.nextLine().split(" ");
            for (String x : nums) {
                list.add(Integer.parseInt(x));
            }
            System.out.println(list.toString());
            int[] array = list.stream().mapToInt(i -> i).toArray();
        }
    }
 
    // 2. 字符串处理
 
    // 2.1. 基础字符串，空格分隔，可能有多行，每行存为一个数组
    public void inputString() {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String[] s = in.nextLine().split(" ");
            for (String str : s) {
                System.out.println(str);
            }
        }
    }
 
    // 2.2. 告知行数
    // 先输入行数，后面输入每行的字符串
    public void inputStringWithLine() {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine(); // 重要！！跳到下一行，避免读到空行
        for (int i = 0; i < n; i++) {
            String s = in.nextLine();
            System.out.println(s);
        }
    }
 
    // 3. 二叉树的输入
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int x) {
            this.val = x;
            this.left = null;
            this.right = null;
        }
    }
    /**
     * 根据数组构建二叉树
     * @param arr 树的数组表示
     * @return 构建成功后树的根节点
     */
    public TreeNode constructBinaryTree(final int[] arr) {
        // 构建和原数组相同的树节点列表
        List<TreeNode> treeNodeList = arr.length > 0 ? new ArrayList<>(arr.length) : null;
        TreeNode root = null;
        // 把输入数值数组，先转化为二叉树节点列表
        for (int i = 0; i < arr.length; i++) {
            TreeNode node = null;
            if (arr[i] != -1) { // 用 -1 表示null
                node = new TreeNode(arr[i]);
            }
            treeNodeList.add(node);
            if (i == 0) {
                root = node;
            }
        }
        // 遍历一遍，根据规则左右孩子赋值就可以了
        // 注意这里 结束规则是 i * 2 + 1 < arr.length，避免空指针
        // 为什么结束规则不能是i * 2 + 2 < arr.length呢?
        // 如果i * 2 + 2 < arr.length 是结束条件
        // 那么i * 2 + 1这个符合条件的节点就被忽略掉了
        // 例如[2,7,9,-1,1,9,6,-1,-1,10] 这样的一个二叉树,最后的10就会被忽略掉
        for (int i = 0; i * 2 + 1 < arr.length; i++) {
            TreeNode node = treeNodeList.get(i);
            if (node != null) {
                // 线性存储转连式存储关键逻辑
                node.left = treeNodeList.get(2 * i + 1);
                //  再次判断下 不忽略任何一个节点
                if(i * 2 + 2 < arr.length)
                node.right = treeNodeList.get(2 * i + 2);
            }
        }
        return root;
    }
 
 
    // 3. 输出格式化相关
 
}

// 自己写的，其中高亮行即为和普通无重复元素的二分查找不同的地方
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = binary(nums, target, true);
        int right = binary(nums, target, false) - 1;
        if (left <= right && nums[left] == target && nums[right] == target) {
            return new int[]{left, right};
        }
        else {
            return new int[]{-1, -1};
        }
    }
 
    public int binary(int[] nums, int target, boolean first_loc) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right ) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            }
            else if (first_loc && nums[mid] == target) {
                right = mid - 1;
            }
            else if (!first_loc && nums[mid] == target) {
                left = mid + 1;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
        }        
        return left;
    }
}

// 自己的
// 我这里用null来隔开每一层，这样就不用记录每一层的节点数了。
// 当然也可以记录每一层的节点数，然后用for循环来遍历每一层。
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> layer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        
        // 初始判断：树空？
        if(root != null) {
            queue.offer(root);
            queue.offer(null);  // 压入null表示隔开这一层
        }
        else return ans;
        // 遍历
        while(!queue.isEmpty()) {
            if(queue.peek() != null) {
                // 顶部非空，正在遍历这一层
                layer.add(queue.peek().val);  // 当前节点入layer
                System.out.println(layer);
                if(queue.peek().left != null) queue.offer(queue.peek().left);  // 压入左
                if(queue.peek().right != null) queue.offer(queue.peek().right);  // 压入右
                queue.poll();  // 弹出顶
            }
            else {
                // 顶部空，这一层遍历完毕
                System.out.println(layer);
                ans.add(layer);  // 当前layer入ans
                layer = new ArrayList<>();  // 当前layer清空
                queue.poll();  // 弹出空
                if(!queue.isEmpty()) queue.offer(null);
            }
        }
        return ans;
    }
}

// 代码随想录
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();
 
    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);
 
        return resList;
    }
 
    //DFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;
 
        if (resList.size() < deep) {
            //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);
 
        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }
 
    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);
 
        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();
 
            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);
 
                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }
 
            resList.add(itemList);
        }
 
    }
}

// 底数factor，指数power，模MOD
private final long MOD = (long) 1e9 + 7;
public long quickPow(long factor, long power) {
    if (power == 0) return 1;
    if (power == 1) return factor;
    long part = quickPow(factor, power / 2);
    if (power % 2 == 1) {
        return (((part % MOD) * (part % MOD)) % MOD * (factor % MOD)) % MOD;
    }
    else {
        return ((part % MOD) * (part % MOD)) % MOD;
    }
}

public class SimpleHash {
    // capacity: 哈希表的容量，哈希值将在0到capacity-1之间
    private int capacity;
    public SimpleHash(int capacity) {
        this.capacity = capacity;
    }
    public int hash(String key) {
        int hash = 0;
        int length = key.length();
        // 遍历输入字符串中的每一个字符
        for (int i = 0; i < length; i++) {
            // 将当前的哈希值乘以31（一个质数），然后加上当前字符的ASCII值，
            // 然后对capacity取模，以确保结果在0到capacity-1之间
            hash = (31 * hash + key.charAt(i)) % capacity;
        }
        return hash;
    }
}

private static int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
private static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

class Solution {
    int[] father;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        father = new int[n];
        init();
        for (int i = 0; i < edges.length; i++) {
            join(edges[i][0], edges[i][1]);
        }
 
        return isSame(source, destination);
    }
 
    // 并查集初始化
    public void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
        }
    }
 
    // 并查集里寻根的过程
    public int find(int u) {
        if (u == father[u]) {
            return u;
        } else {
            father[u] = find(father[u]);
            return father[u];
        }
    }
 
    // 判断 u 和 v是否找到同一个根
    public boolean isSame(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
 
    // 将v->u 这条边加入并查集
    public void join(int u, int v) {
        u = find(u); // 寻找u的根
        v = find(v); // 寻找v的根
        if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        // 注意以上写法不能替换为if(isSame(u, v)) return;
        // 否则可能会断开原有的连接
 
        father[v] = u;
    }
}

class Solution {
    public int minCostConnectPoints(int[][] points) {
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i <= points.length - 2; i++) {
            for (int j = i + 1; j <= points.length - 1; j++) {
                edges.add(new Edge(i, j, 
                Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1])));
            }
        }
        Collections.sort(edges, new Comparator<Edge>() {
            public int compare(Edge o1, Edge o2) {
                return o1.dis - o2.dis;
            }
        });
        int n = points.length;
        int cost = 0;
        int count = 1;
        int index = 0;
        Union un = new Union(n);
        while (count < n) {
            Edge now_edge = edges.get(index);
            if (!un.isSame(now_edge.x, now_edge.y)) {
                un.join(now_edge.x, now_edge.y);
                cost += now_edge.dis;
                count++;
            }
            index++;
        }
        return cost;
    }
}
 
class Union {
    int[] father;
    public Union(int n) {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }
    public int find(int u) {
        if (u == father[u]) return u;
        else return father[u] = find(father[u]);
    }
    public boolean isSame(int u, int v) {
        return find(u) == find(v);
    }
    public void join(int u, int v) {
        u = find(u);
        v = find(v);
        father[v] = u;
    }
}
 
class Edge {
    public int x;
    public int y;
    public int dis;
    public Edge(int x, int y, int dis) {
        this.x = x;
        this.y = y;
        this.dis = dis;
    }
    public String toString() {
        return "x: " + x + ", y: " + y + ", dis: " + dis;
    }
}

class Solution {
 
    // 和 Dijkstra 一样，堆优化都必须自定义数据结构（Java中）
    class Node implements Comparable<Node> {
        int val;
        int dis;
 
        public Node(int v, int d) {
            val = v;
            dis = d;
        }
 
        public int compareTo(Node node) {
            if (dis == node.dis) { 
                return val - node.val; // 养成习惯，不轻易定义相等
            }
            return dis - node.dis;
        }
 
    }
 
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        // 典型稠密图，邻接矩阵存图。
        // 注意，用什么存图，和是否自定义Node没有关系。取决于图的疏密程度。
        int[][] g = new int[n][n];
        for (int i = 0; i < n; i++) {
            g[i][i] = 0;
            for (int j = i + 1; j < n; j++) {
                g[i][j] = g[j][i] = Math.abs(points[i][0] - points[j][0])
                        + Math.abs(points[i][1] - points[j][1]);
            }
        }
 
        // 和最短路径一样，用这两个数据结构就够了
        int[] dis = g[0]; // 0 表示已遍历，大于0表示 距离已遍历点群的最短距离
        PriorityQueue<Node> heap = new PriorityQueue<>();
        for (int i = 1; i < n; i++) {
            heap.add(new Node(i, dis[i]));
        }
 
        // 开始遍历
        int rs = 0;
        while (!heap.isEmpty()) {
            Node node = heap.poll();
            if(dis[node.val] == 0) {
                // Java 优先队列没有删除方法，使用延迟删除：遇到遍历过的点就跳过。
                continue;
            }
            dis[node.val] = 0;
            rs += node.dis;
 
            for(int i = 0; i < dis.length; i++) {
                if(dis[i] == 0) {
                    continue;
                }
                // 新距离是到刚加入的点的距离 g[node.val][i]。
                // 如果是最短路径，还要加上 刚加入的点到起点的距离 node.val。
                int newDis = g[node.val][i]; 
                if(newDis < dis[i]) {
                    dis[i] = newDis;
                    // 更新的话，直接再存一个，反正有延迟删除
                    heap.add(new Node(i, newDis)); 
                }
            }
        }
 
        return rs;
    }
}

public class MinHeap {
    private int[] heap;
    private int size;
 
    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }
 
    // 获取父节点
    private int getParentIndex(int childIndex) {
        return (childIndex - 1) / 2;
    }
 
    // 获取左子节点
    private int getLeftChildIndex(int parentIndex) {
        return 2 * parentIndex + 1;
    }
 
    // 获取右子节点
    private int getRightChildIndex(int parentIndex) {
        return 2 * parentIndex + 2;
    }
 
    // 判断是否有父节点
    private boolean hasParent(int index) {
        return getParentIndex(index) >= 0;
    }
 
    // 判断是否有左子节点
    private boolean hasLeftChild(int index) {
        return getLeftChildIndex(index) < size;
    }
 
    // 判断是否有右子节点
    private boolean hasRightChild(int index) {
        return getRightChildIndex(index) < size;
    }
 
    // 交换两个节点
    private void swap(int indexOne, int indexTwo) {
        int temp = heap[indexOne];
        heap[indexOne] = heap[indexTwo];
        heap[indexTwo] = temp;
    }
 
    // 确保堆的性质
    private void heapifyUp() {
        int index = size - 1;
        while (hasParent(index) && heap[getParentIndex(index)] > heap[index]) {
            swap(getParentIndex(index), index);
            index = getParentIndex(index);
        }
    }
 
    // 确保堆的性质
    private void heapifyDown() {
        int index = 0;
        while (hasLeftChild(index)) {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && heap[getRightChildIndex(index)] < heap[getLeftChildIndex(index)]) {
                smallerChildIndex = getRightChildIndex(index);
            }
            if (heap[index] < heap[smallerChildIndex]) {
                break;
            } else {
                swap(index, smallerChildIndex);
            }
            index = smallerChildIndex;
        }
    }
 
    // 添加元素
    public void add(int item) {
        heap[size] = item;
        size++;
        heapifyUp();
    }
 
    // 删除元素
    public int poll() {
        if (size == 0) throw new IllegalStateException();
        int item = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return item;
    }
 
    // 查看堆顶元素
    public int peek() {
        if (size == 0) throw new IllegalStateException();
        return heap[0];
    }
}