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

Commit9461a37

Browse files
refactor 667
1 parenta1cf007 commit9461a37

File tree

2 files changed

+61
-73
lines changed

2 files changed

+61
-73
lines changed

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

Lines changed: 20 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -9,54 +9,34 @@ public class _667 {
99

1010
publicstaticclassSolutoin1 {
1111
/**
12-
*This brute force solution will result in TLE as soon as n = 10 and k = 4.
12+
*inspired by this post: https://leetcode.com/problems/beautiful-arrangement-ii/discuss/1154683/Short-and-Simple-Solution-or-Multiple-Approaches-Explained-with-Examples-! and implemented it on my own
1313
*/
1414
publicint[]constructArray(intn,intk) {
15-
List<List<Integer>>allPermutaions =findAllPermutations(n);
16-
int[]result =newint[n];
17-
for (List<Integer>perm :allPermutaions) {
18-
if (isBeautifulArrangement(perm,k)) {
19-
convertListToArray(result,perm);
20-
break;
15+
List<Integer>list =newArrayList<>();
16+
intmaxSoFar =1;
17+
list.add(1);
18+
booleanplus =true;
19+
while (k >0) {
20+
if (plus) {
21+
plus =false;
22+
intnum =list.get(list.size() -1) +k;
23+
maxSoFar =Math.max(maxSoFar,num);
24+
list.add(num);
25+
}else {
26+
plus =true;
27+
list.add(list.get(list.size() -1) -k);
2128
}
29+
k--;
2230
}
23-
returnresult;
24-
}
25-
26-
privatevoidconvertListToArray(int[]result,List<Integer>perm) {
27-
for (inti =0;i <perm.size();i++) {
28-
result[i] =perm.get(i);
31+
for (intstart =maxSoFar +1;start <=n;start++) {
32+
list.add(start);
2933
}
30-
}
31-
32-
privatebooleanisBeautifulArrangement(List<Integer>perm,intk) {
33-
Set<Integer>diff =newHashSet<>();
34-
for (inti =0;i <perm.size() -1;i++) {
35-
diff.add(Math.abs(perm.get(i) -perm.get(i +1)));
34+
int[]result =newint[n];
35+
for (inti =0;i <list.size();i++) {
36+
result[i] =list.get(i);
3637
}
37-
returndiff.size() ==k;
38-
}
39-
40-
privateList<List<Integer>>findAllPermutations(intn) {
41-
List<List<Integer>>result =newArrayList<>();
42-
backtracking(newArrayList<>(),result,n);
4338
returnresult;
4439
}
45-
46-
privatevoidbacktracking(List<Integer>list,List<List<Integer>>result,intn) {
47-
if (list.size() ==n) {
48-
result.add(newArrayList<>(list));
49-
return;
50-
}
51-
for (inti =1;i <=n;i++) {
52-
if (list.contains(i)) {
53-
continue;
54-
}
55-
list.add(i);
56-
backtracking(list,result,n);
57-
list.remove(list.size() -1);
58-
}
59-
}
6040
}
6141

6242
publicstaticclassSolutoin2 {
Lines changed: 41 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1,44 +1,52 @@
11
packagecom.fishercoder;
22

3+
importcom.fishercoder.common.utils.CommonUtils;
34
importcom.fishercoder.solutions._667;
45
importorg.junit.BeforeClass;
5-
importorg.junit.Ignore;
66
importorg.junit.Test;
77

88
importstaticorg.junit.Assert.assertArrayEquals;
99

1010
publicclass_667Test {
11-
privatestatic_667.Solutoin1solution1;
12-
privatestatic_667.Solutoin2solution2;
13-
privatestaticint[]expected;
14-
15-
@BeforeClass
16-
publicstaticvoidsetup() {
17-
solution1 =new_667.Solutoin1();
18-
solution2 =new_667.Solutoin2();
19-
}
20-
21-
@Test
22-
publicvoidtest1() {
23-
expected =newint[] {1,2,3 };
24-
assertArrayEquals(expected,solution1.constructArray(3,1));
25-
assertArrayEquals(expected,solution2.constructArray(3,1));
26-
}
27-
28-
@Test
29-
@Ignore//this problem requires you to return any one of the legit answer, so the results vary from time to time, so comment out this test
30-
publicvoidtest2() {
31-
expected =newint[] {1,3,2 };
32-
assertArrayEquals(expected,solution1.constructArray(3,2));
33-
assertArrayEquals(expected,solution2.constructArray(3,2));
34-
}
35-
36-
@Test
37-
@Ignore//this problem requires you to return any one of the legit answer, so the results vary from time to time, so comment out this test
38-
publicvoidtest3() {
39-
expected =newint[] {1,5,2,4,3,6,7,8,9,10 };
40-
//assertArrayEquals(expected, solution1.constructArray(10, 4));//this is not working, so comment out
41-
assertArrayEquals(expected,solution2.constructArray(10,4));
42-
}
11+
privatestatic_667.Solutoin1solution1;
12+
privatestatic_667.Solutoin2solution2;
13+
privatestaticint[]expected;
14+
15+
@BeforeClass
16+
publicstaticvoidsetup() {
17+
solution1 =new_667.Solutoin1();
18+
solution2 =new_667.Solutoin2();
19+
}
20+
21+
@Test
22+
publicvoidtest1() {
23+
expected =newint[]{1,2,3};
24+
assertArrayEquals(expected,solution1.constructArray(3,1));
25+
assertArrayEquals(expected,solution2.constructArray(3,1));
26+
}
27+
28+
@Test
29+
publicvoidtest2() {
30+
CommonUtils.printArray(solution1.constructArray(3,2));
31+
CommonUtils.printArray(solution2.constructArray(3,2));
32+
}
33+
34+
@Test
35+
publicvoidtest3() {
36+
CommonUtils.printArray(solution1.constructArray(10,4));
37+
CommonUtils.printArray(solution2.constructArray(10,4));
38+
}
39+
40+
@Test
41+
publicvoidtest4() {
42+
CommonUtils.printArray(solution1.constructArray(5,3));
43+
CommonUtils.printArray(solution2.constructArray(5,3));
44+
}
45+
46+
@Test
47+
publicvoidtest5() {
48+
CommonUtils.printArray(solution1.constructArray(5,2));
49+
CommonUtils.printArray(solution2.constructArray(5,2));
50+
}
4351

4452
}

0 commit comments

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