传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可，但是因为数组在不断增长， 每增长一位便排一次，很浪费时间，于是可以考虑在增加数据的同时将其有序化，这个过程就让我们想到了插入排序：遍历后续数组每个元素时将它插入前面排好序的部分的相应位置。 step 1：用一数组存储输入的数据流。 step 2：Insert函数在插入的同时，遍历之前存储在数组中的数据，按照递增顺序依次插入，如此一来，加入的数据流便是有序的。 step 3：GetMedian函数可以根据下标直接访问中位数，分为数组为奇数个元素和偶数个元素两种情况。记得需要类型转换为double。 private ArrayL...

快速排序：每次移动，可以找到一个标杆元素，然后将大于它的移到左边，小于它的移到右边。然后分别对左边和右边进行排序，不断划分左右子段，直到整个数组有序。放到这道题中，如果标杆元素左边刚好有K-1个比它大的，那么该元素就是第K大，如果它左边的元素比K - 1多，说明第K大在其左边，直接二分，不用管标杆元素右边，同理如果它左边的元素比K-1少，那第K大在其右边，左边不用管。 step 1：进行一次快排，大元素在左，小元素在右，得到的中轴p点。 step 2：如果 p - low + 1 = k ，那么p点就是第K大。 step 3：如果 p - low + 1 > k，则第k大的元素在左半段，...

注意写法必须先后在前，不然不对。 public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { if(k==0) return new ArrayList<Integer>(); quicksort(input,0,input.length-1); ArrayList<Integer> list=new ArrayList<Integer>(); for (int i=0;i<k;i++)...

public boolean isValid (String s) { // write code here Stack<Character> stack=new Stack<Character>(); for (int i=0;i<s.length();i++){ if(s.charAt(i)=='(') stack.push(')'); else if(s.charAt(i)=='[') stack.push(']'); else if(s.char...

public class Solution { Stack<Integer> stack1=new Stack<Integer>(); Stack<Integer> stack2=new Stack<Integer>(); public void push(int node) { if(stack2.isEmpty()){ stack1.push(node); stack2.push(node); }else { st...

public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack2.push(node); } public int pop() { if(stack1.isEmpty()){ while (!stack2.isEm...

菜到了天际。

日常看不懂系列 public TreeNode buildTree(int[] xianxu,int l1,int r1,int[] zhongxu,int l2,int r2){ if(l1>r1||l2>r2){ return null; } TreeNode root=new TreeNode(xianxu[l1]); int rootIndex=0; for (int i=l2;i<=r2;i++){ if(zhongxu[i]==xianxu[...

递归。 public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { int m= pre.length; int n= vin.length; if(m==0||n==0) return null; TreeNode root=new TreeNode(pre[0]); for (int i=0;i<vin.length;i++){ if(pre[0]==vin[i]){ root.left=reCo...

依旧采用通用的解法。 public int lowestCommonAncestor (TreeNode root, int o1, int o2) { // write code here TreeNode node=dfs(root,o1,o2); return node.val; } public TreeNode dfs(TreeNode root,int p,int q){ if(root==null||root.val==p||root.val==q) return root; Tre...

第一种为通用一些的解法。 public int lowestCommonAncestor (TreeNode root, int p, int q) { // write code here TreeNode node=dfs(root,p,q); return node.val; } public TreeNode dfs(TreeNode root,int p,int q){ if(root==null||root.val==p||root.val==q) return root; TreeNo...

此题由题意进行递归判断，即树的高度差不超过1，并且左右两边均为平衡二叉树。 二叉搜索树：左<根<右 完全二叉树：除最后一层外其他层节点均是满节点，最后一层如果不满也必须靠左。 平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

层次遍历，最后加条件判断即可。 public boolean isCompleteTree (TreeNode root) { if(root==null) return true; Deque<TreeNode> queue=new LinkedList<TreeNode>(); boolean flag=false; queue.add(root); while (!queue.isEmpty()){ TreeNode node=queue.poll(); ...

递归判断 public boolean isValidBST (TreeNode root) { // write code here return dfs(root,Integer.MIN_VALUE,Integer.MAX_VALUE); } public boolean dfs(TreeNode root,int l,int r){ if(root==null) return true; if(root.val<l||root.val>r) return false; ...