每日一题之《剑指offer》11，12题

未经允许，不得转载

前言

我做出的调整：
本来想一个月内刷完《剑指offer》所有Java代码并写完解析以提供自己复习，但是发现自己求量不求质的思想着实龌龊。这本书的题目每一道都值得深思，今天看到别人写的代码如此精妙美丽，而自己的却像一坨屎。我痛定思痛，决定改成每日一题的模式，把本书所有的代码及解法吃透。由于前十题，写的代码稀巴烂，在我更新好最后一题后，会重新写前十题。

第十一题

难易度：⭐

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
例如：
输入数字 9 ,9 的二进制表示为1001，所以 1 的个数为 2，结果输出 2

不需要算法的思路：
在Java中提供了 Integer.toBinaryString(n) 的方法，将一个数字转换为二进制的数后再转换为字符串，我们只需要将字符串转换为char数组依次遍历并统计字符'1' 的个数即可，但很显然这样做并不是面试官期待的做法

代码如下：

public class Solution {
    public int NumberOf1(int n) {
        String str = Integer.toBinaryString(n);
        char[] chars = str.toCharArray();
        int res = 0;
        for(int i = 0;i < chars.length; i++){
            if(chars[i] == '1'){
                res ++;
            }
        }
        return res;
    }
}

使用位运算
对数字1依次左移，直到左移至0为止。在左移的过程中同输入的数字n取 &,我们只需要判断取 & 的结果是否等于0，如果为0，说明该位上的数字是0，如果不等于 0 说明该位的数字为 1。
举例：

9 这个数字的二进制为 1001

0001 & 1001  结果不为 0  res++

将 0001 左移一位

0010 & 1001 结果为 0 

将 0010 左移一位

0100 & 1001 结果为 0

将 0100 左移一位

1000 & 1001 结果不为 0 res++
... ...
直到将最初的 1 移动至int的长度也就是32位 溢出为 0 为止

代码如下：

public class Solution {
    public int NumberOf1(int n) {
        int flag = 1;
        int res = 0;
        while (flag != 0) {
            if ((flag & n) != 0) {
                res++;
            }
            flag = flag << 1;
        }
        return res;
    }
}

本解法需要将数字1进行一个类型长度的左移运算，有没有办法做到不移动那么长的距离就可以得到结果呢？

最优解
结论：
n & (n - 1) 的结果是将 n的二进制数最右边的那个 1 变为 0
举例：

1101 & 1100  的结果为 1100 实际上就是将 1101最右边的1变成了 0
1010 & 1001 的结果为 1000 实际上就是将1010最右边的 1变成了0

对于这样一个结论，不妨试着自己证明一下，这里就不再给证明了。
有了这样的一个结论，我们就可以这样写代码:

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

这样我们就可以遍历 n 的二进制数中 1 的个数这样一个长度，就可以得到结果。

第十二题

难易度：⭐

给定一个double类型的浮点数base和int类型的整数exponent。
求base的exponent次方，要求不使用函数库中的方法

本题的重点是对于各种case的考察

首先，如果base和exponent均为 0 ，我们需要抛出异常
当 base 为 0 时，exponent无论正负结果均为 1

对于 exponent 来讲，有正数or负数两种情况：

exponent为正，我们需要遍历exponent 让 base自乘即可获得结果
exponent为负，我们需要对exponent取正后，在将得到的结果取倒数

理清各种case后，代码并不难：

public class Solution {

    public double Power(double base, int exponent) {
        if (base == 0 && exponent == 0) {
            throw new RuntimeException("base 与 exponent 不能同时为 0 ");
        }
        // base 为 0 ；无论exponent为正or负 结果均为0
        if (base == 0) {
            return 0;
        }
        // exponent 为负数时，结果为 对exponent取反的倒数
        if (exponent < 0) {
            return 1 / PowerWithUnsignedExponent(base, (-exponent));
        }else {
            return PowerWithUnsignedExponent(base,exponent);
        }
    }

    private double PowerWithUnsignedExponent(double base, int exponent) {
        double res = 1d;
        for (int i = 0; i < exponent; i++) {
            res *= base;
        }
        return res;
    }
}

但是本代码并不是最优解，对于上面的 PowerWithUnsignedExponent 方法有更优秀的写法

试想如果 exponent 为 32，我们上面的 PowerWithUnsignedExponent中要循环31次乘法运算。如果换一个思路思考：

32 = 16 * 16
16 = 8 * 8
8 = 4 * 4
... ...

不难想到，对于PowerWithUnsignedExponent 可以使用递归的思路
我们有如下公式：

最优解代码如下：

public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0 && exponent == 0) {
            throw new RuntimeException("base 与 exponent 不能同时为 0 ");
        }
        // base 为 0 ；无论exponent为正or负 结果均为0
        if (base == 0) {
            return 0;
        }
        // exponent 为负数时，结果为 对exponent取反的倒数
        if (exponent < 0) {
            return 1 / PowerWithUnsignedExponent(base, (-exponent));
        } else {
            return PowerWithUnsignedExponent(base, exponent);
        }
    }

    private double PowerWithUnsignedExponent(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        double res = PowerWithUnsignedExponent(base, exponent >> 1);
        res *= res;
        if ((exponent & 1) != 0) { // 等同于 exponent/ 2 ! = 0 
            res *= base;
        }
        return res;
    }
}