剑指offer刷题结果

重建二叉树

public class Main { 
    public int c = -1;
    
    public TreeNode construction(int s,int e,int[] pre,int []in){
        if(s<=e){
            c++;
            TreeNode node = new TreeNode(pre[c]);
            int mid = 0;
            for(int i=s;i<=e;i++){
                if(in[i]==pre[c]){
                    mid=i;
                    break;
                }
            }
            node.left=construction(s,mid-1,pre,in);
            node.right=construction(mid+1,e, pre, in);
            return node;
            
        }else{
            return null;
        }
        
        
    }
    
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0){
            return null;
        }
        return construction(0,pre.length-1,pre,in);
    }
    
    public static void main(String[] args){
        
    }
}

链表中倒数第k个结点

public ListNode FindKthToTail(ListNode head,int k) {
        if(k<=0){
            return null;
        }
        ListNode k1=head,k2=head;
        for(int i=0;i<k;i++){
            if(k1==null) return null;
            k1=k1.next;
        }
        while(k1!=null){
            k1=k1.next;
            k2=k2.next;
        }
        return k2;
        
    }

最小的k个数

O(n) , 基于快排思想，但是会修改原数组

public int partition(int [] input,int s,int e){
        int value = input[e];
        int i = s-1;
        int j = s;
        for(;j<e;j++){
            if(input[j]<value){
                i++;
                int temp = input[i];
                input[i] = input[j];
                input[j] = temp;
            }
        }
        input[e] = input[i+1];
        input[i+1] = value;
        return i+1;
    }
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<Integer>();    
            int len = input.length;
            int mid;
            int s=0,e=len-1;
            if(k<=0||k>len){
                return list;
            }
            while((k-1)!=(mid=partition(input,s,e))){
                if(mid>(k-1)){
                    e=mid-1;
                }else{
                    s=mid+1;
                }
            }
            for(int i=0;i<k;i++){
                list.add(input[i]);
            }
            return list;
            
    }

O(nlogk)，堆排序，建立k个元素的堆

import java.util.ArrayList;

public class Solution {
    public int maxHeap[];
    public int length;
    
    public void adjustHeap(int p){
        int child = p*2+1;
        int value = maxHeap[p];
        while(child<length){
            if((child+1)<length&&maxHeap[child+1]>maxHeap[child]){
                child++;
            }
            if(maxHeap[child]>value){
                maxHeap[p] = maxHeap[child];
                p=child;
                child=2*p+1;
            }else
                break;
        }
        maxHeap[p] = value;
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(k<=0||k>input.length){
            return new ArrayList<Integer>();
        }
        maxHeap= new int[k];
        length = k;
        for(int i=0;i<k;i++){
            maxHeap[i] = input[i];
        }
        for(int i=k/2-1;i>=0;i--){
            adjustHeap(i);
        }
        for(int i=k;i<input.length;i++){
            if(input[i]<maxHeap[0]){
                maxHeap[0] = input[i];
                adjustHeap(0);
            }
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<length;i++){
            list.add(maxHeap[i]);
        }
        return list;
    }
}

两个栈实现队列

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

旋转数组的最小数字

import java.util.ArrayList;
public class Solution {
    public int findMonor(int [] a, int s , int e){
        if(a[s]<a[e]) return a[s];
        int mid = (s+e)/2;
        //以防出现101111的情况
        if(a[s]==a[mid]&&a[e]==a[mid]){
            int minor = a[s];
            for(int i=s+1;i<=e;i++){
                if(a[s]>a[i]){
                    minor = a[i];
                }
            }
            return minor;
        }
        if((e-s)==1){
            return a[e];
        }
        if(a[mid]<=a[e]){
            e = mid;
        }else{
            s=mid;
        }
        return findMonor(a,s,e);
    }
    
    public int minNumberInRotateArray(int [] array) {
        int len = array.length;
        if(len==0) return 0;
        return findMonor(array,0,array.length-1);
    }
}

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法

  public class Main {
    public int JumpFloorII(int target) {
        if(target==0) return 0;
        if(target==1) return 1;
        int sum=1;
        for(int i=2;i<=target;i++){
            sum = 2*sum ;
        }
        return sum;
    }
    
    public static void main(String[] args){
        
        Main m = new Main();
        int a = m.JumpFloorII(3);
        System.out.println(a);
    }
}

