11.二進(jìn)制中1的個(gè)數(shù)
12.數(shù)值的整數(shù)次方
13.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
14.鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)
15.反轉(zhuǎn)鏈表
16.合并兩個(gè)排序的鏈表
17.樹的子結(jié)構(gòu)
18.二叉樹的鏡像
19.順時(shí)針打印矩陣
20.包含min函數(shù)的棧

11.二進(jìn)制中1的個(gè)數(shù)

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。

     public static int NumberOf1(int n) {
         String x=Integer.toBinaryString(n);
         int m=0;
         for(int i=0;i<x.length();i++)
             if(x.charAt(i)=='1')
                 m++;
         System.out.println(x);
         return m;
      }

如果一個(gè)整數(shù)不為0，那么這個(gè)整數(shù)至少有一位是1。如果我們把這個(gè)整數(shù)減1，那么原來處在整數(shù)最右邊的1就會變?yōu)?，原來在1后面的所有的0都會變成1(如果最右邊的1后面還有0的話)。其余所有位將不會受到影響。
舉個(gè)例子：一個(gè)二進(jìn)制數(shù)1100，從右邊數(shù)起第三位是處于最右邊的一個(gè)1。減去1后，第三位變成0，它后面的兩位0變成了1，而前面的1保持不變，因此得到的結(jié)果是1011.我們發(fā)現(xiàn)減1的結(jié)果是把最右邊的一個(gè)1開始的所有位都取反了。這個(gè)時(shí)候如果我們再把原來的整數(shù)和減去1之后的結(jié)果做與運(yùn)算，從原來整數(shù)最右邊一個(gè)1那一位開始所有位都會變成0。如1100&1011=1000.也就是說，把一個(gè)整數(shù)減去1，再和原整數(shù)做與運(yùn)算，會把該整數(shù)最右邊一個(gè)1變成0.那么一個(gè)整數(shù)的二進(jìn)制有多少個(gè)1，就可以進(jìn)行多少次這樣的操作。

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

12.數(shù)值的整數(shù)次方

給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。

13.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。
方法一
1.要想保證原有次序，則只能順次移動或相鄰交換。
2.i從左向右遍歷，找到第一個(gè)偶數(shù)。
3.j從i+1開始向后找，直到找到第一個(gè)奇數(shù)。
4.將[i,...,j-1]的元素整體后移一位，最后將找到的奇數(shù)放入i位置，然后i++。
5.終止條件：j向向后遍歷查找失敗。

       public void reOrderArray(int [] a) {
           if(a==null||a.length==0)
               return;
           int i=0,j;
           while(i<a.length){
               while(i<a.length&&!isEven(a[i]))
                   i++;
               j=i+1;
               while(j<a.length&&isEven(a[j]))
                   j++;
               if(j<a.length){
                   int tmp=a[j];
                   for(int k=j-1;k>=i;k--){
                       a[k+1]=a[k];
                   }
                   a[i++]=tmp;
               }else{//查找失敗
                   break;
               }
           }
       }
               
       boolean isEven(int n){
           if(n%2==0)
               return true;
           return false;
       }

方法二：
整體思路：
首先統(tǒng)計(jì)奇數(shù)的個(gè)數(shù)
然后新建一個(gè)等長數(shù)組，設(shè)置兩個(gè)指針，奇數(shù)指針從0開始，偶數(shù)指針從奇數(shù)個(gè)數(shù)的末尾開始 遍歷，填數(shù)

 public void reOrderArray2(int [] a) {
           if(a.length==0||a.length==1)
               return;
           int oddCount=0,oddBegin=0;
           int b[]=new int[a.length];
           for(int i=0;i<a.length;i++)
               if((a[i]&1)==1)
                   oddCount++;
           for(int i=0;i<a.length;i++){
               if((a[i]&1)==1)
                   b[oddBegin++]=a[i];
               else
                   b[oddCount++]=a[i];
           }
           for(int i=0;i<a.length;i++)
               a[i]=b[i];
       }

14.鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

//公共部分
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
     }
    }

