Leetcode:338. Counting Bits

Posted on | Comments: | Views:
DP

338. Counting Bits

题目理解:

找到长度为n的数组, 每个位置的值为对应下标二进制下1的个数

思路:

先看一下二进制规律:

十进制 二进制 1的个数
0 000 0
1 001 1
2 010 1
3 011 2
4 100 1
5 101 2
6 110 2
7 111 3

容易看出来, [4-7]的值正是[0-3]的值+1, 而[2-3]的值正是[0-1]的值+1, 他们的区别在于最高位的1出现在二进制的第几位, 以此来分组, 第二组的值总是为第一组的值+1
可以设定一个 gap 值, 若 gap = 2 认为现在在计算[2-3], 那么就是[0-1]+1就好了, 进而 gap = 4, 位于[4-7], 即为[0-3]+1, …… , gap = 2^n 位于 [2^n-2^(n-1)], 值为[0-2^n-1]+1
根据这个规则, 递推算出整个数组就完成了

小结:

状态表示和状态转移方程在这道题不会表示…而且这个算法也不好, 需要计算gap的增加情况, 造成额外的开销, 看到别人的实际可以直接 v[i] = v[i&(i-1)] + 1(要考虑一些情况), 非常厉害实在佩服

Submission Detail:

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> countBits(int num) {
        std::vector<int> v;
        int gap = 2;
        int time = 2;
        v.push_back(0);
        v.push_back(1);
        for (int i = 2; i <= num; ++i) {
            v.push_back(v[i-gap]+1);
            time--;
            if (time == 0) {
                gap *= 2;
                time = gap;
            }
        }
        while (v.size() > num+1) v.pop_back();
        return v;
    }
};