剑指 Offer（第 2 版）7/7 14-17

1.剑指 Offer 15. 二进制中1的个数 简单

二进制知识

 public class Solution {
    
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
    
            int ans = 0;
            while (n != 0){
    
                ans++;
                //n & (n - 1) -》 消除最后一位1
                n = n & (n - 1);
            }
            return ans;
        }
    }

2.剑指 Offer 16. 数值的整数次方 中等

方法一：快速幂 迭代
有空间复杂度
注意点：Math.abs(n) n取整数最小值的情况

 class Solution {
    
        public double myPow(double x, int n) {
    
            //n转换位long类型，防止Math.abs越界，当n位整数最小值时abs方法会越界
            long tempN = n;
            long absN = Math.abs(tempN);
            //将原本的O(N) 时间复杂度 降为 O(LogN)
            List<Integer> list = new ArrayList<>();
            while (absN > 0) {
    
                if (absN % 2 == 0) list.add(0);
                else list.add(1);
                absN = absN / 2;
            }
            double ret = 1;
            for (int i = list.size() - 1; i >= 0; i--) {
    
                if (list.get(i) == 0) ret *= ret;
                else ret = ret * ret * x;
            }
            return n > 0 ? ret : 1 / ret;
        }
    }

方法二：快速幂 递归

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) {
    
        if (N == 0) {
    
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

方法三：快速幂 迭代
无空间复杂度
根据此题二进制的特点

class Solution {
    
        public double myPow(double x, int n) {
    
            //注意第二个参数 不能些 -n
            //必须要先转换为long 类型再添负号
            return n > 0 ? quickPow(x,n) : 1 / quickPow(x,-((long) n));
        }
        public double quickPow(double x,long n){
    
            double ans = 1;
            double contribute = x;
            while (n > 0){
    
                if ((n & 1) == 1){
    
                    //此位为1才纳入贡献
                    ans *= contribute;
                }
                contribute *= contribute;
                n = n >> 1;
            }
            return ans;
        }
    }

3.剑指 Offer 17. 打印从1到最大的n位数 简单

class Solution {
    
    public int[] printNumbers(int n) {
    
        int end = (int)Math.pow(10, n) - 1;
        int[] res = new int[end];
        for(int i = 1; i <= end; i++)
            res[i-1] = i;
        return res;
    }
}

4.剑指 Offer 24. 反转链表 简单

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
 class Solution {
    
        public ListNode reverseList(ListNode head) {
    
            ListNode node = new ListNode(0);
            while (head != null){
    
                ListNode temp = head.next;
                head.next = node.next;
                node.next = head;
                head = temp;
            }
            return node.next;
        }
    }