static boolean find(int target, int [][] array) {
  int rowLength = array.length;//总行数
  int colLength = array[0].length;//总列数
  int currentRow = 0;//起始遍历位置是右上角，行号为0
  int currentCol = colLength - 1;//起始遍历位置是右上角，列号为最大值
  while (currentRow <rowLength && currentCol >= 0) {//防止超出边界
    if (array[currentRow][currentCol] == target) {
      return true;
    } else if (array[currentRow][currentCol]  > target) {//比要找的数大，那么排除更大的数，也就是排除这一列
      currentCol--;
    } else {//比要找的数小，那么排除更小的数，也就是排除这一行
      currentRow++;
    }
  }
  return false;
}

String replaceSpace(StringBuffer str) {
        int number = 0;//空格数目
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                number++;
            }
        }
        int oldLength = str.length();
        int newLength = str.length()+ 2*number;
        str.setLength(newLength);
        int tempIndex = newLength - 1;//新字符串正在的位置
        for (int i = oldLength-1; i >=0; i--) {//遍历
            if (str.charAt(i) != ' ') {
                str.setCharAt(tempIndex, str.charAt(i));
                tempIndex--;
            } else {
                str.setCharAt(tempIndex, '0');
                str.setCharAt(tempIndex-1, '2');
                str.setCharAt(tempIndex-2, '%');
                tempIndex = tempIndex - 3;
            }
        }
        return str.toString();
}

ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null ){
                return list;
        }
        printListFromTailToHead(listNode.next);
        list.add(listNode.val);
        return list;
}

public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return reConstructBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);
    }
    public static TreeNode reConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode treeNode = new TreeNode(pre[preStart]);
        for (int i = inStart; i <= inEnd; i++) {
            if (in[i] == pre[preStart]) {
                int leftLength = i - inStart;//左子树长度
                treeNode.left = reConstructBinaryTree(pre, preStart + 1, preStart+leftLength, in, inStart, i-1);
                treeNode.right = reConstructBinaryTree(pre, preStart +leftLength+1, preEnd, in, i+1, inEnd);
               break;
            }
        }
        return treeNode;
    }

Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(Integer number) {
        stack1.push(number);
    }
    public Integer pop() {
        if (stack2.size()>0) {
            return stack2.pop();
        }else if (stack1.size()>=0) {
            while (stack1.size()>0) {
                Integer temp = stack1.pop();
                stack2.push(temp);
            }
            return stack2.pop();
        }
        return null;
    }

int minNumberInRotateArray(int[] array) {
        if (array[0]<array[array.length-1]){//当前就是一个递增的情况
            return array[0];
        }
        int start = 0;
        int end = array.length-1;
        int mid = 0;
        while (array[start] >= array[end]) {
            System.out.println(start+"======"+mid+"====="+end);
            if (end-start == 1) {
                return array[end];
            }
            mid = (end + start)/2;
            if (array[start] == array[mid] && array[start] == array[end]) {//左边界，中间值，右边界相等
                int min = array[start];
                for (int i = start+1; i <=end ; i++) {
                    if (array[i]< min) {
                        min = array[i];
                    }
                }
                return min;
            }
            if ( array[mid]>=array[start]){//左半部分是递增的，那么就去掉左半部分
                start = mid;
            } else if(array[mid]<=array[end]) {//右半部分是递增的，那么就去掉右半部分
                end = mid;
            }
        }
        return array[mid];
    }

int Fibonacci(int n) {
    if (n == 0){
        return 0;
    } else if (n==1) {
        return 1;
    }
    return Fibonacci(n-1) + Fibonacci(n-2);
}

-1的补码是
1、先取1的原码：00000000 00000000 00000000 00000001
2、得反码： 11111111 11111111 11111111 11111110
3、得补码： 11111111 11111111 11111111 11111111
-2的补码是
1、先取1的原码：00000000 00000000 00000000 00000010
2、得反码： 11111111 11111111 11111111 11111101
3、得补码： 11111111 11111111 11111111 11111110

public int NumberOf1(int n) {
        int count = 0;
        int bit = 1;
        int times =0;
        while(times<32) {
      //不为0说明这一个二进制位为1，
                if((bit&n) != 0) {count++;}
                times++;
                bit = bit<<1;
        }
    return count;
}

public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n-1);
        }
        return count;
    }

double Power(double base ,int exponent) {
    if (exponent<0) {
        if (base!=0) {
            return 1/Power(base,-exponent);
        } else {
            //抛出异常
        }
    }
    if (exponent == 0) { return 1;}
    else if (exponent == 1) { return base;}
    double result = Power(base, exponent / 2);
    if ((exponent & 0x1) == 0) {
        return result * result;
    }
    return base * result * result;
}

public static void reOrderArray(int [] array) {
    int j = 0;//第一个偶数的位置。用于存放下一个奇数
    for (int i = 0; i < array.length; i++) {
        if (array[i]%2==1) {//奇数
            for (int k = i;k>j;k--) {
                int temp = array[k];
                array[k] = array[k-1];
                array[k-1] = temp;
            }
            j++;
        }
    }
}

ListNode FindKthToTail(ListNode head, int k) {
    if (head==null || k <= 0) {//空链表，或者k小于等于0
        return null;
    }
    ListNode secondNode = head;
    for (int i=0 ; i < k-1 ; i++) {//向前走k-1步
        if (secondNode.next==null) {//链表长度不足k个
            return null;
        }
        secondNode = secondNode.next;
    }
    ListNode firstNode = head;
    while (secondNode.next != null) {//一直遍历到secondNode成为最后一个节点
        secondNode = secondNode.next;
        firstNode = firstNode.next;
    }
    return firstNode;
}

public static ListNode ReverseList(ListNode head) {
    if (head == null) return null;//链表为空
    if (head.next==null) return head;//链表只有一个节点
    ListNode lastNode = head;
    ListNode currentNode = head.next;
    head.next = null;//将原来的头结点指向null
    while (currentNode != null) {//一直到currentNode是最好一个节点
        ListNode saveNextNode = currentNode.next;
        currentNode.next = lastNode;
        lastNode = currentNode;
        currentNode = saveNextNode;
    }
    return lastNode;
}

public ListNode findLastNode(ListNode node) {
        if(node==null ||node.next ==null) {
                return node;
        }
        //至少有两个节点
        ListNode first = node;
        ListNode second = node.next;
        ListNode three = second.next;
        first.next = null;
        while(second!=null) {
                second.next = first;
                first = second;
                second = three;
                if (three == null){break};
                else {
                    three = three.next;
                }
        }
        return first;
}

ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null || list2 == null ) { //存在链表为空
                return list1 == null ? list2 : list1;
        }
        ListNode newHead, currentNode;
        //取出较小值作为新链表的头结点
        if (list1.val < list2.val) {
            newHead = list1;
            list1 = list1.next;
        }else {
            newHead = list2;
            list2 = list2.next;
        }
        currentNode = newHead;
        while (list1 != null && list2 != null ) {
            if (list1.val<list2.val) {
                currentNode.next = list1;
                list1 = list1.next;
            } else {
                currentNode.next = list2;
                list2 = list2.next;
            }
            currentNode = currentNode.next;
        }
        if (list1!=null) {
            currentNode.next = list1;
        } else {
            currentNode.next = list2;
        }
        return newHead;
 }

