拓冰网站定制 
题目描述给你一个整数n对于0 i n中的每个i计算其二进制表示中1的个数返回一个长度为n 1的数组ans作为答案。不要使用内置函数来解决例如C 中的__builtin_popcount。示例 1输入n 2输出[0,1,1]解释0 -- 0 1 -- 1 2 -- 10示例 2输入n 5输出[0,1,1,2,1,2]解释0 -- 0 1 -- 1 2 -- 10 3 -- 11 4 -- 100 5 -- 101进阶很容易就能实现时间复杂度为O(n log n)的解决方案你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗解题思路方法一动态规划最低有效位核心思路对于任意整数ii 的二进制中 1 的个数 (i 1) 的二进制中 1 的个数 (i 1)因为i 1是i去掉最低位i 1是最低位是否为 1。代码实现class Solution { public: vectorint countBits(int n) { vectorint dp(n 1, 0); for (int i 1; i n; i) { dp[i] dp[i 1] (i 1); } return dp; } };具体过程示例n 5i二进制i1i1dp[i]00--01101dp[0]1121010dp[1]0131111dp[1]12410020dp[2]01510121dp[2]12结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(n)dp 数组不算输出的话是 O(1)方法二动态规划最高有效位核心思路找到小于等于i的最大 2 的幂highBitdp[i] dp[i - highBit] 1因为i比i - highBit多了一个最高位的 1。代码实现class Solution { public: vectorint countBits(int n) { vectorint dp(n 1, 0); int highBit 0; for (int i 1; i n; i) { if ((i (i - 1)) 0) { highBit i; // i 是 2 的幂 } dp[i] dp[i - highBit] 1; } return dp; } };具体过程示例n 5ihighBitdp[i]0-011dp[0]1122dp[0]1132dp[1]1244dp[0]1154dp[1]12结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(n)dp 数组方法三动态规划最低设置位核心思路dp[i] dp[i (i - 1)] 1因为i (i - 1)是i去掉最低位的 1所以dp[i]比它多 1。代码实现class Solution { public: vectorint countBits(int n) { vectorint dp(n 1, 0); for (int i 1; i n; i) { dp[i] dp[i (i - 1)] 1; } return dp; } };具体过程示例n 5ii(i-1)dp[i]0-010dp[0]1120dp[0]1132dp[2]1240dp[0]1154dp[4]12结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(n)dp 数组方法四暴力法O(n log n)核心思路对0到n中的每一个数单独统计它二进制表示中1的个数。统计单个数的 1 的个数对于一个整数num看它的最低位是不是1num 1把num右移一位num 1重复上述过程直到num 0例子num 5二进制101步骤numnum 1count11011121001311240-结束结果count 2代码实现class Solution { public: vectorint countBits(int n) { vectorint result(n 1, 0); for (int i 1; i n; i) { int count 0; int num i; while (num 0) { count num 1; num 1; } result[i] count; } return result; } };具体过程示例n 5i二进制统计过程count00-011111 → 012101010 → 111 → 013111111 → 111 → 02410010010 → 1010 → 111 → 01510110111 → 1010 → 111 → 02结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n log n)每个数最多遍历 log n 位空间复杂度O(n)结果数组缺点不是最优但容易理解。四种方法对比方法时间复杂度空间复杂度推荐度最低有效位O(n)O(n)⭐⭐⭐⭐⭐最高有效位O(n)O(n)⭐⭐⭐⭐最低设置位O(n)O(n)⭐⭐⭐⭐⭐暴力法O(n log n)O(n)⭐⭐总结要点说明核心思想利用i和i1或i(i-1)的关系递推最优解法最低有效位 / 最低设置位时间 O(n)关键公式dp[i] dp[i1] (i1) 【位运算-1】338.比特位计数
题目描述给你一个整数n对于0 i n中的每个i计算其二进制表示中1的个数返回一个长度为n 1的数组ans作为答案。不要使用内置函数来解决例如C 中的__builtin_popcount。示例 1输入n 2输出[0,1,1]解释0 -- 0 1 -- 1 2 -- 10示例 2输入n 5输出[0,1,1,2,1,2]解释0 -- 0 1 -- 1 2 -- 10 3 -- 11 4 -- 100 5 -- 101进阶很容易就能实现时间复杂度为O(n log n)的解决方案你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗解题思路方法一动态规划最低有效位核心思路对于任意整数ii 的二进制中 1 的个数 (i 1) 的二进制中 1 的个数 (i 1)因为i 1是i去掉最低位i 1是最低位是否为 1。代码实现class Solution { public: vectorint countBits(int n) { vectorint dp(n 1, 0); for (int i 1; i n; i) { dp[i] dp[i 1] (i 1); } return dp; } };具体过程示例n 5i二进制i1i1dp[i]00--01101dp[0]1121010dp[1]0131111dp[1]12410020dp[2]01510121dp[2]12结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(n)dp 数组不算输出的话是 O(1)方法二动态规划最高有效位核心思路找到小于等于i的最大 2 的幂highBitdp[i] dp[i - highBit] 1因为i比i - highBit多了一个最高位的 1。代码实现class Solution { public: vectorint countBits(int n) { vectorint dp(n 1, 0); int highBit 0; for (int i 1; i n; i) { if ((i (i - 1)) 0) { highBit i; // i 是 2 的幂 } dp[i] dp[i - highBit] 1; } return dp; } };具体过程示例n 5ihighBitdp[i]0-011dp[0]1122dp[0]1132dp[1]1244dp[0]1154dp[1]12结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(n)dp 数组方法三动态规划最低设置位核心思路dp[i] dp[i (i - 1)] 1因为i (i - 1)是i去掉最低位的 1所以dp[i]比它多 1。代码实现class Solution { public: vectorint countBits(int n) { vectorint dp(n 1, 0); for (int i 1; i n; i) { dp[i] dp[i (i - 1)] 1; } return dp; } };具体过程示例n 5ii(i-1)dp[i]0-010dp[0]1120dp[0]1132dp[2]1240dp[0]1154dp[4]12结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n)一次遍历空间复杂度O(n)dp 数组方法四暴力法O(n log n)核心思路对0到n中的每一个数单独统计它二进制表示中1的个数。统计单个数的 1 的个数对于一个整数num看它的最低位是不是1num 1把num右移一位num 1重复上述过程直到num 0例子num 5二进制101步骤numnum 1count11011121001311240-结束结果count 2代码实现class Solution { public: vectorint countBits(int n) { vectorint result(n 1, 0); for (int i 1; i n; i) { int count 0; int num i; while (num 0) { count num 1; num 1; } result[i] count; } return result; } };具体过程示例n 5i二进制统计过程count00-011111 → 012101010 → 111 → 013111111 → 111 → 02410010010 → 1010 → 111 → 01510110111 → 1010 → 111 → 02结果[0,1,1,2,1,2]✅复杂度分析维度复杂度说明时间复杂度O(n log n)每个数最多遍历 log n 位空间复杂度O(n)结果数组缺点不是最优但容易理解。四种方法对比方法时间复杂度空间复杂度推荐度最低有效位O(n)O(n)⭐⭐⭐⭐⭐最高有效位O(n)O(n)⭐⭐⭐⭐最低设置位O(n)O(n)⭐⭐⭐⭐⭐暴力法O(n log n)O(n)⭐⭐总结要点说明核心思想利用i和i1或i(i-1)的关系递推最优解法最低有效位 / 最低设置位时间 O(n)关键公式dp[i] dp[i1] (i1)