题目描述

题目链接：338. Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

例子

例子 1

Input:n = 2 Output:[0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10

例子 2

Input:n = 5 Output:[0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

Follow Up

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Constraints

• 0 <= n <= 10^5

解题思路

这道题看似比较比较抽象需要逐个数每个数字中二进制表示下 1 的位数，实际上用位操作的思路来看就很直观，如果是奇数则是在上一个数的结果上加 1 （最后一位从 0 变 1，其他位不变），而偶数则相当于他的一半的二进制表示左移一位，因此它的结果和它的一半的结果一致。代码如下：

#include <vector>

class Solution {
public:
    std::vector<int> countBits(int n) {
        std::vector<int> ans(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            if (i % 2 == 1) {
                ans[i] = ans[i - 1] + 1;
            }
            else {
                ans[i] = ans[i / 2];
            }
        }

        return ans;
    }
};

• 时间复杂度: O(1)
• 空间复杂度: O(n) （输出结果所需空间，没有利用额外空间）

GitHub 代码同步地址： 338.CountingBits.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions