public class Solution {
public int[] CountBits(int num) {
var ary = new int[num + ]; for (int i = ; i <= num; i++)
{
var count = ;
var cur = i;
do
{
var c = cur % ;
if (c == )
{
count++;
}
cur = cur / ;
} while (cur != ); ary[i] = count;
} return ary;
}
}
https://leetcode.com/problems/counting-bits/#/description
另一个版本,246ms:
public class Solution
{
public int[] CountBits(int num)
{
int[] counts = new int[num + ];
for (int i = ; i <= num; i++)
{
int n = i;
int count = ;
while (n != )
{
if ((n & ) == )
{
count++;
}
n >>= ;
}
counts[i] = count;
}
return counts;
}
}
补充一个使用动态规划思想的代码,使用python实现:
class Solution:
def countBits(self, num: 'int') -> 'List[int]':
if num==0:
return [0]
elif num==1:
return [0,1]
else:
d = [0] * (num+1)
d[0] = 0
d[1] = 1
for i in range(2,num+1):
if i % 2 ==0:
d[i] = d[i//2]
else:
d[i] = d[i//2] + 1
return d