Commit61a3d6b

committed

dp approach to counting bits

1 parente9f54b5 commit61a3d6bCopy full SHA for 61a3d6b

File tree

+16

-2

lines changed

+16

-2

lines changed

Lines changed: 16 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -27,7 +27,21 @@ Space complexity should be O(n).`
`27`	`27`	`*`
`28`	`28`	`*/`
`29`	`29`	`publicclassCountingBits {`
`30`		`-//TODO: follow its hint to solve it using DP`
	`30`	`+privateclassDP_Solution{`
	`31`	`+//lixx2100's post is cool:https://discuss.leetcode.com/topic/40162/three-line-java-solution`
	`32`	`+//An easy recurrence for this problem is f[i] = f[i / 2] + i % 2`
	`33`	`+//and then we'll use bit manipulation to express the above recursion function`
	`34`	`+// right shift by 1 means to divide by 2`
	`35`	`+//AND with 1 means to modulo 2`
	`36`	`+//this is so cool!`
	`37`	`+publicint[]countBits(intnum) {`
	`38`	`+int[]ones =newint[num+1];`
	`39`	`+for(inti =1;i <=num;i++){`
	`40`	`+ones[i] =ones[i >>1] + (i&1);`
	`41`	`+ }`
	`42`	`+returnones;`
	`43`	`+ }`
	`44`	`+ }`
`31`	`45`
`32`	`46`
`33`	`47`	`//use the most regular method to get it AC'ed first`
`@@ -50,7 +64,7 @@ private int countOnes(int i) {`
`50`	`64`
`51`	`65`	`publicstaticvoidmain(String...strings){`
`52`	`66`	`CountingBitstest =newCountingBits();`
`53`		`-intnum =5;`
	`67`	`+intnum =15;`
`54`	`68`	`int[]ones =test.countBits(num);`
`55`	`69`	`CommonUtils.printArray(ones);`
`56`	`70`	`}`

Comments

(0)