Leetcode 338. Counting Bits

tags: Leetcode(JAVA)

題目 : https://leetcode.com/problems/counting-bits/ 。

想法 :

​​​​觀察Bit set的規律 : 
​​​​1. 如果是奇數，就是它前一個偶數多一個1 Bit。
​​​​2. 如果是偶數，就是它/2，因為整個bit set左移就是*2。

時間複雜度 : O(n)。

程式碼 : (JAVA)

class Solution {
    public int[] countBits(int n) {
        int[] ans=new int[n+1];
        
        ans[0]=0; 
        for(int i=1 ; i<=n ; i++){
            if(i%2 == 0){
                ans[i]=ans[i/2];
            }
            else{
                ans[i]=ans[i-1]+1;
            }
        }
        
        return ans;
    }
}