汉明距离——还是求1的个数(二)

LeetCode_338_CountingBits

题目分析:

当然可以利用上题方法逐个求解。
题目提示我们思考能否利用已有结论进行推论。
其实就是dp了。
到数字i的时候,我们存储所有i之前的结果,尝试利用这些结果推导出i的值。
利用上一题结论,i & (i - 1) 正好是一个比i小,且比i少一个1的值。
写出方程就是:dp[i] = dp[i & (i - 1)] + 1

解法:

public static int[] countBits(int num) {
    int []res = new int[num + 1];
    for (int i = 1; i <= num; ++i) {
        res[i] = res[i & (i - 1)] + 1;
    }
    return res;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容