338. 比特位计数

港控/mmm° 2022-11-05 03:16 160阅读 0赞

##### 题目描述 #####

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

##### 示例一 #####

输入: 2
    输出: [0,1,1]

##### 示例二 #####

输入: 5
    输出: [0,1,1,2,1,2]

##### 解题思路 #####

**动态规划——最高有效位**

<table> 
 <thead> 
  <tr> 
   <th align="left">nums</th> 
   <th align="left">二进制</th> 
   <th align="left">个数</th> 
   <th align="left">结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left">0</td> 
   <td align="left">0</td> 
   <td align="left">0</td> 
   <td align="left"></td> 
  </tr> 
  <tr> 
   <td align="left">1</td> 
   <td align="left">01</td> 
   <td align="left">1</td> 
   <td align="left">2^0</td> 
  </tr> 
  <tr> 
   <td align="left">2</td> 
   <td align="left">10</td> 
   <td align="left">1</td> 
   <td align="left">2^1</td> 
  </tr> 
  <tr> 
   <td align="left">3</td> 
   <td align="left">0011</td> 
   <td align="left">2</td> 
   <td align="left">nums[i - 2] + 1</td> 
  </tr> 
  <tr> 
   <td align="left">4</td> 
   <td align="left">0100</td> 
   <td align="left">1</td> 
   <td align="left">2^2</td> 
  </tr> 
  <tr> 
   <td align="left">5</td> 
   <td align="left">0101</td> 
   <td align="left">2</td> 
   <td align="left">nums[i - 4] + 1</td> 
  </tr> 
  <tr> 
   <td align="left">6</td> 
   <td align="left">0110</td> 
   <td align="left">2</td> 
   <td align="left">nums[i - 4] + 1</td> 
  </tr> 
  <tr> 
   <td align="left">7</td> 
   <td align="left">0111</td> 
   <td align="left">3</td> 
   <td align="left">nums[i - 4] + 1</td> 
  </tr> 
  <tr> 
   <td align="left">8</td> 
   <td align="left">1000</td> 
   <td align="left">1</td> 
   <td align="left">2^3</td> 
  </tr> 
  <tr> 
   <td align="left">9</td> 
   <td align="left">1000</td> 
   <td align="left">1</td> 
   <td align="left">nums[i - 8] + 1</td> 
  </tr> 
  <tr> 
   <td align="left">10</td> 
   <td align="left">1000</td> 
   <td align="left">1</td> 
   <td align="left">nums[i - 8] + 1</td> 
  </tr> 
 </tbody> 
</table>

*  如果 i&(i−1)=0，则令 highBit=i，更新当前的最高有效位。
 *  i 比 i−highBit 的「一比特数」多 1，由于是从小到大遍历每个数，因此遍历到 i 时，i−highBit 的「一比特数」已知，令bits\[i\]=bits\[i−highBit\]+1。

**代码**

/** * @param {number} num * @return {number[]} */
    var countBits = function(num) { 
        const bits = new Array(num + 1).fill(0);
        let highBit = 0;
        for (let i = 1; i <= num; i++) { 
            if ((i & (i - 1)) == 0) { 
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-338. 比特位计数

目录题目思路动态规划题目来源 [338. 比特位计数][338.] 题目思路奇数：二进制表示中，奇数一定比前面那个偶数多一

小灰灰/ 2024年03月24日 14:42/ 0 赞/ 43 阅读

相关 338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。示例 1: 输入: 2

本是古典何须时尚/ 2023年10月05日 20:59/ 0 赞/ 4 阅读

相关 338. 比特位计数

题目： [338. 比特位计数][338.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

系统管理员/ 2022年11月27日 00:53/ 0 赞/ 163 阅读

相关 338. 比特位计数

题目描述给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。示例一输

港控/mmm°/ 2022年11月05日 03:16/ 0 赞/ 161 阅读

相关 LeetCode 338. 比特位计数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhp

梦里梦外;/ 2022年11月04日 14:24/ 0 赞/ 153 阅读

相关 338. 比特位计数

> 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 > > 示例 1: > > 输入:

柔情只为你懂/ 2022年10月08日 15:21/ 0 赞/ 165 阅读

相关 338. 比特位计数

题目描述给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

亦凉/ 2022年03月22日 14:00/ 0 赞/ 214 阅读

相关 LeetCode338——比特位计数

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

我会带着你远行/ 2022年01月24日 00:37/ 0 赞/ 195 阅读

相关 Leetcode338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。示例 1: 输入: 2 输出: \

水深无声/ 2021年12月07日 13:51/ 0 赞/ 225 阅读

相关 338.比特位计数

//给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 // // 示例 1: /

桃扇骨/ 2021年06月22日 15:38/ 0 赞/ 306 阅读