正文
java实现《剑指offer》（二）11~20 更新中
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
11、二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
（1）最优解
public class Solution {
public int NumberOf1(int n) {
int count=0;
while(n!=0){
n = n&(n-1);
count++;
}
return count;
}
}
（2）
public class Solution {
public int NumberOf1(int n) {
int count=0;
int flag=1;
while(flag!=0){
if((n&flag)!=0){
count++;
}
flag = flag<<1;
}
return count;
}
}
（3）注意：>>>是右移补0的逻辑右移，>>是右移补符号位的算术右移
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!=0){
if((n&1)==1){
count++;
}
n = n>>>1;
}
return count;
}
}
12、数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
（1）
public class Solution {
public double Power(double base, int exponent) {
if(exponent==0) return 1;
if(exponent<0){
return 1/base*(Power(base, exponent+1));
}else{
return base*(Power(base, exponent-1));
}
}
}
（2） 递归求解
public class Solution {
public double Power(double base, int exponent) {
int n = Math.abs(exponent);
if(n==0) return 1;
if(n==1) return base;
double result = Power(base, n>>1);
result *= result;
//如果是奇数
if((n&1)==1)
result *= base;
if(exponent < 0)
result = 1/result;
return result;
}
}
13、调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
（1）
public class Solution {
public void reOrderArray(int [] array) {
int[] arr = new int[array.length];
int num = 0;
for(int i=0; i<array.length; i++){
if((array[i]%2)==1) {
arr[num] = array[i];
num++;
}
}
for(int i=0; i<array.length; i++){
if((array[i]%2)==0) {
arr[num] = array[i];
num++;
}
}
//由于aray变量在栈内存中，数组对象在堆内存，不能array=arr
for(int i=0; i<array.length; i++){
array[i] = arr[i];
}
}
}
14.链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
(1)
/*
public class ListNode {
int val;
ListNode next = null; ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode front = head;
int i=0;
for(; front != null && i<k; i++){
front = front.next;
}
if(i!=k) return null;
ListNode behind = head;
while(front!=null){
front = front.next;
behind = behind.next;
}
return behind;
}
}
15.输入一个链表，反转链表后，输出新链表的表头。
17.输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
public class Solution{
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root2==null) return false; //由题可知，B为空，不是A的子树
if(root1==null && root2!=null) return false; //如果A树为空，B树非空，则B不可能为A的子树
boolean flag = false;
if(root1.val==root2.val){
flag = isSubTree(root1,root2);
}
if(!flag){
flag = HasSubtree(root1.left, root2); //A树左子树是否含有B树
if(!flag){
flag = HasSubtree(root1.right, root2); //如果A树左子树没有，则查看A树右子树是否含有B树
}
}
return flag;
}
private boolean isSubTree(TreeNode root1, TreeNode root2) {
if(root2==null) return true; //B树走到这里还是null，那么B的根节点绝不为null，故为A的子树
if(root1==null && root2!=null) return false;
if(root1.val==root2.val){//不断向下比较
return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
}else{
return false;
}
}
}
18.操作给定的二叉树，将其变换为源二叉树的镜像。
import java.util.*;
public class Solution {
public void Mirror(TreeNode root) {
if(root == null) return;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()) {
TreeNode node = stack.pop(); //pop弹出元素并删除，peek只弹出元素不删
if(node.left != null || node.right != null) {
TreeNode nodeLeft = node.left;
TreeNode nodeRight = node.right;
node.left = nodeRight;
node.right = nodeLeft;
}
if(node.left != null) stack.push(node.left);
if(node.right != null) stack.push(node.right);
}
}
}
