左神算法新手班课程学习笔记06
纳西妲首席爹粉
2023-01-10 22:33
阅读1900
#算法#
//++++++++++++++++++++++++++++++++++++++++++++++
06 比较器、优先级队列、二叉树
内容：
比较器
对自己定义的对象进行排序。需要自己定义比较器，才可以调用系统排序对自己创建的对象进行排序。
//谁id小，谁放前面
public static class IdComparator implements Comparator<Student>{
//如果返回负数，认为第一个参数应该排在前面
//如果返回正数，认为第二个参数应该排前面
//如果返回0，认为谁放前面无所谓
public int compara(Student o1, student o2){
if(o1.id < o2.id){
return -1;
}else if(o2.id < o1.id){
return 1;
}else{
return 0;
}
}
}
}
//利用系统排序
Arrays.sort(students, new IdComparator());
优先级队列
//根据入队列的值进行排序，logN级别
//PriorityQueue 小根堆
//如何实现大根堆，自己写比较器
public static class MyComparator implements Comparator<Integer>{
//负值，第一个参数在前
//正值，第二个参数在前
//0，谁放前面都行
if(o1 > o2){
return -1;
}else if(o1 < o2){
return 1;
}else{
return 0;
}
}
//使用方式如下:
PriorityQueue<Integer> heap = new PriorityQueue<>(new MyComparator( ))
二叉树的基本遍历
//先序遍历
public static void pre(Node head){
if(head == null){
return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
//中序遍历
public static void in(Node head){
if(head == null){
return;
}
in(head.left);
System.out.println(head.value);
in(head.right);
}
//后序遍历
public static void pos(Node head){
if(head == null){
return;
}
pos(head.left);
pos(head.right);
System.out.println(head.value);
}
二叉树的递归套路
先序遍历、中序遍历、后序遍历都是递归序列的变种。
题目：
补充了一个链表的题目
1. 合并多个有序链表
Leetcode原题，https://leetcode.com/problems/merge-k-sorted-lists
public static class ListNodeComparator implements Comparator<ListNode>{
public int compara(ListNode o1, ListNode o2){
return o1.val - o2.val;
}
}
public static ListNode mergeKLists(ListNode[] list){
if(list == null){
return null;
}
PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
for(int i = 0; i < lists.length; i++){
if(lists[i] != null){
heap.add(list[i]);
}
}
if(heap.isEmpty()){
return null;
}
//先弹出一个最小值
ListNode head = heap.poll();
ListNode pre = head;
//如果弹出来的值的下一个值非空的话，就加入优先队列中去
if(pre.next != null){
heap.add(pre.next);
}
//在优先队列全空之前，进行以下操作：把从优先队列中弹出来的一个数先赋值给当前节点，pre的指针指向当前节点。 当前节点赋值给pre。如果cur的下一个值非空的话，就加如到优先队列里去。
while(!heap.isEmpty()){
ListNode cur = heap.poll();
pre.next = cur;
pre = cur;
if(cur.next != next){
heap.add(cur.next);
}
}
}
2. 判断两颗树是否结构相同
Leetcode原题，https://leetcode.com/problems/same-tree
public static boolean isSameTree(TreeNode p, TreeNode q){
//如果当p和q之中任意一个为空另一个不为空时，返回false;
if(p == null ^ q == null){
return false;
}
//如果q和p都为空时，两个空树是相同的。
if(p == null && q == null){
return true;
}
/*只有同时满足下列三个条件时，两棵树的结构才相等：
1.p和q的值相等
2. p的左子树和q的左子树结构相同
3. p的右子树与q的右子树结构相同
*/
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right,q.right);
}
3. 判断一棵树是否是镜面树
Leetcode原题，https://leetcode.com/problems/symmetric-tree
public boolean isSymmetric(TreeNode root) {
return isMirror(root,root);
}
public boolean isMirror(TreeNode p,TreeNode q){
if(p == null ^ q == null){
return false;
}
if(p == null && q == null){
return true;
}
return p.val == q.val && isMirror(p.left,q.right) && isMirror(p.right, q.left);
}
4. 返回一棵树的最大深度
Leetcode原题，https://leetcode.com/problems/maximum-depth-of-binary-tree
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
5. 用先序数组和中序数组重建一棵树
Leetcode原题，https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null || preorder.length != inorder.length){
return null;
}
return f(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
public static TreeNode f(int[] pre, int L1,int R1,int[] in,int L2,int R2){
if(L1 > R1){
return null;
}
TreeNode head = new TreeNode(pre[L1]);
if(L1 == R1){
return head;
}
int find = L2;
while(in[find] != pre[L1]){
find++;
}
head.left = f(pre,L1+1,L1+find-L2,in,L2,find-1);
head.right = f(pre,L1+find-L2+1,R1,in,find+1,R2);
return head;
}
通过携带存储数据的中序序列的哈希表，减少遍历的时间。空间换时间
用code展示比较器的使用
二叉树先序、中序、后序遍历的代码实现、介绍递归序
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
