剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 #
- 标签:位运算、动态规划
- 难度:简单
题目大意 #
给定一个整数 n
。
要求:对于 0 ≤ i ≤ n
的每一个 i
,计算其二进制表示中 1
的个数,返回一个长度为 n + 1
的数组 ans
作为答案。
解题思路 #
可以根据整数的二进制特点将其分为两类:
- 奇数:一定比前面相邻的偶数多一个
1
。 - 偶数:一定和除以
2
之后的数一样多。 - 边界
0
:1
的个数为0
。
于是可以根据规律,从 0
开始到 n
进行递推求解。
代码 #
|
|