二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

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

数值的整数次方

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

public class Solution {
    public double Power(double base, int exponent) {
        int e = Math.abs(exponent); 
        if(exponent==0) return 1;
        if(exponent==1) return base;
        double half = Power(base,e>>1);
        double result = half*half;
        if((e&1)==1){
            result = result * base;
        }
        if(exponent<0){
            result = 1/result;
        }
        return result; 
    }   
}

调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
队列实现

public class Solution {
    public void reOrderArray(int [] array) {
        Queue<Integer> q1 = new LinkedList<Integer>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        for(int i=0;i<array.length;i++){
            if((array[i]%2)==1){
                q1.offer(array[i]);
            }else{
                q2.offer(array[i]);
            }
        }
        int k=0;
        while(!q1.isEmpty()){
            array[k++]=q1.poll();
        }
        while(!q2.isEmpty()){
            array[k++]=q2.poll();
        }
    }
}

反转链表

输入一个链表，反转链表后，输出新链表的表头。

public class Solution {
   public ListNode ReverseList(ListNode head) {
        if(head==null) return null;
        if(head.next==null) return head;
        ListNode l1 = head;
        ListNode l2 = head.next;
        ListNode l3 = l2.next;
        while(l3!=null){
            l2.next=l1;
            l1=l2;
            l2=l3;
            l3=l3.next;
        }
        l2.next=l1;
        head.next=null;
        return l2;
        
    }
}

合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode l = head;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                l.next=list1;
                list1=list1.next;
                l=l.next;
            }else{
                l.next=list2;
                list2=list2.next;
                l=l.next;
            }
        }
        while(list1!=null){
            l.next=list1;
            list1=list1.next;
            l=l.next;
        }
        while(list2!=null){
            l.next=list2;
            list2=list2.next;
            l=l.next;
        }
        l.next=null;
        return head.next;
    }
}

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

public ArrayList<Integer> printMatrix(int [][] matrix) {
           ArrayList<Integer> list = new ArrayList<Integer>();
           int xlen =matrix.length;
           int ylen =matrix[0].length;
           int minlen = xlen>ylen?ylen:xlen;
           int startx = 0;
           int starty = 0;
           for(int i=0;i<(minlen-1)/2+1;i++){
               print(matrix,startx+i,starty+i,xlen-2*i,ylen-2*i,list);
           }
           return list;
    }
    public void print(int[][]matrix,int startx,int starty,int xlen,int ylen,ArrayList<Integer> list){
        for(int i=0;i<ylen;i++){
            list.add(matrix[startx][starty+i]);
            System.out.println(matrix[startx][starty+i]);
        }
        for(int i=1;i<xlen;i++){
            list.add(matrix[startx+i][starty+ylen-1]);
            System.out.println(matrix[startx+i][starty+ylen-1]);
        }
        if(xlen!=1){
            for(int i=1;i<ylen;i++){
                list.add(matrix[startx+xlen-1][starty+ylen-1-i]);
                System.out.println(matrix[startx+xlen-1][starty+ylen-1-i]);
            }
        }
        if(ylen!=1){
            for(int i=1;i<xlen-1;i++){
                list.add(matrix[startx+xlen-1-i][starty]);
                System.out.println(matrix[startx+xlen-1-i][starty]);
            }
        }   
    }

包含min函数的栈

public class Main {
    public Stack<Integer> stack = new Stack<Integer>();
    public Stack<Integer> stackMin = new Stack<Integer>();

    public void push(int node) {
        if (stack.isEmpty()) {
            stack.push(node);
            stackMin.push(node);
        } else {
            stack.push(node);
            if (stackMin.peek() > node) {
                stackMin.push(node);
            } else {
                stackMin.push(stackMin.peek());
            }
        }
    }

    public void pop() {
        stack.pop();
        stackMin.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return stackMin.peek();
    }