ListNode Merge(ListNode list1,ListNode list2) {
    if (list1 == null || list2 == null ) { //存在链表为空
            return list1 == null ? list2 : list1;
    }
    ListNode newHead;
    if (list1.val < list2.val) {
        newHead = list1;
        newHead.next = Merge(list1.next,list2);
    }else {
        newHead = list2;
        newHead.next = Merge(list1,list2.next);
    }
    return newHead;
}

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    boolean result = false;
    if (root1 != null && root2 != null) {
        if (root1.val == root2.val) {
            result = judgeTheTree(root1, root2);
        }
        if (result == false) {
            result = HasSubtree(root1.left, root2);
        }
        if (result == false) {
            result = HasSubtree(root1.right, root2);
        }
    }
    return result;
}
boolean judgeTheTree(TreeNode root1, TreeNode root2) {
    if (root2 == null) {return true;}
    if (root1 == null) {return false;}
    if (root1.val == root2.val) {
        return judgeTheTree(root1.left, root2.left) && judgeTheTree(root1.right, root2.right);
    }
    return false;
}

public void Mirror(TreeNode root) {
    if (root != null) {
        TreeNode tempNode = root.left;
        root.left = root.right;
        root.right = tempNode;
        Mirror(root.left);
        Mirror(root.right);
    }
}

public ArrayList<Integer> printMatrix(int [][] matrix) {
                if(matrix==null) {
                        return null;
                }
        ArrayList<Integer> arrayList = new  ArrayList<Integer>();
        return printMatrix(arrayList, matrix, 0, matrix.length-1,0,matrix[0].length -1);
    }
    public ArrayList<Integer> printMatrix(ArrayList<Integer> arrayList, int [][] matrix,int rowStart, int rowEnd, int colStart, int colEnd) {
        if (rowStart> rowEnd || colStart>colEnd) {
            return arrayList;
        }
        for (int i = colStart; i <=colEnd;i++) {
            arrayList.add(matrix[rowStart][i]);
        }
        for (int i = rowStart+1; i <=rowEnd-1;i++) {
            arrayList.add(matrix[i][colEnd]);
        }
        for (int i = colEnd; i >=colStart&&rowEnd>rowStart;i--) {//要加rowEnd>rowStart判断，不然对于单行情况会重复打印
            arrayList.add(matrix[rowEnd][i]);
        }
        for (int i = rowEnd-1; i >=rowStart+1&& colStart < colEnd;i--) {//要加rowEnd>rowStart判断，不然对于单列情况会重复打印
            arrayList.add(matrix[i][colStart]);
        }
        printMatrix(arrayList, matrix,rowStart+1,rowEnd-1, colStart+1,colEnd-1);
        return arrayList;
    }

private Stack<Integer> stack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>();
public void push(int node) {
    stack.push(node);
    if (minStack.size()==0 || node<=minStack.peek()) {
        minStack.push(node);
    }
}
public void pop() {
   if(stack.size()>0 && minStack.size()>0) {
        Integer value = stack.pop();
        if (value == minStack.peek()) {
            minStack.pop();
        }
    }
}
public int top() {
    return stack.peek();
}
public int min() {
    return minStack.peek();
}

public static boolean IsPopOrder1(int [] pushA,int [] popB) {
        if (pushA==null||popB==null) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;
                 //先根据入栈序列，往栈中压入数据
        for (int i = 0; i < pushA.length; i++) {
            //如果当前栈顶元素跟出栈序列当前遍历的元素一样，那么进行出栈处理
            while (stack.size()>0 && j<popA.length && popB[j] == stack.peek()) {
                j++;
                stack.pop();
            }
          //将后面的元素压栈
            stack.push(pushA[i]);
        }
        //对剩余元素出栈
        while (stack.size()>0 && j<popA.length && popB[j] == stack.peek()) {
            j++;
            stack.pop();
        }
        // stack.size()==0代表所有元素都出栈了，弹出序列是与弹入序列是一一对应的
        return stack.size()==0;
    }

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if (root==null) {
            return arrayList;
        }
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        queue.add(root);
        while (queue.size()>0) {
            TreeNode treeNode = queue.remove(0);
            arrayList.add(treeNode.val);
            if (treeNode.left!=null) queue.add(treeNode.left);
            if (treeNode.right!=null) queue.add(treeNode.right);
        }
        return arrayList;
}

ArrayList<TreeNode> list = new ArrayList<TreeNode>();
void deepTranverse(TreeNode node) {
            if(node!=null) {
                list.add(node);
                    deepTranverse(node.left);
          deepTranverse(node.right);
            }
}
//栈的解法
void deepTranverse(TreeNode node) {
      Stack<TreeNode> stack=new Stack<TreeNode>();
     List<Integer> list=new ArrayList<Integer>();
     if(root==null)
            return list;
     //压入根节点
        stack.push(root);
    //然后就循环取出和压入节点，直到栈为空，结束循环
        while (!stack.isEmpty()){
            TreeNode t=stack.pop();
            if(t.right!=null)
                stack.push(t.right);
            if(t.left!=null)
                stack.push(t.left);
            list.add(t.val);
        }
        return  list;
}

public static boolean VerifySquenceOfBST(int [] sequence) {
    if (sequence == null || sequence.length ==0) {
        return false;
    }
    return VerifySquenceOfBST(sequence,0,sequence.length-1);
}
public static boolean VerifySquenceOfBST(int[] sequence, int start, int end) {
    if (start==end) {
        return true;
    }
    Integer rightChildIndex = null;
    for (int i = start;i<end;i++) {
            if (sequence[i] > sequence[end]&&rightChildIndex==null) {
                rightChildIndex = i;
            }
            if (rightChildIndex!=null&&sequence[i] < sequence[end]) {//右子树有更小的元素
                return false;
            }
    }
    if(rightChildIndex==null) {//说明全部位于左子树
        return VerifySquenceOfBST(sequence,start,end-1);
    } else if(rightChildIndex== start) {//说明全部位于右边子树
        return VerifySquenceOfBST(sequence,start,end-1);
    }
  //继续校验
    return VerifySquenceOfBST(sequence,start,rightChildIndex-1) && VerifySquenceOfBST(sequence,rightChildIndex, end-1);
}

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    ArrayList<ArrayList<Integer>> arrayContainer = new ArrayList<ArrayList<Integer>>();
    if (root == null) {
        return arrayContainer;
    }
    judgeIfIsTarget(arrayContainer, new ArrayList<Integer>(),root,target,0);
    return arrayContainer;
}
public void judgeIfIsTarget(ArrayList<ArrayList<Integer>> arrayContainer, ArrayList<Integer> currentArrayList, TreeNode root, int target,int sum) {
    if (root == null) {
        return ;
    }
    currentArrayList.add(root.val);
    sum = sum+root.val;
    if (sum == target && root.left == null && root.right == null) {
        ArrayList<Integer> copyArrayList = new ArrayList<>(currentArrayList);
        arrayContainer.add(copyArrayList);
    } else {
        judgeIfIsTarget(arrayContainer, new ArrayList<>(currentArrayList), root.left, target,sum);
        judgeIfIsTarget(arrayContainer, new ArrayList<>(currentArrayList), root.right, target,sum);
    }
}

