《剑指offer》java实现（二）11~20 更新中

11、二进制中1的个数

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

（1）最优解

 1 public class Solution {
 2     public int NumberOf1(int n) {
 3         int count=0;
 4         while(n!=0){
 5             n = n&(n-1);
 6             count++;
 7     }
 8         return count;
 9     }
10  }

（2）

 1 public class Solution {
 2     public int NumberOf1(int n) {
 3         int count=0;
 4         int flag=1;
 5         while(flag!=0){
 6             if((n&flag)!=0){
 7                 count++;
 8             }
 9             flag = flag<<1;
10         }
11         return count;
12     }
13 }

（3）注意：>>>是右移补0的逻辑右移，>>是右移补符号位的算术右移

 1 public class Solution {
 2     public int NumberOf1(int n) {
 3         int count = 0;
 4         while(n!=0){
 5             if((n&1)==1){
 6                 count++;
 7             }
 8             n = n>>>1;
 9         }
10         return count;
11     }
12 }

12、数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

（1）

 1 public class Solution {
 2     public double Power(double base, int exponent) {
 3         if(exponent==0) return 1;
 4         if(exponent<0){
 5             return 1/base*(Power(base, exponent+1));
 6         }else{
 7             return base*(Power(base, exponent-1));
 8         }
 9     }
10 }

（2）递归求解

 1 public class Solution {
 2     public double Power(double base, int exponent) {
 3         int n = Math.abs(exponent);
 4         
 5         if(n==0) return 1;
 6         if(n==1) return base;
 7         
 8         double result = Power(base, n>>1);
 9         result *= result;
10         //如果是奇数
11         if((n&1)==1)
12             result *= base;
13         if(exponent < 0)
14             result = 1/result;
15         return result;
16   }
17 }

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

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

（1）

 1 public class Solution {
 2     public void reOrderArray(int [] array) {
 3         int[] arr = new int[array.length];
 4         int num = 0;
 5         for(int i=0; i<array.length; i++){
 6             if((array[i]%2)==1) {
 7                 arr[num] = array[i];
 8                 num++;
 9             }
10         }
11         for(int i=0; i<array.length; i++){
12             if((array[i]%2)==0) {
13                 arr[num] = array[i];
14                 num++;
15             }
16         }
17         //由于aray变量在栈内存中，数组对象在堆内存，不能array=arr      
18         for(int i=0; i<array.length; i++){
19             array[i] = arr[i];
20         }
21     }
22 }

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

输入一个链表，输出该链表中倒数第k个结点。

(1)

 1 /*
 2 public class ListNode {
 3     int val;
 4     ListNode next = null;
 5 
 6     ListNode(int val) {
 7         this.val = val;
 8     }
 9 }*/
10 public class Solution {
11     public ListNode FindKthToTail(ListNode head,int k) {
12         ListNode front = head;
13         int i=0;
14         for(; front != null && i<k; i++){
15             front = front.next;
16         }
17         if(i!=k) return null;
18         ListNode behind = head;
19         while(front!=null){
20             front = front.next;
21             behind = behind.next;
22         }
23         return behind;
24     }
25 }

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

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

 1 public class Solution{
 2     public boolean HasSubtree(TreeNode root1,TreeNode root2) {
 3         if(root2==null) return false; //由题可知，B为空，不是A的子树
 4         if(root1==null && root2!=null) return false; //如果A树为空，B树非空，则B不可能为A的子树  
 5         boolean flag = false;
 6         if(root1.val==root2.val){
 7             flag = isSubTree(root1,root2);
 8         }
 9         if(!flag){
10             flag = HasSubtree(root1.left, root2); //A树左子树是否含有B树
11             if(!flag){
12                 flag = HasSubtree(root1.right, root2); //如果A树左子树没有，则查看A树右子树是否含有B树
13             }
14         }
15         return flag;
16     }
17        
18     private boolean isSubTree(TreeNode root1, TreeNode root2) {
19         if(root2==null) return true; //B树走到这里还是null，那么B的根节点绝不为null，故为A的子树
20         if(root1==null && root2!=null) return false;      
21         if(root1.val==root2.val){//不断向下比较
22             return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
23         }else{
24         return false;
25         }
26     }
27 }

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

 1 import java.util.*;
 2 public class Solution {
 3     public void Mirror(TreeNode root) {
 4         if(root == null) return;
 5         Stack<TreeNode> stack = new Stack<TreeNode>();
 6         stack.push(root);
 7         while(!stack.empty()) {
 8             TreeNode node = stack.pop(); //pop弹出元素并删除，peek只弹出元素不删
 9             if(node.left != null || node.right != null) {
10                 TreeNode nodeLeft = node.left;
11                 TreeNode nodeRight = node.right;
12                 node.left = nodeRight;
13                 node.right = nodeLeft;
14             }
15             if(node.left != null) stack.push(node.left);
16             if(node.right != null) stack.push(node.right);
17         }
18     }
19 }