    public static void main(String[] args) {
        Main m = new Main();
        m.push(3);
        System.out.println(m.min());
        m.push(4);
        System.out.println(m.min());
        m.push(2);
        System.out.println(m.min());
        m.push(3);
        System.out.println(m.min());
        m.pop();
        System.out.println(m.min());
        m.pop();
        System.out.println(m.min());
        m.pop();
        System.out.println(m.min());
        m.push(0);
        System.out.println(m.min());
    }
}

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
          Stack<Integer> stack = new Stack<Integer>();
          int j=0;
          for(int i=0;i<pushA.length;i++){  
              stack.push(pushA[i]); 
              if(stack.peek()==popA[j]){
                  j++;
                  stack.pop();
              }
          }
          while(!stack.isEmpty()){
              if(stack.peek()==popA[j]){
                  stack.pop();
                  j++;
              }else{
                  return false;
              }
          }
          return true;  
    }
}

从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        if(root==null){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left!=null) queue.offer(node.left);
            if(node.right!=null) queue.offer(node.right);
        }
        return list;
    }
}

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

public class Solution {
   public boolean Verify(int a[],int s,int e){
        if(s>=e){
            return true;
        }
        int rootVal = a[e];
        int mid=s-1;
        for(int i=s;i<e;i++){
            if(a[i]<rootVal){
                mid++;
            }else
                break;
        }
        for(int i=mid+1;i<e;i++){
            if(a[i]<rootVal){
                return false;
            }
        }
        return Verify(a,s,mid)&&Verify(a,mid+1,e-1);
    }
    
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0) return false;
        return Verify(sequence,0,sequence.length-1);
    }
}

二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

import java.util.ArrayList;
import java.util.Stack;
import java.util.Iterator;


/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>>  list = new ArrayList<ArrayList<Integer>>();
    
    public Stack<Integer> stack = new Stack<Integer>();
    public int sum = 0;
    
    public void Find(TreeNode root,int target){
         if(root!=null){
                stack.push(root.val);
                sum = sum + root.val;
                if(root.left==null
                        &&root.right==null
                        &&sum == target){
                    Iterator<Integer> iter = stack.iterator();
                    ArrayList<Integer> nList = new ArrayList<Integer>();
                    while(iter.hasNext()){
                        nList.add(iter.next());
                    }
                    list.add(nList);
                }
                if(root.left!=null)  Find(root.left,target);
                if(root.right!=null) Find(root.right,target);   
                stack.pop();
                sum=sum-root.val;
            }
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        Find(root,target);
        return list;
    }
}

复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

public RandomListNode Clone(RandomListNode phead)
    {
        if(phead==null)
            return null;
        RandomListNode head = phead;
        while(head!=null){
            RandomListNode node = new RandomListNode(head.label);
            node.next=head.next;
            head.next=node;
            head = node.next;
        }
        head = phead;
        while(head!=null){
            if(head.random!=null){
                head.next.random=head.random.next;
            }
            head = head.next.next;
        }
        head = phead;
        RandomListNode newHead=head.next;
        RandomListNode p = newHead;
        while(head!=null){
            head.next = head.next.next;
            if(p.next!=null)
            p.next = p.next.next;
            p = p.next;
            head = head.next;
        }       
        return newHead;
    }
}

数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

public class Solution {
    public HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    public int MoreThanHalfNum_Solution(int [] array) {
        int midLen = array.length/2;
        for(int i=0;i<array.length;i++){
           int key = array[i];
           if(map.containsKey(key)){
               map.put(key, map.get(key)+1);
           }else{
               map.put(key, 1);
           }
       }
       Iterator<Integer> iter = map.keySet().iterator();
       while(iter.hasNext()){
           int key = iter.next();
           if(map.get(key)>midLen){
               return key;
           }
       }
       return 0;
           
    }
}

二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

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

数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