public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null){return null;}
        RandomListNode currentNode= pHead;
        //当成单链表来赋值一遍
        while (currentNode!=null) {
            RandomListNode newNode = new RandomListNode(currentNode.label);
                RandomListNode nextNode = currentNode.next;
                currentNode.next = newNode;
                newNode.next = nextNode;
                currentNode = nextNode;
        }
        //设置新链表的特殊指针
        RandomListNode oldCurrentNode= pHead;
        RandomListNode newCurrentNode;
        while (oldCurrentNode!=null) {
            newCurrentNode = oldCurrentNode.next;
            RandomListNode specialNode = oldCurrentNode.random;
            newCurrentNode.random = specialNode == null ? null : specialNode.next;//random可能会为null
            oldCurrentNode = oldCurrentNode.next.next;
        }
        //链表分离
        oldCurrentNode = pHead;
        newCurrentNode = oldCurrentNode.next;
        RandomListNode newHead = pHead.next;
        while (oldCurrentNode!=null) {
            RandomListNode oldNextNode = oldCurrentNode.next.next;
            if (oldNextNode== null) {//到最后一个节点了
                oldCurrentNode.next = null;//不然会指向新链表的最后一个节点
                break;
            }
            RandomListNode newNextNode = oldNextNode.next;
            oldCurrentNode.next = oldNextNode;
            oldCurrentNode = oldNextNode;
            newCurrentNode.next = newNextNode;
            newCurrentNode = oldCurrentNode.next;
        }
        return newHead;
    }

TreeNode head = null;//主要记录双向链表头结点
    TreeNode   lastNode = null;//主要记录中序遍历时，上一次遍历的节点
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        Convert(pRootOfTree.left);
        if (head == null) {//这里相当于是把第一次执行Convert方法的元素设置为链表头结点，也就是中序遍历第一个位置的节点，也就最左边的叶子节点。
            head = pRootOfTree;
        }
        if (lastNode != null) {//中序遍历时，假设存在上一个遍历的节点，将上一个节点与这个节点进行关联
                        lastNode.right = pRootOfTree;
            pRootOfTree.left = lastNode;
        } 
          //完成对当前节点的遍历，将当前设置为lastNode。
        lastNode = pRootOfTree;
        Convert(pRootOfTree.right);
        return head;
    }

public ArrayList<String> Permutation1(String str) {
        ArrayList<String> list = new ArrayList<String>();
        if (str==null||str.length()==0) {
            return list;
        }
        Permutation(list,str,0,str.length()-1);
        return list;
    }
    public void Permutation(ArrayList<String> list,String str,int start,int end) {
        StringBuffer stringBuffer = new StringBuffer(str);
        HashSet<Character> set = new HashSet<>();
      //递归到最后一层，此时只有一个字符了，肯定是排在第一个，将当前字符串添加到list
        if (start == end) {
            list.add(str);
            return;
        }
        for (int i = start; i <= end; i++) {
            Character c = str.charAt(i);
            if (set.contains(c) == false) {
                //添加当前字符到set，代表已经做了首元素了  
                set.add(c);
                //将当前字符与首字符交换
                Character startChar = stringBuffer.charAt(start);
                stringBuffer.setCharAt(start,c);
                stringBuffer.setCharAt(i,startChar);
              //继续递归
                Permutation(list, stringBuffer.toString(),start+1,end);
            }
        }
    }

public int MoreThanHalfNum_Solution(int [] array) {
    if (array==null||array.length==0) {
        return 0;
    }
    if (array.length==1) {
        return array[0];
    }
    int result = array[0];
    int times = 1;
    for (int i = 1; i < array.length; i++) {
        if (times == 0) {
            times = 1;
            result = array[i];
        } else if (array[i] == result) {
            times++;
        } else {
            times--;
        }
    }
    //下面就是判断这个数字是否满足条件
    int statTimes = 0;
    for (int i = 0; i < array.length; i++) {
      if (array[i] == result) {
        statTimes++;
      }
    }
    if (statTimes>array.length/2) {
      return result;
    }
    return 0;
}

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if(input==null || input.length==0 ||input.length<k || k == 0) {
            return null;
        }
        arrayList.add(input[0]);
        for (int i = 1; i < input.length; i++) {
            if (arrayList.size() < k) {//子数组个数没有达到K
                arrayList.add(input[i]);
            } else if (input[i] > arrayList.get(arrayList.size()-1)) {//子数组个数达到了K，并且当前数比子数组最后一个数大
                continue;
            } else if (input[i] < arrayList.get(arrayList.size()-1)) {
                arrayList.remove(arrayList.size()-1);
                arrayList.add(input[i]);
            }
            //将最后一个元素移动合适的位置
            for (int j = arrayList.size()-1; j > 0 ; j--) {
                if (arrayList.get(j) < arrayList.get(j-1)) {
                    int temp = arrayList.get(j);
                    arrayList.set(j, arrayList.get(j-1));
                    arrayList.set(j-1, temp);
                }
            }
        }
        return arrayList;
    }

public int FindGreatestSumOfSubArray(int[] array) {
        if(array==null || array.length==0) {
            return 0;
        }
        int currentSum = array[0];
        int maxSum = currentSum;
        for (int i = 1; i < array.length; i++) {
            if (currentSum<0) {//前面的和是负数，就直接丢弃
                currentSum = array[i];
            } else {
                currentSum = currentSum + array[i];
            }
            if (currentSum>maxSum) {
                maxSum = currentSum;
            }
        }
        return maxSum;
    }

public int NumberOf1Between1AndN_Solution(int n) {
    int count = 0;
    for (int i = 1; i <= n; i *= 10) {
        int a = n / i,b = n % i;
        //之所以补8，是因为当百位为0，则a/10==(a+8)/10，
        //当百位>=2，补8会产生进位位，效果等同于(a/10+1)
        count += (a + 8) / 10 * i + ((a % 10 == 1) ? b + 1 : 0);
    }
    return count;
}

