题目

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

https://leetcode.cn/problems/counting-bits/description/

解法：动态规划

首先可以确定的是 ans[0] = 0。

当 1 <= i <= n 时，假设 j = i & (i - 1)，即 j 为 i 删除最低位后的值，如下表所示：

由上表可知，ans[i] = ans[j] + 1 = ans[i & (i - 1)] + 1，即 ans[i] 可以由 ans[j] 推导出来，且因为 0 <= j < i 所以计算 ans[i] 的时候 ans[j] 肯定已经计算过了，所以可以直接拿来用。

代码实现

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

本篇文章来源于微信公众号: i余数