🌗 338. 比特位计数

难度: 🌗

问题描述

---

解法

class Solution {
    public int[] countBits(int n) {
        // 思路：
        // 找规律
        // 奇 --> 偶：最低位的 0 变为 1，其余 1 的个数不变，∴ i ++
        // 偶 --> 奇：偶 / 2 的二进制全部左移一位，1 的个数不变
        int[] res = new int[n + 1];
        res[0] = 0;
        for(int i = 1; i <= n; i ++) {
            if((i & 1) == 1) {
                // 奇数
                res[i] = res[i - 1] + 1;
            } else {
                res[i] = res[i / 2];
            }
        }
        return res;
    }
}

---

输出