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

Commit645684b

Browse files
add a solution for 763
1 parent6d58fe9 commit645684b

File tree

2 files changed

+77
-21
lines changed

2 files changed

+77
-21
lines changed
Lines changed: 38 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,26 @@
11
packagecom.fishercoder.solutions;
22

33
importjava.util.ArrayList;
4+
importjava.util.HashMap;
45
importjava.util.List;
6+
importjava.util.Map;
57

68
publicclass_763 {
79

810
publicstaticclassSolution1 {
9-
publicList<Integer>partitionLabels(StringS) {
11+
publicList<Integer>partitionLabels(Strings) {
1012
List<Integer>result =newArrayList<>();
1113
int[]last =newint[26];
1214
/**This is the key step:
1315
* we find the last occurrence of each letter and record them in last[]*/
14-
for (inti =0;i <S.length();i++) {
15-
last[S.charAt(i) -'a'] =i;
16+
for (inti =0;i <s.length();i++) {
17+
last[s.charAt(i) -'a'] =i;
1618
}
1719
/**record the last end index of the current substring*/
1820
intend =0;
1921
intstart =0;
20-
for (inti =0;i <S.length();i++) {
21-
end =Math.max(end,last[S.charAt(i) -'a']);
22+
for (inti =0;i <s.length();i++) {
23+
end =Math.max(end,last[s.charAt(i) -'a']);
2224
if (end ==i) {
2325
result.add(end -start +1);
2426
start =end +1;
@@ -28,4 +30,35 @@ public List<Integer> partitionLabels(String S) {
2830
}
2931
}
3032

33+
publicstaticclassSolution2 {
34+
/**
35+
* My completely original solution on 10/14/2021.
36+
*
37+
* Again, using a pen and paper to visualize how this works,
38+
* from the left to the right of the given string helps
39+
* sort out the algorithm greatly and clears up any ambiguities!
40+
*/
41+
publicList<Integer>partitionLabels(Strings) {
42+
List<Integer>ans =newArrayList<>();
43+
Map<Character,Integer>lastIndexMap =newHashMap<>();
44+
for (inti =0;i <s.length();i++) {
45+
lastIndexMap.put(s.charAt(i),i);
46+
}
47+
for (inti =0;i <s.length();i++) {
48+
intboundary =i;
49+
intstart =i;
50+
do {
51+
intlastIndex =lastIndexMap.get(s.charAt(i));
52+
boundary =Math.max(lastIndex,boundary);
53+
i++;
54+
}while (i <boundary);
55+
if (i >boundary) {
56+
i--;
57+
}
58+
ans.add(boundary -start +1);
59+
}
60+
returnans;
61+
}
62+
}
63+
3164
}
Lines changed: 39 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,50 @@
11
packagecom.fishercoder;
22

33
importcom.fishercoder.solutions._763;
4+
45
importjava.util.Arrays;
6+
importjava.util.List;
7+
58
importorg.junit.BeforeClass;
69
importorg.junit.Test;
710

811
importstaticorg.junit.Assert.assertEquals;
912

1013
publicclass_763Test {
11-
privatestatic_763.Solution1solution1;
12-
13-
@BeforeClass
14-
publicstaticvoidsetup() {
15-
solution1 =new_763.Solution1();
16-
}
17-
18-
@Test
19-
publicvoidtest1() {
20-
assertEquals(Arrays.asList(9,7,8),solution1.partitionLabels("ababcbacadefegdehijhklij"));
21-
}
22-
23-
@Test
24-
publicvoidtest2() {
25-
assertEquals(Arrays.asList(9,7,8),solution1.partitionLabels("ababcbacadefegdehijhklij"));
26-
}
14+
privatestatic_763.Solution1solution1;
15+
privatestatic_763.Solution2solution2;
16+
privatestaticList<Integer>expected;
17+
privatestaticStrings;
18+
19+
@BeforeClass
20+
publicstaticvoidsetup() {
21+
solution1 =new_763.Solution1();
22+
solution2 =new_763.Solution2();
23+
}
24+
25+
@Test
26+
publicvoidtest1() {
27+
expected =Arrays.asList(9,7,8);
28+
s ="ababcbacadefegdehijhklij";
29+
assertEquals(expected,solution1.partitionLabels(s));
30+
assertEquals(expected,solution2.partitionLabels(s));
31+
}
32+
33+
@Test
34+
publicvoidtest2() {
35+
expected =Arrays.asList(10);
36+
s ="eccbbbbdec";
37+
assertEquals(expected,solution1.partitionLabels(s));
38+
assertEquals(expected,solution2.partitionLabels(s));
39+
}
40+
41+
@Test
42+
publicvoidtest3() {
43+
expected =Arrays.asList(1,9);
44+
s ="caedbdedda";
45+
assertEquals(expected,solution1.partitionLabels(s));
46+
assertEquals(expected,solution2.partitionLabels(s));
47+
}
48+
49+
2750
}

0 commit comments

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