首页 > 代码库 > LeetCode 338. Counting Bits

LeetCode 338. Counting Bits

转载请注明出处:http://www.cnblogs.com/liangyongrui/p/6350267.html 

 

我用了一个很蹩脚的做法做出来了。

虽然也是O(n) 但是看了标算后,感觉自己的dp实在是不够敏感

 

我的做法就是堆基底(1 2 4 8 16 32...)

public class Solution {
    public void dfs(int[] ans, int num, int idx, int cnt, int num222) {
        for (int i = idx + 1; (1 << i) <= num222; i++) {
            dfs(ans, num + (1 << i), i, cnt + 1, num222);
        }
        if (num <= num222)
            ans[num] = cnt;
    }

    public int[] countBits(int num) {
        int[] ans = new int[num + 1];
        for (int i = 0; (1 << i) <= num; i++) {
            dfs(ans, (1 << i), i, 1, num);
        }
        return ans;
    }
}

 

 

但是用了dp的思想后,都是三行就搞定了

法一:

public int[] countBits(int num) {
    int[] f = new int[num + 1];
    for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
    return f;
}

这个简单的递推,谁都能看懂。

 

法二:

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num+1, 0);
        for (int i = 1; i <= num; ++i)
            ret[i] = ret[i&(i-1)] + 1;
        return ret;
    }
};

 

这里的i & (i-1) 很巧妙,

i & (i-1) 就是得到了 把二进制数 去掉最后一个1 的数字

只管的理解就是,如果一个末尾有0的数(没有0也是一样的)-1的话,就会把末尾的所有0都变成1,而最后一个1变成了0,

然后和源数字相与,就会得到把原数的二进制 最后一个1变成0 的数字

 

这样的话,得到的数的1的个数+1,就得到了,这个数的1的个数。

真巧妙,想不出,只能积累了。。。

LeetCode 338. Counting Bits