《LeetCode刷题》—338.比特位计算

《LeetCode刷题》—338.比特位计算

一、题目内容

原题连接：https://leetcode.cn/problems/counting-bits/submissions/

题目：

二、个人答案（Java）

思路：遇事不决for循环，一招鲜吃遍天（思路看注释）

代码：

class Solution01 {
    public int[] countBits(int n) {
        int[] arr = new int[n + 1];//定义需要的数组
        for (int i = 0; i <n+1 ; i++) {//外层循环异常遍历[0,n]
            int g=i;//取i的值，后续要变换
            int temp=0;//记录二进制为1个个数
            for (int j = 0; g!=0 ; j++) {//内存循环求二进制为1的个数
                if (g%2==1){//依次判断二进制的每一位，有一位为1就加一次此时
                    temp++;
                    g=g/2;//判断完要除以2
                }else {
                    g=g/2;
                }
            }
            arr[i]=temp;//外层循环结束一次，就赋值一次给数组
        }
        return arr;//返回该数组
    }
}

三、官方答案（Java）

前言：

方法一：Brian Kernighan 算法

代码：

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }

    public int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }
}

方法二：动态规划——最高有效位

代码：

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
}

方法三：动态规划——最低有效位

代码：

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}

方法四：动态规划——最低设置位

代码：

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i & (i - 1)] + 1;
        }
        return bits;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。