public String PrintMinNumber(int [] numbers) {
    if(numbers.length==1) {
        return new StringBuffer().append(numbers[0]).toString();
    }
    StringBuffer stringBuffer = new StringBuffer();
    for (int i = 1; i < numbers.length; i++) {
        for (int j = 0; j < numbers.length - i ; j++) {
            if (compare(numbers[j], numbers[j+1])) {//numbers[i-1]更大
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
            }
        }
    }
    for (int i = 0; i < numbers.length; i++) {
        stringBuffer.append(numbers[i]);
    }
    return stringBuffer.toString();
}
public Boolean compare(int a, int b) {
    String first = new StringBuffer().append(a).append(b).toString();
    String second = new StringBuffer().append(b).append(a).toString();
    for (int i = 0; i < first.length(); i++) {
        Character char1 = first.charAt(i);
        Character char2 = second.charAt(i);
        if (char1.equals(char2)) {
            continue;
        } else if (char1 > char2) {
            return true;
        } else {
            return false;
        }
    }
    return true;
}

public int GetUglyNumber_Solution(int index) {
    if (index == 0) return 0;
    int[] array = new int[index];
    array[0] = 1;//最小的丑数是1
    int index2 =0 ,index3 = 0, index5 = 0;//分别代表上一次乘了2，3，5的index
    for (int i = 1; i< index;i++){
        int temp2 = array[index2]*2;
        int temp3 = array[index3]*3;
        int temp5 = array[index5]*5;
        int minTemp = temp2 < temp3 ? temp2 : temp3;
        minTemp = minTemp < temp5 ? minTemp : temp5;
        if (temp2 == minTemp) {
            index2++;
        }
        if (temp3 == minTemp) {
            //可能存在一个丑数可以由多种丑数相乘得到，
            // 例如12可以是6*2，也可以是4*3，所以这里的三个if需要分开判断赋值
            index3++;
        }
        if (temp5 == minTemp) {
            index5++;
        }
        array[i] = minTemp;
    }
    return array[index-1];
}

public int FirstNotRepeatingChar(String str) {
        if (str == null|| str.length() == 0) {
            return -1;
        }
        int[] array = new int[256*256];
        for (int i = 0; i < str.length(); i++) {
            char value = str.charAt(i);
            array[value]++;
        }
        for (int i = 0; i < str.length(); i++) {
            char value = str.charAt(i);
            if(array[value] == 1) {
                return i;
            }
        }
        return -1;
  }

对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5

public int InversePairs(int [] array) {
        int[] temp = new int[array.length];
        int count = inversePairsort2(array,0,array.length-1,temp);
        return count;
}
public int inversePairsort2(int[] array, int left, int right, int[] temp) {
    int count = 0;
    if (left < right) {
        int mid = (left + right)/2;
        count += inversePairsort2(array,left,mid, temp);
        count += inversePairsort2(array,mid+1, right ,temp);
        //进行合并
        int leftIndex=left,rightIndex = mid+1,newIndex = left;
        while (leftIndex<=mid && rightIndex<= right) {
            if (array[leftIndex] <= array[rightIndex]) {
                temp[newIndex] = array[leftIndex];
                leftIndex++;
                newIndex++;
            } else {
                temp[newIndex] = array[rightIndex];
                count += mid - leftIndex + 1;
                if (count>1000000007) {
                    System.out.println(count);
                }
                rightIndex++;
                newIndex++;
            }
        }
        while (leftIndex<=mid) {
            temp[newIndex] = array[leftIndex];
            leftIndex++;
            newIndex++;
        }
        while (rightIndex<=right) {
            temp[newIndex] = array[rightIndex];
            rightIndex++;
            newIndex++;
        }
        for (int i = left; i <= right; i++) {
            array[i] = temp[i];
        }
    }
    return count;
}

public static int[] sort(int[] array,int start, int end) {
        if (start == end) {
            return new int[]{array[start]};
        }
        int mid = (start+end)/2;
        int[] leftArray = sort(array, start, mid);
        int[] rightArray = sort(array, mid+1, end);
        int leftIndex = 0, rightIndex = 0, newIndex = 0;
        //开始合并
        int[] newArray = new int[leftArray.length+rightArray.length];
        while (leftIndex<leftArray.length && rightIndex<rightArray.length) {
            if (leftArray[leftIndex]<rightArray[rightIndex]) {
                newArray[newIndex] = leftArray[leftIndex];
                leftIndex++;
                newIndex++;
            } else {
                newArray[newIndex] = rightArray[rightIndex];
                rightIndex++;
                newIndex++;
            }
        }
        while (leftIndex<leftArray.length) {
            newArray[newIndex] = leftArray[leftIndex];
            leftIndex++;
            newIndex++;
        }
        while (rightIndex<rightArray.length) {
            newArray[newIndex] = rightArray[rightIndex];
            rightIndex++;
            newIndex++;
        }
        return newArray;
    }

public static int[] sort2(int[] array, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (left + right)/2;
        sort2(array,left,mid, temp);
        sort2(array,mid+1, right ,temp);
        //进行合并
        int leftIndex=left,rightIndex = mid+1,newIndex = left;
        while (leftIndex<=mid && rightIndex<= right) {
            if (array[leftIndex] < array[rightIndex]) {
                temp[newIndex] = array[leftIndex];
                leftIndex++;
                newIndex++;
            } else {
                temp[newIndex] = array[rightIndex];
                rightIndex++;
                newIndex++;
            }
        }
        while (leftIndex<=mid) {
            temp[newIndex] = array[leftIndex];
            leftIndex++;
            newIndex++;
        }
        while (rightIndex<=right) {
            temp[newIndex] = array[rightIndex];
            rightIndex++;
            newIndex++;
        }
        for (int i = left; i <= right; i++) {
            array[i] = temp[i];
        }
    }
    return array;
}

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if (pHead1==null|| pHead2 == null) {
        return null;
    }
    //统计长度
    int length1 = 0;
    ListNode currentNode1 = pHead1;
    while (currentNode1!=null) {
        length1++;
        currentNode1 = currentNode1.next;
    }
    int length2 = 0;
    ListNode currentNode2 = pHead2;
    while (currentNode2!=null) {
        length2++;
        currentNode2 = currentNode2.next;
    }
    currentNode1 = pHead1;
    currentNode2 = pHead2;
    while (length1!=length2) {
        if (length1>length2) {
            length1--;
            currentNode1 = currentNode1.next;
        } else {
            length2--;
            currentNode2 = currentNode2.next;
        }
    }
    while (currentNode1!=null&¤tNode2!=null) {
        if (currentNode1==currentNode2){
            return currentNode1;
        } else {
            currentNode1 = currentNode1.next;
            currentNode2 = currentNode2.next;
        }
    }
    return null;
}

public int findByHalf (int[] array, double target) {
    int start = 0;
    int end = array.length - 1;
    while (start <= end) {
        int mid = (start+end)/2;
        if (target < array[mid]) {
            end = mid - 1;
        } else if (target > array[mid]){
            start = mid+1;
        } else { //相等
            return mid;
        }
    }
    return -1;
}

