Day 6

剑指offer 15.二进制中1的个数

题目描述

解答

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count=0;
        while(n!=0){
         // n & (n-1)可以将n的从左往右数的最后一位1变成0
            n=n & (n-1);
            count++;
        }
        return count;
    }
}
// 时间复杂度  O(logn)
// 空间复杂度  O(1)

剑指offer 16.数值的整数次方

题目描述

解答一

class Solution {
    public double myPow(double x, int n) {
        double pow=1;
        for(int i=0;i<Math.abs(n);i++){
            pow*=x;
        }
         return n>0?pow:1.0/pow;
    }
}

很可惜，以上解法超出时间限制

解答二

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
        // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
         // 将贡献不断地平方
            x_contribute *= x_contribute;
        // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }
}

// 时间复杂度  O(logn)
// 空间复杂度  O(1)