題目

給定一個(gè)非負(fù)整數(shù) n ，請(qǐng)計(jì)算 0 到 n 之間的每個(gè)數(shù)字的二進(jìn)制表示中 1 的個(gè)數(shù)，并輸出一個(gè)數(shù)組。

示例 1:

輸入: n = 2
輸出: [0,1,1]
解釋:
0 --> 0
1 --> 1
2 --> 10

題解

• 題解一
  本體最直觀的想法是，求每個(gè)數(shù)的二進(jìn)制位個(gè)數(shù)，如下：`

int count_1(int n){int index = 1, res = 0;while (n > 0){//將n的最后一位1置0n &= (n - 1);res++;}return res;}vector<int> countBits(int n) {vector<int> res(n+1);for(int i = 0; i <= n; ++i)res[i] = count_1(i);return res;}

時(shí)間復(fù)雜度n*logn

• 題解二 動(dòng)歸思路，參考力扣官方題解
  // leecode官方題解 最低設(shè)置位
  // 最低設(shè)置位定義為整數(shù)x的最低為1的位置 如10(1010)的最低設(shè)置位為2
  // 令y = x & (x - 1),則y變?yōu)?000，相當(dāng)于將x的最低設(shè)置位置0
  // 可以發(fā)現(xiàn) x的比特位比y大一，且x > y，由此推出等式 bits[i] = bits[i & (i - 1)] + 1;

vector<int> countBits(int n) {vector<int> bits(n + 1);for (int i = 1; i <= n; i++) {bits[i] = bits[i & (i - 1)] + 1;}return bits;} 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的剑指Offer Ⅱ 003.二进制加法(力扣剑指Offer专项突击版——整数_3)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。