剑指offer

(9)把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的
旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数
组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为 1.
(二分查找法找最小值，等两个index相差1的时候取小的那个)

int index1=0;
int index2=num.length()-1;
int indexMin=0;
while(num[index1]>num[index2]){
    if(index2-index1==1){
        indexMin=index2;
    }
    indexMin=index1+index2/2;
    if(num[index1]==num[index2]&&num[index1]==num[indexMin]){
        int min = num[0];
        for(int i=1;i<num.length;i++){
          if(num[i] > min){
            min = num[0]
          }
        }
        return min[0]
    }
    if(num[index1]<=num[indexMin]){
        index1=indexMin;
    }
    if(num[index2]>=num[indexMin]){
        index2=indexMin;
    }
return indexMin;
}

(10) 菲波那切数列数列的两种写法

long long fibonacci(int n ){
  if(n<= 0) return 0;
  if(n<= 1) return 1;
   return fibonacci(n-1)+fibonacci(n-2);

}

long long fibonacci(int n ){
   int[] nums = {1,0};
   if(n<2){
    return nums[n];
   }
    int zero = 0;
    int one = 1;
    int result=0;
    for(int i=2;i<n;i++){
        result=one+zero;
        zero=one;
        one=result;
    }
    return result;
}

(11)法1：循环的向右移动，判断有多少个一

int numberof(int n ){
  if(n==0){
    return 0;
  }
  int count=0;
 while(n){
  if(n&1)
     count++;
  
     n=n>>1
 }
 return count;
}

法2：用flag自己向左移动判断有多少给1

int numberof(int n ){
  if(n==0){
    return 0;
  }
  int flag=1;
 while(n){
  if(n&flag)
     count++;
  
    flag=flag<<1;
 }
 return count;
}

法3:把一个数减1，则最右的1变为0，若右边还有0也会变为0

int numberof(int n ){
  if(n==0){
    return 0;
  }
 while(n){
    count++;
    n=n&n-1;
 }
 return count;
}

(12)运用斐波那契数列的方法进行求一个数的次方的值

double PowerWithExponent(int base,int Exponent ){
        if(Exponent==0) return 0;
        if(Exponent==1) return base;
        result = PowerWithExponent(base,Exponent>>2);
        result*=result;
        //&1用于判断是否为整数
        if(Exponent&0x1==1){
        result*=base;
        }
        return result;
    }

（13）输入一个数n,打印n为的最大值，eg:n=3则输出999

public static void main(String[] args) {
        int n=3;
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < 3; i++) {
            sb.append(9);
        }
        String result = new String (sb);
        int num = Integer.parseInt(result);
        for(int i=0;i<=num;i++){
            System.out.println(i);
        }
    }

（14）给定单向链表的头指针和一个结点指针，定义一个函数在 O(1)时间删除
该结点。不能采用从头变量的方法，那样是O（N）只能从要被删除的节点入手。

    int deleteNode (ListNode headNode,ListNode deleteNode){
        if(headNode==null || deleteNode==null ) return null;
        if(headNode==deleteNode){headNode=null;} //删除头节点
        else{
               if(deleteNode.nextNode==null){
                    ListNode pointListNode = head;
                    //跳出条件为pointListNode后面第二个为空，
                    //也证明pointListNode到倒数第二个了。
                    while(pointListNode.nextNode.nextNode!=null){
                        pointListNode = pointListNode.nextNode;
                    }
                     pointListNode.nextNode=null;
               }else{
                    deleteNode.value = deleteNode.nextNode.value;
                    deleteNode.nextNode =deleteNode.nextNode.nextNode; 
               }        
        }
    
    }

（15）输入一个整数数组，实现一个函数来调整该函数数组中数字的顺序，使得
所有奇数位于数组的前半部分，所有的数组位于数组的后半部分。

private int order(int array[]){
        if(array==null||array.length==0)
            return;
        int start=0;
        int end=array.length-1;
        while(start<end){
           if(start<end&&（array[start]& 0x01）!=0) start++;
           if(start<end&&（array[end]& 0x01）==0) end--;  
           if(start<end){
              int temp = array[start];
              array[start]= array[end];
              array[end] =temp;
           }
        }   
    }

（16）输入一个链表，输出该链表中倒数第 k 个结点。为了符合大多数人的习惯，
本题从 1 开始计数，即链表的尾结点是倒数第一个结点。例如一个有 6 个结点的
链表，从头结点依次是 1,2,3,4,5,6。倒数第三个结点就是值为 4 的结点。
注意不要忽略边界条件。

