Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

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

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5e78f73

Browse files
refactor 377
1 parent13658a4 commit5e78f73

File tree

3 files changed

+123
-42
lines changed

3 files changed

+123
-42
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -252,7 +252,7 @@ Your ideas/fixes/algorithms are more than welcome!
252252
|380|[Insert Delete GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_380.java)| O(n) | O(1)| Medium| Design, HashMap
253253
|379|[Design Phone Directory](https://leetcode.com/problems/design-phone-directory/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_379.java)| O(1)|O(n)| Medium|
254254
|378|[Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_378.java)| O(logm*n) | O(1)| Medium| Binary Search
255-
|377|[Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_377.java)| O(?)|O(?)| Medium|
255+
|377|[Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_377.java)| O(n^2)|O(n) | Medium| DP
256256
|376|[Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_376.java)| O(n)|O(1) | Medium| DP, Greedy
257257
|375|[Guess Number Higher or Lower II](https://leetcode.com/problems/guess-number-higher-or-lower-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_375.java)| O(n^2)|O(n^2) | Medium| DP
258258
|374|[Guess Number Higher or Lower](https://leetcode.com/problems/guess-number-higher-or-lower/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_374.java)| O(logn)|O(1) | Easy| Binary Search
Lines changed: 78 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,12 @@
11
packagecom.fishercoder.solutions;
22

3-
importcom.fishercoder.common.utils.CommonUtils;
4-
53
importjava.util.ArrayList;
64
importjava.util.Arrays;
75
importjava.util.List;
8-
/**Given an integer array with all positive numbers and no duplicates,
6+
7+
/**
8+
* 377. Combination Sum IV
9+
* Given an integer array with all positive numbers and no duplicates,
910
* find the number of possible combinations that add up to a positive integer target.
1011
1112
Example:
@@ -29,54 +30,90 @@
2930
Follow up:
3031
What if negative numbers are allowed in the given array?
3132
How does it change the problem?
32-
What limitation we need to add to the question to allow negative numbers?*/
33+
What limitation we need to add to the question to allow negative numbers?
34+
*/
35+
3336
publicclass_377 {
34-
/**since this question doesn't require to return all the combination result, instead, it just wants one number, we could use DP
35-
the idea is similar to Climbing Stairs.
36-
adopted this solution: https://discuss.leetcode.com/topic/52186/my-3ms-java-dp-solution*/
37-
publicintcombinationSum4(int[]nums,inttarget) {
38-
Arrays.sort(nums);
39-
int[]result =newint[target +1];
40-
for (inti =1;i <result.length;i++) {
41-
for (intn :nums) {
42-
if (n >target) {
43-
break;
44-
}elseif (n ==target) {
45-
result[i]++;
46-
}else {
47-
result[i] +=result[i -n];
37+
38+
publicstaticclassSolution1 {
39+
/**
40+
* this normal backtracking recursive solution will end up in MLE by this testcase: [4,2,1], 32
41+
*/
42+
publicintcombinationSum4(int[]nums,inttarget) {
43+
List<List<Integer>>result =newArrayList();
44+
Arrays.sort(nums);
45+
backtracking(nums,target,newArrayList(),result);
46+
returnresult.size();
47+
}
48+
49+
privatevoidbacktracking(int[]nums,inttarget,List<Integer>list,
50+
List<List<Integer>>result) {
51+
if (target ==0) {
52+
result.add(newArrayList(list));
53+
}elseif (target >0) {
54+
for (inti =0;i <nums.length;i++) {
55+
list.add(nums[i]);
56+
backtracking(nums,target -nums[i],list,result);
57+
list.remove(list.size() -1);
4858
}
4959
}
5060
}
51-
returnresult[target];
5261
}
5362

54-
//this normal backtracking recursive solution will end up in TLE.
55-
publicList<List<Integer>>combinationSum4_printout(int[]nums,inttarget) {
56-
List<List<Integer>>result =newArrayList();
57-
Arrays.sort(nums);
58-
backtracking(0,nums,target,newArrayList(),result);
59-
returnresult;
60-
}
63+
publicstaticclassSolution2 {
64+
/**
65+
* Since we don't need to get all of the combinations, instead,
66+
* we only need to get the possible count, I can use only a count instead of "List<List<Integer>> result"
67+
* However, it also ended up in TLE by this testcase: [1,2,3], 32
68+
*/
69+
publicstaticintcount =0;
70+
publicintcombinationSum4(int[]nums,inttarget) {
71+
Arrays.sort(nums);
72+
backtracking(nums,target,newArrayList());
73+
returncount;
74+
}
6175

62-
privatevoidbacktracking(intstart,int[]nums,inttarget,ArrayListtemp,
63-
List<List<Integer>>result) {
64-
if (target ==0) {
65-
List<Integer>newTemp =newArrayList(temp);
66-
result.add(newTemp);
67-
}elseif (target >0) {
68-
for (inti =start;i <nums.length;i++) {
69-
temp.add(nums[i]);
70-
backtracking(i,nums,target -nums[i],temp,result);
71-
temp.remove(temp.size() -1);
76+
privatevoidbacktracking(int[]nums,inttarget,List<Integer>list) {
77+
if (target ==0) {
78+
count++;
79+
}elseif (target >0) {
80+
for (inti =0;i <nums.length;i++) {
81+
list.add(nums[i]);
82+
backtracking(nums,target -nums[i],list);
83+
list.remove(list.size() -1);
84+
}
7285
}
7386
}
7487
}
7588

76-
publicstaticvoidmain(String...strings) {
77-
_377test =new_377();
78-
int[]nums =newint[]{1,2,3};
79-
inttarget =4;
80-
CommonUtils.printListList(test.combinationSum4_printout(nums,target));
89+
publicstaticclassSolution3 {
90+
/**
91+
* Since this question doesn't require to return all the combination result, instead, it just wants one number, we could use DP
92+
* the idea is similar to Climbing Stairs.
93+
*
94+
* The idea is very clear as the code speaks for itself:
95+
* It's easy to find the routine
96+
* dp[0] = 0;
97+
* dp[1] = 1;
98+
* ...
99+
*
100+
* Reference: https://discuss.leetcode.com/topic/52186/my-3ms-java-dp-solution
101+
*/
102+
publicintcombinationSum4(int[]nums,inttarget) {
103+
Arrays.sort(nums);
104+
int[]result =newint[target +1];
105+
for (inti =1;i <result.length;i++) {
106+
for (intnum :nums) {
107+
if (num >i) {
108+
break;
109+
}elseif (num ==i) {
110+
result[i]++;
111+
}else {
112+
result[i] +=result[i -num];
113+
}
114+
}
115+
}
116+
returnresult[target];
117+
}
81118
}
82119
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._377;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticjunit.framework.Assert.assertEquals;
8+
9+
publicclass_377Test {
10+
privatestatic_377.Solution1solution1;
11+
privatestatic_377.Solution2solution2;
12+
privatestatic_377.Solution3solution3;
13+
privatestaticint[]nums;
14+
privatestaticinttarget;
15+
16+
@BeforeClass
17+
publicstaticvoidsetup() {
18+
solution1 =new_377.Solution1();
19+
solution2 =new_377.Solution2();
20+
solution3 =new_377.Solution3();
21+
}
22+
23+
@Test
24+
publicvoidtest1() {
25+
nums =newint[]{1,2,3};
26+
target =4;
27+
assertEquals(7,solution1.combinationSum4(nums,target));
28+
assertEquals(7,solution2.combinationSum4(nums,target));
29+
assertEquals(7,solution3.combinationSum4(nums,target));
30+
}
31+
32+
@Test
33+
publicvoidtest2() {
34+
nums =newint[]{4,2,1};
35+
target =32;
36+
// assertEquals(39882198, solution1.combinationSum4(nums, target));//this results in MLE, so comment out
37+
38+
solution2.count =0;//always have to reset this global variable to be zero before using it again
39+
assertEquals(39882198,solution2.combinationSum4(nums,target));
40+
41+
assertEquals(39882198,solution3.combinationSum4(nums,target));
42+
}
43+
44+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp