1. 建立数组

1. 包含括号的数组

输入:[1,2,3,4,5]

// 输入字符串，去除左右括号后，在以逗号分割成字符串数组
String[] strs = sc.nextLine().replace("[", "").replace("]", "").split(",");
int[] arr = new int[strs.length];
// 把字符串注意放入整型数组中
for (int i=0; i<strs.length; i++){
   arr[i] = Integer.parseInt(strs[i]);
}

2. 不确定长度的数组

输入:1 2 3 4 5

相比于正常题目，我们不知道数组的长度，所以按照字符串输入转化处理。

// 输入字符串，去除可能的首尾多余的空格，在以逗号分割成字符串数组
String[] strs = sc.nextLine().trim().split(",");
int[] arr = new int[strs.length];
// 把字符串注意放入整型数组中
for (int i=0; i<strs.length; i++){
   arr[i] = Integer.parseInt(strs[i]);
}

2. 建立链表

1. 输入字符串

输入:
5
1 2 3 4 5
1 3

第一行输入链表的长度，第二行是值，第三行是反转区间

public static void main (String[]args){
    Scanner sc =  new Scanner(System.in);
    int len = Integer.parseInt(sc.nextLine().trim());
    // 分割字符串，转化成字符串数组
    String[] rawInput = sc.nextLine().trim().split(" ");
    // 通过迭代方法建立链表，返回头节点
    ListNode head = buildList(rawInput);
    rawInput = sc.nextLine().trim().split(" ");
    int L = Integer.parseInt(rawInput[0]);
    int R = Integer.parseInt(rawInput[1]);
    sc.close();
}

public static ListNode buildList(String[] rawInput) {
    if (rawInput == null) {
        return null;
    }
    // 设置头节点
    ListNode head = new ListNode(Integer.parseInt(rawInput[0]));
    ListNode cur = head;
    for (int i=1; i<rawInput.length; i++) {
        cur.next = new ListNode(Integer.parseInt(rawInput[i]));
        cur = cur.next;
    }
    return head;
}

3. 建立二叉树

1. 输入数字

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)
ps:节点的编号就是节点的值。

3 2
2 1 3
1 0 0
3 0 0

这种输入情况下，节点的值不可能重复的, 每个值是独一无二的几点，可以用递归建立树。

public static void main(String[] args) {
    // 输入
    Scanner sc = new Scanner(System.in);
    // 缓存数组
    int len = sc.nextInt();
    int[][] matrix = new int[len][3];
    // 头节点
    int rootValue = sc.nextInt();
    for(int i=0; i<len; i++){
        // 输入的值就是存放在第几行
        int head = sc.nextInt();
        matrix[head-1][0] = head;
        matrix[head-1][1] = sc.nextInt();
        matrix[head-1][2] = sc.nextInt();
    }
    // 输入完毕
    // sc.close();
    // 构建树
    Node root = new Node(rootValue);
    buildTree(root, matrix);
    System.out.println(process(root).maxBSTSize);
}

public static void buildTree( Node root, int[][] matrix){
    if(root == null){
        return;
    }
    int index = root.value;
    int left = matrix[index-1][1];
    int right = matrix[index-1][2];
    // 当为0时，是空节点
    if(left!=0){
        Node leftNode = new Node(left);
        root.left = leftNode;
        buildTree(leftNode, matrix);
    }
    if(right!=0){
        Node rightNode = new Node(right);
        root.right = rightNode;
        buildTree(rightNode, matrix);
    }
}

2. 从属上下级的关系

在最大派对开心值的题目中，输入描述:

第一行两个整数 n 和 root，n 表示公司的总人数，root 表示公司的老板。
第二行 n 个整数 happy_i 表示员工 i 的快乐值。
接下来 n - 1 行每行两个整数 u_i 和 v_i 表示 u_i 是 v_i 的直接上级。

3 1
5 1 1
1 2
1 3

建立员工节点，里面包括员工的下属(用动态数组表示)和他的快乐值。用一个HashMap记录每个员工的id和他自身，从bossId(1)开始累加。
剩下的数据，用来记录每个员工的下属数组。

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext()){
     // 员工数量
    int num = sc.nextInt();
    // boss的值
    int bossIndex = sc.nextInt();
    // happy值输入
    HashMap<Integer, Employee> employeeHashMap= new HashMap<>();
    for(int i=0; i<num; i++){
        int happyValue = sc.nextInt();
        Employee employ = new Employee(happyValue);
        employeeHashMap.put(bossIndex++, employ);
    }
    // 关系矩阵
    for (int i=0; i<num-1; i++){
        int upper = sc.nextInt();
        Employee boss = employeeHashMap.get(upper);
        int employ = sc.nextInt();
        boss.nexts.add(employeeHashMap.get(employ));
    }
    System.out.println(5);
    }
}

