分类标签归档：Java算法
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
利用大根堆存放较小的一半元素，小根堆存放较大的一半元素。维持大小堆的元素个数差不超过 1。
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* @author bingo
* @since 2018/12/...输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
由于是二叉搜索树，因此中序遍历的结果就是排序的。
中序遍历利用栈来实现。遍历时，前一个结点的 right 指向后一个结点，后一个结点的 left 指向前一个结点。
pre.right = cur
cur.left = pre
import java.util.Stack;
/**
* @author bingo
* @since 2018/11/24
*/
/**
public class TreeNode {
int val = 0;
T...数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组 {1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。
利用快排中的 partition 思想。
数组中有一个数字出现次数超过了数组长度的一半，那么排序后，数组中间的数字一定就是我们要找的数字。我们随机选一个数字，利用 partition() 函数，使得比选中数字小的数字都排在它左边，比选中数字大的数字都排在它的右边。
判断选中数字的下标 index：
index = n/2，那么这个...输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
第一步，在每个节点的后面插入复制的节点；
第二步，对复制节点的 random 链接进行赋值；
第三步，分离两个链表。
/**
* @author bingo
* @since 2018/11/24
*/
/*
public class RandomListNode {
int label;
RandomListNod...输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
import java.util.ArrayList;
/**
* @author bingo
* @since 2018/11/23
*/
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int...请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
如二叉树：
1
/ \
2 3
/ \ / \
4 5 6 7打印结果为：
1
3 2
4 5 6 7对于上述二叉树：
首先访问根结点，之后把2、3存入某结构。打印的时候，先打印3、2。这不就是栈？
依次弹出栈元素，分别是3、2。弹出时需要把3、2的子结点存入结构。由于访问时顺序是4 5 6 7。所以也需要用栈来存放。而且，此时需要先存...
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
序列的最后一个元素是二叉搜索树的根节点。
在序列中从左到右找到根节点的左子树(比根节点小)、右子树(比根节点大)。
/**
* @author bingo
* @since 2018/11/23
*/
public class Solution {
/**
* 判断数组是否是某个二叉搜索树的后序遍历序列
*
*...从上往下打印出二叉树的每个节点，同层节点从左至右打印。
先将根节点进入队列。
队头元素出队，将值存入 list，判断该元素是否有左/右子树，有的话依次进入队列中。队列为空时结束。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author bingo
* @since 2018/11/23
*/
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
Tre...从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
与上一题类似，只不过需要用变量记录每一层要打印多少个节点。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author bingo
* @since 2018/11/23
*/
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
...定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。
定义两个stack。
压栈时，先将元素node压入stack1。然后判断stack2的情况：
stack2栈为空或者栈顶元素大于node，则将node压入stack2中。stack2栈不为空且栈定元素小于node，则重复压入栈顶元素。获取最小元素时，从stack2中获取栈顶元素即可。
import java.util.Stack;
/**
* @author bingo
* @since 2018/11/22
*/
public class Solu...