Skip to content

Commit 8d26585

Browse files
algorithmzuoalgorithmzuo
committed
modify code
1 parent 63cbb10 commit 8d26585

6 files changed

Lines changed: 181 additions & 132 deletions

‎src/class06/Code01_MergeKSortedLists.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ public static class ListNodeComparator implements Comparator<ListNode> {
1515

1616
@Override
1717
public int compare(ListNode o1, ListNode o2) {
18-
return o1.val - o2.val;
18+
return o1.val - o2.val;
1919
}
2020

2121
}

‎src/class06/Code02_SameTree.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@ public static boolean isSameTree(TreeNode p, TreeNode q) {
1616
if (p == null && q == null) {
1717
return true;
1818
}
19+
// 都不为空
1920
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
2021
}
2122

‎src/class06/Code04_MaximumDepthOfBinaryTree.java‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ public static class TreeNode {
99
public TreeNode right;
1010
}
1111

12+
// 以root为头的树，最大高度是多少返回！
1213
public static int maxDepth(TreeNode root) {
1314
if (root == null) {
1415
return 0;

‎src/class06/Code05_ConstructBinaryTreeFromPreorderAndInorderTraversal.java‎

Lines changed: 41 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -15,26 +15,57 @@ public static class TreeNode {
1515
}
1616
}
1717

18-
public static TreeNode buildTree(int[] preorder, int[] inorder) {
19-
HashMap<Integer, Integer> inMap = new HashMap<>();
20-
for (int i = 0; i < inorder.length; i++) {
21-
inMap.put(inorder[i], i);
18+
public static TreeNode buildTree1(int[] pre, int[] in) {
19+
if (pre == null || in == null || pre.length != in.length) {
20+
return null;
21+
}
22+
return f(pre, 0, pre.length - 1, in, 0, in.length - 1);
23+
}
24+
25+
// 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]
26+
// 请建出整棵树返回头节点
27+
public static TreeNode f(int[] pre, int L1, int R1, int[] in, int L2, int R2) {
28+
if (L1 > R1) {
29+
return null;
30+
}
31+
TreeNode head = new TreeNode(pre[L1]);
32+
if (L1 == R1) {
33+
return head;
34+
}
35+
int find = L2;
36+
while (in[find] != pre[L1]) {
37+
find++;
38+
}
39+
head.left = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
40+
head.right = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
41+
return head;
42+
}
43+
44+
public static TreeNode buildTree2(int[] pre, int[] in) {
45+
if (pre == null || in == null || pre.length != in.length) {
46+
return null;
47+
}
48+
HashMap<Integer, Integer> valueIndexMap = new HashMap<>();
49+
for (int i = 0; i < in.length; i++) {
50+
valueIndexMap.put(in[i], i);
2251
}
23-
return process(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
52+
return g(pre, 0, pre.length - 1, in, 0, in.length - 1, valueIndexMap);
2453
}
2554

26-
public static TreeNode process(int[] pre, int L1, int R1, int[] in, int L2, int R2,
27-
HashMap<Integer, Integer> inMap) {
55+
// 有一棵树，先序结果是pre[L1...R1]，中序结果是in[L2...R2]
56+
// 请建出整棵树返回头节点
57+
public static TreeNode g(int[] pre, int L1, int R1, int[] in, int L2, int R2,
58+
HashMap<Integer, Integer> valueIndexMap) {
2859
if (L1 > R1) {
2960
return null;
3061
}
3162
TreeNode head = new TreeNode(pre[L1]);
3263
if (L1 == R1) {
3364
return head;
3465
}
35-
int find = inMap.get(pre[L1]);
36-
head.left = process(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, inMap);
37-
head.right = process(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, inMap);
66+
int find = valueIndexMap.get(pre[L1]);
67+
head.left = g(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, valueIndexMap);
68+
head.right = g(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, valueIndexMap);
3869
return head;
3970
}
4071

‎src/class06/ShowComparator.java‎

Lines changed: 59 additions & 121 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,6 @@
33
import java.util.ArrayList;
44
import java.util.Arrays;
55
import java.util.Comparator;
6-
import java.util.TreeMap;
76

87
public class ShowComparator {
98

@@ -19,148 +18,87 @@ public Student(String name, int id, int age) {
1918
}
2019
}
2120

22-
// 任何比较器：
23-
// compare方法里，遵循一个统一的规范：
24-
// 返回负数的时候，认为第一个参数应该排在前面
25-
// 返回正数的时候，认为第二个参数应该排在前面
26-
// 返回0的时候，认为无所谓谁放前面
27-
public static class IdShengAgeJiangOrder implements Comparator<Student> {
21+
// 谁id大，谁放前！
22+
public static class IdComparator implements Comparator<Student> {
2823

29-
// 根据id从小到大，但是如果id一样，按照年龄从大到小
24+
// 如果返回负数，认为第一个参数应该排在前面
25+
// 如果返回正数，认为第二个参数应该排在前面
26+
// 如果返回0，认为谁放前面无所谓
3027
@Override
3128
public int compare(Student o1, Student o2) {
32-
return o1.id != o2.id ? (o1.id - o2.id) : (o2.age - o1.age);
29+
if (o1.id < o2.id) {
30+
return 1;
31+
} else if (o2.id < o1.id) {
32+
return -1;
33+
} else {
34+
return 0;
35+
}
3336
}
34-
35-
}
36-
37-
public static class IdAscendingComparator implements Comparator<Student> {
38-
39-
// 返回负数的时候，第一个参数排在前面
40-
// 返回正数的时候，第二个参数排在前面
41-
// 返回0的时候，谁在前面无所谓
42-
@Override
43-
public int compare(Student o1, Student o2) {
44-
return o1.id - o2.id;
45-
}
46-
47-
}
48-
49-
public static class IdDescendingComparator implements Comparator<Student> {
50-
51-
@Override
52-
public int compare(Student o1, Student o2) {
53-
return o2.id - o1.id;
54-
}
55-
5637
}
38+
39+
// 谁age大，谁放前！
40+
public static class AgeComparator implements Comparator<Student> {
5741

58-
// 先按照id排序，id小的，放前面；
59-
// id一样，age大的，前面；
60-
public static class IdInAgeDe implements Comparator<Student> {
61-
42+
// 如果返回负数，认为第一个参数应该排在前面
43+
// 如果返回正数，认为第二个参数应该排在前面
44+
// 如果返回0，认为谁放前面无所谓
6245
@Override
6346
public int compare(Student o1, Student o2) {
64-
return o1.id != o2.id ? o1.id - o2.id : (o2.age - o1.age);
65-
}
66-
67-
}
68-
69-
public static void printStudents(Student[] students) {
70-
for (Student student : students) {
71-
System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
47+
if (o1.age < o2.age) {
48+
return 1;
49+
} else if (o2.age < o1.age) {
50+
return -1;
51+
} else {
52+
return 0;
53+
}
7254
}
7355
}
7456

75-
public static void printArray(Integer[] arr) {
76-
if (arr == null) {
77-
return;
78-
}
57+
public static void printArray(int[] arr) {
7958
for (int i = 0; i < arr.length; i++) {
8059
System.out.print(arr[i] + " ");
8160
}
8261
System.out.println();
8362
}
8463

85-
public static class MyComp implements Comparator<Integer> {
86-
87-
@Override
88-
public int compare(Integer o1, Integer o2) {
89-
return o2 - o1;
90-
}
91-
92-
}
93-
94-
public static class AComp implements Comparator<Integer> {
95-
96-
// 如果返回负数，认为第一个参数应该拍在前面
97-
// 如果返回正数，认为第二个参数应该拍在前面
98-
// 如果返回0，认为谁放前面都行
99-
@Override
100-
public int compare(Integer arg0, Integer arg1) {
101-
102-
return arg1 - arg0;
103-
104-
// return 0;
64+
public static void printStudents(Student[] students) {
65+
for (int i = 0; i < students.length; i++) {
66+
System.out.println(students[i].name + ", " + students[i].id + ", " + students[i].age);
10567
}
106-
10768
}
10869

10970
public static void main(String[] args) {
110-
111-
Integer[] arr = { 5, 4, 3, 2, 7, 9, 1, 0 };
112-
113-
Arrays.sort(arr, new AComp());
114-
115-
for (int i = 0; i < arr.length; i++) {
116-
System.out.println(arr[i]);
117-
}
118-
119-
System.out.println("===========================");
120-
121-
Student student1 = new Student("A", 4, 40);
122-
Student student2 = new Student("B", 4, 21);
123-
Student student3 = new Student("C", 3, 12);
124-
Student student4 = new Student("D", 3, 62);
125-
Student student5 = new Student("E", 3, 42);
126-
// D E C A B
127-
128-
Student[] students = new Student[] { student1, student2, student3, student4, student5 };
129-
System.out.println("第一条打印");
130-
131-
Arrays.sort(students, new IdShengAgeJiangOrder());
132-
for (int i = 0; i < students.length; i++) {
133-
Student s = students[i];
134-
System.out.println(s.name + "," + s.id + "," + s.age);
135-
}
136-
137-
System.out.println("第二条打印");
138-
ArrayList<Student> studentList = new ArrayList<>();
139-
studentList.add(student1);
140-
studentList.add(student2);
141-
studentList.add(student3);
142-
studentList.add(student4);
143-
studentList.add(student5);
144-
studentList.sort(new IdShengAgeJiangOrder());
145-
for (int i = 0; i < studentList.size(); i++) {
146-
Student s = studentList.get(i);
147-
System.out.println(s.name + "," + s.id + "," + s.age);
71+
int[] arr = { 8, 1, 4, 1, 6, 8, 4, 1, 5, 8, 2, 3, 0 };
72+
printArray(arr);
73+
Arrays.sort(arr);
74+
printArray(arr);
75+
76+
Student s1 = new Student("张三", 5, 27);
77+
Student s2 = new Student("李四", 1, 17);
78+
Student s3 = new Student("王五", 4, 29);
79+
Student s4 = new Student("赵六", 3, 9);
80+
Student s5 = new Student("左七", 2, 34);
81+
82+
Student[] students = { s1, s2, s3, s4, s5 };
83+
printStudents(students);
84+
System.out.println("=======");
85+
Arrays.sort(students, new IdComparator());
86+
printStudents(students);
87+
System.out.println("=======");
88+
89+
ArrayList<Student> arrList = new ArrayList<>();
90+
arrList.add(s1);
91+
arrList.add(s2);
92+
arrList.add(s3);
93+
arrList.add(s4);
94+
arrList.add(s5);
95+
for (Student s : arrList) {
96+
System.out.println(s.name + ", " + s.id + ", " + s.age);
14897
}
149-
// N * logN
150-
System.out.println("第三条打印");
151-
student1 = new Student("A", 4, 40);
152-
student2 = new Student("B", 4, 21);
153-
student3 = new Student("C", 4, 12);
154-
student4 = new Student("D", 4, 62);
155-
student5 = new Student("E", 4, 42);
156-
TreeMap<Student, String> treeMap = new TreeMap<>((a, b) -> (a.id - b.id));
157-
treeMap.put(student1, "我是学生1，我的名字叫A");
158-
treeMap.put(student2, "我是学生2，我的名字叫B");
159-
treeMap.put(student3, "我是学生3，我的名字叫C");
160-
treeMap.put(student4, "我是学生4，我的名字叫D");
161-
treeMap.put(student5, "我是学生5，我的名字叫E");
162-
for (Student s : treeMap.keySet()) {
163-
System.out.println(s.name + "," + s.id + "," + s.age);
98+
System.out.println("=======");
99+
arrList.sort(new AgeComparator());
100+
for (Student s : arrList) {
101+
System.out.println(s.name + ", " + s.id + ", " + s.age);
164102
}
165103

166104
}

‎src/class06/ShowComparator2.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package class06;
2+
3+
import java.util.Comparator;
4+
import java.util.PriorityQueue;
5+
6+
public class ShowComparator2 {
7+
8+
public static class MyComparator implements Comparator<Integer> {
9+
10+
// 负，第一个参数在前
11+
// 正，第二个参数在前
12+
// 0, 谁放前都行
13+
@Override
14+
public int compare(Integer o1, Integer o2) {
15+
if (o1 < o2) {
16+
return 1;
17+
} else if (o1 > o2) {
18+
return -1;
19+
} else {
20+
return 0;
21+
}
22+
}
23+
24+
}
25+
26+
public static class Student {
27+
public String name;
28+
public int id;
29+
public int age;
30+
31+
public Student(String name, int id, int age) {
32+
this.name = name;
33+
this.id = id;
34+
this.age = age;
35+
}
36+
}
37+
38+
// 谁id大，谁放前！
39+
public static class IdComparator implements Comparator<Student> {
40+
41+
// 如果返回负数，认为第一个参数应该排在前面
42+
// 如果返回正数，认为第二个参数应该排在前面
43+
// 如果返回0，认为谁放前面无所谓
44+
@Override
45+
public int compare(Student o1, Student o2) {
46+
if (o1.id < o2.id) {
47+
return 1;
48+
} else if (o2.id < o1.id) {
49+
return -1;
50+
} else {
51+
return 0;
52+
}
53+
}
54+
}
55+
56+
public static void main(String[] args) {
57+
String str1 = "abc";
58+
String str2 = "b";
59+
System.out.println(str1.compareTo(str2));
60+
PriorityQueue<Student> heap = new PriorityQueue<>(new IdComparator());
61+
Student s1 = new Student("张三", 5, 27);
62+
Student s2 = new Student("李四", 1, 17);
63+
Student s3 = new Student("王五", 4, 29);
64+
Student s4 = new Student("赵六", 3, 9);
65+
Student s5 = new Student("左七", 2, 34);
66+
heap.add(s1);
67+
heap.add(s2);
68+
heap.add(s3);
69+
heap.add(s4);
70+
heap.add(s5);
71+
System.out.println("=========");
72+
while (!heap.isEmpty()) {
73+
Student s = heap.poll();
74+
System.out.println(s.name + ", " + s.id + ", " + s.age);
75+
}
76+
}
77+
78+
}

0 commit comments

Comments
 (0)