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

Commit5db9f12

Browse files
add a solution for 46
1 parent6784784 commit5db9f12

File tree

2 files changed

+43
-0
lines changed

2 files changed

+43
-0
lines changed

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

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,9 @@
11
packagecom.fishercoder.solutions;
22

33
importjava.util.ArrayList;
4+
importjava.util.HashSet;
45
importjava.util.List;
6+
importjava.util.Set;
57

68
publicclass_46 {
79

@@ -29,4 +31,41 @@ private List<List<Integer>> backtracking(int[] nums, int index, List<List<Intege
2931
}
3032
}
3133

34+
publicstaticclassSolution2 {
35+
/**
36+
* My completely original solution on 10/11/2021, although a little verbose and super as efficient as the above one.
37+
* Basically, insert the next unused number into all possible positions in the currently formed list,
38+
* as soon as the size of this list equals nums.length, add this new permutation into the result;
39+
* I'll have to use a HashSet to filter out duplicates.
40+
*/
41+
publicList<List<Integer>>permute(int[]nums) {
42+
Set<List<Integer>>ans =newHashSet<>();
43+
boolean[]used =newboolean[nums.length];
44+
backtracking(newArrayList<>(),nums,ans,used);
45+
List<List<Integer>>result =newArrayList<>();
46+
for (List<Integer>list :ans) {
47+
result.add(list);
48+
}
49+
returnresult;
50+
}
51+
52+
privatevoidbacktracking(List<Integer>list,int[]nums,Set<List<Integer>>ans,boolean[]used) {
53+
if (list.size() ==nums.length) {
54+
ans.add(newArrayList<>(list));
55+
return;
56+
}
57+
for (inti =0;i <=list.size();i++) {
58+
for (intj =0;j <nums.length;j++) {
59+
if (!used[j]) {
60+
used[j] =true;
61+
list.add(i,nums[j]);
62+
backtracking(list,nums,ans,used);
63+
used[j] =false;
64+
list.remove(i);
65+
}
66+
}
67+
}
68+
}
69+
}
70+
3271
}

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

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,19 +7,23 @@
77

88
publicclass_46Test {
99
privatestatic_46.Solution1solution1;
10+
privatestatic_46.Solution2solution2;
1011

1112
@BeforeClass
1213
publicstaticvoidsetup() {
1314
solution1 =new_46.Solution1();
15+
solution2 =new_46.Solution2();
1416
}
1517

1618
@Test
1719
publicvoidtest1() {
1820
CommonUtils.printListList(solution1.permute(newint[]{1,2,3}));
21+
CommonUtils.printListList(solution2.permute(newint[]{1,2,3}));
1922
}
2023

2124
@Test
2225
publicvoidtest2() {
2326
CommonUtils.printListList(solution1.permute(newint[]{1,2,3,4,5,6}));
27+
CommonUtils.printListList(solution2.permute(newint[]{1,2,3,4,5,6}));
2428
}
2529
}

0 commit comments

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