338. Counting Bits 位计数

题目描述：给定一个非负整数，给出 0这个整数的每一个数的二进制中1的个数

Input: 2
Output: [0,1,1]

Input: 5
Output: [0,1,1,2,1,2]

第一种解法：找规律

以 2 的N次方为组看看后面是否能够通过前面的结果计算得来，不难发现随着 N 的增加前一半的数基本都跟前组的计数相同，后一半的数基本就是前一半的加上多出来的一个 1

vector<int> countBits(int num) {
    vector<int> res = {0, 1, 1, 2};
    if (num < 3)
        return vector<int>(res.begin(), res.begin()+num+1);

    int offset=2;
    while((offset<<1) <= num) {
        for(int i=0;i<=1;++i) {
            for(int j=0;j<offset&&res.size()<=num;++j)
                res.push_back(res[offset+j]+i);
        }
        offset<<=1;
    }
    return res;
}

第二种解法：动态规划递推

仔细观察一下，N的1的个数和N/2的1的个数其实是有关系的递推式：count(N) = count(N>>1) + (N & 1)

vector<int> countBits(int num) {
    vector<int> ret(num+1, 0);
    for (int i = 1; i <= num; ++i)
        ret[i] = ret[i&(i-1)] + 1;
    return ret;
}

#位运算 #DP

3. Longest Substring Without Repeating Characters 34. Find First and Last Position of Element in Sorted Array 寻找排序数组目标的开始和结束