public int findByHalf (int[] array, double target) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start+end)/2;
            if (target < array[mid]) {
                end = mid - 1;
            } else if (target > array[mid]){
                start = mid+1;
            }
        }
        System.out.println("start"+start);
        return start;
    }

public int GetNumberOfK(int [] array , int k) {
        if (array==null||array.length== 0) {
            return 0;
        }
        return findByHalf(array, k+0.5) - findByHalf(array, k-0.5) ;
    }
    public int findByHalf (int[] array, double target) {
        int start = 0;
        int end = array.length - 1;
        while (start <= end) {
            int mid = (start+end)/2;
            if (target < array[mid]) {
                end = mid - 1;
            } else if (target > array[mid]){
                start = mid+1;
            }
        }
        return start;
    }

public int TreeDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return left > right ? left+1 : right+1;
    }

public boolean IsBalanced_Solution(TreeNode root) {
    int depth = IsBalanced_Solution_Depth(root);
    return depth == -1 ? false : true;//返回-1代表有节点不满足平衡二叉树的要求
}
public int IsBalanced_Solution_Depth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = IsBalanced_Solution_Depth(root.left);
    int right = IsBalanced_Solution_Depth(root.right);
    if (left!=-1 && right!= -1) {
        int temp = left-right;
        if (temp<=1 && temp>=-1) {
            return left > right ? left + 1 : right + 1;
        }
    }
    return -1;//返回-1代表有节点不满足平衡二叉树的要求
}

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    int result = 0;
    for (int i = 0; i < array.length; i++) {
        result = result ^ array[i];
    }
    //发现result第一个为1的位数
    int bit = 1;
    int tempResult = result & bit;
    while (tempResult==0) {
        bit = bit*2;
        tempResult = result & bit;
    }
    int number1 = 0;
    int number2 = 0;
    for (int i = 0; i < array.length; i++) {
        int temp = array[i]&bit;
        if (temp == 0) {
            number1 = number1 ^ array[i];
        } else {
            number2 = number2 ^ array[i];
        }
    }
    num1[0] = number1;
    num2[0] = number2;
}

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList arrayList = new ArrayList<ArrayList<Integer>>();
    int low=1,high=2;
    while (low<high) {
        int currentSum = (low+high)*(high-low+1)/2;//除以2的操作放在后面，否则在前面除时，(low+high)/2除不尽会丢掉1，比如3/2*2会丢掉1。
        if (currentSum==sum) {
            ArrayList tempArrayList = new ArrayList<Integer>();
            for (int k =low;k<=high;k++) {
                tempArrayList.add(k);
            }
            arrayList.add(tempArrayList);
            low++;
        } else if (currentSum<sum) {
            high++;
        } else {
            low++;
        }
    }
    return arrayList;
}

public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        int low = 0;
        int high = array.length-1;
        while (low<high) {
            int currentSum = array[low]+array[high];
            if (currentSum == sum) {
                if (array[low]*array[high] < temp) {
                    arrayList.add(array[low]);
                    arrayList.add(array[high]);
                    break;
                }
            } else if (currentSum<sum) {
                low++;
            } else {
                high--;
            }
        }
        return arrayList;
    }

public String LeftRotateString(String str,int n) {
    if (str==null|| str.length()==0 || str.length()<n) {
        return str;
    }
    str = reverse(str,0,n-1);
    str = reverse(str, n,str.length()-1);
    str = reverse(str,0,str.length()-1);
    return str;
}
public String reverse(String str, int start, int end) {
    if (start>=end) {
        return str;
    }
    StringBuffer stringBuffer = new StringBuffer(str);
    for (int i = start,j = end; i < j; i++,j--) {
        char temp = stringBuffer.charAt(i);
        stringBuffer.setCharAt(i, stringBuffer.charAt(j));
        stringBuffer.setCharAt(j, temp);
    }
    return stringBuffer.toString();
}

public String ReverseSentence(String str) {
        StringBuffer stringBuffer = new StringBuffer(str);
        //先将字符串整体翻转
        for (int i = 0,j=stringBuffer.length()-1; i < j; i++,j--) {
            char temp = stringBuffer.charAt(i);
            stringBuffer.setCharAt(i, stringBuffer.charAt(j));
            stringBuffer.setCharAt(j, temp);
        }
        //对每个单词进行翻转
        int start=0,end=0;
        int i = 0;
        while (i<stringBuffer.length()) {
            while (i < stringBuffer.length() && stringBuffer.charAt(i) == ' ') { i++; }
            start = i;
            end = i;
            //找到最后一个不为空格的字符
            while (i < stringBuffer.length() && stringBuffer.charAt(i) != ' ') {
                end = i;
                i++;
            }
            //进行替换
            for (int j = start,k=end; j < k; j++,k--) {
                char temp = stringBuffer.charAt(j);
                stringBuffer.setCharAt(j, stringBuffer.charAt(k));
                stringBuffer.setCharAt(k, temp);
            }
        }
        return stringBuffer.toString();
    }

