每日一题 338. 比特位计数

338. 比特位计数

难点是发现规律

1. class Solution {
2. public:
3.     vector<int> countBits(int n) {
4.         
5.         vector<int> dp(n+1,0);
6.         if(n <=0)
7.         {
8.             return dp;
9.         }
10.         dp[1] = 1;
11.         if(n == 1)
12.         {
13.             return dp;
14.         }
15.         int bin = 0;
16.         for(int i=2;i<=n;++i)
17.         {
18.             int base = getBinary(i);
19.             dp[i] = dp[i-(1<<base)] + 1;
20.         }
21.         return dp;
22.     }
24.     int getBinary(int num)
25.     {
26.         int ret = 0;
27.         while( num != 0)
28.         {
29.             num  = num >> 1;
30.             ++ret;
31.         }
32.         return ret-1;
33.     }
34. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。