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

Commitaa503b9

Browse files
add 667
1 parent0cb6052 commitaa503b9

File tree

3 files changed

+157
-0
lines changed

3 files changed

+157
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ Your ideas/fixes/algorithms are more than welcome!
2323
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
2424
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
2525
|668|[Kth Smallest Number in Multiplication Table](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_668.java) | O(logm*n) | O(1) | Hard | Binary Search
26+
|667|[Beautiful Arrangement II](https://leetcode.com/problems/beautiful-arrangement-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_667.java) | O(n) | O(1) | Medium | Array
2627
|666|[Path Sum IV](https://leetcode.com/problems/path-sum-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_666.java) | O(1) | O(1) | Medium | Tree, DFS
2728
|665|[Non-decreasing Array](https://leetcode.com/problems/non-decreasing-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_665.java)| O(n)| O(n)| Easy|
2829
|664|[Strange Printer](https://leetcode.com/problems/strange-printer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_664.java) | O(n^3) | O(n^2) | Hard | DP
Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
packagecom.fishercoder.solutions;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.HashSet;
5+
importjava.util.List;
6+
importjava.util.Set;
7+
8+
/**
9+
* 667. Beautiful Arrangement II
10+
*
11+
* Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n
12+
* and obeys the following requirement:
13+
* Suppose this list is [a1, a2, a3, ... , an],
14+
* then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] has exactly k distinct integers.
15+
* If there are multiple answers, print any of them.
16+
17+
Example 1:
18+
19+
Input: n = 3, k = 1
20+
Output: [1, 2, 3]
21+
Explanation: The [1, 2, 3] has three different positive integers ranging from 1 to 3, and the [1, 1] has exactly 1 distinct integer: 1.
22+
23+
Example 2:
24+
25+
Input: n = 3, k = 2
26+
Output: [1, 3, 2]
27+
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
28+
29+
Note:
30+
31+
The n and k are in the range 1 <= k < n <= 104.
32+
*/
33+
34+
publicclass_667 {
35+
36+
publicstaticclassSolutoin1 {
37+
/**This brute force solution will result in TLE as soon as n = 10 and k = 4.*/
38+
publicint[]constructArray(intn,intk) {
39+
List<List<Integer>>allPermutaions =findAllPermutations(n);
40+
int[]result =newint[n];
41+
for (List<Integer>perm :allPermutaions) {
42+
if (isBeautifulArrangement(perm,k)) {
43+
convertListToArray(result,perm);
44+
break;
45+
}
46+
}
47+
returnresult;
48+
}
49+
50+
privatevoidconvertListToArray(int[]result,List<Integer>perm) {
51+
for (inti =0;i <perm.size();i++) {
52+
result[i] =perm.get(i);
53+
}
54+
}
55+
56+
privatebooleanisBeautifulArrangement(List<Integer>perm,intk) {
57+
Set<Integer>diff =newHashSet<>();
58+
for (inti =0;i <perm.size() -1;i++) {
59+
diff.add(Math.abs(perm.get(i) -perm.get(i +1)));
60+
}
61+
returndiff.size() ==k;
62+
}
63+
64+
privateList<List<Integer>>findAllPermutations(intn) {
65+
List<List<Integer>>result =newArrayList<>();
66+
backtracking(newArrayList<>(),result,n);
67+
returnresult;
68+
}
69+
70+
privatevoidbacktracking(List<Integer>list,List<List<Integer>>result,intn) {
71+
if (list.size() ==n) {
72+
result.add(newArrayList<>(list));
73+
return;
74+
}
75+
for (inti =1;i <=n;i++) {
76+
if (list.contains(i)) {
77+
continue;
78+
}
79+
list.add(i);
80+
backtracking(list,result,n);
81+
list.remove(list.size() -1);
82+
}
83+
}
84+
}
85+
86+
publicstaticclassSolutoin2 {
87+
/**This is a very smart solution:
88+
* First, we can see that the max value k could reach is n-1 which
89+
* comes from a sequence like this:
90+
* when n = 8, k = 5, one possible sequence is:
91+
* 1, 8, 2, 7, 3, 4, 5, 6
92+
* absolute diffs are:
93+
* 7, 6, 5, 4, 1, 1, 1
94+
* so, there are total 5 distinct integers.
95+
*
96+
* So, we can just form such a sequence by putting the first part first and
97+
* decrement k along the way, when k becomes 1, we just put the rest numbers in order.*/
98+
publicint[]constructArray(intn,intk) {
99+
int[]result =newint[n];
100+
intleft =1;
101+
intright =n;
102+
for (inti =0;i <n &&left <=right;i++) {
103+
if (k >1) {
104+
result[i] =k-- %2 !=0 ?left++ :right--;
105+
}else {
106+
result[i] =k %2 !=0 ?left++ :right--;
107+
}
108+
}
109+
returnresult;
110+
}
111+
}
112+
}
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._667;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Ignore;
6+
importorg.junit.Test;
7+
8+
importstaticorg.junit.Assert.assertArrayEquals;
9+
10+
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+
}
43+
44+
}

0 commit comments

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