NotificationsYou must be signed in to change notification settings
Fork8
Star4

Commit63c6c59

committed

refactor 377

1 parent5e78f73 commit63c6c59Copy full SHA for 63c6c59

File tree

2 files changed

+57

-1

lines changed

src
- main/java/com/fishercoder/solutions
  - _377.java
- test/java/com/fishercoder
  - _377Test.java

2 files changed

+57

-1

lines changed

`‎src/main/java/com/fishercoder/solutions/_377.java`

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -2,7 +2,9 @@`
`2`	`2`
`3`	`3`	`importjava.util.ArrayList;`
`4`	`4`	`importjava.util.Arrays;`
	`5`	`+importjava.util.HashMap;`
`5`	`6`	`importjava.util.List;`
	`7`	`+importjava.util.Map;`
`6`	`8`
`7`	`9`	`/**`
`8`	`10`	`* 377. Combination Sum IV`
`@@ -67,6 +69,7 @@ public static class Solution2 {`
`67`	`69`	`* However, it also ended up in TLE by this testcase: [1,2,3], 32`
`68`	`70`	`*/`
`69`	`71`	`publicstaticintcount =0;`
	`72`	`+`
`70`	`73`	`publicintcombinationSum4(int[]nums,inttarget) {`
`71`	`74`	`Arrays.sort(nums);`
`72`	`75`	`backtracking(nums,target,newArrayList());`
`@@ -88,6 +91,9 @@ private void backtracking(int[] nums, int target, List<Integer> list) {`
`88`	`91`
`89`	`92`	`publicstaticclassSolution3 {`
`90`	`93`	`/**`
	`94`	`+ * Time: O(n^2)`
	`95`	`+ * Space: O(n)`
	`96`	`+ *`
`91`	`97`	`* Since this question doesn't require to return all the combination result, instead, it just wants one number, we could use DP`
`92`	`98`	`* the idea is similar to Climbing Stairs.`
`93`	`99`	`*`
`@@ -116,4 +122,32 @@ public int combinationSum4(int[] nums, int target) {`
`116`	`122`	`returnresult[target];`
`117`	`123`	`}`
`118`	`124`	`}`
	`125`	`+`
	`126`	`+publicstaticclassSolution4 {`
	`127`	`+/**`
	`128`	`+ * Time: O(n)`
	`129`	`+ * Space: O(n)`
	`130`	`+ *`
	`131`	`+ * Reference: https://discuss.leetcode.com/topic/52255/java-recursion-solution-using-hashmap-as-memory`
	`132`	`+ */`
	`133`	`+publicstaticMap<Integer,Integer>map =newHashMap<>();//need to remove public static before submitting on Leetcode as it doesn't reset static variables`
	`134`	`+`
	`135`	`+publicintcombinationSum4(int[]nums,inttarget) {`
	`136`	`+if (nums ==null \|\|nums.length ==0 \|\|target <0) {`
	`137`	`+return0;`
	`138`	`+ }`
	`139`	`+if (target ==0) {`
	`140`	`+return1;`
	`141`	`+ }`
	`142`	`+if (map.containsKey(target)) {`
	`143`	`+returnmap.get(target);`
	`144`	`+ }`
	`145`	`+intcount =0;`
	`146`	`+for (intnum :nums) {`
	`147`	`+count +=combinationSum4(nums,target -num);`
	`148`	`+ }`
	`149`	`+map.put(target,count);`
	`150`	`+returncount;`
	`151`	`+ }`
	`152`	`+ }`
`119`	`153`	`}`

`‎src/test/java/com/fishercoder/_377Test.java`

Lines changed: 23 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,7 @@`
`1`	`1`	`packagecom.fishercoder;`
`2`	`2`
`3`	`3`	`importcom.fishercoder.solutions._377;`
	`4`	`+importorg.junit.Before;`
`4`	`5`	`importorg.junit.BeforeClass;`
`5`	`6`	`importorg.junit.Test;`
`6`	`7`
`@@ -10,6 +11,7 @@ public class _377Test {`
`10`	`11`	`privatestatic_377.Solution1solution1;`
`11`	`12`	`privatestatic_377.Solution2solution2;`
`12`	`13`	`privatestatic_377.Solution3solution3;`
	`14`	`+privatestatic_377.Solution4solution4;`
`13`	`15`	`privatestaticint[]nums;`
`14`	`16`	`privatestaticinttarget;`
`15`	`17`
`@@ -18,6 +20,14 @@ public static void setup() {`
`18`	`20`	`solution1 =new_377.Solution1();`
`19`	`21`	`solution2 =new_377.Solution2();`
`20`	`22`	`solution3 =new_377.Solution3();`
	`23`	`+solution4 =new_377.Solution4();`
	`24`	`+ }`
	`25`	`+`
	`26`	`+@Before`
	`27`	`+publicvoidsetUp()throwsException {`
	`28`	`+//always have to reset these global variables before using it again`
	`29`	`+solution2.count =0;`
	`30`	`+solution4.map.clear();`
`21`	`31`	`}`
`22`	`32`
`23`	`33`	`@Test`
`@@ -27,6 +37,7 @@ public void test1() {`
`27`	`37`	`assertEquals(7,solution1.combinationSum4(nums,target));`
`28`	`38`	`assertEquals(7,solution2.combinationSum4(nums,target));`
`29`	`39`	`assertEquals(7,solution3.combinationSum4(nums,target));`
	`40`	`+assertEquals(7,solution4.combinationSum4(nums,target));`
`30`	`41`	`}`
`31`	`42`
`32`	`43`	`@Test`
`@@ -35,10 +46,21 @@ public void test2() {`
`35`	`46`	`target =32;`
`36`	`47`	`// assertEquals(39882198, solution1.combinationSum4(nums, target));//this results in MLE, so comment out`
`37`	`48`
`38`		`-solution2.count =0;//always have to reset this global variable to be zero before using it again`
`39`	`49`	`assertEquals(39882198,solution2.combinationSum4(nums,target));`
`40`	`50`
`41`	`51`	`assertEquals(39882198,solution3.combinationSum4(nums,target));`
	`52`	`+`
	`53`	`+assertEquals(39882198,solution4.combinationSum4(nums,target));`
	`54`	`+ }`
	`55`	`+`
	`56`	`+@Test`
	`57`	`+publicvoidtest3() {`
	`58`	`+nums =newint[]{9};`
	`59`	`+target =3;`
	`60`	`+assertEquals(0,solution1.combinationSum4(nums,target));`
	`61`	`+assertEquals(0,solution2.combinationSum4(nums,target));`
	`62`	`+assertEquals(0,solution3.combinationSum4(nums,target));`
	`63`	`+assertEquals(0,solution4.combinationSum4(nums,target));`
`42`	`64`	`}`
`43`	`65`
`44`	`66`	`}`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit63c6c59

File tree

2 files changed

2 files changed

`‎src/main/java/com/fishercoder/solutions/_377.java`

`‎src/test/java/com/fishercoder/_377Test.java`

0 commit comments