ListNode findToTail(ListNode headNode ,int k ){
    if(headNode==null || k==0) return null;
    ListNode printNode=headNode;
    for(int i=0; i<k-1;i++){
        if(headNode.nextNode !=null){
            headNode=headNode.nextNode;
        }else{
            return null;    
        }
    }
    while (headNode.nextNode!=null)
    {
        headNode=headNode.nextNode
        printNode=printNode.nextNode;
    }
    return printNode;
}

（17）定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的
头结点。

    ListNode reverseList(ListNode head){
       if(head==null) return null;
       if(head.nextNode==null) return head;
       ListNode  preListNode=null;
       ListNode  nowListNode=null;
       ListNode  reversedListNode=null;
       while(nowListNode.nextNode!=null){
       //用于保存下一个节点
       ListNode nextListNode = nowListNode.nextNode
       if(nextListNode==null) reversedListNode=nextListNode;
       //把当前节点的上一个指针指向当前节点
        nowListNode.nextNode=preListNode;
        preListNode = nowListNode;
        nowListNode= nextListNode;
       }
    }

（18）输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按
照递增排序的。

ListNode merge(ListNode node1 ,ListNode node2){
    if(node1 == null) return node2;
    else if (node2 == null)
    {
        return node1;
    }
    ListNode mergeNode = null;
    if(node1.value < node2.value){
        mergeNode = node1;
        mergeNode.nextNode = merge(node1.nextNode,node2);
    }else {
        mergeNode = node2;
        mergeNode.nextNode  = merge(node1,node2.nextNode);
    }
    return mergeNode;
}

（19）输入两颗二叉树 A 和 B，判断 B 是不是 A 的子结构

    boolean hasSubTree(BinaryTreeNode root1,BinaryTreeNode root2){
        boolean result = false;
        if(root1!=null&&root2!=null){
            //DoseTree用于判断根节点相同的左右子树是否相等
            if(roo1.value==root2.value){ result=DoseTree(root1,root2)}
            //下面两个函数用于寻找左右子树中根节点相同的
            if(!result){
                result=hasSubTree(root1.nextNode,root2);
            }
            if(!result){
                result=hasSubTree(root1,root2.nextNode);
            }
        }       
        
        return result;
    }

    static boolean DoseTree(BinaryTreeNode root1,BinaryTreeNode root2){
        //如果root2先消耗完毕，那么就是找到了。
        if(root2==null){
            return true;
        }else if (root1=null){
            return false;
        }
        if(root1.value != root2.value){return false};
        return DoseTree(root1.leftNode,root2.leftNode)&&DoseTree(root1.rightNode,root2.rightNodeNode);
    }

（20） 请完成一个函数，输入一个二叉树，该函数输出它的镜像

    void MirrorRecursively(BinaryTreeNode pNode){
        if((pNode==null) ||  (pNode.leftNode=null &&pNode.rightNode=null)) return;
        BinaryTreeNode temp = pNode.leftNode;
        pNode.leftNode=pNode.rightNode;
        pNode.rightNode=temp;
        //对左右两颗子树进行递归
        if(pNode.leftNode!=null){MirrorRecursively(pNode.leftNode);}
        if(pNode.rightNode!=null){MirrorRecursively(pNode.rightNode);}
    }

（21） 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

    public void printMatixClokwisely(int[][] array){
        if(array==null) return;
        int start=0;
        while(array[0].length>start*2 && array.length>start*2 ){
            printOneCircle(array,start);
            //这个start++是关键，用于标志是否画完
            start++;
        }
        
    }
    static printOneCircle(int[][] array,int start){
        int columns = array[0].length;
        int rows=array.length;
        int endX = columns-1-start; //列
        int endY = rows-1-start;  //行
        //从左到右打印一行
        for(int i=start;i <=endY;i++){
            int number=numbers[start][i];
            printNumber(number);
        }
        //从上到下打印一列
        if(start< endY){
            for(int i = start+1;i <=endY ;++i){
                int number=numbers[i][endY];
                printNumber(number);
            }
            
        }
        //从右到左打印一行
        if(start<endX && start<endY){
            for(int i = end-1;i >=start ;--i){
                int number=numbers[endY][i];
                printNumber(number);
            }
        }
        //从下到上打印一列
        if(start<endX && start<endY-1){
            for(int i = end-1;i >=start+1 ;--i){
                int number=numbers[i][start];
                printNumber(number);
            }
        }
    }

（21） 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、 push及pop德尔时间复杂度都是O(1)

