牛客网算法——名企高频面试题143题（3）

给定一棵树，求出这棵树的直径，即树上最远两点的距离。示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11

543. 二叉树的直径

package 复现代码;

/**
 * @Classname 二叉树的直径
 * @Description TODO
 * @Date 2020/12/8 16:09
 * @Created by xjl
 */
public class 二叉树的直径 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    //表示二叉数据的直径
    int dis = 1;

    /**
     * @description TODO 表示的是的二叉树的直径
     * @param: root
     * @date: 2020/12/8 16:10
     * @return: int
     * @author: xjl
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        deepth(root);
        return dis - 1;
    }

    private int deepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = deepth(root.left);
        int right = deepth(root.right);
        dis = Math.max(dis, left + right + 1);
        return Math.max(left, right) + 1;
    }

}

剑指 Offer 55 - I. 二叉树的深度

package 复现代码;

/**
 * @Classname 二叉树的直径
 * @Description TODO
 * @Date 2020/12/8 16:09
 * @Created by xjl
 */
public class 二叉树的直径 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    //表示二叉数据的直径 表示的是如果存在话至少1的
    int dis = 1;

    /**
     * @description TODO 表示的是的二叉树的直径
     * @param: root
     * @date: 2020/12/8 16:10
     * @return: int
     * @author: xjl
     */
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        deepth(root);
        return dis-1;
    }

    private int deepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = deepth(root.left);
        int right = deepth(root.right);
        dis = Math.max(dis, left + right + 1);
        return Math.max(left, right) + 1;
    }
}

题目描述

有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。 [要求] 1. 如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。

2. 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)

 

每行有一个整数opt表示操作类型

若opt=1，则接下来有一个整数N表示将N加入到结构中。 若opt=2，则表示询问当前所有数的中位数

package 名企高频面试题143;

import org.junit.Test;

import java.util.*;

/**
 * @Classname 随机找到数据流中位数
 * @Description TODO
 * @Date 2020/12/8 16:30
 * @Created by xjl
 */
public class 随机找到数据流中位数 {

    public double[] flowmedian(int[][] operations) {
        ArrayList result = new ArrayList();
        ArrayList list = new ArrayList();
        for (int[] arr : operations) {
            if (arr[0] == 1) {
                //存元素
                list.add(arr[1]);
            } else {
                Collections.sort(list);
                if (list.size() == 0) {
                    result.add((double) -1);
                    continue;
                }
                if (list.size() % 2 != 0) {
                    result.add((double) list.get(list.size() / 2));
                } else {
                    result.add((double) (list.get(list.size() / 2 - 1) + list.get(list.size() / 2)) / 2);
                }
            }
        }
        return result.stream().mapToDouble(Double::valueOf).toArray();
    }

    @Test
    public void test() {
        //{{1, 5}, {2}, {1, 3}, {2}, {1, 6}, {2}, {1, 7}, {2}}  {{2}, {1, 1}, {2}}
        double[] flowmedian = flowmedian1(new int[][]{{1, 5}, {2}, {1, 3}, {2}, {1, 6}, {2}, {1, 7}, {2}});
        for (double a : flowmedian) {
            System.out.println(a);
        }
    }

    /**
     * @description TODO 采用的是大跟堆和小根堆
     * @param: operations
     * @date: 2020/12/8 19:04
     * @return: double[]
     * @author: xjl
     */
    public double[] flowmedian1(int[][] operations) {
        int sum = 0;
        PriorityQueue queMax = new PriorityQueue((o1, o2) -> {
            return o2 - o1;
        });
        PriorityQueue queMin = new PriorityQueue((o1, o2) -> (o1 - o2));
        List resD = new ArrayList();

        for (int i = 0; i < operations.length; i++) {
            if (operations[i][0] == 1) {
                //插入
                int number = operations[i][1];
                sum++;
                queMax.add(number);
                queMin.add(queMax.poll());
                if (sum % 2 == 1) {
                    queMax.add(queMin.poll());
                }
            } else {
                //查找
                if (sum == 0) {
                    resD.add((double) -1);
                } else {
                    if (sum % 2 == 1) {
                        //res.add((double)-1);
                        double dt = queMax.peek();
                        resD.add(dt);
                    } else {
                        //res.add(getMidNum(temD));
                        double dt = (queMax.peek() + queMin.peek()) / 2.0;
                        resD.add(dt);
                    }
                }

            }
        }
        double[] res = new double[resD.size()];
        for (int i = 0; i < resD.size(); i++) {
            res[i] = resD.get(i);
        }
        return res;
    }
}