方法一：兩個(gè)指針，先讓第一個(gè)指針和第二個(gè)指針都指向頭結(jié)點(diǎn)，然后再讓第一個(gè)指正走(k-1)步，到達(dá)第k個(gè)節(jié)點(diǎn)。然后兩個(gè)指針同時(shí)往后移動，當(dāng)?shù)谝粋€(gè)結(jié)點(diǎn)到達(dá)末尾的時(shí)候，第二個(gè)結(jié)點(diǎn)所在位置就是倒數(shù)第k個(gè)節(jié)點(diǎn)了

    public ListNode FindKthToTail(ListNode head,int k){
        if(head==null||k<=0)
            return null;
        ListNode pre=head;
        ListNode last=head;
        for(int i=1;i<k;i++){
            if(pre.next!=null)
                pre=pre.next;
            else
                return null;
        }
        while(pre.next!=null){
            pre=pre.next;
            last=last.next;
        }
        return last;
    }

方法二：全部進(jìn)棧然后出棧第k個(gè)

    public ListNode FindKthToTail2(ListNode head,int k) {
        if(head==null||k<=0)
            return null;
        Stack<ListNode> stack=new Stack<>();
        ListNode node=head;
        while(node!=null){          
            stack.push(node);
            node=node.next;
        }
        if(k>stack.size())
            return null;
        while(k!=1&&!stack.isEmpty()){
            stack.pop();
            k--;
            
        }
        return stack.pop();  
     }

15.反轉(zhuǎn)鏈表

輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
           this.val = val;
        }
    }
    
    public ListNode ReverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode pre=null;
        ListNode next=null;      
        while(head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }

16.合并兩個(gè)排序的鏈表

輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

    public class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
           this.val = val;
        }
    }

非遞歸方法

       public ListNode Merge(ListNode list1,ListNode list2) {
           ListNode head=new ListNode(-1);
           head.next=null;
           ListNode root=head;
           while(list1!=null&&list2!=null){
               if(list1.val<list2.val){
                   head.next=list1;
                   head=list1;
                   list1=list1.next;
               }else{
                   head.next=list2;
                   head=list2;
                   list2=list2.next;
               }
           }
           if(list1!=null)
               head.next=list1;
           if(list2!=null)
               head.next=list2;
           return root.next;
       }

遞歸方法

       public ListNode Merge(ListNode list1,ListNode list2) {
           if(list1==null)
               return list2;
           else if(list2==null)
               return list1;
           ListNode mergeHead=null;
           if(list1.val<list2.val){
               mergeHead=list1;
               mergeHead.next=Merge(list1.next,list2);
           }else{
               mergeHead=list2;
               mergeHead.next=Merge(list1,list2.next);
           }
           return mergeHead;
       }

17.樹的子結(jié)構(gòu)

輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）

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

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

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

18.二叉樹的鏡像

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

19.順時(shí)針打印矩陣

輸入一個(gè)矩陣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字，例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

       public ArrayList<Integer> printMatrix(int [][] array) {
           ArrayList<Integer> result=new ArrayList<Integer>();
           if(array.length==0)
               return result;
           int n=array.length,m=array[0].length;
           if(m==0)
               return result;
           int layers=(Math.min(n, m)-1)/2+1;
           for(int i=0;i<layers;i++){
               for(int k=i;k<m-i;k++)//左到右
                   result.add(array[i][k]);
               for(int j=i+1;j<n-i;j++)//右上到右下
                   result.add(array[j][m-i-1]);
               for(int k=m-i-2;(k>=i)&&(n-i-1!=i);k--)//右到左
                   result.add(array[n-i-1][k]);
               for(int j=n-i-2;(j>i)&&(m-i-1!=i);j--)//左上到左下
                   result.add(array[j][i]);
           }
           return result;
        }

20.包含min函數(shù)的棧

定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。

    private Stack<Integer> data=new Stack<Integer>();
    private Stack<Integer> min=new Stack<Integer>();
    Integer temp=null;
    public void push(int node) {
            if(temp!=null){
                if(node<=temp){
                    temp=node;
                    min.push(node);
                }
                data.push(node);
            }else{
                temp=node;
                data.push(node);
                min.push(node);
            }
        }
        
        public void pop() {
            int num=data.pop();
            int num2=min.pop();
            if(num!=num2)
                min.push(num2);
        }
        
        public int top() {
            return data.peek();
        }
        
        public int min() {
            return min.peek();
        }