11、二进制中1的个数
12、数值的整数次方
13、调整数组顺序使奇数位于偶数前面
14、链表中倒数第k个结点
15、反转链表
16、合并两个排序的链表
17、树的子结构
18、二叉树的镜像
20、包含min函数的栈

11、二进制中1的个数

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

解法一

找一个标志位1，从最右边开始和这个二进制数做&运算，每个不为0的与结果就表明出现了一个1

public class Solution {
public int NumberOf(int n) {
   int t = 0;
   int flag = 1;
   while(flag != 0){
       if((n&flag)!=0){
           t++;
       }
       flag = flag << 1; //当位运算到最大值(32位)时，回到0，跳出循环
   }
   return t;
}
}

解法二

一个二进制数1100，从右边数起第三位是处于最右边的一个1,
减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，
因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。
这个时候如果我们再把原来的整数和减去1之后的结果做与运算，
从原来整数最右边一个1那一位开始所有位都会变成0。
如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0
那么一个整数的二进制有多少个1，就可以进行多少次这样的操作

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

12、数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方
保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数

解法一

直接暴力求解

先对指数进行处理，指数为负数，则底数base变成1/base，exponent=-exponent

public class Solution {
public double Power(double base, int exponent) {
   if(exponent<0){
       base = 1/base;
       exponent = -exponent;
   }
   double result = 1;
   for(int i=0;i<exponent;i++){
       result = result*base;
   }
   return result;
}
}

解法二

主要是讨论指数大于0，等于0，小于0 以及底数为0时的情况

/**
* 1.全面考察指数的正负、底数是否为零等情况
* 2.写出指数的二进制表达，例如13表达为二进制1101
* 3.举例:10^1101 = 10^0001 * 10^0100 * 10^1000
* 4.通过&1和>>1来逐位读取1101，为1时将该位代表的乘数累乘到最终结果
*/

public class Solution {
public double Power(double base, int exponent) {
   double res = 1,curr = base;
   int temp; //temp对指数进行处理，若为负数，转换为正指数
   if(exponent>0){
       temp = exponent;
   }else if(exponent<0){
       if(base==0)
           throw new RuntimeException("分母不能为0"); 
       temp = -exponent;
   }else{// exponent==0
       return 1;// 0的0次方
   }
   while(temp!=0){
       if((temp&1)==1)
           res*=curr;
       curr*=curr;// 翻倍
       temp>>=1;// 右移一位
   }
   return exponent>=0?res:(1/res);  
}
}

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

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

解法一

使用辅助数据，遍历数组，将奇数添加到数据里面；再次遍历数组，将偶数添加到数组里面

import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param array int整型一维数组 
* @return int整型一维数组
*/
public int[] reOrderArray (int[] array) {
   // write code here
   int[] temp = new int[array.length];
   int t = 0;
   for(int i=0;i<array.length;i++){
       if(array[i]%2 == 1){
           temp[t++] = array[i];
       }
   }
   for(int i=0;i<array.length;i++){
       if(array[i]%2 == 0){
           temp[t++] = array[i];
       }
   }
   return temp;
}
}

14、链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点
如果该链表长度小于k，请返回空

解法一，遍历列表，通过算术计算出这是正数第几个结点 ```java import java.util.; /
- public class ListNode {
- int val;
- ListNode next = null;
- public ListNode(int val) {
- this.val = val;
- }
- } */

public class Solution { /**

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
public ListNode FindKthToTail (ListNode pHead, int k) {
    // write code here
    int length = 0;
    ListNode temp = pHead;
    while(temp != null){
        length++;
        temp = temp.next;
    }
    if(length < k){
        return null;
    }
    int key = length - k;
    temp = pHead;
    while(key>0){
        temp = temp.next;
        key--;
    }
    return temp;
}

}


- 解法二
   - 快慢指针，快指针先走k步，假如还未到k步就为空，就返回空；否则，在快指针走了k步后，快慢指针同时走，直到快指针为空，返回慢指针
```java
import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead == null){
            return pHead;
        }
        ListNode fast = pHead;
        int i = 0;
        while(i < k){
            if(fast == null){
                return fast;
            }
            i++;
            fast = fast.next;
        }
        ListNode slow = pHead;
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

15、反转链表

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

解法一

定义三个指针，第1个指针和第2个指针为待处理指针指向的前后指针，第3个指针为正准备处理的链表尾部

/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
   this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
   if(head == null){
       return head;
   }
   ListNode left = head;
   ListNode mid = left.next;
   if(mid == null){
       return head;
   }
   ListNode right = mid.next;
   head.next = null;
   while(right != null){
       mid.next = left;
       left = mid;
       mid = right;
       right = right.next;
   }
   mid.next = left;
   return mid;
}
}

与解法一类似，更巧妙

/*
public class ListNode {
  int val;
  ListNode next = null;
  ListNode(int val) {
      this.val = val;
  }
}*/
public class Solution {
  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、合并两个排序的链表

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

解法一

递归：怎么理解呢，为啥想不上来

从两个头结点中取出小数，那么它的下一个结点就是剩下的链表继续合并，跳出递归是：list1为空，返回剩下的list2；list2为空，返回的是剩下的list1

/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
   this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
   if(list1 == null){
       return list2;
   }
   if(list2 == null){
       return list1;
   }
   if(list1.val <= list2.val){
       list1.next = Merge(list1.next,list2);
       return list1;
   }else{
       list2.next = Merge(list1,list2.next);
       return list2;
   }
}
}

解法二