public class Solution {
    public int binaryFindLeft(int []a,int s,int e,int k){
        if(s<=e){
            int mid = (s+e)/2;
            if(mid==0&&a[mid]==k){
                return mid;
            }else if(mid!=0&&a[mid]==k&&a[mid-1]<k){
                return mid;
            }else if(a[mid]>=k){
                return binaryFindLeft(a,s,mid-1,k);
            }else{
                return binaryFindLeft(a,mid+1,e,k);
            }
        }
        return -1;
    }
    public int binaryFindRight(int []a,int s,int e,int k){
        if(s<=e){
            int mid = (s+e)/2;
            if(mid==(a.length-1)&&a[mid]==k){
                return mid;
            }else if(mid!=(a.length-1)&&a[mid]==k&&a[mid+1]>k){
                return mid;
            }else if(a[mid]>k){
                return binaryFindRight(a,s,mid-1,k);
            }else{
                return binaryFindRight(a,mid+1,e,k);
            }
        }
        return -1;
    }
    
    public int GetNumberOfK(int [] array , int k) {
           if(array.length==0){
               return 0;
           }
           int a = binaryFindLeft(array,0,array.length-1,k);
           int b= binaryFindRight(array,0,array.length-1,k);
           if(a==-1){
               return 0;
           }else{
               return b-a+1;
           }
    }
}

两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

public class Solution {
    public Stack<ListNode> stack1 = new Stack<ListNode>();
    public Stack<ListNode> stack2 = new Stack<ListNode>();

    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1=pHead1,l2=pHead2; 
        while(l1!=null){
            stack1.push(l1);
            l1=l1.next;
        }
        while(l2!=null){
            stack2.push(l2);
            l2=l2.next;
        }
        ListNode parent = null;
        while(!stack1.isEmpty()&&!stack2.isEmpty()){
            ListNode temp = stack1.peek();
            if(stack1.pop()==stack2.pop()){
                parent = temp;
            }else{
                break;
            }
        }
        return parent;
    }
}

丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index==0){
            return 0;
        }
        int s[] = new int[index];
        s[0]=1;
        int t2=0,t3=0,t4=0;
        for(int i=1;i<index;i++){
            int m2=0,m3=0,m5=0;
            for(int j=t2;j<i;j++){
                if(s[j]*2>s[i-1]){
                    m2 = 2*s[j];
                    break;
                }
                t2++;
                
            }
            for(int j=t3;j<i;j++){
                if(s[j]*3>s[i-1]){
                    m3 = 3*s[j];
                    break;
                }
                t3++;
            }
            for(int j=t4;j<i;j++){
                if(s[j]*5>s[i-1]){
                    m5=5*s[j];
                    break;
                }
                t4++;
            }
            if(m2>m3) m2 = m3;
            if(m2>m5) m2 = m5;
            s[i] = m2;
        }
        return s[index-1];
    }
}

连续子数组的最大和

public int FindGreatestSumOfSubArray(int[] array) {
        int sum=0;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<array.length;i++){
            sum = sum + array[i];
            if(sum>max){
                max = sum;
            }
            if(sum<0){
                sum = 0;
            }
        }
        return max;
}

数组中只出现一次的数字

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int val = 0;
        for(int i=0;i<array.length;i++){
            val = val ^ array[i];
        }
        int index =1;
        while((index&val)==0){
            index= index<<1;
        }
        int a=0;
        int b=0;
        for(int i=0;i<array.length;i++){
            int data = array[i];
            if((data&index)==0){
                a = a^ data;
            }else{
                b= b^data;
            }
        }
        num1[0] = a;
        num2[0] = b;
        
    }
}

平衡二叉树

public class Solution {
    public boolean isBalanced(TreeNode root ,int[] depth ){
        if(root==null){
            depth[0]=0;
            return true;
        }
        int []da = new int[1];
        int []db = new int[1];
        if(isBalanced(root.left,da)&&
                isBalanced(root.right,db)){
            if(Math.abs(da[0]-db[0])<=1){
                int max = da[0]>db[0]?da[0]:db[0];
                depth[0] = 1 + max;
                return true;
            }
        }
        return false;
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        return isBalanced(root,new int[1]);
    }
}

数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

