题意
O(n)复杂度计算0到num每个数字二进制表示中1的个数。
思路
- 找出最优子结构：当计算二进制为n位的数字时，n-1位的所有情况已经计算过了
- 推出状态转移方程：ans[i] = ans[i>>1]+(i&1)
代码
1 2 3 4 5 6 7 8
| public class Solution { public int[] countBits(int num) { int[] ans = new int[num+1]; for(int i = 1;i <= num;i++) ans[i] = ans[i>>1]+(i&1); return ans; } }
|