Commit9ce8a27

authored

Update 0779-k-th-symbol-in-grammar.java

1 parentf3a508f commit9ce8a27Copy full SHA for 9ce8a27

File tree

+13

-10

lines changed

+13

-10

lines changed

Lines changed: 13 additions & 10 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,15 +1,18 @@`
`1`		`-//Explanation: https://leetcode.com/problems/k-th-symbol-in-grammar/discuss/2174956/Easy-java-solution-or-Imagine-a-binary-tree. (Upvote if you liked!!)`
`2`		`-//Asked in: Google (lintcode)`
`3`		`-`
`4`	`1`	`classSolution {`
`5`		`-`
`6`	`2`	`publicintkthGrammar(intn,intk) {`
`7`		`-if (n ==1 \|\|k ==1)return0;`
`8`		`-intprevK = (int)Math.pow(2,n -2);`
`9`		`-if (k <=prevK)returnkthGrammar(n -1,k);else {`
`10`		`-intpresK =k %prevK;`
`11`		`-intval =kthGrammar(n -1,presK ==0 ?k /2 :k %prevK);`
`12`		`-returnval ==1 ?0 :1;`
	`3`	`+intleft =1;`
	`4`	`+intright = (int)Math.pow(2,n-1);`
	`5`	`+intcur =0;`
	`6`	`+`
	`7`	`+for(inti =0;i <n-1;i++){`
	`8`	`+intmid = (left +right)/2;`
	`9`	`+if(k <=mid)`
	`10`	`+right =mid;`
	`11`	`+else{`
	`12`	`+left =mid +1;`
	`13`	`+cur = (cur ==1)?0:1;`
	`14`	`+ }`
`13`	`15`	`}`
	`16`	`+returncur;`
`14`	`17`	`}`
`15`	`18`	`}`

Comments

(0)