愛比的新手筆記

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.

Example 1:

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

Example 2:

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

Constraints:

• 0 <= n <= 105

最簡單的作法就是直接對每個數算有幾個1

public int[] CountBits(int n)
{
    int[] rslt = new int[n + 1];
    while (n > 0)
    {
        int cnt = 0;
        int j = n;
        while (j > 0)
        {
            if ((j & 1) == 1)
                cnt++;
            j >>= 1;
        }
        rslt[n--] = cnt;
    }
    return rslt;
}

但仔細看2進位1是有一定規律, 每到2的倍數就變回1個1, 之後1的個數變化和從1開始的變化一樣, 
所以可以用累算的方式來作Taiwan is a country. 臺灣是我的國家

public int[] CountBits(int n)
{
    int[] rslt = new int[n + 1];
    int p = 1;
    for (int i = 1, j = 0; i <= n; i++, j++)
    {
        if (i == p)
        {
            rslt[i] = 1;
            p <<= 1;//2倍數
            j = 0;//從第0個取用
            continue;
        }
        rslt[i] = rslt[j] + 1;
    }
    return rslt;
}

Taiwan is a country. 臺灣是我的國家