Commit2ed7661

committed

refactor 198

1 parent34ee3d3 commit2ed7661Copy full SHA for 2ed7661

File tree

+57

-3

lines changed

src
- main/java/com/fishercoder/solutions
  - _198.java
- test/java/com/fishercoder
  - _198Test.java

+57

-3

lines changed

Lines changed: 27 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,7 @@`
`1`	`1`	`packagecom.fishercoder.solutions;`
`2`	`2`
	`3`	`+importjava.util.Arrays;`
	`4`	`+`
`3`	`5`	`publicclass_198 {`
`4`	`6`
`5`	`7`	`publicstaticclassSolution1 {`
`@@ -10,9 +12,6 @@ public int rob(int[] nums) {`
`10`	`12`	`if (nums.length ==1) {`
`11`	`13`	`returnnums[0];`
`12`	`14`	`}`
`13`		`-if (nums.length ==2) {`
`14`		`-returnMath.max(nums[0],nums[1]);`
`15`		`- }`
`16`	`15`	`int[]dp =newint[nums.length];`
`17`	`16`	`dp[0] =nums[0];`
`18`	`17`	`dp[1] =Math.max(nums[0],nums[1]);`
`@@ -22,4 +21,29 @@ public int rob(int[] nums) {`
`22`	`21`	`returndp[nums.length -1];`
`23`	`22`	`}`
`24`	`23`	`}`
	`24`	`+`
	`25`	`+publicstaticclassSolution2 {`
	`26`	`+/**`
	`27`	`+ * recursion + memoization, basically the same as the above solution1`
	`28`	`+ * credit: https://leetcode.com/problems/house-robber/solution/`
	`29`	`+ */`
	`30`	`+int[]memo;`
	`31`	`+`
	`32`	`+publicintrob(int[]nums) {`
	`33`	`+memo =newint[nums.length];`
	`34`	`+Arrays.fill(memo, -1);`
	`35`	`+returnrobFrom(0,nums);`
	`36`	`+ }`
	`37`	`+`
	`38`	`+privateintrobFrom(intstart,int[]nums) {`
	`39`	`+if (start >=nums.length) {`
	`40`	`+return0;`
	`41`	`+ }`
	`42`	`+if (this.memo[start] != -1) {`
	`43`	`+returnthis.memo[start];`
	`44`	`+ }`
	`45`	`+this.memo[start] =Math.max(robFrom(start +1,nums),robFrom(start +2,nums) +nums[start]);`
	`46`	`+returnthis.memo[start];`
	`47`	`+ }`
	`48`	`+ }`
`25`	`49`	`}`

Lines changed: 30 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,30 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.solutions._198;`
	`4`	`+importorg.junit.BeforeClass;`
	`5`	`+importorg.junit.Test;`
	`6`	`+`
	`7`	`+importstaticorg.junit.Assert.assertEquals;`
	`8`	`+`
	`9`	`+publicclass_198Test {`
	`10`	`+privatestatic_198.Solution1solution1;`
	`11`	`+privatestatic_198.Solution2solution2;`
	`12`	`+`
	`13`	`+@BeforeClass`
	`14`	`+publicstaticvoidsetup() {`
	`15`	`+solution1 =new_198.Solution1();`
	`16`	`+solution2 =new_198.Solution2();`
	`17`	`+ }`
	`18`	`+`
	`19`	`+@Test`
	`20`	`+publicvoidtest1() {`
	`21`	`+assertEquals(4,solution1.rob(newint[]{1,2,3,1}));`
	`22`	`+assertEquals(4,solution2.rob(newint[]{1,2,3,1}));`
	`23`	`+ }`
	`24`	`+`
	`25`	`+@Test`
	`26`	`+publicvoidtest2() {`
	`27`	`+assertEquals(4,solution1.rob(newint[]{2,1,1,2}));`
	`28`	`+ }`
	`29`	`+`
	`30`	`+}`

Comments

(0)