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

Commita962eed

Browse files
add a solution for 47
1 parentf056ba0 commita962eed

File tree

2 files changed

+47
-11
lines changed

2 files changed

+47
-11
lines changed

‎src/main/java/com/fishercoder/solutions/_47.java

Lines changed: 43 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,9 @@
22

33
importjava.util.ArrayList;
44
importjava.util.Arrays;
5+
importjava.util.HashSet;
56
importjava.util.List;
7+
importjava.util.Set;
68

79
publicclass_47 {
810
publicstaticclassSolution1 {
@@ -15,14 +17,13 @@ public List<List<Integer>> permuteUnique(int[] nums) {
1517
returnresult;
1618
}
1719
boolean[]used =newboolean[nums.length];
18-
List<Integer>list =newArrayList();
19-
Arrays.sort(nums);
20-
dfs(nums,used,list,result);
20+
Arrays.sort(nums);//this sorting is critical for the correctness of this backtracking algorithm as we compare the two adjancent neighbors to filter out possible duplicate permutations
21+
backtracking(nums,used,newArrayList(),result);
2122
returnresult;
2223
}
2324

2425

25-
privatevoiddfs(int[]nums,boolean[]used,List<Integer>list,List<List<Integer>>result) {
26+
privatevoidbacktracking(int[]nums,boolean[]used,List<Integer>list,List<List<Integer>>result) {
2627
if (list.size() ==nums.length) {
2728
result.add(newArrayList(list));
2829
return;
@@ -31,20 +32,51 @@ private void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integ
3132
if (used[i]) {
3233
continue;
3334
}
34-
if (i >0 &&nums[i -1] ==nums[i] && !used[i -1]) {
35+
if (i >0 &&nums[i -1] ==nums[i] &&used[i -1]) {
36+
/**
37+
* For this line, both !used[i-1] and used[i-1] will AC.
38+
* It is because the first one makes sure when duplicates are selected, the order is ascending (index from small to large).
39+
* However, the second one means the descending order.
40+
* But without this used[i - 1] or !used[i - 1] will not yield a correct result as the program will not yield a correct result.
41+
*/
3542
continue;
3643
}
37-
/**
38-
* For this line, both !used[i-1] and used[i-1] will AC. It is because the first one makes sure when
39-
* duplicates are selected, the order is ascending (index from small to large). However,
40-
* the second one means the descending order.
41-
*/
4244
used[i] =true;
4345
list.add(nums[i]);
44-
dfs(nums,used,list,result);
46+
backtracking(nums,used,list,result);
4547
used[i] =false;
4648
list.remove(list.size() -1);
4749
}
4850
}
4951
}
52+
53+
publicstaticclassSolution2 {
54+
publicList<List<Integer>>permuteUnique(int[]nums) {
55+
Arrays.sort(nums);
56+
Set<List<Integer>>set =newHashSet<>();
57+
set.add(newArrayList<>());
58+
set =recursion(nums,set,0);
59+
List<List<Integer>>res =newArrayList<>();
60+
for (List<Integer>list :set) {
61+
res.add(list);
62+
}
63+
returnres;
64+
}
65+
66+
privateSet<List<Integer>>recursion(int[]nums,Set<List<Integer>>set,intpos) {
67+
if (pos ==nums.length) {
68+
returnset;
69+
}
70+
Set<List<Integer>>newSet =newHashSet<>();
71+
for (List<Integer>list :set) {
72+
for (inti =0;i <=list.size();i++) {
73+
List<Integer>newList =newArrayList<>(list);
74+
newList.add(i,nums[pos]);
75+
newSet.add(newList);
76+
}
77+
}
78+
set =newSet;
79+
returnrecursion(nums,set,pos +1);
80+
}
81+
}
5082
}

‎src/test/java/com/fishercoder/_47Test.java

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,17 +9,21 @@
99

1010
publicclass_47Test {
1111
privatestatic_47.Solution1solution1;
12+
privatestatic_47.Solution2solution2;
1213
privatestaticList<List<Integer>>actual;
1314

1415
@BeforeClass
1516
publicstaticvoidsetup() {
1617
solution1 =new_47.Solution1();
18+
solution2 =new_47.Solution2();
1719
}
1820

1921
@Test
2022
publicvoidtest1() {
2123
actual =solution1.permuteUnique(newint[]{1,1,2});
2224
CommonUtils.printListList(actual);
25+
actual =solution2.permuteUnique(newint[]{1,1,2});
26+
CommonUtils.printListList(actual);
2327
}
2428

2529
}

0 commit comments

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