网站设计技能培训,网站搭建分站需要多少钱,网站的建设主题,网站在线提交询盘系统 能直接发到邮箱本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个整数 n 对于 0 i n 中的每个 i 计算其二进制表示中 1 的个数 返回一个长度为 n 1 的数组 ans 作为答案。
示例 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提示
0 n 10^5
进阶
很容易就能实现时间复杂度为 O(n log n) 的解决方案你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗你能不使用任何内置函数解决此问题吗如C 中的 __builtin_popcount 这道题需要计算从 0 0 0 到 n n n 的每个整数的二进制表示中的 1 1 1 的数目。
部分编程语言有相应的内置函数用于计算给定的整数的二进制表示中的 1 1 1 的数目例如 Java 的 Integer.bitCount C 的 __builtin_popcount 。下列各种方法均为不使用内置函数的解法。
为了表述简洁下文用「一比特数」表示二进制表示中的 1 1 1 的数目。 解法1 B r i a n K e r n i g h a n Brian Kernighan BrianKernighan 算法
最直观的做法是对从 0 0 0 到 n n n 的每个整数直接计算「一比特数」。每个int型的数都可以用 32 32 32 位二进制数表示只要遍历其二进制表示的每一位即可得到 1 1 1 的数目。
利用 Brian Kernighan 算法可以在一定程度上进一步提升计算速度。该算法的原理是对于任意整数 x x x 令 x x ( x − 1 ) xx~\~(x-1) xx (x−1) 该运算将 x x x 的二进制表示的最后一个 1 1 1 变成 0 0 0 。因此对 x x x 重复该操作直到 x x x 变成 0 0 0 则操作次数即为 x x x 的「一比特数」。
对于给定的 n n n计算从 0 0 0 到 n n n 的每个整数的「一比特数」的时间都不会超过 O ( log n ) O(\log n) O(logn) 因此总时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) 。
class Solution {public int[] countBits(int n) {int[] bits new int[n 1];for (int i 0; i n; i) bits[i] countOnes(i);return bits;}public int countOnes(int x) {int ones 0;while (x 0) {x (x - 1);ones;}return ones;}
}复杂度分析:
时间复杂度 O ( n log n ) O(n \log n) O(nlogn) 。需要对从 0 0 0 到 n n n 的每个整数使用计算「一比特数」对于每个整数计算「一比特数」的时间都不会超过 O ( log n ) O(\log n) O(logn) 。空间复杂度 O ( 1 ) O(1) O(1) 。除了返回的数组以外空间复杂度为常数。 解法2 动态规划——最高有效位
方法一需要对每个整数使用 O ( log n ) O(\log n) O(logn) 的时间计算「一比特数」。可以换一个思路当计算 i i i 的「一比特数」时如果存在 0 ≤ j i 0 \le ji 0≤ji j j j 的「一比特数」已知且 i i i 和 j j j 相比 i i i 的二进制表示只多了一个 1 1 1 则可以快速得到 i i i 的「一比特数」。令 bits [ i ] \textit{bits}[i] bits[i] 表示 i i i 的「一比特数」则上述关系可以表示成 bits [ i ] bits [ j ] 1 \textit{bits}[i] \textit{bits}[j]1 bits[i]bits[j]1 。
对于正整数 x x x 如果可以知道最大的正整数 y y y 使得 y ≤ x y \le x y≤x 且 y y y 是 2 2 2 的整数次幂则 y y y 的二进制表示中只有最高位是 1 1 1 其余都是 0 0 0此时称 y y y 为 x x x 的「最高有效位」。令 z x − y zx-y zx−y 显然 0 ≤ z x 0 \le zx 0≤zx 则 bits [ x ] bits [ z ] 1 \textit{bits}[x]\textit{bits}[z]1 bits[x]bits[z]1 。 为了判断一个正整数是不是 2 2 2 的整数次幂可以利用方法一中提到的按位与运算的性质。如果正整数 y y y 是 2 2 2 的整数次幂则 y y y 的二进制表示中只有最高位是 1 1 1其余都是 0 0 0因此 y ( y − 1 ) 0 y~\~(y-1) 0 y (y−1)0 。由此可见正整数 y y y 是 2 2 2 的整数次幂当且仅当 y ( y − 1 ) 0 y~\~(y-1)0 y (y−1)0 。 显然 0 0 0 的「一比特数」为 0 0 0 。使用 highBit \textit{highBit} highBit 表示当前的最高有效位遍历从 1 1 1 到 n n n 的每个正整数 i i i进行如下操作。
如果 i ( i − 1 ) 0 i~\~(i-1)0 i (i−1)0 则令 highBit i \textit{highBit}i highBiti 更新当前的最高有效位。 i i i 比 i − highBit i-\textit{highBit} i−highBit 的「一比特数」多 1 1 1 由于是从小到大遍历每个整数因此遍历到 i i i 时 i − highBit i-\textit{highBit} i−highBit 的「一比特数」已知令 bits [ i ] bits [ i − highBit ] 1 \textit{bits}[i]\textit{bits}[i-\textit{highBit}]1 bits[i]bits[i−highBit]1 。最终得到的数组 bits \textit{bits} bits 即为答案。
class Solution {public int[] countBits(int n) {int[] bits new int[n 1];int highBit 0;for (int i 1; i n; i) {if ((i (i - 1)) 0) highBit i;bits[i] bits[i - highBit] 1;}return bits;}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 。对于每个整数只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。空间复杂度 O ( 1 ) O(1) O(1) 。除了返回的数组以外空间复杂度为常数。 解法3 动态规划——最低有效位
方法二需要实时维护最高有效位当遍历到的数是 2 2 2 的整数次幂时需要更新最高有效位。如果再换一个思路可以使用「最低有效位」计算「一比特数」。
对于正整数 x x x 将其二进制表示右移一位等价于将其二进制表示的最低位去掉得到的数是 ⌊ x 2 ⌋ \lfloor \frac{x}{2} \rfloor ⌊2x⌋ 。如果 bits [ ⌊ x 2 ⌋ ] \textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big] bits[⌊2x⌋] 的值已知则可以得到 bits [ x ] \textit{bits}[x] bits[x] 的值
如果 x x x 是偶数则 bits [ x ] bits [ ⌊ x 2 ⌋ ] \textit{bits}[x]\textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big] bits[x]bits[⌊2x⌋]如果 x x x 是奇数则 bits [ x ] bits [ ⌊ x 2 ⌋ ] 1 \textit{bits}[x]\textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big]1 bits[x]bits[⌊2x⌋]1
上述两种情况可以合并成 bits [ x ] \textit{bits}[x] bits[x] 的值等于 bits [ ⌊ x 2 ⌋ ] \textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big] bits[⌊2x⌋] 的值加上 x x x 除以 2 2 2 的余数。
由于 ⌊ x 2 ⌋ \lfloor \frac{x}{2} \rfloor ⌊2x⌋ 可以通过 x 1 x 1 x1 得到 x x x 除以 2 2 2 的余数可以通过 x 1 x~\~1 x 1 得到因此有 bits [ x ] bits [ x 1 ] ( x 1 ) \textit{bits}[x]\textit{bits}[x1](x~\~1) bits[x]bits[x1](x 1) 遍历从 1 1 1 到 n n n 的每个正整数 i i i 计算 bits \textit{bits} bits 的值。最终得到的数组 bits \textit{bits} bits 即为答案。
class Solution {public int[] countBits(int n) {int[] bits new int[n 1];for (int i 1; i n; i)bits[i] bits[i 1] (i 1);return bits;}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 。对于每个整数只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。空间复杂度 O ( 1 ) O(1) O(1) 。除了返回的数组以外空间复杂度为常数。 解法4 动态规划——最低设置位
定义正整数 x x x 的「最低设置位」为 x x x 的二进制表示中的最低的 1 1 1 所在位。例如 10 10 10 的二进制表示是 101 0 ( 2 ) 1010_{(2)} 1010(2) 其最低设置位为 2 2 2 对应的二进制表示是 1 0 ( 2 ) 10_{(2)} 10(2) 。
令 y x ( x − 1 ) yx~\~(x-1) yx (x−1) 则 y y y 为将 x x x 的最低设置位从 1 1 1 变成 0 0 0 之后的数显然 0 ≤ y x 0 \le yx 0≤yx bits [ x ] bits [ y ] 1 \textit{bits}[x]\textit{bits}[y]1 bits[x]bits[y]1 。因此对任意正整数 x x x 都有 bits [ x ] bits [ x ( x − 1 ) ] 1 \textit{bits}[x]\textit{bits}[x~\~(x-1)]1 bits[x]bits[x (x−1)]1 。
遍历从 1 1 1 到 n n n 的每个正整数 i i i计算 bits \textit{bits} bits 的值。最终得到的数组 bits \textit{bits} bits 即为答案。
class Solution {public int[] countBits(int n) {int[] bits new int[n 1];for (int i 1; i n; i)bits[i] bits[i (i - 1)] 1;return bits;}
}复杂度分析
时间复杂度 O ( n ) O(n) O(n) 。对于每个整数只需要 O ( 1 ) O(1) O(1) 的时间计算「一比特数」。空间复杂度 O ( 1 ) O(1) O(1) 。除了返回的数组以外空间复杂度为常数。
