Commitf7f94b2

committed

add a solution for 279

1 parent490edbd commitf7f94b2Copy full SHA for f7f94b2

File tree

+62

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _279.java
- test/java/com/fishercoder
  - _279Test.java

+62

-0

lines changed

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -37,4 +37,35 @@ public int numSquares(int n) {`
`37`	`37`	`}`
`38`	`38`	`}`
`39`	`39`
	`40`	`+publicstaticclassSolution3 {`
	`41`	`+/**`
	`42`	`+ * My completely original DP solution on 10/14/2021.`
	`43`	`+ * <p>`
	`44`	`+ * Again, once you use a pen and paper to visualize your thought process, the idea flows out very quickly.`
	`45`	`+ * Thinking without a pen and paper is a waste of time in most cases! :)`
	`46`	`+ */`
	`47`	`+publicintnumSquares(intn) {`
	`48`	`+int[]dp =newint[n +1];`
	`49`	`+for (inti =1;i <=n;i++) {`
	`50`	`+intx = (int)Math.sqrt(i);`
	`51`	`+if (Math.pow(x,2) ==i) {`
	`52`	`+dp[i] =1;`
	`53`	`+ }else {`
	`54`	`+dp[i] =i;`
	`55`	`+intleft =1;`
	`56`	`+intright =i -1;`
	`57`	`+while (left <right) {`
	`58`	`+dp[i] =Math.min(dp[i],dp[left] +dp[right]);`
	`59`	`+left++;`
	`60`	`+right--;`
	`61`	`+ }`
	`62`	`+if (left ==right &&i %left ==0) {`
	`63`	`+dp[i] =Math.min(dp[i], (i /left) *dp[left]);`
	`64`	`+ }`
	`65`	`+ }`
	`66`	`+ }`
	`67`	`+returndp[n];`
	`68`	`+ }`
	`69`	`+ }`
	`70`	`+`
`40`	`71`	`}`

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,31 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.solutions._279;`
	`4`	`+importcom.fishercoder.solutions._340;`
	`5`	`+importorg.junit.BeforeClass;`
	`6`	`+importorg.junit.Test;`
	`7`	`+`
	`8`	`+importstaticorg.junit.Assert.assertEquals;`
	`9`	`+`
	`10`	`+publicclass_279Test {`
	`11`	`+privatestatic_279.Solution1solution1;`
	`12`	`+privatestatic_279.Solution2solution2;`
	`13`	`+privatestatic_279.Solution3solution3;`
	`14`	`+`
	`15`	`+@BeforeClass`
	`16`	`+publicstaticvoidsetup() {`
	`17`	`+solution1 =new_279.Solution1();`
	`18`	`+solution2 =new_279.Solution2();`
	`19`	`+solution3 =new_279.Solution3();`
	`20`	`+ }`
	`21`	`+`
	`22`	`+@Test`
	`23`	`+publicvoidtest1() {`
	`24`	`+intn =9;`
	`25`	`+intexpected =1;`
	`26`	`+assertEquals(expected,solution1.numSquares(n));`
	`27`	`+assertEquals(expected,solution2.numSquares(n));`
	`28`	`+assertEquals(expected,solution3.numSquares(n));`
	`29`	`+ }`
	`30`	`+`
	`31`	`+}`

Comments

(0)