public static boolean isContinuous(int [] numbers) {
        if (numbers == null || numbers.length == 0) return false;
        qsort(numbers,0,numbers.length-1);
        int count = 0;
        int needKing = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i]==0) {
                count++;
            }
            if (i>=1 && numbers[i]!=0&&numbers[i-1]!=0) {
                if (numbers[i] == numbers[i-1]) {
                    return false;
                }
                needKing += numbers[i] - numbers[i-1]-1;
            }
        }
        if (needKing>count) {
            return false;
        }
     return true;
}
//快排写法
public static void qsort(int[] array, int start ,int end) {
    if (start>=end) {return;}
    int threhold = array[start];//阀值
    int i        = start;
    int j        = end;
    while (i < j) {
        while (array[j] >= threhold && i < j) j--;//从右端找的应该需要写在前面
        while (array[i] <= threhold && i < j) i++;
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    //将现在最中间的数与最左端的数（也就是阀值）交换
    array[start] = array[i];
    array[i] = threhold;
    qsort(array, start, i - 1);
    qsort(array, i + 1, end);
}

public int LastRemaining_Solution(int n, int m) {
    if (n<1|| m<1) {
        return -1;
    }
    int last = 0;
    for (int i = 2; i<=n; i++) {
        last = (last+m)%i;
    }
    return last;
}

public int Sum_Solution(int n) {
        int sum = n;
        boolean ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
        return sum;
    }

public int Add(int num1,int num2) {
    if(num2 == 0) {
    return num1;
  } 
  return Add(num1^num2, (num1&num2)<<1);
}

public int Add(int num1,int num2) {
    while (num2!=0) {
        int temp  = num1 ^ num2;
        int temp2 = (num1 & num2) << 1;
        num1 = temp;
        num2 = temp2;
    }
    return  num1;
}

public static int StrToInt(String str) {
    if (str==null || str.length()==0) {
        return 0;
    }
    int isNegative = 0;
    if (str.charAt(0) == '+') {
        str = str.substring(1,str.length());
    } else if (str.charAt(0) == '-') {
        str = str.substring(1,str.length());
        isNegative = 1;
    }
    long sum =0;
    for (int i = 0; i <str.length(); i++) {
        char c = str.charAt(i);
        if (c<'0'|| c>'9') {//字符不合法
            return 0;
        } else {
            sum = sum * 10 + c - '0';
        }
    }
    if (isNegative ==1) {
        sum = 0-sum;
    }
    if (sum>Integer.MAX_VALUE || sum <Integer.MIN_VALUE) {
        return 0;
    }
    return (int)sum;
}

public boolean duplicate(int numbers[],int length,int [] duplication) {
    if (numbers == null || numbers.length==0) {
        return false;
    }
    for (int i=0;i<numbers.length;i++) {
        int current = numbers[i];
        if (current == -1) {//当前存储的值为-1，说明这个下标之前出现过，但是不重复
            continue;
        }else if (numbers[current] == -1) {//说明有重复的了
            duplication[0] = current;
            return true;
        } else if (current == i) {//等于当前下标，直接标识为-1
            numbers[i]= -1;
        } else {//不等于当前下标，进行交换后，然后标识为-1
            int temp = numbers[current];
            numbers[current] = -1;
            numbers[i] = temp;
            i--;
        }
    }
    return false;
}

就是B[i] = A[0]A[1]...A[i-1]  A[i+1]...*A[n-1]，通过拆分成两部分，
C[i] = A[0]A[1]...A[i-1]
D[i] = A[i+1]...*A[n-1]
B[i]=C[n]*D[n]来解决。
public int[] multiply(int[] A) {
    int[] b = new int[A.length];
    int[] c = new int[A.length];
    int[] d = new int[A.length];
    c[0] = 1;
    int result1 = c[0];
    //构建数组C
    for (int i = 1; i < c.length; i++) {
        result1 = result1 * A[i-1];
        c[i] = result1;
    }
    d[d.length-1] = 1;
    int result2 = 1;
    //构建数组D
    for (int i = d.length-2; i >=0; i--) {
        result2 = result2 * A[i+1];
        d[i] = result2;
    }
    for (int i = 0; i < b.length; i++) {
        b[i] = c[i]*d[i];
    }
    return b;
}

StringBuffer str = new StringBuffer();
    int[] table = new int[256];//记录出现次数，0代表0次，1代表1次，2代表2次及2次以上
    public void Insert(char ch)
    {
        if (table[ch] < 2) {//出现次数为0次和1次时才累加。
            table[ch]++;
        }
        str.append(ch);
    }
public char FirstAppearingOnce()
{
    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);
      if (table[c] == 1) {
        return c;
      }
    }
    return '#';
}

public ListNode EntryNodeOfLoop(ListNode pHead)
{
    if (pHead == null || pHead.next==null) {
        return null;
    }
    //计算环的长度
    ListNode slowNode = pHead.next;
    ListNode quickNode = slowNode.next;
    ListNode nodeInLoop = null;//获取环上的某个节点
    while (quickNode!=null && slowNode!= null) {
        if (quickNode == slowNode) {
            nodeInLoop =  quickNode;
            break;
        }
        slowNode = slowNode.next;
        quickNode = quickNode.next;
        if (quickNode!= null) {
            quickNode=quickNode.next;
        }
    }
    if (nodeInLoop == null) {//说明没有环
        return null;
    }
    //根据环上的某个节点来计算环的长度count
    ListNode tempNode = nodeInLoop;
    int count = 1;//将当前计算计算在内
    while (tempNode.next!=nodeInLoop) {
        tempNode = tempNode.next;
        count++;
    }
    //从链表头结点出发，第一个指针先走count步，然后两个指针每次只走一步，相遇的地方就是环的入口，
    // 然后第一个指针和第二个指针一起走，当第二个指针刚好走了x步到环入口时，
    // 第一个指针正好走了x+count步，在环中走了一圈，也在环的入口，
    quickNode = pHead;
    for (int i = 0; i < count; i++) {
        quickNode = quickNode.next;
    }
    slowNode = pHead;
    while (quickNode!=slowNode) {
        quickNode = quickNode.next;
        slowNode=slowNode.next;
    }
    return slowNode;
}

public ListNode EntryNodeOfLoop1(ListNode pHead)
{
    if (pHead==null) {
        return null;
    }
    HashSet<ListNode> set = new HashSet<ListNode>();
    ListNode node = pHead;
    while (node !=null) {
        if (set.contains(node)) {
            return node;
        } else {
            set.add(node);
        }
        node= node.next;
    }
    return null;
}

public ListNode deleteDuplication(ListNode pHead)
{
    if (pHead == null || pHead.next == null) {
        return pHead;
    }
    ListNode ourHead = new ListNode(0);
    ourHead.next = pHead;
    ListNode preNode = ourHead;
    ListNode currentNode = ourHead.next;
    while (currentNode!=null) {//往后遍历
        if (currentNode.next!=null && currentNode.val == currentNode.next.val) {//如果当前节点与下一个节点相等，就找到一个与当前节点不相等的节点，然后把中间多出来的这些相等的节点都删除掉
            ListNode tempNode = currentNode.next;
            //找到第一个不相等的节点
            while (tempNode!=null) {
                if(tempNode.val == currentNode.val) { tempNode = tempNode.next; }
                else { break; }
            }
            preNode.next = tempNode;
            currentNode = preNode.next;
        } else {//如果当前节点与下一个节点相等，就跳过，遍历下一个节点
            preNode = preNode.next;
            currentNode = currentNode.next;
        }
    }
    return  ourHead.next;
}

这个节点有父节点

public TreeLinkNode GetNext(TreeLinkNode pNode)
{
    //这个节点有右子树
    if (pNode.right != null) {
        TreeLinkNode right = pNode.right;
        if (right.left==null) {//右子树没有左节点
            return right;
        } else {
            TreeLinkNode leftNode = right.left;
            while (leftNode.left!= null) {//右子树有左节点
                leftNode = leftNode.left;
            }
            return leftNode;
        }
    } else {//这个节点没有右子树，那么就去找父节点
        TreeLinkNode father = pNode.next;
        if (father == null) {//父节点为空
            return null;
        } else if(father.left == pNode) {//父节点不为空,该节点为父节点的左子树
            return father;
        } else {
                while (father.next!=null) {
                    TreeLinkNode grandFather = father.next;
                    if (grandFather.left == father) {
                        return grandFather;
                    } else {
                        father = grandFather;
                        continue;
                    }
                }
            }
        }
    return null;
}

