338. Counting Bits - Easy

前往題目

想法

• 毫無想法，只想得到轉成binary然後直接疊代

思路

1. 觀察0~8的binary會發現有一定規律，如下圖
   
2. Offset從0,1,4,8,16，兩倍成長
3. 只要1加上最近的offset的值就是答案，那個1就是MSB(Most significant bit)

可能看解是有點模糊，但是看code應該就會清楚很多了

Code

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        int offset = 1;

        dp[0] = 0;

        for (int i = 1; i <= n; ++i) {
            // 更新offset
            if (offset * 2 == i) {
                offset = i;
            }

            dp[i] = 1 + dp[i - offset];
        }

        return dp;
    }
}

2024/04/24

• 忘了要找規律，本來還想說轉成binary然後用AND 1就可以知道有幾個1，但是這樣每個數字都要比較一次，已非n次能解決