private Stack<Integer> datastack = new Stack<Integer>();
private Stack<Integer> minstack = new Stack<Integer>();
public void push(int value){
  datastack.push(value);
  if(value>minstack.head.value) minstack.push(value)
  else minstack.push(minstack.head.value);
}
public int  pop(){
    if(datastack!=null && minstack!=null){
        datastack.pop();    
    }
    return minstack.pop();
}

public int min(){
    if(minstack!=null&&minstack.length!=0){
        return minstack.pop().value;
    }else{
        return null;
    }
}

（23） 从上往下打印二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

public printFormTopToBottom(BinaryTreeNode root){
    if(root==null) return null;
    Queue<BinaryTreeNode> queue = new Queue<BinaryTreeNode>();
    queue.add(root);
    while (queue!=null)
    {
        BinaryTreeNode root = queue.poll();
                System.out.println(root.toString())
        if(root.leftNode!=null){
            queue.add(root.leftNode);
        }
        if(root.rightNode!=null){
            queue.add(root.rightNode);
        }
    }
}

（24）输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
是则返回true，否则返回false。

    public boolean verifySequenceOfBST(int[] sequeue){
        if(sequeue==null || sequeue.length=0){
            return fasle;
        }
        int length = sequeue.length();
        int root= sequeue[length-1];
        int cut=0;
        for(int i=0 ;i<length;i++){
            if(sequeue[i]>root){
             cut=i+1;
            }
        }
        if(cut==0){
            verifySequenceOfBST(Arrays.copyofRange(sequeue,0,length-1))
        }else{
            if(int i =cut;i<length;i++){
                if(sequeue[i]<root){
                    return false;
                }       
            }
        }
        boolean left =true;
        if(cut>0){
            left=verifySequenceOfBST(Arrays.copyofRange(sequeue,0,cut));
        }
        boolean rigth =true;
        if(cut<length){
            right=verifySequenceOfBST(Arrays.copyofRange(sequeue,cut,length-1));
        }

        return right&&left;
    }

（25）输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所
有路径。从树的根节点开始往下一直到叶结点所经过的结点形成一条路径。

    public void findPath(BinaryTreeNode root ,int sum){
        if(root==null) return;
        Stack<Integer> stack = new Stack<Integer>();
        int currentSum=0;
        //这个stack是用于记录数据的，用于输出路径
        findPath(root,sum,stack,currentSum);
    }
    private void findPath(BinaryTreeNode root,int sum ,Stack<Integer> stack,
    int currentSum){
        currentSum+=root.value;
        stack.push(root.value);
        if(root.leftNode==null && root.rightNode==null){
            if(currentSum==sum){
                for(int path:stack){syso(path);}
            }
        
        }
        if(root.leftNode!=null){
            findPath(root.leftNode,sum,stack,currentSum);
        }
        if(root.rightNode!=null){
            findPath(root.rightNode,sum,stack,currentSum);
        }
        //试探到最后，不是所求，则把stack中的值pop出去，并删除掉总值
        currentSum-=root.value;
        stack.pop();
    }

（26） 输入一个字符串，打印出该字符串中字符的所有排列。eg:abc输出它的全排列

public class problem1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        permutation(str,0);
    }

    private static void permutation(String str, int index) {
        char[] arr =str.toCharArray();
        if(index>str.length()){
            return;
        }else if(index==str.length()){
            System.out.println(String.valueOf(str));
        }else {
            for (int i = index; i < str.length(); i++) {
                char temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
                permutation(String.valueOf(arr), index + 1);
            }
        }
    }
}

（27） 数组中有一个数字出现次数超过数组长度的一半，请找出这个数字。例如
输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。 2出现的次数超过数组长度的
一半，因此输出2.

    public void cishu(int[] arr){
       Map<Integer,Integer> map=new HashMap<Integer,Integer>();
       for(int i=0;i<arr.length;i++){
           Intege num = map.get(arr[i]);
           map.put(arr[i],num=null?1:num+1);
       }
       for(Entry<Integer,Integer> entry:map.entrySet()){
            if(entity.getValue==1){
                System.out.print(entity.getkey);
            }
       }
    }

（30） 输入 n 个整数，找出其中最小的 k 个数。例如输入 4,5,1， 6,2,7,3,8 这
8 个数字，则最少的 4 个数字是 1,2,3,4.(用快排判断index)

    int start = 0;
    int end = n-1;
    int index = Partition(input,n,start,end);
    while(index ！=k-1){
        if(index > k-1){
            end=index-1;
            index=Partition(input,n,start,end);
        }
        else{
            start=index+1；
            index = Partition(input,n,start,end);
        }
        for(int i=0;i<k;++i){syso(i)}
    }

