剑指Offer 03比特位计数

只是记录

题目链接

题目链接

自己想出来的 第一种解法

思路简述

遍历[0,n]之间的数字，对于每一个数字按照二进制的方式展开，判断最低位置是否为1，若为1则+1，反之不加，直到该数字等于0就停止。

    public static  int[] countBits(int n) {int[] res = new int[n+1];res[0] = 0;for(int i=1;i<=n;i++){int t = i;int sum = 0;while (t>0){sum = sum + (t&1);t/=2;}res[i]=sum;}return res;}

时间复杂度：O（NlogN）
空间复杂度：O(N)

解法二 动态规划

我是没有想到的哈，我想到的是题目既然说有一种时间复杂度为O(N)的解法
我当时想到的是找数字和他们二进制数中含1的个数之间的规律。但冥思苦想了好久，实在想不出来，看别人的讲解

下面的推导过程
十进制 二进制 二进制中含1的个数
$000->000->0$
$001->001->1$
$002->010->1$
$003->0011->2$
$004->0100->1$
$005->0101->2$
$006->0110->2$
$007->0111->3$
$008->1000->1$
既然是偶数，那么一定可以将2左移一定次数后得到该偶数。我们假设左移1位的数字是n,不做任何操作的数字是n/2, 那么dp[n] = dp [n/2],
例如6和3，他们中的二进制数含1的个数是一样的
偶数解决了，奇数怎么办？奇数可以看成偶数+1，又因为偶数是dp[n]=dp[n/2],所以奇数直接就是dp[n]=dp[n/2]+1

好，递推公式搞定，接下来初始化问题，当n为0的时候，那么结果就是0，所以你不用初始化也可以

    public static  int[] countBits(int n) {int[] res = new int[n+1];res[0] = 0;for(int i=1;i<=n;i++){if(i % 2 == 0)res[i] = res[i/2];elseres[i] = res[i/2] + 1;}return res;}

搞定