public class Main{
    int xa[] = new int[100];
    int lena = 0;
    int xb[] = new int[100];
    int lenb = 0;
    public  boolean compareSmaller(int a,int b){
        lena=0;
        while(a!=0){
            xa[lena] = a%10;
            a=a/10;
            lena++;
        }
        lenb = 0;
        while(b!=0){
            xb[lenb] = b%10;
            b=b/10;
            lenb++;
        }
        int i=lena-1;
        int j=lenb-1;
        while(i>=0&&j>=0){
            if(xa[i]>xb[j]){
                return false;
            }
            i--;j--;
        }
        if(i>=0&&xa[i]>xb[lenb-1])  return false;
        if(j>=0&&xa[lena-1]>xb[j]) return false;
        return true;
    }
    
    public String PrintMinNumber(int [] numbers) {
        for(int i=0;i<numbers.length;i++){
            for(int j=i;j<numbers.length;j++){
                if(!compareSmaller(numbers[i],numbers[j])){
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
                
            }
        }
        StringBuilder strb = new StringBuilder();
        for(int i=0;i<numbers.length;i++){
            strb.append(String.valueOf(numbers[i]));
        }
        return strb.toString();
    }
    
    public static void main(String[] args)  {
        Main m = new Main();
        System.out.println(m.PrintMinNumber(new int[]{3,32,321}));
    }
}

第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

public class Main{
    public int FirstNotRepeatingChar(String str) {
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c, 1);
            }
        }
        for(int i=0;i<str.length();i++){
            if(map.get(str.charAt(i))==1){
                return i;
            }
        }
        return -1;
    }
    
    public static void main(String[] args)  {
        Main m = new Main();
        System.out.println(m.FirstNotRepeatingChar("google"));
    }
}

数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

public class Solution {
    public long  InversePairsCore(int a[],int start,int end,int temp[]){
        if(start<end){
            int mid = (start+end)/2;
            long left = InversePairsCore(a,start,mid,temp);
            long right = InversePairsCore(a,mid+1,end,temp);
            int s = mid;
            int e = end;
            int i=0;
            long count=0;
            while(s>=start&&e>mid){
                if(a[s]>a[e]){
                    temp[i++] = a[s--];
                    count = (count+e-mid)%1000000007;
                }else{
                    temp[i++] = a[e--];
                }
            }
            while(s>=start){
                temp[i++] = a[s--];
            }
            while(e>mid){
                temp[i++] = a[e--];
            }
            for(int j=start;j<=end;j++,i--){
                a[j] = temp[i-1];
            }
            return (count+left+right)%1000000007;
        }else{
            return 0;
        }
    }
    
    public int InversePairs(int [] array) {
        int [] a = array.clone();
        int temp[] = new int[array.length];
        int out = (int)InversePairsCore(a,0,array.length-1,temp);
        return out%1000000007;
    }
}

翻转单词顺序列

public void reverse(char a[],int start,int end){
        while(start<end){
            char temp= a[start];
            a[start] = a[end];
            a[end] = temp;
            start++;end--;
        }
        
    }
    
    public String ReverseSentence(String str) {
        char[] a = str.toCharArray();
        reverse(a,0,str.length()-1);
        int last=0;
        int i=0;
        while(i<a.length){
            if(a[i]==' '){
                reverse(a,last,i-1);
                last = i+1;
            }
            i++;    
        }
        reverse(a,last,str.length()-1);
        return String.valueOf(a);
        
    }

扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

public class Solution {
    public boolean isContinuous(int [] numbers) {
        if(numbers.length==0) return false;
        Arrays.sort(numbers);
        int king = 0;
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i=0;i<numbers.length;i++){
            if(numbers[i]==0){
                king++;
            }else{
                if(set.contains(numbers[i])){//判断是否有重复
                    return false;
                }else{
                    set.add(numbers[i]);
                }
            }
        }
        if(king==numbers.length) return true;
        int min = numbers[king];
        int max = numbers[numbers.length-1];
        int count = 0;
        while(min<=max){
            if(!set.contains(min)) count++;
            min++;
        }
        if(count>king){
            return false;
        }else{
            return true;
        }
    }
}