0338. 比特位计数 Counting Bits

问题描述

方法1, Brute Force

很容易就有了这个想法. 遍历 0..=n 的整数, 然后依次计算每个整数中比特位为1的个数. Rust 提供了 i32::count_ones() 这样的方法, 它内部是调用的本平台的汇编指令, 还是很快的.

时间复杂度是 O(n).

#![allow(unused)]
fn main() {
// Brute Force
pub fn count_bits1(n: i32) -> Vec<i32> {
    assert!(n >= 0);
    (0..=n).map(|i| i.count_ones() as i32).collect()
}
}

方法2, 使用动态规划

这个方法利用了一个重要的特性: f(n) = f(n/2) + lsb

解释一下就是, 整数 n 右移一位, 丢弃掉它的最低有效位 (least significant bit, lsb) 后, 就是 n/2

可以看下面的图:

left-shift

时间复杂度是 O(n).

#![allow(unused)]
fn main() {
// Dynamic Programming
pub fn count_bits2(n: i32) -> Vec<i32> {
    assert!(n >= 0);
    let mut vec = vec![0; n as usize + 1];
    for i in 0..=n {
        let i_usize = i as usize;
        // f(n) = f(n/2) + lsb
        // 下面两行的写法是等效的:
        //vec[i_usize] = vec[i_usize / 2] + i % 2;
        vec[i_usize] = vec[i_usize >> 1] + (i & 1);
    }
    vec
}
}