boolean isSymmetrical(TreeNode pRoot)
{
    return isSymmetrical(pRoot,pRoot);
}
boolean isSymmetrical(TreeNode leftRoot,TreeNode rightRoot)
{
    if (leftRoot == null || rightRoot == null) {
        return (leftRoot == null) & (rightRoot == null);
    }
    if (leftRoot.val!=rightRoot.val) {
        return false;
    } else {
        return isSymmetrical(leftRoot.left, rightRoot.right)
                & isSymmetrical(leftRoot.right, rightRoot.left);
    }
}

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<ArrayList<Integer>>();
    if (pRoot==null) return arrayLists;
    Stack<TreeNode> stack1 = new Stack<TreeNode>();//存放奇数层的栈
    Stack<TreeNode> stack2 = new Stack<TreeNode>();//存放偶数层的栈
     int flag = 0;//代表当前遍历的是奇数层还是偶数层。区别在于添加子节点的顺序。
     stack1.add(pRoot);
     while ((flag == 0 && stack1.size()>0) || (flag == 1 && stack2.size()>0)) {
         if (flag==0) {//代表是偶数层
             ArrayList<Integer> array = new ArrayList<Integer>();
             while (stack1.size()>0) {
                 TreeNode node = stack1.pop();
                 array.add(node.val);
                 if (node.left!=null) stack2.push(node.left);
                 if (node.right!=null) stack2.push(node.right);
             }
             arrayLists.add(array);
             flag = 1;
         } else {
             ArrayList<Integer> array = new ArrayList<Integer>();
             while (stack2.size()>0) {
                 TreeNode node = stack2.pop();
                 array.add(node.val);
                 if (node.right!=null) stack1.push(node.right);
                 if (node.left!=null) stack1.push(node.left);
             }
             arrayLists.add(array);
             flag = 0;
         }
     }
    return arrayLists;
}

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        Stack<TreeNode> otherStack = new Stack<TreeNode>();
        Stack<TreeNode> currentStack = new Stack<TreeNode>();
        if(pRoot == null) {
            return list;
        }
        currentStack.push(pRoot);
        int addChildFromRightFlag = 0;//
        while(currentStack.size()>0 || otherStack.size()>0) {
            ArrayList<Integer> array = new ArrayList<Integer>();
            while(currentStack.size()>0) {
                TreeNode node = currentStack.pop();
                array.add(node.val);
                if(addChildFromRightFlag == 0) {//根据层数的不同，决定从右边还是左边添加节点。
                    if(node.left!=null) {
                        otherStack.add(node.left);
                    }
                    if(node.right!=null) {
                        otherStack.add(node.right);
                    }
                } else {
                    if(node.right!=null) {
                        otherStack.add(node.right);
                    }
                    if(node.left!=null) {
                        otherStack.add(node.left);
                    }
                }
            }
            list.add(array);
            addChildFromRightFlag = addChildFromRightFlag == 0 ? 1:0;
            currentStack = otherStack;
            otherStack = new Stack<TreeNode>();
        }
         return list;
    }

ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> arrayLists= new ArrayList<ArrayList<Integer>>();
    if (pRoot == null) return arrayLists;
    ArrayList<TreeNode> queue = new ArrayList<>();
    queue.add(pRoot);
    queue.add(null);//每一层结束时，添加标志节点
    ArrayList<Integer> tempArrayList = new ArrayList<>();
    while (queue.size()>0) {
        TreeNode treeNode = queue.remove(0);
        if (treeNode==null) {//null是标志节点，说明这一层已经打印结束了
            arrayLists.add(tempArrayList);
            tempArrayList = new ArrayList<>();
            if (queue.size() == 0)  {break;}//如果队列里没有元素了，就结束循环
            else { queue.add(null); }//如果队列里还有元素就继续添加标志节点
        } else {
            tempArrayList.add(treeNode.val);
            if (treeNode.left!=null) queue.add(treeNode.left);
            if (treeNode.right!=null) queue.add(treeNode.right);
        }
    }
    return arrayLists;
}

ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<ArrayList<Integer>>();
    if (pRoot==null)return arrayLists;
    find(pRoot,1,arrayLists);
    return arrayLists;
}
void find(TreeNode pRoot, int depth, ArrayList<ArrayList<Integer>> arrayLists) {
    if (arrayLists.size()< depth) {//还没有存放这一层节点的数组
        arrayLists.add(new ArrayList<Integer>());
    }
    ArrayList<Integer> tempArrayList = arrayLists.get(depth-1);
    tempArrayList.add(pRoot.val);
    if (pRoot.left!=null) find(pRoot.left,depth+1,arrayLists);
    if (pRoot.right!=null) find(pRoot.right,depth+1,arrayLists);
}

