输入输出IO模版总结
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或者null | offer | poll | peek |
| 抛出异常 | add | remove | element |
队列操作，选择返回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在各个方面的性能都要好的多！