（30-1）针对上面方法提供一个求k个数的快排的算法

    private static int[] quickSort(int nums[],int start,int k){
        int begin = k-1;
        int end=nums.length-1;
        swap(nums,begin,end);
        int small = start-1;
        for(int index=start;index<end;++index){
            if(nums[start]<nums[end]){
                ++small;
                if(small !=index){
                    swap(nums,small,index);
                }
            }
        }
        ++small;
        swap(nums,small,end);
    }
    
    private static void swap(int[] arr, int index, int end) {
        int temp=arr[index];
        arr[index]=arr[end];
        arr[end]=temp;      
    }

（31）输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整
数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。 例
如输入的数组为{1,-2,3,10,-4,7,2,-5}，和最大的子数组为{3,10， -4,7,2}。

public int findGreatNumberOfArrays(int[] array){
    if(array=null) return null;
    int CurrentSum=0;
    int GreateSum=0;
    for(int i=0;i<array.length;i++){
        if(CurrentSum<0){
            CurrentSum=0;
        }else{
            CurrentSum+=array[i];
        }
        if(CurrentSum>GreateSum){
            GreateSum=CurrentSum;
        }
    }
}

（32）输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次
数。例如输入 12，这些整数中包含 1 的数字有 1,10,11,12， 1 一共出现了 5 次

    int NumberOfOne(int n ){
        int count;
        for (int i =0;i<=n ;i++ )
        {
            count+=One(i);
        }
    }
    public int One(int n ){
        int nums=0;
        if(n<=0) return 0;
        while (n!=0)
        {
            if(n%10==1) nums++;
            n/=10;
        }

    }

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

    private static void MaxNumberFunction(int[] arr){
        String s="";
        List<Integer> list = new ArrayList<Integer>();
        for(int i =0;i<arr.length;i++){
            list.add(i)
        }
        Collections.sort(list,new Comparator<Integer>()){
            String s1=str1+" "+str2;
            String s2=str2+" "+str1;
            return s1.compareTo(s2);
        }
        for(int result:list){
            System.out.print(result);
        }
    }

(34)我们把只包含因子 2,3,和 5 的称为丑数。求按从小到大的顺序的第 1500
个丑数。例如 6、 8 都是丑数，但 14 不是，因为它包含因子 7.习惯上我们把 1
当做第一个丑数。

    int multiply2=1;
    int multiply3=1;
    int multiply5=1;
    for(int i=1;i<uglyArray.length;i++){
        int min =min (multiply2*2,multiply3*3,multiply5*5);
        uglyArray[i] = min;
        while(multiply2*2<=min) multiply2++;
        while(multiply3*3<=min) multiply3++;
        while(multiply5*5<=min) multiply5++;
    }

(35)在字符串中找出第一个只出现一次的字符。如果输入“ abaccdeff”，则
输出‘ b’。

    public Charaster firstNotRepeatChar(String str){
        if(str==null) return null;
        char[] strChar = str.toCharArray();
        LinkedHashMap<Charaster,Integer> hash =  new LinkedHashMap<Charaster,Integer>();
        for(char item:strChar ){
            if(hash.containsKey(item)){
                hash.put(item,hash.get(item)+1);
            }else{
                hash.put(item,1);
            }
        }
        for(char key :hash.keySet())
         if(hash.get(key)==1)
        {
            System.out.print(key);
        }
    }

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

    public ListNode findFirstCommonNode(ListNode node1,ListNode node2){
        int len1 = getListLength(node1);
        int len2 = getListLength(node2);
        ListNode longListNode =null;
        ListNode shortListNode =null;
        int dif=0;
        if(len1>len2){
            longListNode=node1;
            shortListNode=node2;
            dif=len1-len2;
        }else{
            longListNode=node2;
            shortListNode=node1;
            dif=len2-len1;
        }
        for(int i=0;i<dif;i++){
            longListNode = longListNode.nextNode;
        }
        //当long等于short的时候，即找到的公共节点
        while(longListNode!=null && shortListNode!=null&& longListNode!=shortListNode ){
            longListNode=longListNode.nextNode;
            shortListNode=shortListNode.nextNode;
        }
        return longListNode;
    }
    public int getListLength(ListNode node){
        if(node==null){ return 0;}
        int result =0;
        ListNode point = node;
        while(point!=null){
            point=point.nextNode;
            result++;
        }
        return result;
    }

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

    pubic int treeDepth(BinaryTreeNode root){
        if(root==null) return 0;
        int left=treeDepth(root.leftNode);
        int right=treeDepth(root.rightNode);

        return left>right?left+1:right+1;
    }