public static class Employee {
    public int happy;
    public List<Employee> nexts;
    public Employee(int h){
        this.happy = h;
        this.nexts = new ArrayList<>();
    }
}

4. 输出

1.大数取余

要求输出对10^9+7+7进行取模后的答案

不仅仅是只对最后的输出取余数，还要对计算过程中，所有的可能的大数都取余数。

5. 建立队列 和 栈

5.1 栈

java官方建立不要使用老旧的 stack类，而使用Deque类去取代它

Deque<TreeNode> stack = new ArrayDeque<>();
// 压入
stack.push(cur);
// 弹出
cur = stack.pop();
// 栈顶元素
cur = stack.peek();

5.2 队列

队列操作，选择返回false or null的offer, poll, peek

Queue<String> queue = new LinkedList<String>();
// 入队
queue.offer();
// 出队
queue.poll();
// 队首
queue.peek();

6. 比较器

建立比较器的方法有很多种，这里依次总结如下:
1.Comparable接口与Comparator接口参考资料skywang12345和Java Zone

Comparable接口

Comparable 是排序接口。

若一个类实现了Comparable接口，就意味着“该类支持排序”。 即然实现Comparable接口的类支持排序，假设现在存在“实现Comparable接口的类的对象的List列表(或数组)”，则该List列表(或数组)可以通过 Collections.sort（或 Arrays.sort）进行排序。

此外，“实现Comparable接口的类的对象”可以用作“有序映射(如TreeMap)”中的键或“有序集合(TreeSet)”中的元素，而不需要指定比较器。

/*
说明：
(01) Person类代表一个人，Persong类中有两个属性：age(年纪) 和 name“人名”。
(02) Person类实现了Comparable接口，因此它能被排序。
*/
private static class Person implements Comparable<Person>{
    int age;
    String name;

        ...

    /** 
     * @desc 实现 “Comparable<String>” 的接口，即重写compareTo<T t>函数。
     *  这里是通过“person的名字”进行比较的
     */
    @Override
    public int compareTo(Person person) {
        return name.compareTo(person.name);
        //return this.name - person.name;
    }   
}

// 在main函数中创建Person的List数组(list)，然后我们通过Collections的sort()函数，对list进行排序。
// 新建ArrayList(动态数组)
ArrayList<Person> list = new ArrayList<Person>();
// 添加对象到ArrayList中
list.add(new Person("ccc", 20));
list.add(new Person("AAA", 30));
list.add(new Person("bbb", 10));
list.add(new Person("ddd", 40));

Collections.sort(list);

Comparator接口

实现接口Comparator<>中compare(object o1, object o2)方法。
其中compare(object o1, object o2)方法，若返回-1，则表示不交换位置，1表示交换位置，0表示什么都不做

a) 升序 ascending [1 2 3 4 5]

public static class AscendingComp implements Comparator<Student>{

    @Override
    public int compare(Student o1, Student o2) {
        // 小的在前面，大的在后面
        return o1.note - o2.note;
    }
}

b) 降序 descending [5 4 3 2 1]

// 降序
public static class DescendingComp implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2) {
        // 大的在前面，小的在后面
        return o2.note - o1.note ;
    }
}

c)调用

Arrays.sort(arr, new DescendingComp());
Arrays.sort(arr, new AscendingComp());

对比后发现，Comparable是排序接口；若一个类实现了Comparable接口，就意味着“该类支持排序”。
而Comparator是比较器；我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。

我们不难发现：Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

匿名内部类

在上个方法中，我们专门创造了两个类分别去实现Comparator接口，但是如果这个类只用一次，就没要必要去创建它，这里就可以用到匿名内部类，它通常用来简化代码编写。

// 按照学生id的升序排列
Arrays.sort(students, new Comparator<Student>(){// 接口名字

    @Override
    public int compare(Student o1, Student o2) { //方法名字
        return o1.id - o2.id;
    }

});

// 也可以写成, 省略了之前实现接口的类的创建
Comparator<Student> AgeAscendingComparator = new Comparator<Student>(){

    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age;
    }

};   
Arrays.sort(students, AgeAscendingComparator);     

lambda表达式

lambda表达式有着函数式编程语言的思想，参考资料 和 zch

// 非常简练，大大简化编写
Arrays.sort(students, (o1, o2)->o1.id - o2.id);

6.1 大根堆

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new DescendingComparator());

6.2 小根堆

PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new AscendingComparator());

7. 建立容器

通过多次的做题发现，对于不定长度的容器来说，ArrayList实现的接口比LinkedList在各个方面的性能都要好的多！