合并时，每次取出链表小的结点，最后将剩下的不为空的链表接上去即可

public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
   //注意传入参数就为空，参数在后端来说，都是不被信任的
   if(list1 == null){
       return list2;
   }
   if(list2 == null){
       return list1;
   }
   ListNode head = null;  //合并后头指针
   ListNode current = null;  //正在处理的结点指针
   if(list1.val <= list2.val){  //找到头指针
       head = current = list1;
       list1 = list1.next;
   }else{
       head = current = list2;
       list2 = list2.next;
   }
   while(list1 != null && list2!= null){
       if(list1.val <= list2.val){
           current.next = list1;
           list1 = list1.next;
           current = current.next;  //注意正在处理指针后移
       }else{
           current.next = list2;
           list2 = list2.next;
           current = current.next;
       }
   }
   if(list1 != null){
       current.next = list1;
   }
   if(list2 != null){
       current.next = list2;
   }
   return head;
}
}

17、树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

什么时候是子结构的开始

树问题解法好多需要递归来解决

比较根节点，比较左子树，比较右子树

/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
   this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
   boolean result = false;
   //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
   if (root2 != null && root1 != null) {
       //如果找到了对应Tree2的根节点的点
       if(root1.val == root2.val){
           //以这个根节点为为起点判断是否包含Tree2
           result = doTree1HaveTree2(root1,root2);
       }
       //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
       if (!result) {
           result = HasSubtree(root1.left,root2);
       }
       //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
       if (!result) {
           result = HasSubtree(root1.right,root2);
          }
       }
       //返回结果
   return result;
}
public static boolean doTree1HaveTree2(TreeNode node1, TreeNode node2) {
   //如果Tree2已经遍历完了都能对应的上，返回true
   if (node2 == null) {
       return true;
   }
   //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
   if (node1 == null) {
       return false;
   }
   //如果其中有一个点没有对应上，返回false
   if (node1.val != node2.val) {  
           return false;
   }
   //如果根节点对应的上，那么就分别去子节点里面匹配
   return doTree1HaveTree2(node1.left,node2.left) && doTree1HaveTree2(node1.right,node2.right);
}
}

18、二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像

解法
- 使用递归
  - 先判断根节点，若根节点为null或者是单个结点则直接返回
  - 处理根节点的左子树
  - 处理根节点的右子树 ```java import java.util.*;

public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
} */

public class Solution { /**

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @param pRoot TreeNode类 
 * @return TreeNode类
 */
public TreeNode Mirror (TreeNode pRoot) {
    // 递归结束条件
    if(pRoot == null){
        return pRoot;
    }
    if(pRoot.left == null && pRoot.right == null){
        return pRoot;
    }
    // 交换根节点的左右儿子
    TreeNode temp = pRoot.left;
    pRoot.left = pRoot.right;
    pRoot.right = temp;
    Mirror(pRoot.left);
    Mirror(pRoot.right);
    return pRoot;
}

}

<a name="bcTrz"></a>
# 19、顺时针打印矩阵
```java
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
例如，如果输入如下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

解法

定义四个变量表示边界范围，其中up、down表示上下边界，left、right表示左右边界。不断收缩边界范围

首先向右遍历，将找到的数加入到集合中，并且边界值up++，如果边界值up大于down，跳出循环
其次向下遍历，将找到的数加入到集合中，并且边界值right—，如果边界值left大于right，跳出循环
其次向左遍历，将找到的数加入到集合中，并且边界值down—，如果边界值up大于down，跳出循环
最后向上遍历，将找到的数加入到集合中，并且边界值left++，如果边界值left大于right，跳出循环

循环遍历下去

import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
    return list;
}
int up = 0;
int down = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
while(true){
    for(int col = left; col<=right;col++){
        list.add(matrix[up][col]);
    }
    up++;
    if(up > down){
        break;
    }
    for(int row = up; row<=down;row++){
        list.add(matrix[row][right]);
    }
    right--;
    if(left > right){
        break;
    }
    for(int col = right; col>=left;col--){
        list.add(matrix[down][col]);
    }
    down--;
    if(up > down){
        break;
    }
    for(int row = down; row>=up;row--){
        list.add(matrix[row][left]);
    }
    left++;
    if(left > right){
        break;
    }
}
return list;
}
}

20、包含min函数的栈

定义栈的数据结构，
请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））

用空间换时间
- 使用一个辅助栈minStack来存最小值
  - 如果此时的数据小于minStack的栈顶，则允许存入该值，否则把minStack的栈顶重新存一遍到minStack
  - push，push数据到stack；如果辅助栈minStack为null，则数据push到minStack，否则数据小于minStack的栈顶时，则允许存入该值，不然把minStack的栈顶重新存一遍到minStack
  - pop，直接弹出两个栈
  - top，返回stack的栈顶
  - min，返回minStack的栈顶 ```java import java.util.Stack;

public class Solution {

private static Stack<Integer> stack = new Stack<Integer>();
private static Stack<Integer> minStack = new Stack<Integer>();
public void push(int node) {
    stack.push(node);
    if(minStack.empty()){
        minStack.push(node);
    }else{
        if(node <= minStack.peek()){
            minStack.push(node);
        }else{
            minStack.push(minStack.peek());
        }
    }
}
public void pop() {
    stack.pop();
    minStack.pop(); //弹出栈顶，做删除
}
public int top() {
    return stack.peek(); //弹出栈顶，不做删除
}
public int min() {
    return minStack.peek();
}

} ```

算法

11-20题