(37-2)输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树
中任意结点的左右子树的深度相差不超过1，那么他就是一棵平衡二叉树。

    private boolean isBalanced(BinaryTreeNode root ,int depth){
        if(root==null){
            depth=0;
            return true;
        }
        int left=0,right=0;
        if(isBalanced(root.leftNode,left)&&isBalanced(root.rightNode,right)){
            int diff=left-right;
            if(diff<=1&&diff>=1){
                depth=1+(left>right?left:right);
                return true;
            }
        }
                return false;
    }

(38)输一个递增排序的数组和一个数字 s,在数组中查找两个数使得它们的
和正好是 s。如果有多对数字的和等于 s，输出任意一对即可。例如：输入数组
{1,2,4,7,11,15}和数字为 15.输出 4 和 11.

    public boolean findNunberWithSum(int[] data,int sum){
        int begin=0;
        int end =data.length-1;
        int num1=0,num2=0;
        //一定有个while条件，一般从是否为空，是否相等，大于小于入手
        while(start<end){
        int result=data[begin]+data[end]
        if(result==sum){
            num1=data[begin];
            num2=data[end];
        }
        if(result>sum){
            end--;
        }else{
            start++;
        }
        }
        

    }

(39)输入一个正数 s，打印出所有和为 s 的连续正数序列（至少含两个数）。
例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1-5、
4-6、和 7-8.

    public void findContinuesSequence(int sum){
        if(sum<3){
            return; 
        }
        int small=1;
        int big=2;
        int middle = 1+sum/2;
        int curSum=small+big;
        while (small<middle)
        {
            if(curSum==sum){
                print(small,big);
            }
            while(curSum>sum && start<middle){
                curSum-=small;
                small++;
                if(curSum==sum){
                    print(small,big);
                }
            }
            //这种是curSum<sum的情况
            big++;
            curSum+=big;
        }
    }

(40-1)输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
为简单起见，标点符号和普通字母一样处理。例如输入字符串“ I am a student.”，
则输出“ student. a am I”

    public String reverseString(String sentence){
        if(sentence==null) return;
        String[] str = sentence.spilt(" ");
        StringBuffer sb = new StringBuffer();
        int len = sentence.length()-1;
        for(int i =len ;i>=0;i--){
            sb.append(str[i]+" ");
        }
        return new String(sb);      
    }

(40-2)字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
请定义一个函数实现字符串左旋转操作的功能。比如输入字符串“ abcdefg”和
数字 2.该函数左旋转 2 位得到的结果“ cdefgab".

    public void leftRotateString(String sentence,int index){
        if(sentence==null || index>sentence.length() || index<0){return ;}
        String[] spiltString ={sentence.split(0,index),sentence.split(index,sentence.length())}
        StringBuffer sb = new StringBuffer();
        for(String s: spiltString){
            sb.appen(reverse(s));
        }
        System.out.print(reverse(new String(sb)));

    }
    public String reverse(String str){
        if(Str==null) return null;
        char[] arr = str.toCharArray();
        for(int i =0;i<arr.length()+1/2;i++){
            char temp = arr[i];
             arr[i] =  arr[arr.length()-1];
             arr[arr.length()-1-i] = temp;
        }
        return String.valueof(arr);
    }

(41)从扑克牌中随机抽 5 张牌，判断是不是顺子，即这 5 张牌是不是连续的。
2-10 为数字本身， A 为 1， J 为 11， Q 为 12， K 为 13，而大小王可以看成任意的
数字。

private static boolean isContinuous(int[] arrays) {
        if(arrays==null) return false; 
        int countOfZero = 0;
        Arrays.sort(arrays);
        for(int i = 0 ;i<arrays.length;i++){
            if(arrays[i]==0){
                countOfZero++;
            }
        }
        int small=countOfZero;
        int span=0;
        for(int j=small;j<arrays.length-1;j++){
            //因为下面有j+1所以要注意数组的越界
            if(arrays[j+1]==arrays[j]) return false;
            span+=(arrays[j+1]-arrays[j]-1);
        }
        return span>countOfZero?false:true;
    }

(42)0,1， ...,n-1 这 n 个数排成一个圆圈，从数字 0 开始每次从这个圆圈里
删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。、

    List list = new ArrayList();
    for(int i=0;i<n;i++){
        list.add(i);
    }
        int i=0;
        while(list.size()>1){
                //以删除2为例
        i=(i+2)%list.size();
        list.remove(i);
    }
    System.out.print(list.get(0));