Java 6ms 17lines O(n) time and space DP solution very easy to understand


  • 0
    4
    public int[] countBits(int num) {
    		if (num == 0) {
    			return new int[] { 0 };
    		}
    		if (num == 1) {
    			return new int[] { 0, 1 };
    		}
    		int result[]=new int[num+1];
    		result[0]=0;
    		result[1]=1;
    		for (int i = 2; i <=num; i++) {
    			if (i%2==0) {
    				result[i]=result[i/2];
    			}else {
    				result[i]=result[i/2]+1;
    			}
    		}
    		return result;
    	}

  • 0
    B

    java timing calculation is wrong @LC.


  • 0
    4

    yes, it tooks 8ms when I commited my answer again.But the method I used is very easy to understand


  • 0
    B

    no offense, I find out that for all java solutions @LC, the timing is extremely good compare to c/c++ solutions, one may get the false impression that java is fastest. take this problem as example, c/c++ solutions with same algorithm took at least 120 ms.


  • 0
    M

    Can someone explain this part ?
    if (i%2==0) {
    result[i]=result[i/2];
    }else {
    result[i]=result[i/2]+1;
    }


  • 0
    4

    if a number i%2==0, the bit 1 number of i must be equal to the the bit 1 number of i/2, because the i can be regard as i/2 rotating the bits once to the left. And the result[i]=result[i/2]+1, you can take some case as examples to find out the rule.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.