String Serialize(TreeNode root) {
        StringBuffer stringBuffer = new StringBuffer();
        if (root == null) {return stringBuffer.toString();}
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        queue.add(root);
        while (queue.size()>0) {
            TreeNode node = queue.remove(0);
            if (node == null) {
                stringBuffer.append("#!");
            } else {
                stringBuffer.append(node.val+"!");
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        return stringBuffer.toString();
}
TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {return null;}
        String[] array = str.split("!");
        Integer rootValue = convert(array[0]);
        if (rootValue == null) {return null;}
        TreeNode rootNode = new TreeNode(rootValue);
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        queue.add(rootNode);
        int currentIndex = 1;
        while (queue.size()>0 && currentIndex<array.length) {
            TreeNode node = queue.remove(0);
            Integer leftValue,rightValue;
            leftValue = convert(array[currentIndex]);
            rightValue = convert(array[currentIndex+1]);
            currentIndex = currentIndex + 2;
            if (leftValue!=null) {
                TreeNode leftNode = new TreeNode(leftValue);
                node.left = leftNode;
                queue.add(leftNode);
            }
            if (rightValue!=null) {
                TreeNode rightNode = new TreeNode(rightValue);
                node.right = rightNode;
                queue.add(rightNode);
            }
        }
        return rootNode;
}
Integer convert(String str) {
        Integer result;
        try {
            result = Integer.parseInt(str);
        } catch (NumberFormatException e) {
            return null;
        }
        return result;
}

Integer index = 0;
TreeNode kNode = null;
TreeNode KthNode(TreeNode pRoot, int k)
{
    find(pRoot,k);
    return kNode;
}
void find(TreeNode node, Integer k) {
    if (node == null) {return;}
    find(node.left, k);
    index++;
    if (index == k) {
        kNode = node;
    } else {
        find(node.right, k);
    }
}

ArrayList<Integer> arrayList = new ArrayList<Integer>();
    public void Insert(Integer num) {
        if (arrayList.size()==0) {
            arrayList.add(num);
        } else {
            for (int i = arrayList.size()-1; i >=0 ; i--) {
                if (arrayList.get(i)<num) {
                    arrayList.add(i+1,num);//需要注意的是ArrayList.add(index)方法是将元素插在index下标下，而当前arrayList.get(i)是小于num的，所以当前元素插在i+1下标下
                    break;
                } else if (arrayList.get(i)>=num && i==0) {//插入的元素比数组中所有元素都小的情况
                    arrayList.add(0,num);
                }
            }
        }
    }
    public Double GetMedian() {
        if (arrayList.size()%2==1) {
            return  arrayList.get(arrayList.size()/2).doubleValue() ;
        } else {
            return (arrayList.get(arrayList.size()/2-1).doubleValue() + arrayList.get(arrayList.size()/2).doubleValue())/2;
        }
    }

public ArrayList<Integer> maxInWindows1(int[] num, int size) {
    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    ArrayList<Integer> sortList  = new ArrayList<Integer>(size);
    if (num == null || num.length == 0 || size <= 0 || size > num.length) {
        return arrayList;
    }
    int i = 0;
    for (; i < size; i++) {//初始化一开始的滑动窗口的值
        sortList = insertValueIntoSorted(sortList, num[i]);
    }
    arrayList.add(sortList.get(size - 1));//添加第一个滑动窗口的最大值
    for (; i < num.length; i++) {
        sortList = removeValueIntoSorted(sortList, num[i - size]);//将离开滑动窗口的值从排序数组移除
        sortList = insertValueIntoSorted(sortList, num[i]);
        arrayList.add(sortList.get(size - 1));
    }
    return arrayList;
}
ArrayList<Integer> insertValueIntoSorted(ArrayList<Integer> sortList, int currentValue) {
    if (sortList.size() == 0) {
        sortList.add(currentValue);
    } else {
        for (int j = sortList.size() - 1; j >= 0; j--) {
            if (currentValue > sortList.get(j)) {
                sortList.add(j + 1, currentValue);
                break;
            } else if (j == 0) {
                sortList.add(0, currentValue);
            }
        }
    }
    return sortList;
}
ArrayList<Integer> removeValueIntoSorted(ArrayList<Integer> sortList, int currentValue) {
    int index = 0;
    for (int i = 0; i < sortList.size(); i++) {
        if (sortList.get(i) == currentValue) {
            index = i;
            break;
        }
    }
    sortList.remove(index);
    return sortList;
}

public ArrayList<Integer> maxInWindows(int[] num, int size) {
    ArrayList<Integer>  arrayList = new ArrayList<Integer>();
    if (num == null || num.length == 0 || size <= 0 || size > num.length) {
        return arrayList;
    }
    LinkedList<Integer> maxQueue  = new LinkedList<>();//存储最大值的下标
    for (int i = 0; i < num.length; i++) {
        int begin = i - size + 1;//滑动窗口最左边的下标
        if (maxQueue.size() == 0) {
            maxQueue.add(i);
        }
        if (maxQueue.peekFirst() < begin) {//说明已经过期
            maxQueue.pollFirst();//将它移除队列
        }
        while (maxQueue.size() > 0 && num[maxQueue.peekLast()] <= num[i]) {//队列末尾的值都小于当前值，将他们都出列
            maxQueue.pollLast();//出列
        }
        maxQueue.add(i);
        if (begin >= 0) {//滑动接口全部处于在数组中时才能添加值
            arrayList.add(num[maxQueue.peekFirst()]);
        }
    }
    return arrayList;
}

public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
    boolean[] flag = new boolean[matrix.length];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i*cols + j] == str[0]) {
                if (judge(matrix,rows,cols,i, j, str, 0, flag)) {
                    return true;
                }
            }
        }
    }
    return false;
}
//flag 标识这个节点是否已经在路径中了
boolean judge(char[] matrix, int rows, int cols, int i, int j, char[] str, int charIndex,boolean[] flag) {
    int index =  i*cols + j;
    if (i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[charIndex] || flag[index] == true) {
        return false;
    }
    if (charIndex==str.length-1) { return true;}
        //用来记录这个位置是否在路径中
    flag[index]=true;
    if (judge(matrix,rows,cols,i+1, j, str, charIndex+1, flag)
            ||judge(matrix,rows,cols,i-1, j, str, charIndex+1, flag)
            ||judge(matrix,rows,cols,i, j+1, str, charIndex+1, flag)
            ||judge(matrix,rows,cols,i, j-1, str, charIndex+1, flag)) {
        return true;
    }
    flag[index]=false;
    return false;
}

public int movingCount(int threshold, int rows, int cols)
{
    if (rows<0||cols<0||threshold<0) {return 0;}
    boolean[][] flagArray = new boolean[rows][cols];
    int count = findCount(rows,cols,0,0,flagArray,threshold);
    return count;
}
int findCount(int rows, int cols,int i,int j, boolean[][]flagArray,int threshold) {
    if (i<0||i>=rows||j<0||j>=cols||flagArray[i][j]==true|| judge(i)+judge(j)>threshold) {
        return 0;
    }
    flagArray[i][j]=true;
    return 1+findCount(rows,cols,i-1,j,flagArray,threshold)
            +findCount(rows,cols,i+1,j,flagArray,threshold)
            +findCount(rows,cols,i,j-1,flagArray,threshold)
            +findCount(rows,cols,i,j+1,flagArray,threshold);
}
int judge(int i) {
    int sum = 0;
    while (i>0) {
        sum += i%10;
        i = i/10;
    }
    return sum;
}

public int cutRope(int target) {
    if (target <= 1) {
        return 0;
    } else if (target==2) {
        return 1;
    } else if (target == 3) {
        return 2;
    }
    int result = 1;
    int times = target/3;
    int number = target%3;
    if (number==1) {//就是余数为1时，给它一个3，凑成一个4，改成2*2乘积更大
        times=times-1;
        result = result * 4;
        for (int i = 0; i < times; i++) {
            result = result * 3;
        }
    } else if (number == 2) {
        result = result * 2;
        for (int i = 0; i < times; i++) {
            result = result * 3;
        }
    }
    return result;
}

public int findByHalf(int[] array, int target) {
    if (array==null||array.length==0) {
        return -1;
    }
    int left = 0;
    int right = array.length-1;
    while (left<=right) {//需要注意是小于等于right，否则会是[left,right),将最后一个元素排除比较
        int mid = left + (right - left)/2;
        if (array[mid] == target){
            return mid;
        } else if (array[mid]<target) {
            left= mid+1;
        } else {
            right = mid-1;
        }
    }
    return -1;
}

public static void main(String[] args) {
        Test002 test002 = new Test002();
        int[] array = new int[]{1,2,2,2,2,4,5,6,7};
        System.out.println(test002.findByHalfLeft(array, 3));
    }
    //二分查找左边界
    public int findByHalfLeft(int[] array, int target) {
        if (array==null||array.length==0) { return -1;}
        int left = 0;
        int right = array.length - 1;
        while (left<=right) {
            int mid = left+(right-left)/2;
            if (array[mid] == target) {
                right = mid-1;
            } else if (array[mid] < target) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        if (left >= array.length || array[left] != target){ return -1;}
            return  array[left]==target ? left : -1;
        }
            // 检查出界情况，因为循环结束的条件是left=right+1，如果target比数组所有元素都大会导致越界
        //如果有左边界就返回左边界，没有时，此时的left应该是最接近左边界，并且大于左边界的数的位置