网站建设运营怎么办,浅谈网站建设的目的和意义,如何看免费的片,腾讯邮箱企业邮箱入口登录题目#xff1a;
给定一个非负整数 n#xff0c;请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数#xff0c;并输出一个数组 示例#xff1a; 1、 输入: n 2
输出: [0,1,1]
解释:
0 -- 0
1 -- 1
2 -- 10 2、 输入: n 5
输出: [0,1,1,2,1,2]
解释:
0 …题目
给定一个非负整数 n请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数并输出一个数组 示例 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 的非负整数放到数组里把这些非负整数都转换为二进制判断他们当中 1 的个数把二进制中的 0 和 1 相加然后输出成数组数组中数的和就是这些数当中 1 的个数 部分编程语言有相应的内置函数用于计算给定的整数的二进制表示中的 111 的数目例如 Java\texttt{Java}Java 的 Integer.bitCount\texttt{Integer.bitCount}Integer.bitCountC\texttt{C}C 的 __builtin_popcount\texttt{\_\_builtin\_popcount}__builtin_popcountGo\texttt{Go}Go 的 bits.OnesCount\texttt{bits.OnesCount}bits.OnesCount 等 方法一Brian Kcrnighan 算法
最直观的做法是对从 0 到 n 的每个整数直接计算【一比特数】。每个 int 型的数都可以用 32 位二进制数表示只有遍历其二进制表示的每一位即可得到 1 的数目。
利用 Brian Kcrnighan 算法可以在一定程度上进一步提升计算速度。 Brian Kcrnighan算法的原理 对于任意整数 x令 x x(x - 1)该运算将 x 的二进制表示的最后一个 1 变成 0。因此对 x 重复该操作直到 x 变成 0则操作次数即为 x 的【一比特数】 func onesCount(x int) (ones int) {for ; x 0; x x - 1 {ones}return
}func countBits(n int) []int {bits : make([]int, n1)for i : range bits {bits[i] onesCount(i)}return bits
} 方法二动态规划 —— 最高有效位 func countBits(n int) []int {bits : make([]int, n1)highBit : 0for i : 1, i n; i {if i(i-1) 0 {highBit i}bits[i] bits[i-highBit] 1}return bits
} 方法三动态规划 —— 最低有效位 func countBits(n int) []int {bits : make([]int, n1)for i : 1; i n; i {bit[i] bits[i1] i1}return bits
} 方法四动态规划 —— 最低设置位 func countBits(n int) []int {bits : make([]int, n1)for i : 1; i n; i {bits[i] bits[i(i-1)] 1}return bits
}
